算法设计与分析编程题.doc

算法设计与分析编程题 1、有10箱产品，每箱1000件，正品每件100克。其中有几箱是次品，每件次品比正品轻10克，问能否用秤只称一次，就找出哪几箱是次品。 算法设计：首先计算标准总重量，存储在变量w1中。输入称取的实际总重量，存储在变量w2中。然后计算出比标准重量轻多少，仍存储在变量w1中。 当w/10=2^k时，则k+1号箱为唯一的一箱次品。 当w/102^k时，k取最大时记为k1，k1+1号箱为次品箱。 当w/10-2^k12^k时，k取最大时记为k2，k2+1号箱为次品箱。 …… 直到取等号w/10-2^(ki-1)=2^ki时，ki+1号箱为次品箱，此时不再有次品。 #includestdio.h void main(){ int i,k,n,t; long w1,w2; printf(Input the number of boxes:); scanf(%d,n); t=1; w1=0; w2=0; for(i=1;i=n;i++){ printf(%d box take %d letter.\n,i,t); w1=w1+t; t=t*2; } w1=w1*100; printf(normal weight : %ld\n,w1); printf(Input reality weight:\n); scanf(%ld,w2); w1=(w1-w2)/10; while(w1!=0){ k=0; t=1; while(w1-t=0){ t=t*2; k++; } printf(%d box is bad.\n,k); w1=w1-t/2; } } 2、编写算法完成完成下面给“余”猜数的游戏。 心里先想好一个1~100之间的整数x，将它分别除以3,5和7并得到3个余数。把这三个余数输入计算机，计算机能马上猜出这个数。 数学模型： 1）不难理解当s=u+3*v+3*w时，s除以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的最公倍数且被3整除余1，最小只能是70； b的系数是7和3的最公倍数且被5整除余1，正好是21。 #includestdio.h #includemath.h void 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,a); printf( “your number divded by 5 has a remainker of”); scanf(%d,b); printf( “your number divded by 7 has a remainker of”); scanf(%d,c); d=70*a+21*b+15*c; while (d105) d=d-105; printf( “your number was %d”, d); } 3、选择问题。求一组数的第二小的数据。 算法设计：将问题转化为求一组数中较小的两个数后，二等分法分解后就可以将原问题“分解为与原问题独立且相似的两个子问题”了。这样，回溯合并的过程就是从两个子问题选出的共4个数中，选取出较小的两个数；直到回溯结束，就得到一组数中较小的两个数。从而也就得到了原问题的解，求出了一组数的中第二小的数据。 #includestdio.h #includemath.h float float second(int n); void two(int i, int j，float fmin2, float fmin1); float a[100]; void main( ) { int n; float min2; sc