《算法设计与分析习题辅导》由会员分享，可在线阅读，更多相关《算法设计与分析习题辅导（10页珍藏版）》请在金锄头文库上搜索。
1、1、编写程序实现求两个整数编写程序实现求两个整数 a、b(ab)的最大公约数的最大公约数(a,b)的欧几里的欧几里 得算法，例如得算法，例如 10920,21420。 #include“stdio.h“ void main() long a,b,c,r; printf(“请输入整数 a,b：“); scanf(“%ld,%ld“, /输入整数 a,b printf(“(%ld,%ld)“,a,b); if(ab r=a%b; while(r!=0) a=b;b=r; /实施“辗转相除” r=a%b; printf(“=%ldn“,b); /输出求解结果 2、试求含有数字试求含有数字 7 且不能
2、被且不能被 7 整除的整除的 5 位数的个数，并求这些整数位数的个数，并求这些整数 的和。的和。 #include void main() int c,j,m,n,f10; long d,k,g1,g2,s1,s2,t; printf(“请输入一位整数 m,n:“); scanf(“%d,%d“, t=1; for(k=1;k0s1+=k; if(fm=2s2+=k; printf(“含数字%d 且不能被%d 整除的%d 位整数的个数 g1=%ldn“,m,m,n,g1); printf(“这些整数的和为 s1=%ldn“,s1); printf(“恰含 2 个数字%d 且不能被%d 整除的%
3、d 位整数个数 g2=%ldn“,m,m,n,g2); printf(“这些整数的和为 s2=%ldn“,s2); 3、韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机 密，便让士兵排队报数。密，便让士兵排队报数。 按从按从 1 至至 5 报数报数,记下最末一个士兵报的数为记下最末一个士兵报的数为 1； 再按从再按从 1 至至 6 报数报数,记下最末一个士兵报的数为记下最末一个士兵报的数为 5； 再按再按 1 至至 7 报数报数,记下最末一个报的数为记下最末一个报的数为 4； 最后按最后按 1 至至 11 报数报数,最末一个士兵报
4、的数为最末一个士兵报的数为 10。 编写程序计算韩信至少有多少兵编写程序计算韩信至少有多少兵? #include void main() int n; for(n=1;n+) if(n%5=1 break; 4、核反应堆中有核反应堆中有 和和 两种粒子，每秒钟内一个两种粒子，每秒钟内一个 粒子可以裂粒子可以裂 变为变为 3 个个 粒子，而一个粒子，而一个 粒子可以裂变为粒子可以裂变为 1 个个 粒子和粒子和 2 个个 粒子。若在粒子。若在 t=0 时刻的反应堆中只有一个时刻的反应堆中只有一个 粒子，求在粒子，求在 t 秒时反秒时反 应堆裂变产生的应堆裂变产生的 粒子和粒子和 粒子数。粒子数。
5、#include void main() int t,a=1,b=0,h,i; scanf(“%d“,for(i=1;i void main() int n,i,j,k,a2020; printf(“请输入行数 n:“); scanf(“%d“, for(i=1;i #include int main() int i,j; j=1; for(i=1;i1)，设计求，设计求 n!的递归函的递归函 数，调用该函数求数，调用该函数求#include double fun (double n) double sum=1; if(n=1)return 1;sum=n*fun(n-1);return su
6、m; void main () int n,i; double s=1; printf (“Enter n:“); scanf (“%d“, for (i=1;ivoid main()int g,i,k,s,t,u,a10;long m1,m2,m3;i=1;a1=1;s=0;while (1)g=1;for (k=i-1;k=1;k-)if (ai=ak )g=0;break;if (i=9 if (ai=9 else ai+;printf (“共以上%d 个解。 n“,s);9、编写程序实现整数编写程序实现整数 762191754639820463 中删除中删除 6 个数字后，剩个数字后，
7、剩 下的数字按原次序组成一个新的正整数，所得最大整数为多大？下的数字按原次序组成一个新的正整数，所得最大整数为多大？/贪心删数字大最大#include “stdio.h“void main ()int i ,k , t, m, n, x, a10000;char b100000;printf (“请输入整数:“);scanf (“%s“,b);for (n=0,i=0;bi!=0;i+)n+;ai=bi-48;printf (“删除数字个数：“);scanf (“%d“,printf (“以上%d 位整数中删除%d 个数字分别为：“,n,k);t=0;m=0;x=0;i=t+1;while (
8、x=0x=x+1;else t=i+;printf(“n 删除后所得最大数:“);for(i=0,x=0;x=wn)mnj=pn;else mnj=0;for (i=n-1;i=1;i-)for (j=0;j=wi sw+=wi;sp+=pi;printf (“%d%3d %4dn“,i,wi,pi);if (m1c-sp=pn)sw+=wi;sp+=pi;printf (“%d%3d %4dn“,n,wn,pn);printf (“w=%d,pmax=%dn“,sw,sp);12、 （贪心算法）已知（贪心算法）已知 5 种物品和一个可容纳种物品和一个可容纳 90 重量的背包，物品重量的背包，
9、物品 i 的重量为的重量为 wi，产生的效益为，产生的效益为 pi。在装包时物品。在装包时物品 i 可拆开装。即可只可拆开装。即可只 装每种物品的一部分，物品装每种物品的一部分，物品 i 的一部分可产生的效益为的一部分可产生的效益为 xipi，这里，这里 xi 属于属于0,1，pi 大于大于 0。设计如何装包，所得装包总效益最大。相。设计如何装包，所得装包总效益最大。相 关参数见下表关参数见下表W1P132.556.2W2P225.340.5W3P337.470.8W4P441.378.4W5P528.240.2 /可拆背包程序实现 #include #define N 100 void main() float pN,wN,xN,c,cw,s,h; int i,j,n; printf(“input n:“); scanf(“%d“, printf(“input c:“); scanf(“%f“, for(i=1;icw)break; xi=1.0; cw=cw-wi; s=s+pi; xi=(float)(cw/wi);s=s+pi*xi; printf(“装包：“); for(i=1;i0 printf(“n 所得最大效益为:%7.1f“,s);
