【编程珠玑】第四章:编写正确的程序

时间:2023-01-01 14:28:57

第一题

问题:二分查找证明起来很费劲,按照某些标准来说,它仍然未完成。你如何证明程序不会出现运行时错误呢?

解答:略。

/***********************************************************/
// 程序目的:二分查找
// 日期:    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;
}

第七题

问题:

第八题

问题:

第九题

问题:

第十题

问题:

第十一题

问题: