第一题
问题:二分查找证明起来很费劲,按照某些标准来说,它仍然未完成。你如何证明程序不会出现运行时错误呢?
解答:略。
/***********************************************************/ // 程序目的:二分查找 // 日期: 2014-09-04 // 作者: spencer_chong // 邮箱: zhuangxb91@qq.com /***********************************************************/ #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; #define n 200 int cmp(const void *a, const void *b) { return (*(int*)a) - (*(int*)b); } int bs(int a[],int i,int j,int v) { if(i>j) return -1; int mid = (i+j)/2; if(a[mid]>v) bs(a,i,mid-1,v); else if(a[mid]<v) bs(a,mid+1,j,v); else return mid; } int main(void) { int a[n]; int i; int v; srand((unsigned)time(NULL)); for (i = 0; i < n; ++i) a[i] = rand()%100; //升序 qsort(a, n, sizeof(int), cmp); for (i = 0; i < n; ++i) cout<<a[i]<<" "; cout<<endl; cin>>v; int pos = bs(a,0,n-1,v); cout<<pos; return 0; }
第二题
问题:如果最初的二分查找对你来说太简单了,那么请你试一下其变型;在p中返回t在数组x中第一次出现的位置(如果t在数组中多次出现的话,原先的算法所返回的是众多位置中的任意一个)。你的代码如何对数组元素进行对数次比较,可能要进行log2(n)次这样的比较才能完成二分查找。
解答:和前面的对比,在a[mid]=v的时候,还应该继续缩小范围搜索,直到满足i>j这种情况。
/***********************************************************/ // 程序目的:二分查找 // 日期: 2014-09-04 // 作者: spencer_chong // 邮箱: zhuangxb91@qq.com /***********************************************************/ #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; #define n 200 int cmp(const void *a, const void *b) { return (*(int*)a) - (*(int*)b); } int bs(int a[],int i,int j,int v) { if(i>j) { if(a[i]==v) return i; else return -1; } int mid = (i+j)/2; if(a[mid]>=v) bs(a,i,mid-1,v); else bs(a,mid+1,j,v); } int main(void) { int a[n]; int i; int v; srand((unsigned)time(NULL)); for (i = 0; i < n; ++i) a[i] = rand()%100; //升序 qsort(a, n, sizeof(int), cmp); for (i = 0; i < n; ++i) cout<<a[i]<<" "; cout<<endl; cin>>v; int pos = bs(a,0,n-1,v); cout<<pos; return 0; }
0 0 1 1 1 2 2 3 3 4 4 4 5 6 6 8 8 8 9 10 11 12 12 12 13 14 14 14 15 16 16 16 17 18 18 18 19 19 20 20 20 20 21 22 22 22 22 24 24 25 25 25 26 26 27 27 27 27 28 28 29 29 29 30 31 31 31 31 31 31 32 32 33 34 34 35 36 36 37 37 37 37 37 37 38 38 38 39 39 40 40 40 41 41 42 43 44 44 45 45 46 46 47 48 48 49 49 49 49 49 50 51 51 52 53 53 53 54 54 54 55 55 57 58 59 60 60 61 61 62 62 62 63 65 65 65 66 66 67 67 67 67 67 69 69 70 70 71 72 72 73 73 73 74 74 75 75 76 76 76 76 76 76 76 76 77 79 80 81 82 82 83 83 85 85 86 87 88 88 89 89 90 90 90 91 92 92 93 93 94 94 95 95 95 95 96 96 96 97 99 查找数:8 位置:(以0开始)15
第三题
问题:编写并验证递归二分查找程序。请指出代码和证明的哪一部分和迭代版本的程序相同,哪一部分不相同。
解答:说明两个概念,就是递归和迭代。递归就是在过程或函数里面调用自身;迭代:利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话,迭代就是A不停的调用B.显然,前面的程序用的是递归。如果只是对i和j进行更新,其实就是迭代。
int bs(int a[],int i,int j,int v) { if(i>j) { if(a[i]==v) return i; else return -1; } int mid = (i+j)/2; if(a[mid]>=v) j=mid-1; else i=mid+1; }
第四题
问题:请往你的二分查找代码里添加虚拟的“计时变量”,以便计时比较次数;并使用程序验证技术证明其运行时间确实是成对数的。
解答:略。添加clock函数即可。
第五题
问题:请证明当输入x是正整数时,此程序将终止。
解答:当x为奇数是,x=3*x+1必将其偶数化,如果是偶数就将其减半。
/***********************************************************/ // 程序目的:验证程序 // 日期: 2014-09-04 // 作者: spencer_chong // 邮箱: zhuangxb91@qq.com /***********************************************************/ #include <iostream> using namespace std; int main(void) { int x; cin>>x; while(x!=1) { if(x%2==0) x=x/2; else x=x*3+1; } return 0; }
第六题
问题:给你一个盛装了一些黑豆和白豆的咖啡罐以及一大堆额外的黑豆。然后你重复进行以下过程,直到罐中只剩下一粒豆子时为止:随机从罐中选择两粒豆子,如果它们颜色一样,就将它们都扔掉,然后并且在罐中放入一粒额外的黑豆。如果它们的颜色不同,则将白豆返回罐中,同时扔掉黑豆。请证明该过程将终止,开始有黑豆和白豆,最终剩下的是什么颜色的豆?
解答:涉及程序终止性证明,即每一步都至少会仍出一个豆子,所以总会结束的。不会无限循环。此外,白色的豆子要么拿两个,要么不扔,所以白色的豆子如果是奇数,则会留下一个来。
/***********************************************************/ // 程序目的:验证程序 // 日期: 2014-09-04 // 作者: spencer_chong // 邮箱: zhuangxb91@qq.com /***********************************************************/ #include <iostream> #include <time.h> using namespace std; int main(void) { int n=20; int a[20]={0}; int temp1,temp2,temp; srand((unsigned)time(NULL)); for(int i=0;i<n;i++) a[i]=rand()%2+1; temp=a[n-1]; while(n>=1) { temp1=rand()%n; temp2=rand()%n; if(temp1==temp2&&n>1) continue; if(n==1) { cout<<a[0]<<endl; break; } if(a[temp1]==a[temp2]) { a[temp1]=0; a[temp2]=0; a[temp1]=1; a[temp2]=temp; } else { if(a[temp1]==2) a[temp2]=temp; else a[temp1]=temp; } a[n-1]=0; n--; temp=a[n-1]; } return 0; }
第七题
问题:
第八题
问题:
第九题
问题:
第十题
问题:
第十一题
问题: