算法设计与分析编程题

《算法设计与分析编程题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析编程题1、有10箱产品，每箱1000件，正品每件100克。其中有几箱是次品，每件次品比正品轻10克，问能否用秤只称一次，就找出哪几箱是次品。算法设计：首先计算标准总重量，存储在变量w1中。输入称取的实际总重量，存储在变量w2中。然后计算出比标准重量轻多少，仍存储在变量w1中。当w/10=2^k时，则k+1号箱为唯一的一箱次品。当w/10>2^k时，k取最大时记为k1，k1+1号箱为次品箱。当w/10-2^k1>2^k时，k取最大时记为k2，k2+1号箱为次品箱。……直到取等号w/10-2^(ki-1)

2、=2^ki时，ki+1号箱为次品箱，此时不再有次品。#includevoidmain(){inti,k,n,t;longw1,w2;printf("Inputthenumberofboxes:");scanf("%d",&n);t=1;w1=0;w2=0;for(i=1;i<=n;i++){printf("%dboxtake%dletter.",i,t);w1=w1+t;t=t*2;}w1=w1*100;printf("normalweight:%ld",w1);printf("Input

3、realityweight:");scanf("%ld",&w2);w1=(w1-w2)/10;while(w1!=0){k=0;t=1;while(w1-t>=0){t=t*2;k++;}printf("%dboxisbad.",k);w1=w1-t/2;}}2、编写算法完成完成下面给“余”猜数的游戏。心里先想好一个1~100之间的整数x，将它分别除以3,5和7并得到3个余数。把这三个余数输入计算机，计算机能马上猜出这个数。数学模型：1）不难理解当s=u+3*v+3*w时，s除以3的余数与u除以3的余数是

4、一样的。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的最公倍数且被3整除余1，最小只能是70；b的系数是7和3的最公倍

5、数且被5整除余1，正好是21。#include#includevoidmain(){inta,b,c,d;printf(“pleasethinkofanumberbetween1and100.”);printf(“yournumberdivdedby3hasaremainkerof”);scanf("%d",&a);printf(“yournumberdivdedby5hasaremainkerof”);scanf("%d",&b);printf(“yournumberdivded

6、by7hasaremainkerof”);scanf("%d",&c);d=70*a+21*b+15*c;while(d>105)d=d-105;printf(“yournumberwas%d”,d);}3、选择问题。求一组数的第二小的数据。算法设计：将问题转化为"求一组数中较小的两个数"后，二等分法分解后就可以将原问题“分解为与原问题独立且相似的两个子问题”了。这样，回溯合并的过程就是从两个子问题选出的共4个数中，选取出较小的两个数；直到回溯结束，就得到一组数中较小的两个数。从而也就得到了原问题的解，求出了一组数

7、的中第二小的数据。#include#includefloatfloatsecond(intn);voidtwo(inti,intj，float&fmin2,float&fmin1);floata[100];voidmain(){intn;floatmin2;scanf("%d",&n);for(i=0;i

8、min1;two(0,n-1,min2,min1);returnmin2;}voidtwo(inti,intj，float&fmin2,float&fmin1){floatlmin2,lmin1,rmin2,rmin1;intmid;if(i=j)fmin2=fmin1=a[i];elseif(i=j-1)if(a[i]