算法设计与分析习题辅导

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

1、1、编写程序实现求两个整数a、b(a>b)的最大公约数(a,b)的欧几里得算法，例如10920,21420。#include"stdio.h"voidmain(){longa,b,c,r;printf("请输入整数a,b：");scanf("%ld,%ld",&a,&b);//输入整数a,bprintf("(%ld,%ld)",a,b);if(abr=a%b;while(r!=0){a=b;b=r;//实施“辗转相除”r=a%b;}printf("=%ld",b);//输出求解结果}2

2、、试求含有数字7且不能被7整除的5位数的个数，并求这些整数的和。#includevoidmain(){intc,j,m,n,f[10];longd,k,g1,g2,s1,s2,t;printf("请输入一位整数m,n:");scanf("%d,%d",&m,&n);t=1;for(k=1;k<=n-1;k++)t=t*10;//求最小的n位整数tg1=0;s1=0;g2=0;s2=0;for(k=t;k<=10*t-1;k++)//枚举每一个n位数{d=k;for(j=0;j<=9;j++)f[j]=0;for(j=1;j<=n

3、;j++){c=d%10;f[c]+=1;//统计n位整数k中各数字的个数d=d/10;}if(f[m]>0&&k%m>0)//k含数字m且不能被m整除{g1++;s1+=k;}if(f[m]==2&&k%m>0)//k恰含2个数字m且不能m整除{g2++;s2+=k;}}printf("含数字%d且不能被%d整除的%d位整数的个数g1=%ld",m,m,n,g1);printf("这些整数的和为s1=%ld",s1);printf("恰含2个数字%d且不能被%d整除的%d位整数个数g2=%ld",m,m,n,g2);printf("

4、这些整数的和为s2=%ld",s2);}1、韩信在点兵的时候，为了知道有多少个兵，同时又能保住军事机密，便让士兵排队报数。按从1至5报数,记下最末一个士兵报的数为1；再按从1至6报数,记下最末一个士兵报的数为5；再按1至7报数,记下最末一个报的数为4；最后按1至11报数,最末一个士兵报的数为10。编写程序计算韩信至少有多少兵?#includevoidmain(){intn;for(n=1;;n++)if(n%5==1&&n%6==5&&n%7==4&&n%11==10){printf("韩信至少有兵:%d",n);bre

5、ak;}}2、核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以裂变为3个β粒子，而一个β粒子可以裂变为1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t秒时反应堆裂变产生的α粒子和β粒子数。#includevoidmain(){intt,a=1,b=0,h,i;scanf("%d",&h);for(i=1;i<=h;i++){t=a;a=b;b=t*3+b*2;}printf("%d,%d",a,b);}5、应用递归设计输出杨辉三角。#includevoidmain(){intn,i,

6、j,k,a[20][20];printf("请输入行数n:");scanf("%d",&n);for(i=1;i<=n;i++){a[i][1]=1;a[i][i]=1;}//确定初始条件for(i=3;i<=n;i++)for(j=2;j<=i-1;j++)//递推实施a[i][j]=a[i-1][j-1]+a[i-1][j];for(i=1;i<=n;i++)//控制输出n行{for(k=1;k<=40-3*i;k++)printf("");for(j=1;j<=i;j++)printf("%6d",a[i][j]);printf("")

7、;}}6、有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了1个。第2天早上又将剩下的桃子吃掉一半，又多吃了1个。以后每天早上都吃了前一天剩下的一半后又多吃1个。到第10天早上想再吃时，见只剩下1个桃子了。编写程序计算第1天共摘了多少个桃子。#include#includeintmain(){inti,j;j=1;for(i=1;i<10;i++){j=2*(j+1);}printf("第一天摘桃子的个数为%d",j);return0;}6、阶乘n!定义:n!=1(n=1)；n!=n*(n-1

8、)!(n>1)，设计求n!的递归函数，调用该函数求#includedoublefun(doublen){doubles