第一题
问题：二分查找证明起来很费劲，按照某些标准来说，它仍然未完成。你如何证明程序不会出现运行时错误呢？
解答：略。
/***********************************************************/
// 程序目的：二分查找
// 日期： 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;
}
第七题
问题：
第八题
问题：
第九题
问题：
第十题
问题：
第十一题
问题：