1.为了保证范围不超过范围,我们需要在初始化的时候,让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的,不会越界。
2.迭代的二分查找。
int bs( int *a, int l, int r, int v ){ while( l <= r ){ if( a[l] == v ) return l; int mid = (l+r)/2; if( a[mid] < v ) l = mid+1; if( a[mid] == v )r = mid; if( a[mid] > v ) r = mid-1; } return -1; }
这个二分可以返回所需要查询的元素第一次出现的位置,如果不存在,则返回-1.在每个循环内,我们假定元素第一次出现的范围是闭区间[l,r]内,当循环体内语句执行完之后,我们得到了一个新的区间。新的区间的范围是一直在收敛的(不会存在r,l执行完循环之后大小没有变化。),所以程序可以终止,得到正确结果。
3.将2的二分程序改写成递归的形式。
int bss( int *a, int l, int r, int v ){ if( l > r ) return -1; if( a[l] == v ) return l; int mid = (l+r)/2; if( a[mid] < v ) return bss( a, mid+1, r, v ); if( a[mid] == v )return bss( a, l, mid, v ); if( a[mid] > v ) return bss( a, l, mid-1, v ); }
递归每加深一层,[l,r]的范围就减小。本层的后置条件要和下一层的前置条件吻合。
4.以下是所做测试查找范围和循环的次数的关系,很明显,当查找范围是指数级的时候,循环次数是线性的。
1 1 2 2 4 3 8 4 16 5 32 6 64 7 128 8 256 9 512 10 1024 11 2048 12 4096 13 8192 14 16384 15 32768 15 65536 17 131072 15 262144 18 524288 19
5.无法证明。
6.每次执行一次,罐子中的豆子数量就减去1,所以此过程可以终止。
如果最后留下的是白色的,那么开始时候白色的个数为奇数,否则为偶数。
7。先是给一个线段的范围。然后选取中间的线,看点在他上面还是下面,然后可以缩小一半的查找范围。类似于二分查找.
8.略
9.(1)两个n维的向量相加。初开始时:i=0表示前i个维度的都已经计算好了。在循环之中,计算一个维度,然后i加一,计算下一个维度,每个循环结束表明前i个维度已经计算完毕。i一直在增大,证明这个过程是可以终止的。当最后一个循环执行完毕的时候,i的值是n,表明前n个维度已经计算好了。所以其代码是正确的。
(2)求x数组的最大值。初开始时候,max=x[0]表示最大值是第一个数,i=1表示前i个数的最大值已经求出。每次循环时候,如果有比max大的数,就替换,当循环结束时候,前i个数的最大值就知道了。当整个过程结束时,i==n,所以前n个数的最大值可以求出。
(3)当循环找个一个t的时候,就停止循环,或者当i超出范围的时候停止。i在每一次循环的时候值都增加,所以这个算法是可以结束的。当超出范围的时候,返回-1,否则返回的就是第一次出现的位置,因为i的值是从小到大递增的。
(4)每次递归,问题的规模都是缩小的,所以问题可以在有限步骤内结束。每次递归完成一次,就可以得到上次层想要的运算结果,接着向上传递。
10.
这些编程也只有有兴趣的人才会慢慢的一个一个的弄,天哪,看到那些文字,头都疼了
求问WordPress代码高亮显示是什么插件? ❓
还有评论的表情是什么插件?谢谢。
SyntaxHighlighter Evolved并在后台选择version 2.x,
Custom Smilies,不过好像图片文件我自己用qq表情替换掉了