《算法设计与分析编程题》由会员分享，可在线阅读，更多相关《算法设计与分析编程题（14页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析编程题算法设计与分析编程题1、有 10 箱产品，每箱 1000 件，正品每件 100 克。其中有几箱是次品，每件次品比正品轻 10 克，问能否用秤只称一次，就找出哪几箱是次品。算法设计：首先计算标准总重量，存储在变量 w1 中。输入称取的实际总重量，存储在变量 w2 中。然后计算出比标准重量轻多少，仍存储在变量 w1 中。当 w/10=2k 时，则 k+1 号箱为唯一的一箱次品。当 w/102k 时，k 取最大时记为 k1，k1+1 号箱为次品箱。当 w/10-2k12k 时，k 取最大时记为 k2，k2+1 号箱为次品箱。直到取等号 w/10-2(ki-1)=2ki 时，ki+
2、1 号箱为次品箱，此时不再有次品。#includevoid main()int i,k,n,t;long w1,w2;printf(“Input the number of boxes:“);scanf(“%d“,t=1;w1=0;w2=0;for(i=1;i=0)t=t*2;k+;printf(“%d box is bad.n“,k);w1=w1-t/2;2、编写算法完成完成下面给“余”猜数的游戏。心里先想好一个 1100 之间的整数 x，将它分别除以 3,5 和 7 并得到 3 个余数。把这三个余数输入计算机，计算机能马上猜出这个数。数学模型：1）不难理解当 s=u+3*v+3*w 时，s
3、 除以 3 的余数与 u 除以 3 的余数是一样的。2）对 s=cu+3*v+3*w，当 c 除以 3 余数为 1 的数时, s 除以 3 的余数与 u 除以 3 的余数也是一样的。证明如下：c 除以 3 余数为 1，记 c=3*k+1，则 s=u+3*k*u+3*v+3*w，由 1)的结论，上述结论正确。记 a，b，c 分别为所猜数据 d 除以 3，5，7 后的余数，则d=70*a+21*b+15*c。为问题的数学模型，其中 70 称作 a 的系数，21 称作 b 的系数,15 称作 c 的系数。c 的系数是 3 和 5 的最公倍数且被 7 整除余 1，正好是 15；a 的系数是 7 和 5
4、 的最公倍数且被 3 整除余 1，最小只能是 70；b 的系数是 7 和 3 的最公倍数且被 5 整除余 1，正好是 21。#include#includevoid main( ) int a,b,c,d;printf( “please think of a number between 1 and 100.”);printf( “your number divded by 3 has a remainker of”);scanf(“%d“,printf( “your number divded by 5 has a remainker of”);scanf(“%d“,printf( “you
5、r number divded by 7 has a remainker of”);scanf(“%d“,d=70*a+21*b+15*c;while (d105)d=d-105;printf( “your number was %d”, d);3、选择问题。求一组数的第二小的数据。算法设计：将问题转化为“求一组数中较小的两个数“后，二等分法分解后就可以将原问题“分解为与原问题独立且相似的两个子问题”了。这样，回溯合并的过程就是从两个子问题选出的共 4 个数中，选取出较小的两个数；直到回溯结束，就得到一组数中较小的两个数。从而也就得到了原问题的解，求出了一组数的中第二小的数据。#include
6、#includefloat float second(int n);void two(int i, int j，float float a100;void main( ) int n;float min2;scanf(“%d“,for (i=0;ivoid main()int i,j,k,m=3,n=7,rest,a100100,gain100;float q100,f100,temp100;printf(“How many item?n“);scanf(“%d“,printf(“How many money?n“);scanf(“%d“,printf(“input one item gain
7、 table :n“);for(j=0;jtempj)tempj = fj-i+qi;akj = i;for(j=0;j=1;i-)gaini = airest;rest = rest - gaini;for(i=1;iqe)qh=qh+1;for(k=1;k8 or j0)qe=sqqe.pre;printf(“(“,sqqe.x,”,”, sqqe.y,”)”); 5.2 走迷宫问题 深度优先算法设计：深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出口就找到一个解。若行不通时，则返回上一个方格，接续搜索其他方向。#includeint maze99 = 0,0,0,0,0,0
8、,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,0,0,0,0,0,1,1,1,1,1,1,0, fx5=0,1,-1,0,0, fy5=0,0,0,-1,1;int i,j,k,total;void out();int check(int i,int j,int k);void search(int i, int j);void main()int total=0;maze11 = 3;s
9、earch(1,1);void search(int i,int j)int k,newi,newj;for(k=1;k8 | j8)flag = 0;else if(mazeij!=0)flag = 0;return flag;6、马的遍历问题在 n x m 的棋盘中，马只能走日字。马从位置（x，y）处出发，把棋盘的每一点都走一次，且只走一次，找出所有路径。算法设计：约束条件是不出边界且每个点只经过一次。结点的扩展规则如问题分析中所述。搜索过程是从任一点（x,y）出发，按深度优先的原则，从八个方向中尝试一个可以走的点，直到走过棋盘上所有 nm 个点。用递归算法易实现此过程。#include
10、int n=5,m=4;int fx9=0,1,2,2,1,-1,-2,-2,-1,fy9=0,2,1,-1,-2,-2,-1,1,2,a65;int dep,x,y,count;int check(int x,int y);void find(int x,int y,int dep);void output();void main()int i,j;count=0;dep=1;printf(“input x,y n“);scanf(“%d,%d“,if(xn | ym | xn | ym | x c1+c2) print(“no solution”); return;MaxLoading(c1);if (s- bestw bestw)bestw=wt;elseAdd(Q,wt);
