算法设计9题编程代码.doc

编程题 von 1.P99【例32】警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中 a说：“我不是小偷。” b说：“c是小偷。” c说：“小偷肯定是d。” d说：“c在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？问题分析：将a,b,c,d将四个人进行编号，号码分别为1，2，3，4。则问题可用枚举尝试法来解决。 算法设计：用变量x存放小偷的编号，则x的取值范围从1取到4，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成： a说的话：x1 b说的话：x=3 c说的话：x=4 d说的话：x4 注意:在x的枚举过程中，当这四个逻辑式的值相加等于3时，即表示“四个人中三人说的是真话，一人说的是假话”。 程序代码： #includestdio.h void main( ) { int x; for(x=1;x=4;x++) if((x!=1)+(x==3)+(x==4)+(x!=4)==3) printf(%c is a thief.\n,(64+x)); } 运行结果： c is a thief . 2.P100【例33】3位老师对某次数学竞赛进行了预测。他们的预测如下： 甲说：学生A得第一名，学生B得第三名。 乙说：学生C得第一名，学生D得第四名。 丙说：学生D得第二名，学生A得第三名。竞赛结果表明，他们都说对了一半，说错了一半，并且无并列名次，试编程输出A、B、C、D各自的名次。问题分析：用数1，2，3，4分别代表学生a，b，c，d获得的名次。问题就可以利用三重循环把所有的情况枚举出来。 算法设计： 1）用a，b，c，d 代表四个同学，其存储的值代表他们的名次。 设置第一层计数循环a的范围从1到4； 设置第二层计数循环b的范围从1到4； 设置内计数循环c的范围从1到来4； 由于无并列名次，名次的和为1+2+3+4=10，由此可计算出d的名次值为10-a-b-c。 2）问题的已知内容，可以表示成以下几个条件式： (1) (a=1)+(b=3)=1 (2) (c=1)+(d=4)=1 (3) (d=2)+(a=3)=1 若三个条件均满足，则输出结果，若不满足，继续循环有哪些信誉好的足球投注网站，直至循环正常结束。 程序代码： #includestdio.h void main( ) { int a,b,c,d; for(a=1;a=4;a=a+1) for(b=1;b=4;b=b+1) if(a!=b) for(c=1;c=4;c=c+1) if(c!=ac!=b) { d=10-a-b-c; if(d!=ad!=bd!=c) if(((a==1)+(b==3))==1((c==1)+(d==4))==1((d==2)+(a==3))==1) printf( a= %d,b= %d,c= %d,d= %d\n,a,b,c,d); } } 运行结果： A=4,b=3,c=1,d=2 3．P146【例15】求数列的最大字段和{0,1,-1,3,-4,5,6,7,-8,88}。 问题分析： 用二分法将实例中的数据分解为{0,1,-1,3,-4}，{5,6,7,-8,88}，第一个子问题的解是3，第二个子问题的解是88，两个子问题的解不能简单的得到原问题的解。由此看出此问题不能用二分法分解成为独立的两个子问题，子问题中间还有公共的子问题，这类问题称为子问题重叠问题。下面仍用二分法解决这类问题中的一些简单问题，处理不独立的子问题。 算法设计：如果将所给的序列a[1:n]分为长度相等的两段a[1:(n/2)]和a[(n/2)+1:n]分别为求出这两段的最大子段和，则a[1:n]的最大子段和有3中情形： 情形（1） a[1:n]的最大子段和与a[1:(n/2)]的最大子段和相同。 情形（2） a[1:n]的最大子段和与a[(n/2)+1:n]的最大子段和相同。 情形（3） a[1:n]的最大子段和为a[i:j)],且1≤i≤(n/2), (n/2)+1≤j≤n。 程序代码： #includestdio.h int max_sub_sum(int a[], int left, int right); int max_sum3(int a[],int n); void main() { int a