《计算机常用算法与程序设计案例教程》习题解答.doc 77页

'《计算机常用算法与程序设计案例教程》习题解答提要习题11-1分数分解算法描述把真分数a/b分解为若干个分母为整数分子为“1”的埃及分数之和：（1）寻找并输出小于a/b的最大埃及分数1/c；（2）若c>900000000，则退出；（3）若c≤900000000，把差a/b-1/c整理为分数a/b，若a/b为埃及分数，则输出后结束。（4）若a/b不为埃及分数，则继续（1）、（2）、（3）。试描述以上算法。解：设(这里int(x)表示取正数x的整数)，注意到，有算法描述：令c=d+1，则input(a,b)while(1){c=int(b/a)+1;if(c>900000000)return;else{print(1/c+);a=a*c-b;b=b*c;//a,b迭代，为选择下一个分母作准备if(a==1){print(1/b);return;}}}1-2求出以下程序段所代表算法的时间复杂度（1）m=0;for(k=1;k<=n;k++) for(j=k;j>=1;j--)m=m+j;解：因s=1+2+…+n=n(n+1)/2时间复杂度为O(n2)。（2）m=0; for(k=1;k<=n;k++) for(j=1;j<=k/2;j++)m=m+j;解：设n=2u+1，语句m=m+1的执行频数为s=1+1+2+2+3+3+…+u+u=u(u+1)=(n−1)(n+1)/4设n=2u，语句m=m+1的执行频数为s=1+1+2+2+3+3+…+u=u2=n2/4时间复杂度为O(n2)。（3）t=1;m=0;for(k=1;k<=n;k++){t=t*k;for(j=1;j<=k*t;j++)m=m+j;}解：因s=1+2×2!+3×3!+…+n×n!=(n+1)!−1时间复杂度为O((n+1)!).（4）for(a=1;a<=n;a++){s=0;for(b=a*100−1;b>=a*100−99;b−=2){for(x=0,k=1;k<=sqrt(b);k+=2)if(b%k==0){x=1;break;}s=s+x;}if(s==50)printf("%ldn",a);break;}}解：因a循环n次；对每一个a,b循环50次；对每一个b,k循环次。因而k循环体的执行次数s满足 时间复杂度为O()。1-3若p(n)是n的多项式，证明：O(log(p(n)))=O(logn)。证：设m为正整数，p(n)=a1×nm+a2×nm-1+…+am×n，取常数c>ma1+(m-1)a2+…+am,则log(p(n))=ma1×logn+(m-1)a2×logn+…=(ma1+(m-1)a2+…)×lognvoidmain() {inti,j,n,a[30][30];printf("请确定方阵阶数n:");scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i==j||i+j==n+1)a[i][j]=0;//方阵对角线元素赋值if(i+jj)a[i][j]=j;//方阵左部元素赋值if(i+j>n+1&&i>j)a[i][j]=n+1-i;//方阵下部元素赋值if(i+j>n+1&&ivoidmain(){inta,c,p,n;p=2011;c=1111;n=4;//变量c与n赋初值while(c!=0)//循环模拟整数竖式除法{a=c*10+1;c=a%p;n=n+1;//每试商一位n增1}printf("由%d个1组成的整数能被%d整除。n",n,p);} 习题22-1解不等式设n为正整数，解不等式解：上下限一般为键盘输入的a,b。//解不等式:a<1+1/(1+1/2)+...+1/(1+1/2+...+1/n)#includevoidmain(){longa,b,c,d,i;doublets,s;printf("请输入a,b:");scanf("%d,%d",&a,&b);i=0;ts=0;s=0;while(svoidmain(){longintx;x=65;while(1){x=x+66;if(x%5==1&&x%7==4){printf("至少有兵:%ld个。",x);break;}}}2-3分解质因数对给定区间[m,n]的正整数分解质因数,每一整数表示为质因数从小到大顺序的乘积形式。如果被分解的数本身是素数，则注明为素数。例如,2012=2*2*503,2011=(素数!)。解：对区间中的每一个整数i(b=i)，用k(2——sqrt(i))试商：若不能整除，说明该数k不是b的因数，k增1后继续试商。 若能整除，说明该数k是b的因数，打印输出"k*"；b除以k的商赋给b(b=b/k)后继续用k试商(注意，可能有多个k因数)，直至不能整除，k增1后继续试商。按上述从小至大试商确定的因数显然为质因数。如果有大于sqrt(n)的因数(至多一个!),在试商循环结束后要注意补上，不要遗失。如果整个试商后b的值没有任何缩减，仍为原待分解数n，说明n是素数，作素数说明标记。若k是b的因数，按格式输出，然后b=b/k后继续试商k。若k不是b的因数，则k增1后继续。若上述试商完成后1voidmain(){longintb,i,k,m,n,w=0;printf("[m,n]中整数分解质因数（乘积形式）.n");printf("请输入m,n:");scanf("%ld,%ld",&m,&n);for(i=m;i<=n;i++)//i为待分解的整数{printf("%ld=",i);b=i;k=2;while(k<=sqrt(i))//k为试商因数{if(b%k==0){b=b/k;if(b>1){printf("%ld*",k);continue;//k为质因数,返回再试}if(b==1)printf("%ldn",k);}k++;}if(b>1&&b=1，即(2k-1)与(2k+1)中至少有一个素数，实施“+”；否则，若a[k]+a[k+1]==0，即(2k-1)与(2k+1)中没有素数，实施“-”。同时，设置最大值变量smax，最小值变量smin。在循环中，每计算一个和值s，与smax比较确定最大值，同时记录此时的项数k1；与smin比较确定最小值，同时记录此时的项数k2。//基于素数的整数和#include#includevoidmain(){intt,j,n,k,k1,k2,a[3000];longs,smax,smin;printf("请输入整数n:");scanf("%d",&n);for(k=1;k<=n+1;k++)a[k]=0;for(k=2;k<=n+1;k++){for(t=0,j=3;j<=sqrt(2*k-1);j+=2)if((2*k-1)%j==0){t=1;break;}if(t==0)a[k]=1;//标记第k个奇数2k-1为素数}s=3;smax=0;smin=s;for(k=2;k<=n;k++){if(a[k]+a[k+1]>=1)s+=(2*k-1)*(2*k+1);//实施代数和elses-=(2*k-1)*(2*k+1);if(s>smax){smax=s;k1=k;}//比较求最大值smaxif(s1(k=0——9)，说明d中存在有重复数字，返回。在不存在重复数字的情形下，检测若f[0]+f[1]+f[4]=0，说明7位平方数d中没有数字“0”,“1”,“4”,d满足题意要求，打印输出。//组成没有重复数字的7位平方数#include#includevoidmain(){intk,m,n,t,f[10];longa,b,c,d,w;n=0;b=sqrt(2356789);c=sqrt(9876532);for(a=b;a<=c;a++){d=a*a;w=d;//确保d为平方数for(k=0;k<=9;k++)f[k]=0;while(w>0){m=w%10;f[m]++;w=w/10;}for(t=0,k=1;k<=9;k++)if(f[k]>1)t=1;//测试三个平方数是否有重复数字if(t==0&&f[0]+f[1]+f[4]==0)//测试平方数中没有数字0,1,4{n++;printf("%2d:",n);printf("%ld=%ld^2n",d,a);}}printf("共可组成%d个没有重复数字的7位平方数.n",n);} 2-6写出例2-2中对称方阵的完整程序，并运行程序。对称方阵程序：#includevoidmain(){inti,j,n,a[30][30];printf("请确定方阵阶数n:");scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i+j<=n+1&&i<=j)a[i][j]=(n+1)/2-i+1;//方阵上部元素赋值if(i+jj)a[i][j]=(n+1)/2-j+1;//方阵左部元素赋值if(i+j>=n+1&&i>=j)a[i][j]=i-n/2;//方阵下部元素赋值if(i+j>n+1&&ivoidmain(){intx,y,t,k,a,b,c,d,e,n=0;intm[6],f[11];for(a=12;a<=98;a++)for(b=2;b<=9;b++)for(c=123;c<=987;c++)//对a,b,c,d实施枚举for(d=2;d<=9;d++){x=c/d;e=a*b+x;if(c!=x*d||e>100)continue;m[1]=a;m[2]=c;m[3]=e;m[4]=b;m[5]=d;for(x=0;x<=9;x++)f[x]=0;for(k=1;k<=5;k++){y=m[k];while(y>0){x=y%10;f[x]=f[x]+1;y=(y-x)/10;//分离数字f数组统计}}for(t=0,x=1;x<=9;x++)if(f[x]!=1){t=1;break;}//检验数字0--9各只出现一次if(t==0)//输出一个解，用n统计个数{n++;printf("%2d:%2d*%1d+%3d/%1d-%2d=0n",n,a,b,c,d,e);}}printf("n=%d.n",n);} 2-8合数世纪探求定义一个世纪的100个年号中不存在一个素数，即100个年号全为合数的世纪称为合数世纪。探索最早的合数世纪。（1）设计要点应用穷举搜索，设置a世纪的的50个奇数年号(偶数年号无疑均为合数)为b，用k试商判别b是否为素数，用变量s统计这50个奇数中的合数的个数。对于a世纪，若s=50，即50个奇数都为合数，找到a世纪为最早的合数世纪，打印输出后退出循环结束。（2）合数世纪程序设计//合数世纪探求#include#includevoidmain(){longa,b,k;ints,x;a=1;while(1){a++;s=0;//检验a世纪for(b=a*100-99;b<=a*100-1;b+=2)//穷举a世纪奇数年号b{x=0;for(k=3;k<=sqrt(b);k+=2)if(b%k==0){x=1;break;}if(x==0)break;//当前为非合数世纪时，跳出循环进行下世纪的探求s=s+x;//年号b为合数时，x=1，s增1}if(s==50)//s=50，即50个奇数均为合数{printf("最早出现的合数世纪为%ld世纪!n",a);break;}}}2-9最小连续n个合数试求出最小的连续n个合数。（其中n是键盘输入的任意正整数。）（1）设计要点 求出区间[c,d]内的所有素数(区间起始数c可由小到大递增)，检验其中每相邻两素数之差。若某相邻的两素数m,f之差大于n，即m-f>n，则区间[f+1,f+n]中的n个数为最小的连续n个合数。应用试商法求指定区间[c,d](约定起始数c=3，d=c+10000)上的所有素数。求出该区间内的一个素数m，设前一个素数为f,判别：若m-f>n，则输出结果[f+1,f+n]后结束；否则，作赋值f=m，为求下一个素数作准备。如果在区间[c,d]中没有满足条件的解，则作赋值：c=d+2，d=c+10000，继续试商下去，直到找出所要求的解。（2）程序实现//求最小的连续n个合数#include#includevoidmain(){longc,d,f,m,j;intt,n;printf("求最小的n个连续合数.n");printf("请输入n:");scanf("%d",&n);c=3;d=c+10000;f=3;while(1){for(m=c;m<=d;m+=2){for(t=0,j=3;j<=sqrt(m);j+=2)if(m%j==0)//实施试商{t=1;break;}if(t==0&&m-f>n)//满足条件即行输出{printf("最小的%d个连续合数区间为:",n);printf("[%ld,%ld]。n",f+1,f+n);getch();return;}if(t==0)f=m;//每求出一个素数m后赋值给f}if(m>d){c=d+2;d=c+10000;}//每一轮试商后改变c,d转下一轮}}2-10和积9数字三角形求解和为给定的正整数s（s≥ 45）的9个互不相等的正整数填入9数字三角形，使三角形三边上的4个数字之和相等（s1）且三边上的4个数字之积也相等（s2）。图2-79数字三角形（1）求解要点。把和为s的9个正整数存储于b数组b(1)，…，b(9)中，分布如下图所示。为避免重复，不妨约定三角形中数字“下小上大、左小右大”，即b(1)#includevoidmain(){intk,j,t,s,s1,s2,n,b[10];printf("请输入正整数s：");scanf("%d",&s);n=0;for(b[1]=1;b[1]<=(s-21)/3;b[1]++)for(b[7]=b[1]+1;b[7]<=(s-28)/2;b[7]++)for(b[4]=b[7]+1;b[4]<=s-36;b[4]++){if((s+b[1]+b[4]+b[7])%3!=0)continue;s1=(s+b[1]+b[4]+b[7])/3;for(b[3]=(s1-b[1]-b[4])/2+1;b[3]voidmain(){intk,n;longb[3000],s;printf("请输入n:");scanf("%d",&n);b[1]=1;b[2]=2;s=3;for(k=3;k<=n;k++){b[k]=3*b[k-1]-b[k-2];s+=b[k];}printf("b(%d)=%ldn",n,b[n]);printf("s=%ldn",s);}3-2双关系递推数列集合M定义如下：1）2）3）再无别的数属于M试求集合M元素从小到大排列的第2011个元素与前2011个元素之和。解：（1）设计要点设n个数在数组m中，2x+1与3x+1均作为一个队列，从两队列中选一排头（数值较小者）送入数组m中。所谓“排头”就是队列中尚未选入m的最小的数（下标）。这里用p2表示2x+1这一列的排头的下标，用p3表示3x+1这一列的排头的下标。if(2*m(p2)<3*m(p3)){m(i)=2*m(p2)+1;p2++;}if(2*m(p2)>3*m(p3)) {m(i)=3*m(p3)+1;p3++;}特别注意：两队列若出现相等时，给m数组赋值后，两排头都要增1。if(2*m(p2)==3*m(p3)){m(i)=2*m(p2)+1;p2++;p3++;//为避免重复项，P2，p3均须增1}（2）程序设计//双关系递推#includevoidmain(){intn,p2,p3,i;longs,m[3000];m[1]=1;s=1;p2=1;p3=1;//排头p2,p3赋初值printf("请输入n:");scanf("%d",&n);for(i=2;i<=n;i++)if(2*m[p2]<3*m[p3]){m[i]=2*m[p2]+1;s+=m[i];p2++;}else{m[i]=3*m[p3]+1;s+=m[i];if(2*m[p2]==3*m[p3])p2++;//为避免重复项，P2须增1p3++;}printf("m(%d)=%ldn",n,m[n]);printf("s=%ldn",s);}3-3多幂序列设x,y,z为非负整数，试计算集合的元素由小到大排列的多幂序列第n项与前n项之和。（1）递推算法设计集合由2的幂、3的幂与5的幂组成，实际上给出的是3个递推关系。显然，第1项也是最小项为1（当x=y=z=0时）。从第2项开始，为了实现从小到大排列，设置3个变量a,b,c，a为2的幂，b为3的幂，c为5的幂，显然a,b,c互不相等。设置k循环（k=2,3,…,n，其中n为键盘输入整数），在k循环外赋初值： a=2;b=3;c=5;s=1;在k循环中通过比较赋值：当avoidmain(){intk,m,t,p2,p3,p5;doublea,b,c,s,f[100];printf("求数列的第m项与前m项和,请输入m:");scanf("%d",&m);f[1]=1;p2=0;p3=0;p5=0;a=2;b=3;c=5;s=1;for(k=2;k<=m;k++){if(avoidmain(){intk,n;longsum,t,s[100];printf("请输入幂指数和至多为n:");scanf("%d",&n);t=1;s[0]=1;sum=1; for(k=1;k<=n;k++){t=t*3;//迭代得t=3^ks[k]=2*s[k-1]+t;//实施递推sum=sum+s[k];}printf("幂指数和至多为%d的幂序列之和为:%ldn",n,sum);}3-5粒子裂变核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以裂变为3个β粒子，而一个β粒子可以裂变为1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t秒时反应堆裂变产生的α粒子和β粒子数。1.算法设计设在t秒时α粒子数为f(t)，β粒子数为g(t)，依题可知：g(t)=3f(t-1)+2g(t-1)（1）f(t)=g(t-1)（2）g(0)=0,f(0)=1由（2）得f(t-1)=g(t-2)（3）将式（3）代入（1）得g(t)=2g(t-1)+3g(t-2)(t≥2)（4）g(0)=0,g(1)=3（5）以递推关系（4）与初始条件（5）完成递推。2．粒子裂变C程序设计//粒子裂变#includevoidmain(){intt,k;longg[100];printf("inputt:");scanf("%d",&t);g[0]=0;g[1]=3;//确定初始条件for(k=2;k<=t;k++)g[k]=2*g[k-1]+3*g[k-2];//完成递推printf("%d秒时反应堆中β粒子数为:%ldn",t,g[t]);printf("%d秒时反应堆中α粒子数为:%ldn",t,g[t-1]);}3-6m行n列逆转矩阵 图3-4所示为4行5列逆转矩阵。1141312112152019103161718945678图3-44行5列逆转矩阵试应用递推设计构造并输出任意指定m行n列逆转矩阵。解：对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。设置i(1——d)循环，从外圈至内圈，分4边进行递推赋值。程序设计：//m×n数字逆转矩阵#includevoidmain(){inti,j,c,d,h,v,m,n,s,a[30][30];printf("m行n列矩阵,请确定m,n:");scanf("%d,%d",&m,&n);c=n;if(mi;h--)//一圈的右列从下至上递增{s++;a[h][v]=s;if(s==m*n){h=i;break;}}for(v=n+1-i;v>i;v--)//一圈的上行从右至左递增{s++;a[h][v]=s;if(s==m*n){v=i;break;}}}printf("%d行%d列旋转矩阵为:n",m,n);for(i=1;i<=m;i++){for(j=1;j<=n;j++)//按m行n列输出矩阵printf("%4d",a[i][j]); printf("n");}}3-7猴子吃桃有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了1个。第2天早上又将剩下的桃子吃掉一半，又多吃了1个。以后每天早上都吃了前一天剩下的一半后又多吃1个。到第10天早上想再吃时，见只剩下1个桃子了。求第1天共摘了多少个桃子。(1)求解要点第1天的桃子数是第2天桃子数加1后的2倍，第2天的桃子数是第3天桃子数加1后的2倍，…，一般地，第k天的桃子数是第k+1天桃子数加1后的2倍。设第k天的桃子数是t(k)，则有递推关系t(k)=2*(t(k+1)+1)(k=1,2,…,9)初始条件：t(10)=1逆推求出t(1)，即为所求的第一天所摘桃子数。(2)程序设计//猴子吃桃程序#includevoidmain(){intk;longt[1000];t[10]=1;//确定初始条件for(k=9;k>=1;k--)//逆推计算t(1)t[k]=2*(t[k+1]+1);printf("第1天摘桃%ld个。n",t[1]);for(k=1;k<=9;k++){printf("第%d天面临%4ld个桃，",k,t[k]);printf("吃了%4ld+1=%4ld个，",t[k]/2,t[k]/2+1);printf("还剩%4ld个。n",t[k]/2-1);}printf("第10天早上还剩1个。");}3-8拓广猴子吃桃有一猴子第1天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了m个。第2天早上又将剩下的桃子吃掉一半，又多吃了m个。以后每天早上都吃了前一天剩下的一半后又多吃m个。到第n天早上想再吃时，见只剩下d个桃子了。 求第1天共摘了多少个桃子(m,n,d由键盘输入)？解：递推关系t(k)=2*(t(k+1)+m)(k=1,2,…,n-1)初始条件：t(n)=d逆推求出t(1)，即为所求的第一天所摘桃子数。//拓广猴子吃桃程序#includevoidmain(){intd,k,m,n;longt[1000];printf("请确定正整数m,n,d:");scanf("%d,%d,%d",&m,&n,&d);t[n]=d;//确定初始条件for(k=n-1;k>=1;k--)//逆推计算t(1)t[k]=2*(t[k+1]+m);printf("第1天摘桃%ld个。n",t[1]);for(k=1;k<=n-1;k++){printf("第%d天面临%4ld个桃，",k,t[k]);printf("吃了%4ld+%d=%4ld个，",t[k]/2,m,t[k]/2+1);printf("还剩%4ld个。n",t[k]/2-m);}printf("第%d天早上还剩%d个。",n,d);}3-9据例3-1中求裴波那契数列的第40项与前40项之和的递推算法与迭代算法，写出完整的程序，并比较其运行结果。(1)应用递推求解//裴波那契数列递推程序#includevoidmain(){intk;longs,f[50];f[1]=1;f[2]=1;s=f[1]+f[2];//数组元素与和变量赋初值for(k=3;k<=40;k++){f[k]=f[k−1]+f[k−2];//实施递推s+=f[k];//实施求和}printf("f数列第40项为:%ldn",f[n]);printf("前40项之和为:%ldn",s);} (2)应用迭代求解//裴波那契数列迭代程序#includevoidmain(){intk;longa,b,s;a=1;b=1;s=a+b;//迭代变量a,b,s赋初值k=2;while(k<=20)//控制迭代次数{a=a+b;//推出a是f数列的第2k-1项b=a+b;//推出b是f数列的第2k项s=s+a+b;//推出s是f数列的前2k项之和k=k+1;}printf("f数列的第40项为：%ldn",b);printf("前40项之和为：%ldn",s);}习题44-1阶乘的递归求解阶乘n!定义:n!=1(n=1)；n!=n*(n-1)!(n>1)设计求n!的递归函数，调用该函数求解：定义n!的递归函数f(n),在求和的k(1——n)循环中实施求和s+=(double)1/f(k);程序设计：#includelongf(intn){longg;if(n==1)g=1;elseg=n*f(n-1);return(g);}voidmain(){intk,n;doubles=1; printf("请输入n:");scanf("%d",&n);for(k=1;k<=n;k++)s+=(double)1/f(k);printf("s=%fn",s);}4-2递归求解f数列已知f数列定义：建立f数列的递归函数，求f数列的第n项与前n项之和。解：定义f数列的递归函数f(n),在求和的k(1——n)循环中实施求和s+=f(k)。程序设计：#includelongf(intn){longg;if(n==1||n==2)g=1;elseg=f(n-1)+f(n-2);return(g);}voidmain(){intk,n;longs=0;printf("请输入n:");scanf("%d",&n);for(k=1;k<=n;k++)s+=f(k);printf("f(%d)=%ldn",n,f(n));printf("s=%ldn",s);}4-3递归求解b数列已知b数列定义：建立b数列的递归函数，求b数列的第n项与前n项之和。解：#includelongb(intn){longg;if(n==1)g=1;elseif(n==2)g=2;elseg=3*b(n-1)-2*b(n-2); return(g);}voidmain(){intk,n;longs=0;printf("请输入n:");scanf("%d",&n);for(k=1;k<=n;k++)s+=b(k);printf("b(%d)=%ldn",n,b(n));printf("s=%ldn",s);}4-4递归求解双递推摆动数列已知递推数列：a(1)=1,a(2i)=a(i)+1,a(2i+1)=a(i)+a(i+1)，（i为正整数），试建立递归，求该数列的第n项与前n项的和。//摆动数列#includeinta(intn){intg;if(n==1)g=1;elseif(n%2==0)g=a(n/2)+1;elseg=a((n-1)/2)+a((n+1)/2);return(g);}voidmain(){intk,n;longs=0;printf("请输入n:");scanf("%d",&n);for(k=1;k<=n;k++)s+=a(k);printf("a(%d)=%dn",n,a(n));printf("s=%ldn",s);}4-5应用递归设计输出杨辉三角。//杨辉三角递归设计voidc(inta[],intn){inti;if(n==0)a[1]=1;elseif(n==1){a[1]=1;a[2]=1;} else{c(a,n-1);a[n+1]=1;for(i=n;i>=2;i--)a[i]=a[i]+a[i-1];a[1]=1;}}#includevoidmain(){inti,j,k,n,a[100];printf("请输入杨辉三角的行数：");scanf("%d",&n);for(j=0;j<=n;j++){c(a,j);for(k=1;k<=30-2*j;k++)printf("");for(i=1;i<=j;i++)printf("%4d",a[i]);printf("%4dn",1);}}4-6试把m×n顺转矩阵的递归设计转变为递推设计。解：对输入的m,n，取c=min(m,n)，计算数字矩阵的圈数d=(c+1)/2。设置i(1——d)循环，从外圈至内圈，分4边进行递推赋值。程序设计：//m×n数字旋转矩阵#include#includevoidmain(){inti,j,c,d,h,v,m,n,s,a[30][30];printf("m行n列矩阵,请确定m,n:");scanf("%d,%d",&m,&n);c=n;if(m=i+1;v--){s++;a[h][v]=s;//d圈的尾行从右至左赋值if(s==m*n){i=d;break;}}//赋值完成即行退出for(h=m+1-i;h>=i+1;h--){s++;a[h][v]=s;//d圈的首列从下至上赋值if(s==m*n){i=d;break;}}}printf("%d行%d列旋转矩阵为:n",m,n);for(i=1;i<=m;i++){for(j=1;j<=n;j++)//按m行n列输出矩阵printf("%4d",a[i][j]);printf("n");}}4-7试应用递归设计构造并输出任意指定逆转m×n矩阵。解：在递归函数中，每圈4边按左列左列从上至下递增、下行从左至右递增、右列从下至上递增、上行从右至左递增给元素赋值。程序设计：//m×n逆转矩阵递归设计#includeintm,n,a[20][20]={0};voidmain(){inth,v,b,s,d;printf("数阵为m行n列，请确定m,n：");scanf("%d,%d",&m,&n);s=m;if(m>n)s=n;b=1;d=1;voidt(intb,ints,intd);//递归函数说明t(b,s,d);//调用递归函数printf("%d×%d逆转矩阵:n",m,n);for(h=1;h<=m;h++) {for(v=1;v<=n;v++)printf("%3d",a[h][v]);printf("n");}return;}voidt(intb,ints,intd)//定义递归函数{intj,h=b,v=b;if(s<=0)return;//递归出口for(j=1;j<=m+1-2*b;j++)//一圈的左列从上至下递增{a[h][v]=d;h++;d++;}for(j=1;j<=n+1-2*b;j++)//一圈的下行从左至右递增{a[h][v]=d;v++;d++;}for(j=1;j<=m+1-2*b;j++)//一圈的右列从下至上递增{a[h][v]=d;h--;d++;if(d>m*n)return;}for(j=1;j<=n+1-2*b;j++)//一圈的上行从右至左递增{a[h][v]=d;v--;d++;if(d>m*n)return;//另一递归出口}t(b+1,s-2,d);//调用内一圈递归函数}4-8应用递归设计实现n个相同元素与另m个相同元素的所有排列。解：设置递归函数p(k)，1≤k≤m+n，元素a[k]取值为0或1。当k=m+n时，作变量h统计“0”的个数。若h=m则打印输出一排列，并用s统计排列个数。然后回溯返回，继续。当kintm,n,r,a[30];longs=0;voidmain(){intp(intk);printf("inputn,m:");scanf("%d,%d",&n,&m);printf("%d个1与%d个0的排列:n",n,m);p(1);//从第1个数开始printf("ns=%ldn",s);//输出排列的个数 }//排列递归函数#includeintp(intk){inth,i,j;if(k<=m+n){for(i=0;i<=1;i++){a[k]=i;//探索第k个数赋值iif(k==m+n)//若已到m+n个数则检测0的个数h{for(h=0,j=1;j<=n+m;j++)if(a[j]==0)h++;if(h==m)//若0的个数为m个,输出一排列{s++;printf("");for(j=1;j<=n+m;j++)printf("%d",a[j]);if(s%10==0)printf("n");}}elsep(k+1);//若没到n+m个数,则调用p(k+1)探索下一个数}}returns;}习题55-1倒桥本分数式把1,2,...,9这9个数字填入下式的9个方格中，数字不得重复,且要求1不得填在各分数的分母，且式中各分数的分子分母没有大于1的公因数，使下面的分数等式成立□□□□□□──+───=──□□□这一填数分数等式共有多少个解?解:在桥本分数式回溯程序中修改//倒桥本分数式回溯实现//把1,2,...,9填入□□/□+□□/□=□□/□ #includevoidmain(){intg,i,k,u,t,a[10];longm1,m2,m3;i=1;a[1]=1;while(1){g=1;for(k=i-1;k>=1;k--)if(a[i]==a[k]){g=0;break;}//两数相同,标记g=0if(i==9&&g==1&&a[1]1&&a[7]>1){m1=a[2]*10+a[3];m2=a[5]*10+a[6];m3=a[8]*10+a[9];for(t=0,u=2;u<=9;u++){if(a[1]%u==0&&m1%u==0)t=1;if(a[4]%u==0&&m2%u==0)t=1;if(a[7]%u==0&&m3%u==0)t=1;}if(t==0&&m1*a[4]*a[7]+m2*a[1]*a[7]==m3*a[1]*a[4])//判断等式{printf("%d/%ld+%d/%ld",m1,a[1],m2,a[4]);printf("=%d/%ldn",m3,a[7]);}}if(i<9&&g==1){i++;a[i]=1;continue;}//不到9个数,往后继续while(a[i]==9&&i>1)i--;//往前回溯if(a[i]==9&&i==1)break;elsea[i]++;//至第1个数为9结束}}5-2两组均分参加拔禾比赛的12个同学的体重如下：48，43，57，64，50，52，18，34，39，56，16，61为使比赛公平，要求参赛的两组每组6个人，且每组同学的体重之和相等。请设计算法解决这“两组均分”问题。（1）求解要点 一般地，对已知的2n(n从键盘输入)个整数，确定这些数能否分成2个组，每组n个数，且每组数据的和相等。我们可采用回溯法逐步实施调整。对于已有的存储在b数组的2n个数,求出总和s与其和的一半s1(若这2n个数的和s为奇数,显然无法分组)。把这2n个数分成二个组,每组n个数。为方便调整,设置数组a存储b数组的下标值，即a(i):1─2n。考察b(1)所在的组,只要另从b(2)─b(2n)中选取n-1个数。即定下a(1)=1,其余的a(i)(i=2,…,n)在2─2n中取不重复的数。因组合与顺序无关,不妨设2≤a(2)#include#includevoidmain(){intn,m,a[N],b[2*N],i,j,t;longs1,s=0;printf("把2n个整数分为和相等的两个组,每组n个数.n");t=time(0)%1000;srand(t);//随机数发生器初始化printf("inputn:");scanf("%d",&n);for(s=0,i=1;i<=2*n;i++)//产生2n个不同的随机整数{t=0;b[i]=rand()%(5*n)+10;for(j=1;j<=i-1;j++)if(b[i]==b[j]){t=1;break;}if(t==1){i--;continue;}//出现相同数时，返回重新产生s+=b[i];printf("%d",b[i]);}if(s%2==0){printf("n以上%d个整数总和为%d.n",2*n,s);s1=s/2; }elseprintf("n和%ld为奇数,无法平分!n",s);a[1]=1;i=2;a[i]=2;m=0;while(1){if(i==n){for(s=0,j=1;j<=n;j++)s+=b[a[j]];if(s==s1)//满足均分条件时输出{m++;printf("NO%d:",m);for(j=1;j<=n;j++)printf("%d",b[a[j]]);}}else{i++;a[i]=a[i-1]+1;continue;}while(a[i]==n+i)i--;//调整或回溯if(i>1)a[i]++;elsebreak;}if(m>0)printf("共有以上%d种分法。",m);elseprintf("无法实现二堆均分.");}5-3指定低逐位整除数探求试求出所有最高位为3的24位低逐位整除数（除个位数字为“0”外,其余各位数字均不得为“0”）。//最高位为3的n位右逐位整除#includevoidmain(){inti,j,n,r,t,a[100];longs=0;printf("逐位整除n位，请确定n：");scanf("%d",&n);printf("所求%d位最高位为3的右逐位整除数：n",n);for(j=1;j<=100;j++)a[j]=1;t=0;a[1]=0;i=1;while(a[1]<1){if(t==0&&i=1;j--)//检测i时是否整除i{r=r*10+a[j];r=r%i;}if(r!=0){a[i]=a[i]+1;t=1;//余数r!=0时a[i]增1,t=1while(a[i]>9&&i>1){a[i]=1;i--;//回溯a[i]=a[i]+1;}}elset=0;//余数r=0时,t=0if(t==0&&i==n){if(a[n]==3){s++;printf("%ld:",s);for(j=n;j>=1;j--)printf("%d",a[j]);printf("n");}a[i]=a[i]+1;}}if(s>0)printf("最高位为3的%d位右逐位整除数共%ld个.",n,s);elseprintf("未找到n位右逐位整除数.",n);}5-4枚举求解8项素数和环，与回溯结果进行比较。(1)设计要点为简化输出，环序列简化为一般序列输出，为避免重复，约定首项为“1”。环中的每一项为一个数字，相连的8项构成一个8位数。因而设置a循环在没有重复数字数字且以“1”开头的8位数812345678——18765432中枚举。注意到所有1——8没有重复数字的8位数的数字和为9的倍数，该数也为9的倍数，为此，枚举循环步长可取9，以精简枚举次数。为操作与判断方便，设置3个数组：f数组统计8位数a中各个数字的频数。如f[3]=2，即a中有2个数字“3”。g数组表示8位数a中每位数的数字。如g[4]=6，即a的从高位开始第4位数为数字“6”。b数组标记整数x是否为素数。如b[13]=1，标识“1”表示13为素数，标识“0”为非素数。 枚举实施：1）注意到8项中每相邻两项之和不超过15,对15以内的5个素数用b数组标注“1”,其余均为“0”。2）在8位数的a循环中，对a实施8次求余分离出各个数字x，应用f[x]++统计数字x的频数，应用g[9-k]=x记录a的各位数字。3）设置k(1——8)判断循环：若f[k]!=1，表明数字k出现重复或遗漏，返回。若b[g[k]+g[k+1]]!=1，表明相邻的第k项与第k+1项之和不是素数，返回。顺便说明，为判断方便，首项“1”先行赋值给g[9]，以与g[8]相邻，在k循环中一道进行判别。4）通过以上判断筛选的a，其各个数字即为所求的8项素数环的各项，打印输出。(2)枚举实现8项素数和环//8项素数和环枚举求解#include#includevoidmain(){intt,k,s,x,g[10],f[10],b[18];longa,y;for(k=1;k<=15;k++)b[k]=0;g[9]=1;s=0;b[3]=b[5]=b[7]=b[11]=b[13]=1;//5个奇素数标记printf("8项素数和环：n");for(a=12345678;a<=18765432;a+=9)//步长为9枚举8位数{t=0;y=a;for(k=0;k<=9;k++)f[k]=0;for(k=1;k<=8;k++){x=y%10;f[x]++;//分离a的8个数字,用f数组统计x的个数g[9-k]=x;//用g数组记录a的第k位数字y=y/10;}for(k=1;k<=8;k++)if(f[k]!=1||b[g[k]+g[k+1]]!=1)t=1;if(t==1)continue;//有相同数字或相邻和非素，返回s++;printf("%d:1",s);//输出8项素数和环for(k=2;k<=8;k++)printf(",%d",g[k]);printf("n");}} 5-5递归求解20项素数环//递归求解素数环问题#include#includeintn,a[2000],b[1000];longs=0;voidmain(){intt,j,k;intp(intk);printf("前n个正整数组成素数环，请输入整数n:");scanf("%d",&n);for(k=1;k<=2*n;k++)b[k]=0;for(k=3;k<=2*n;k+=2){for(t=0,j=3;j<=sqrt(k);j+=2)if(k%j==0){t=1;break;}if(t==0)b[k]=1;//奇数k为素数的标记}a[1]=1;k=2;p(k);printf("前%d个正整数组成素数环，以上是其中3个。n",n);}//素数环递归函数p(k)#includeintp(intk){inti,j,u;if(k<=n){for(i=2;i<=n;i++){a[k]=i;//探索第k个数赋值ifor(u=0,j=1;j<=k-1;j++)if(a[k]==a[j]||b[a[k]+a[k-1]]==0)//若出现重复数字u=1;//若第k数不可置i,则u=1if(u==0)//若第k数可置i,则检测是否到n个数{if(k==n&&b[a[n]+a[1]]==1&&s<3)//若已到n个数时打印出一个解{s++;printf("%ld:1",s);for(j=2;j<=n;j++)printf(",%d",a[j]);printf("n");} elsep(k+1);//若没到m个数,则探索下一个数p(k+1)}}}returns;}5-6枚举探索6珠所能覆盖的最大和s。//数码串珠探索#includevoidmain(){intd,i,j,s,t,u,v,a[20],b[300];for(s=31;s>=28;s--){printf("s=%2d：n",s);v=0;//v统计s时解的个数a[0]=0;a[1]=1;a[6]=s;for(a[2]=a[1]+1;a[2]<=s-4;a[2]++)for(a[3]=a[2]+1;a[3]<=s-3;a[3]++)for(a[4]=a[3]+1;a[4]<=s-2;a[4]++)for(a[5]=a[4]+1;a[5]<=s-1;a[5]++){for(i=7;i<=11;i++)a[i]=s+a[i-6];for(t=0,i=0;i<=5;i++)for(j=i+1;j<=i+5;j++){t++;b[t]=a[j]-a[i];}//除s外，产生30个部分和u=0;for(d=1;d<=s-1;d++)for(i=1;i<=30;i++)if(b[i]==d)//b有[1,s-1]中的一个数，u增1{u+=1;i=30;}if(u==s-1)//u=s-1时为完全环覆盖{v++;printf("(%2d)%2d",v,1);for(i=1;i<=5;i++)printf(",%2d",a[i+1]-a[i]);if(v%2==0)printf("n");}} if(v>0)return;}}5-7枚举探索4阶德布鲁金环，并与德布鲁金环的回溯程序运行结果进行比较。求解由16个0或1组成的环序列，形成的由每相连4个数字组成的16个二进制数恰好在环中都出现一次。(1)枚举设计要点约定序列由0000开头，第5个数字与第16个数字显然都为1(否则会出现00000)。余下10个数字应用枚举探求。设置一维a数组，由约定0000开头，即a(0)～a(3)均为0；a(4)=1,a(15)=1。其余10个数字a(5)～a(14)通过枚举探求。因为是环序列，a(16)～a(18)即为开头的0。分析10个数字0、1组成的二进制数，高位最多2个0（否则出现0001或0000重复），即循环的初值可定为n1=27。同时，高位不会超过4个1（否则出现11111超界），即循环的终值可定为n2=29+28+27+26。对区间[n1,n2]中的每一个整数n(为不影响循环，赋值给b)，通过除以2取余转化为10个二进制数码。用变量i统计该二进制数中1的个数，若i≠6返回，确保16个数字中有8个1时转入下面的检验：计算m1,m2并通过比较，检验a(0)～a(18)中每4个相连数字组成的二进制数若有相同，显然不能满足题意要求，标记t=1退出。若所有由4个相连数字组成的16个二进制数没有相同的，满足德布鲁金环序列条件，作打印输出。（2）4阶德布鲁金环序列枚举实现#includevoidmain(){  intb,m,m1,m2,n,n1,n2,i,j,k,t,a[20];m=0;n1=128;n2=512+256+128+64;//确定枚举范围for(n=n1;n=5;k--)//正整数n(即b)转化为二进制数{a[k]=b%2;b=b/2;i+=a[k];}if(i!=6)continue;//确保8个1转入以下检验for(t=0,k=0;k<=14;k++) for(j=k+1;j<=15;j++)//计算并检验16个二进制数是否相同{m1=a[k]*8+a[k+1]*4+a[k+2]*2+a[k+3];m2=a[j]*8+a[j+1]*4+a[j+2]*2+a[j+3];if(m1==m2){t=1;break;}}if(t==0)//若16个二进制数没有相同，输出结果{m=m+1;printf("No(%2d):",m);for(j=0;j<=15;j++)//依次输出16个二进制数printf("%1d",a[j]);if(m%2==0)printf("n");}}}5-8回溯实现组合C(n,m)对指定的正整数m,n(约定1＜m≤n),回溯实现从n个不同元素中取m个（约定1＜m＜n）的组合C(n,m)。（1）回溯算法设计注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。设置一维数组a，a(i)(i=1,2,…,m)在1～n中取值。首先从a(1)=1开始取值。以后各项从前一项增1取值：a[i]=a[i-1]+1。若a(i)=n+i-m，则返回前一个数组元素a(i-1)。直到i=0，已无法返回，意味着已全部试毕，求解结束。问题的解空间是由数字1～n组成的m位整数组，其约束条件是没有相同数字。按以上所描述的回溯的参量：m,n(m≤n)元素初值：a[1]=1，数组元素初值取1。取值点：a[i]=a[i-1]+1，以保持升序。回溯点：a[i]=n+i-m，各数组元素取值至n+i-m后回溯。（2）回溯实现C(n,m)的C程序实现//实现组合C(n,m)#includevoidmain(){inti,j,n,m,a[100];longs=0;printf("inputn(n<10):");scanf("%d",&n);printf("inputm(10)a[i]++;elsebreak;}printf("n总数为:%ldn",s);//输出C(n,m)的值}5-9回溯实现复杂排列应用回溯法探索从n个不同元素中取m（约定1＜m≤n）个元素与另外n-m个相同元素组成的复杂排列。（1）算法设计要点引入变量k来控制0的个数，当k＜n-m时，a[i]=0，元素需从0开始取值；否则，0的个数已达n-m个，a[i]=1，即从1开始取值。这样处理，使0的个数不超过n-m，减少一些无效操作，提高了回溯效率。按以上所描述的回溯的参量：n,m(m≤n)元素初值：a[1]=0，数组元素取初值0。取值点：当k＜n-m时，a[i]=0，需从0开始取值；否则，a[i]=1，即从1开始取值。回溯点：a[i]=n，各元素取值至n时回溯。约束条件1：a[k]!=0&&a[i]=a[k]||a[i]*a[k]＞0&&fabs(a[i]-a[k])=i-k,(其中i＞k)，排除同一列或同对角线上出现2个皇后。约束条件2：i=n&&h=n-m&&b[1-n][1-n]=1,当取值达n个，其中n-m个零，且棋盘全控时输出一个解。（2）复杂排列回溯优化设计#include#defineN30voidmain(){inti,j,h,k,n,m,t,a[N];longs=0;printf("inputn(n<10):");scanf("%d",&n); printf("inputm(10){if(a[i]==0)k--;//改变取值为0的元素值前先把0的个数k减1a[i]++;}elsebreak;}printf("ns=%ldn",s);}5-108对夫妇特殊的拍照一对夫妇邀请了7对夫妇朋友来家餐聚，东道主夫妇编为0号，其他各对按先后分别编为1，2，…，7号。餐聚后拍照，摄影师要求这8对夫妇男左女右站在一排，东道主夫妇相邻排位在横排的正中央，其他各对排位，1号夫妇中间安排1个人,2号夫妇中间安排2个人,依此类推。共有多少种拍照排队方式？1.设计要点在n组每组2个相同元素（相当于n对情侣），a数组从0取到2n-1不重复，对n同余的两个数为一对编号：余数为0的为0号（即东道主），余数为1的为1号，…，余数为n-1的为n-1号。例如，n=4，数组元素为0与4，对4同余，为一对“0”；1与5对4同余，为一对 “1”；一般地，i与4+i对4同余，为一对i,(i=0,1,2,3)。返回条件修改为（当ja(i)ora(j)+1!=i-j)其中a(j)=a(i)，为使a数组的2n个元素不重复取值；a(j)%n=a(i)%nanda(j)>a(i)，避免同一对取余相同的数左边大于右边，导致重复；a(j)%n=a(i)%nanda(j)+1!=i-j，避免同一对数位置相差不满足题意相间要求。例如，a(j)=0时，此时a(i)=n，为0号情侣，位置应相差1（即中间没有人），即i-j=1。a(j)=1时，此时a(i)=n+1，为1号情侣，位置应相差2（即中间有1人），即i-j=2。这些都应满足条件a(j)+1=i-j。如果a(j)+1!=i-j，不满足要求，返回。设m=2n，若满足条件(g>0andi=manda(1)%n#includevoidmain(){inti,j,g,n,m,s,a[20];printf("inputn(2a[i]||a[j]+1!=i-j)){g=0;break;}//出现相同元素或同余小在后时返回if(g&&i==m&&a[1]%n0)a[i]++;elsebreak;}printf("n共有解s=%d个。n",s);}习题66-1n个矩阵连乘问题设矩阵A为p行q列，矩阵B为q行r列，求矩阵乘积AB共需做pqr次乘法。试求n（n>2）个矩阵的乘积的最少乘法次数。其中n与的行、列数均从键盘输入。解：注意是的列数，也是的行数，这样才能确保与能相乘。多个矩阵相乘，满足乘运算结合律。例如，求，先求前两个矩阵的乘积，还是先求后两个的乘积，都是可以的，但两者的乘法次数不一定相等，我们要求最少乘法次数。设m(i,j)是求乘积的最少乘法次数，则有递推关系(i+1=j)(i≤k≤j,ivoidmain(){intd,n,i,j,k,t,r[100],m[100][100];printf("请输入矩阵的个数n:");scanf("%d",&n);printf("请输入第1个矩阵的行数:");scanf("%d",&r[1]); for(i=1;i<=n-1;i++){printf("请输入第%d个矩阵的列数，也是第%d个矩阵的行数:",i,i+1);scanf("%d",&r[i+1]);}printf("请输入第%d个矩阵的列数:",n);scanf("%d",&r[n+1]);for(i=1;i<=n;i++)m[i][i]=0;for(d=1;d<=n-1;d++)for(i=1;i<=n-d+1;i++){j=i+d;m[i][j]=m[i][i]+m[i+1][j]+r[i]*r[i+1]*r[j+1];for(k=i+1;ka[i][j-1]+r[i][j-1])a[i][j]=a[i-1][j]+d[i-1][j];elsea[i][j]=a[i][j-1]+r[i][j-1];printf("%d",a[n][m]);所求左上角顶点到右下角顶点的最大路程即最优值为a(n,m)。6-4求解边数值三角形的最短路径已知边数值三角形每两点间距离如图7-4所示，每一个点可向左或向右两个去向，求三角形顶点到底边的最短路径。图7-4三角形边数值数据1)算法设计设边数值三角形为n行(不包含作为边终止点的三角形底边)，每点为(i，j)，i=1,2,……，n；j=1,2,……，i.从点(i,j)向左的边长记为l(i,j)，点(i,j)向右的边长记为r(i,j)。记a(i,j)为点（i,j）到底边的最短路程。显然a(i,j)=min(a(i+1,j)+l(i,j),a(i+1,j+1)+r(i,j))st(i,j)={‘l’,’r’}应用逆推求解，所求的顶点A到底边的最短路程为a(1,1).2)边数值三角形最短路径搜索C程序设计//边数值三角形最短路径搜索#include"math.h"#includevoidmain(){intn,i,j,t,s;inta[50][50],l[50][50],r[50][50];charst[50][50];t=time()%1000;srand(t);//随机数发生器初始化printf("请输入数字三角形的行数n:");scanf("%d",&n);for(i=1;i=1;i--)//逆推求取最短路径{for(j=1;j<=i;j++)if(a[i+1][j]+l[i][j]min,说明前面为b(i,j)赋值不对,作修改:b(i,j)=yb+min若min为b(i+1,j),则stc(i,j)="D",否则stc(i,j)="R"这样反推所得b(1,1)即为所求的最小路径数字和。为了打印最小路径,利用c数组从上而下操作:先打印a(1,1),i=1,j=1.若stc(i,j)="R"则j增1,即j=j+1,然后打印"-R-"与右边整数a(i,j);若stc(i,j)="D"则i增1,即i=i+1,然后打印"-D-"与下面整数a(i,j);若stc(i,j)="O"则i,j均增1,即i=i+1,j=j+1,然后打印"-O-"与斜向右下整数a(i,j);依此类推,直至打印到终点a(n,m)。6-6西瓜分堆已知的n个西瓜的重量分别为整数，请把这堆西瓜分成两堆，每堆的个数不一定相等，使两堆西瓜重量之差为最小。(1）设计要点两组数据之和不一定相等，不妨把较少的一堆称为第1堆。设n个整数b(i)之和为s，则第1堆数据之和s1≤[s/2]，这里[x]为x的取整。问题要求在满足s1≤[s/2]前提下求s1最大值maxc，这样两堆数据和之差的最小值为mind=s-2*maxc。为了求s1的最大值，应用动态规划设计，按分每一个瓜为一个阶段，共分为n个阶段。每一个阶段都面临两个决策：选与不选该瓜到第1组。1）建立递推关系设m(i,j)为第1堆距离c1=[s/2]还差重量为j，可取瓜编号范围为：i,i+1,…,n的最大装载重量值。则当0≤j=1;i--)//逆推计算m(i,j)for(j=0;j<=c1;j++)if(j>=b(i)&&m(i+1,j)m(i+1,cb))（其中cb为当前的剩余量，i=1,2,n−1）第1堆分b(i);else不分b(i);if(m(1,c1)-sb=b(n))则第1堆分b(n)。（2）求解两组数据和之差的最小值程序设计//求解两组数据和之差的最小值#include#defineN40voidmain(){intn,c1,i,j,s,t,cb,sb,b[N],m[N][10*N];printf("inputn:");scanf("%d",&n);s=0;for(i=1;i<=n;i++)//输入n个西瓜重量整数{printf("请输入第%d个整数：",i);scanf("%d",&b[i]);s+=b[i];}c1=s/2;printf("各个西瓜重量：");for(i=1;i<=n;i++)printf("%d",b[i]);printf("n总重量s=%dn",s);for(j=0;j=1;i--)//逆推计算m(i,j) for(j=0;j<=c1;j++)if(j>=b[i]&&m[i+1][j]m[i+1][cb]){cb-=b[i];sb+=b[i];printf("%3d",b[i]);b[i]=0;//b(i)分后赋0,为输出第2堆作准备}if(m[1][c1]-sb==b[n]){printf("%3d",b[n]);sb+=b[n];b[n]=0;}printf("(%d)n",sb);printf("第2堆:");for(sb=0,i=1;i<=n;i++)//输出第2堆西瓜if(b[i]>0){sb+=b[i];printf("%3d",b[i]);}printf("(%d)n",sb);}6-7应用递推实现动态规划求解序列的最小子段和应用递推实现动态规划求解：给定n个整数（可能为负整数）组成的序列，求该序列形如段和的最小值。递推实现动态规划求解：1）动态规划算法设计设q[j]为序列前j项之和的最小值，即由q[j]的定义,得q[j]的递推关系: 初始条件：Q[0]=0(没有项时，其值自然为0)。（2）动态规划程序实现//动态规划求最小子段和#include#include#includevoidmain(){inti,j,k,t,n,s,smin,q[1000],a[1000];t=time(0)%1000;srand(t);//随机数发生器初始化printf("序列中n个正负项,请确定n:");scanf("%d",&n);printf("序列的%d个整数为：n",n);for(i=1;i<=n;i++){t=rand()%(4*n)+10;//随机产生n个整数if(t%2==1)a[i]=-1*(t-1)/2;//把奇数变为负数，大小减半elsea[i]=t/2;//把偶数大小减半printf("%d,",a[i]);}smin=1000;q[0]=0;for(j=1;j<=n;j++){if(q[j-1]>=0)q[j]=a[j];elseq[j]=q[j-1]+a[j];if(q[j]=1;i--)//反推最小和子段的首标i{s+=a[i];if(s==smin)break;}printf("最小子段从序列的第%d项到第%d项。n",i,k);}6-8应用递归实现动态规划求解序列的最小子段和应用递归实现动态规划求解：给定n个整数（可能为负整数）组成的序列，求该序列形如段和的最小值。递归实现动态规划求解： 1）动态规划算法设计设q(j)为序列前j项之和的最小值，即由q(j)的定义,得q(j)的递推关系:初始条件：q(0)=0(没有项时，其值自然为0)。（2）动态规划程序实现//动态规划(递归)求最小子段和#include#include#includeintj,a[1000];voidmain(){inti,k,n,t,s,smin;intq(intj);t=time(0)%1000;srand(t);//随机数发生器初始化printf("序列中n个正负项,请确定n:");scanf("%d",&n);printf("序列的%d个整数为：n",n);for(i=1;i<=n;i++){t=rand()%(4*n)+10;//随机产生n个整数if(t%2==1)a[i]=-1*(t-1)/2;//把奇数变为负数，大小减半elsea[i]=t/2;//把偶数大小减半printf("%d,",a[i]);}smin=1000;for(j=1;j<=n;j++)if(q(j)=1;i--)//反推最小和子段的首标i{s+=a[i];if(s==smin)break;}printf("最小子段从序列的第%d项到第%d项。n",i,k);}intq(intj)//定义递归函数q(j) {intf;if(j==0)f=0;else{if(q(j-1)>=0)f=a[j];elsef=q(j-1)+a[j];}returnf;}6-9插入加号求最小值在一个n位整数a中插入r个加号，将它分成r+1个整数，找出一种加号的插入方法，使得这r+1个整数的和最小。1）动态规划求解设f(i,k)表示在前i位数中插入k个加号所得和的最小值，a(i,j)表示从第i个数字到第j个数字所组成的j−i+1(i≤j)位整数值。为了求取f(i,k)，考察数字串的前i个数字，设前j（k≤j#includevoidmain(){charsr[16];intn,i,j,k,u,r,b[16],t[16],c[16][16];doublef[17][17],d;printf("请输入整数：");scanf("%s",sr);n=strlen(sr);printf("请输入插入的+号个数r：");scanf("%d",&r);if(n<=r){printf("输入的整数位数不够或r太大！");return;}printf("在整数%s中插入%d个+号，使和最小：n",sr,r);for(d=0,j=0;j<=n-1;j++) b[j]=sr[j]-48;//把输入的数串逐位转换到b数组for(i=1;i<=n;i++)for(j=1;j<=r;j++)f[i][j]=1e16;for(d=0,j=1;j<=n;j++){d=d*10+b[j-1];//把b数组的一个字符转化为数值f[j][0]=d;//f[j][0]赋初始值}for(k=1;k<=r;k++)for(i=k+1;i<=n;i++)for(j=k;jf[j][k-1]+d)//递推求取f[i][k]{f[i][k]=f[j][k-1]+d;c[i][k]=j;}}t[r]=c[n][r];for(k=r-1;k>=1;k--)t[k]=c[t[k+1]][k];//逆推出第k个+号的位置t[k]t[0]=0;t[r+1]=n;for(k=1;k<=r+1;k++){for(u=t[k-1]+1;u<=t[k];u++)printf("%c",sr[u-1]);//输出最优解if(kvoidmain(){intp,i,j,m,n,k;staticintt[12];longb,s;staticlonga[12][1001]; printf("请输入整币值n(单位数):");//输入处理数据scanf("%d",&n);printf("请输入零币种数m:");scanf("%d",&m);printf("(从小至大依次输入每种零币值)n");for(i=1;i<=m;i++){printf("第%d种零币值(单位数):",i);scanf("%d",&t[i]);}for(j=0;j<=n;j++)//确定初始条件if(j%t[1]==0)a[1][j]=1;elsea[1][j]=0;for(s=a[1][n],i=2;i<=m;i++)//递推计算a(2,n),a(3,n),...{for(j=t[i];j<=n;j++){p=j-t[i];b=0;for(k=1;k<=i;k++)b+=a[k][p];a[i][j]=b;}s+=a[i][n];//累加a(1,n),a(2,n),...}printf("整币兑零种数为:%ldn",s);//输出兑零种数}2.求解整币兑零最少零币个数程序设计//整币兑零,最少零币个数动态规划求解#includevoidmain(){inti,j,m,n;staticintt[12],g[20][1001];printf("请输入整币值(单位数):");//输入处理数据scanf("%d",&n);printf("请输入零币种数:");scanf("%d",&m);printf("(从小至大依次输入每种零币值)n");for(i=1;i<=m;i++){printf("第%d种零币值(单位数):",i);scanf("%d",&t[i]);}for(j=1;j<=n;j++)if(j%t[1]!=0)g[1][j]=0;elseg[1][j]=j/t[1]; for(i=2;i<=m;i++)for(j=1;j<=n;j++){if(jt[i]&&g[i][j-t[i]]==0)g[i][j]=g[i-1][j];elseg[i][j]=g[i][j-t[i]]+1;}printf("最少零币个数为:%dn",g[m][n]);//输出最少零币个数}习题77-1删除数字求最小值给定一个高精度正整数a,去掉其中s个数字后按原左右次序将组成一个新的正整数。对给定的a,s寻找一种方案,使得剩下的数字组成的新数最小。解：应用贪心算法设计求解（1）设计要点操作对象为n位高精度数，存储在数组a中。在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。当k=1时，在n位整数中删除哪一个数字能达到最大的目的？从左到右每相邻的两个数字比较：若出现减，即左边大于右边，则删除左边的大数字。若不出现减，即所有数字全部降序或相等，则删除左边的大数字。当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。3.贪心算法程序设计//贪心删数字达最小#includevoidmain(){inti,j,k,m,n,x,a[200];charb[200];printf("请输入整数：");scanf("%s",b);//以字符串方式输入高精度整数 for(n=0,i=0;b[i]!="";i++){n++;a[i]=b[i]-48;}printf("删除数字个数:");scanf("%d",&k);printf("以上%d位整数中删除%d个数字分别为:",n,k);i=0;m=0;x=0;while(k>x&&m==0){i=i+1;if(a[i-1]>a[i])//出现递减,删除左边的数字{printf("%d,",a[i-1]);for(j=i-1;j<=n-x-2;j++)//删除一数字后，后面的数字前移a[j]=a[j+1];x=x+1;//x统计删除数字的个数i=0;//从头开始查递增区间}if(i==n-x-1)m=1;//已无递减区间,m=1脱离循环}printf("删除后所得最小数:");for(i=1;i<=n-k;i++)//打印剩下的左边n−k个数字printf("%d",a[i-1]);printf("n");}7-2枚举求解埃及分数式本章应用贪心算法构造了埃及分数式：3/11=1/5+1/15+1/165，试用枚举法求解分数3/11的所有3项埃及分数式，约定各项分母不超过200。解：（1）设计要点设指定的分数m/d的三个埃及分数的分母为a,b,c(avoidmain(){inta1,a2,a,b,c,d,m,n,z;doublex,y;printf("确定分数m/d,请输入m,d:");scanf("%d,%d",&m,&d);printf("请确定分母的上界：");scanf("%d",&z);printf("把分数%d/%d分解为三个埃及分数之和:n",m,d);printf("(分母不得为%d,最大分母不超过%d)n",d,z);n=0;a1=d*z/(m*z-2*d);a2=d*3/m+1;for(a=a1;a<=a2;a++)for(b=a+1;b<=z-1;b++)for(c=b+1;c<=z;c++){x=m*a*b*c;//计算x,y值y=d*(a*b+b*c+c*a);if(x==y&&b!=d&&c!=d)//输出分解式{n=n+1;printf("NO%d:%d/%d=1/%d",n,m,d,a);printf("+1/%d+1/%dn",b,c);break;}}printf("共上述%d个分解式.n",n);}7-3币种统计单位给每个职工发工资（约定精确到元），为了保证不至临时兑换零钱，且使每个职工取款的张数最少，请在取工资前统计所有职工所需的各种票面（约定为100,50,20,10,5,2,1元共7种）的张数，并验证币种统计是否正确。(1)算法设计各职工的工资额依次从键盘输入，同时用su统计工资总额。为了确保各职工所得款的张数最少，应用“贪心”策略，优先取大面值币种，即首先付100元币；小于100元时，优先付50元币；依此类推。设置b数组，存储7种票面的值，即b[1]=100,b[2]=50,…,b[7]=1。设置s数组，存储对应票面的张数，即s[1]为100元的张数，…，s[7]为1元的张数。最后验证：各种票面的总额su1是否等于su？若相等，验证正确。（2）程序实现 //币种统计#includevoidmain(){inti,j,m,n,gz;longsu1,su=0;ints[8]={0,0,0,0,0,0,0,0};intb[8]={0,100,50,20,10,5,2,1};printf("请输入人数：");scanf("%d",&n);printf("请依次输入各职工的工资：n");for(i=1;i<=n;i++){printf("输入第%d个职工工资：",i);scanf("%d",&gz);su=su+gz;for(j=1;j<=7;j++){m=gz/b[j];s[j]=s[j]+m;gz=gz-m*b[j];}}printf("单位工资总额为:%ldn",su);printf("各面值币的统计结果:n");su1=0;for(j=1;j<=7;j++){printf("%3d---%3dn",b[j],s[j]);su1=su1+b[j]*s[j];}if(su==su1)printf("经检验统计无误！n");}7-4只显示两端的取数游戏A与B玩取数游戏：随机产生的2n个整数排成一排，但只显示排在两端的数。两人轮流从显示的两端数中取一个数，取走一个数后即显示该端数，以便另一人再取，直到取完。胜负评判：所取数之和大者为胜。A的取数策略：“取两端数中的较大数”这一贪心策略。B的取数策略：当两端数相差较大时，取大数；当两端数相差为1时，随意选取。试模拟A与B取数游戏进程，2n个整数随机产生。（1）算法要点设置k循环（k=1——2n），当k%2=1时A取数，k%2=0时B取数，体现了A先取，A，B轮留取数。 每次显示排两端整数为d[k]与d[2*n]，通过比较其中较大者t为所取数，并分别加入A的得分sa。B的取数从键盘输入，所取数t加入B的得分sb。特别地，当A、B所取数t=d[2*n]，则前面的数均需后移一位：d[j]=d[j-1];（j=2*n,2*n-1,…,k）这样处理，为后续取数提供方便。取数完毕，比较最后得分即可评定胜负。算法操作为取数与移位，时间复杂度为O(n2)。（2）程序实现//模拟A,B取数游戏#include#include#includevoidmain(){intj,k,n,sa,sb,t,c[1000],d[1000];sa=sb=0;t=time(0)%1000;srand(t);//随机数发生器初始化printf("序列中2n个整数,请确定n:");scanf("%d",&n);for(j=1;j<=2*n;j++){c[j]=rand()%(2*n)+2;//随机产生2n个整数d[j]=c[j];}printf("序列的%d个整数已产生，每次只显示两端整数。n",2*n);printf("A先取，A，B轮流取，直到取完。n");for(k=1;k<=2*n;k++){if(k<2*n)printf("n两端数为：%2d,%2d",d[k],d[2*n]);elseprintf("n只剩下1个数：%2d",d[2*n]);if(k%2==1){t=d[k];if(t=k+1;j--)d[j]=d[j-1];}sa=sa+t;printf("A取数%2d;",t);}else{printf("B取数:");scanf("%d",&t);if(t==d[k]||t==d[2*n]){sb=sb+t; if(t==d[2*n]){for(j=2*n;j>=k+1;j--)d[j]=d[j-1];}}else{printf("A取数有误，重新开始！");return;}}}printf("原序列的%d个整数为：",2*n);for(j=1;j<=2*n;j++)printf("%d",c[j]);printf("n最后得分为A=%d,B=%d,",sa,sb);if(sa>sb)printf("此游戏A胜！n");elseif(sas2，B取所有奇数号整数：先取a[1]，则A必取偶数号（2或2n）上的整数；随后B“连号”取数，即A若取a[2]，B取a[3]；A若取a[2*n]，B取a[2*n-1]；…这样可确保B取完所有奇数号整数而获胜。3）否则，即s1≤s2，B取所有偶数号整数：先取a[2*n]，则A必取奇数号（1或2n-1）上的整数；随后B“连号”取数，即A若取a[1]，B取a[2]；A若取a[2*n-1]，B取a[2*n-2]；…这样可确保B取完所有偶数号整数而不败（当s1=s2时平手）。4）A按贪心策略取数，即取两端数的较大者。5）算法操作为取数与移位，时间复杂度为O(n2)。（2）程序实现//所有数显示，B先取不败取数游戏 #include#include#includevoidmain(){intj,k,n,d1,d2,s1,s2,t,a[1000];s1=s2=0;t=time(0)%1000;srand(t);//随机数发生器初始化printf("序列中2n个整数,请确定n:");scanf("%d",&n);printf("序列的%d个整数依次为：",2*n);for(j=1;j<=2*n;j++){a[j]=rand()%(2*n)+2;//随机产生并显示2n个整数printf("%d",a[j]);if(j%2==1)s1+=a[j];elses2+=a[j];}printf("nB先取。");d1=1;d2=2*n;if(s1>s2){printf("B取数%d;n",a[d1]);d1=d1+1;}else{printf("B取数%d;n",a[d2]);d2=d2-1;}printf("请在剩余项：");for(j=d1;j<=d2;j++)printf("%d",a[j]);printf("的两端取数。n");for(k=2;k<=n;k++){if(a[d1]>a[d2]){printf("A取数:%d;",a[d1]);printf("B取数:%d;n",a[d1+1]);d1=d1+2;}else{printf("A取数:%d;",a[d2]);printf("B取数:%d;n",a[d2-1]);d2=d2-2; }printf("请在剩余项：");for(j=d1;j<=d2;j++)printf("%d",a[j]);printf("的两端数取数。n");}printf("A最后取数:%d;n",a[d2]);if(s1>s2){printf("最后得分为:B=%d,A=%dn",s1,s2);printf("此游戏B胜！n");}elseif(s1#include voidmain(){intc,d,e,j,k,t,w,m,n;longa;printf("A给出整数n:");scanf("%d",&n);c=0;m=0;while(1){m++;j=m;{e=j/10;t=1;w=1;while(e>0)//对每一个j,计算t{e=e/10;t=t*10;w=w+1;}e=j;for(k=1;k<=w;k++)//对每一个j,分位试商{d=e/t;e=e%t;t=t/10;a=c*10+d;c=a%n;}}if(c==0){printf("B寻求的整数m：%d.n",m);printf("连写数12...%d/%d=",m,n);c=1;for(j=2;j<=m;j++){e=j/10;t=1;w=1;while(e>0)//对每一个j,计算t{e=e/10;t=t*10;w=w+1;}e=j;for(k=1;k<=w;k++)//对每一个j,分位试商{d=e/t;e=e%t;t=t/10;a=c*10+d;c=a%n;printf("%d",a/n);}}printf("n");}if(c==0)break;}}8-201串积程序设计爱好者A，B进行计算游戏：B任给一个正整数b，A寻求另一个整数a,使a与b的积最小且全为0与1组成的数。例如，B给出b=23，A找到a=4787,其最小01串积为110101。 1.设计要点01串积问题相对前面的积全为“1”的乘数问题要复杂一些，我们应用求余数判别。（1）注意到01串积为十进制数，应用求余运算“%”可分别求得个位“1”，十位“1”，…，分别除以已给b的余数，存放在c数组中：c(1)为1,c(2)为10除以b的余数,c(3)为100除以b的余数，…。（2）要从小到大搜索01串，不重复也不遗漏，从中找出最小的能被b整除01串积。为此，设置k从1开始递增，把k转化为二进制，就得到所需要的这些串。不过，这时每个串不再看作二进制数，而要看作十进制数。（3）在某一k转化为二进制数过程中，每转化一位a(i)(0或1)，求出该位除以b的余数a(i)*c(i)，通过累加求和得k转化的整个二进制数除以b的余数s。（4）判别余数s是否被b整除：若s%b=0,即找到所求最小的01串积。（5）a从高位开始除以b的商存储在d数组，实施整数除法运算：x=e*10+a[j];//e为上轮余数，x为被除数d[j]=x/b;//d为a从高位开始除以b的商e=x%b;//e为试商余数去掉d数组的高位“0”后，输出d即为所寻求的数。（6）最后从高位开始打印a数组，即为01串积。2.程序设计//01串积C程序#includevoidmain(){intb,e,i,j,t,x,a[2000],d[2000],c[2000];longk,s;printf("B给出整数b:");scanf("%d",&b);c[1]=1;for(i=2;i<200;i++)c[i]=10*c[i-1]%b;//c(i)为右边第i位1除以b的余数k=1;while(1){k++;j=k;i=0;s=0;while(j>0){i++;a[i]=j%2;s+=a[i]*c[i];j=j/2;s=s%b;//除2取余法转化为二进制}if(s%b==0){for(e=0,j=i;j>=1;j--){x=e*10+a[j];d[j]=x/b;e=x%b;//a从高位开始除以b的商为d} j=i;while(d[j]==0)j--;//去掉d数组的高位“0”printf("A寻求整数a：");for(t=j;t>=1;t--)printf("%d",d[t]);printf("na*b的最小01串积为：");for(t=i;t>=1;t--)printf("%d",a[t]);printf("n");break;}}}8-3自然对数底e的高精度计算自然对数的底数e是一个无限不循环小数,是“自然律”的一种量的表达，在科学技术中用得非常多。学习了高数后我们知道，以e为底数的对数是最简的，用它是最“自然”的，所以叫“自然对数”。试设计程序计算自然对数的底e，精确到小数点后指定的x位。1．算法设计（1）选择计算公式计算自然对数的底e，我们选用以下公式：（1）（2）确定计算项数其次，要依据输入的计算位数x确定所要加的项数n。显然，若n太小，不能保证计算所需的精度；若n太大，会导致作过多的无效计算。可证明，式中分式第n项之后的所有余项之和。因此，只要选取n，满足即可。即只要使（2）于是可设置对数累加实现计算到x位所需的项数n。为确保准确，算法可设置计算位数超过x位（例如x+2位），只打印输出x位。（3）竖式除模拟设置a数组，下标预设5000，必要时可增加。计算的整数值存放在a(0)，小数点后第i位存放在a(i)中(i=1,2,…)。 依据公式（1），应用竖式除模拟进行计算：数组除以n，加上1；再除以n−1，加上1；…。这些数组操作设置在j(j=n,n-1,…,2)循环中实施。按公式实施除竖式计算操作:被除数为c，除数d分别取n,n−1,……,2。商仍存放在各数组元素(a(i)=c/d)。余数(c%d)乘10加在后一数组元素a(i+1)上，作为后一位的被除数。按数组元素从高位到低位顺序输出。因计算位数较多，为方便查对，每一行控制打印50位，每10位空一格。注意，在输出结果时，整数部分a(0)需加1。（4）模拟乘除竖式计算求解e，程序运行非常快捷。注意到其计算项数n小于计算e的位数x，该算法的时间复杂度为O(xn)。2．自然对数的底e的程序实现//高精度计算自然对数的底e#include#includevoidmain(){doubles;intx,n,c,i,j,d,l,a[5000];printf("请输入精确位数:");scanf("%d",&x);for(s=0,n=2;n<=5000;n++)//累加确定计算的项数n{s=s+log10(n);if(s>x)break;}for(i=0;i<=x+2;i++)a[i]=0;for(c=1,j=n;j>=2;j--)//按公式分步计算{d=j;for(i=0;i<=x+1;i++)//各位实施除j{a[i]=c/d;c=(c%d)*10+a[i+1];}a[x+2]=c/d;a[0]=a[0]+1;c=a[0];//整数位加1}printf("ne=%d.",a[0]+1);//遂位输出计算结果for(l=10,i=1;i<=x;i++){printf("%d",a[i]);l++;if(l%10==0)printf("");if(l%50==0)printf("n"); }printf("n");}8-4进站时间模拟根据统计资料，车站进站口进一个人的时间至少为2秒，至多为8秒。试求n个人进站所需时间。（1）随机模拟算法一个人的进站时间至少为2秒，至多为8秒，设时间精确到小数点后一位，则每一个人进站的时间在2.0,2.1,2.2,…,8.0等数据中随机选取。应用C语言库函数srand(t)进行随机数发生器初始化，其中t为所取的时间秒数。这样可避免随机数从相同的整数取值。C库函数中的随机函数rand()产生−90～32767之间的随机整数，在随机模拟设计时，为产生区间[a,b]中的随机整数，可以应用C语言的整数求余运算实现：rand()%(b−a+1)+a;为简化设计，把每一个人的进站时间乘以10转化为整数，即每一个人的进站时间为rand()%61+20，随机取值范围为20,21,22,…,80，单位为1/10秒。则n个人的进站时间为for(t=0,i=1;i<=n;i++)t=t+rand()%61+20;求和完成后，转化为时间的分，秒输出。（2）进站时间模拟程序实现//进站时间模拟#includevoidmain(){inti,n,m,s;longt;printf("请输入进站人数n：");scanf("%d",&n);t=time()%1000;srand(t);//随机数发生器初始化printf("%d人进站所需时间约为:",n);for(t=0,i=1;i<=n;i++)t=t+rand()%61+20;//计算进站时间总和m=t/600;s=(t%600)/10;//转化为分秒输出printf("%d分%d秒.n",m,s);}8-5模拟扑克升级发牌模拟扑克升级发牌，把含有大小王的共54张牌随机分发给4家，每家12张，底牌保留6张。 1．模拟算法设计（1）模拟花色与点数模拟发牌必须注意随机性。所发的一张牌是草花还是红心，是随机的；是5点还是J点，也是随机的。同时要注意不可重复性。如果在一局的发牌中出现两个黑桃K就是笑话了。同时局与局之间必须作到互不相同，如果某两局牌雷同，也不符合发牌要求。为此，对应4种花色，设置随机整数x，对应取值为1～4。对应每种花色的13点，设置随机整数y，对应取值为1～13。为避免重复，把x与y组合为三位数：z=x*100+y，并存放在数组m(54)中。发第i+1张牌，产生一个x与y，得一个三位数z，数z与已有的i个数组元素m(0),m(1),…m(i−1)逐一进行比较，若不相同则打印与x,y对应的牌(相当于发一张牌)后，然后赋值给m(i)，作为以后发牌的比较之用。若有相同的，则重新产生随机整数x与y得z，与m数组值进行比较。（2）模拟大小王注意到在升级扑克中有大小王，它的出现给程序设计带来一定的难度。大小王的出现也是随机的，为此，把随机整数y的取值放宽到0～13，则z可能有100，200，300，400。定义z=200时对应大王，z=100时对应小王，同上作打印与赋值处理。若z=300或400，则返回重新产生x与y。（3）随机生成模拟描述在已产生i张牌并存储在m数组中，产生第i+1张牌的模拟算法：for(j=1;j<=10000;j++){x=rand()%4+1;y=rand()%14;//x表花色，y表点数z=x*100+y;if(z==300||z==400)continue;t=0;for(k=0;k<=i−1;k++)if(z==m[k]){t=1;break;}//与前产生的牌比较确保牌不重复if(t==0){m[i]=z;break;}//产生的新牌赋值给m(i)}（4）打印输出打印直接应用C语言中ASCII码1～6的字符显示大小王与各花色。设置字符数组d，打印点数时把y=1、13、12、11分别转化为A、K、Q、J。为实现真正的随机，根据时间的不同，设置t=time()%10000;srand(t)初始化随机数发生器，从而达到真正随机的目的。2．发扑克牌C程序实现//发扑克升级牌,有大小王,4个人每人12张牌,底牌6张.#includevoidmain(){intx,y,z,t,i,j,k,m[55]; chard[14]="A234567891JQK";printf("nESWNn");t=time()%1000;srand(t);//随机数发生器初始化m[0]=0;for(i=1;i<=54;i++){if(i==49)printf("bottom:n");for(j=1;j<=10000;j++){x=rand()%4+1;y=rand()%14;z=x*100+y;if(z==300||z==400)continue;t=0;for(k=0;k<=i−1;k++)if(z==m[k]){t=1;break;}//确保牌不重复if(t==0){m[i]=z;break;}}if(z==100||z==200)printf("%c",x);elseif(y==10)printf("%c10",x+2);elseprintf("%c%c",x+2,d[y]);if(i%4==0)printf("n");}printf("n");}8-6特殊洗牌模拟给你2n张牌，编号为1,2,3,…n,n+1,…,2n，这也是最初牌的顺序。一次洗牌是把序列变为n+1,1,n+2,2,n+3,3,n+4,4,…,2n,n。可以证明，对于任意自然数n，都可以在经过m次洗牌后重新得到初始的顺序。编程对于小于10000的自然数n（n从键盘输入）的洗牌，求出重新得到初始顺序的洗牌次数m的值，并显示洗牌过程。1．过程模拟设计设洗牌前位置k的编号为p(k)，洗牌后位置k的编号变为b(k)。我们寻求与确定洗牌前后牌的顺序改变规律。前n个位置的编号赋值变化：位置1的编号赋给位置2，位置2的编号赋给位置4，……，位置n的编号赋给位置2n。即b(2k)=p(k)(k=1,2,…,n)。后n个位置的编号赋值变化：位置n+1的编号赋给位置1，位置n+2的编号赋给位置3，……，位置2n的编号赋给位置2n−1。即b(2k−1)=p(n+k)(k=1,2,…,n)。约定洗牌10000次（可增减），设置m循环，在m循环中实施洗牌，每次洗牌后检测是否得到初始的顺序。 2．模拟洗牌过程程序实现#includevoidmain(){intk,n,m,y,p[10000],b[10000];printf("nn=");scanf("%d",&n);printf("n");for(k=1;k<=2*n;k++)//最初牌的顺序{p[k]=k;printf("%d",p[k]);}for(m=1;m<=20000;m++){y=0;for(k=1;k<=n;k++)//实施一次洗牌{b[2*k]=p[k];b[2*k−1]=p[n+k];}for(k=1;k<=2*n;k++)p[k]=b[k];printf("n%d:",m);//打印第m次洗牌后的结果for(k=1;k<=2*n;k++)printf("%d",p[k]);for(k=1;k<=2*n;k++)//检测是否回到初始的顺序if(p[k]!=k)y=1;if(y==0){printf("nm=%dn",m);break;}//输出回到初始的洗牌次数}}习题99-1完成递归求解最大子段和程序以上递归求解最大子段和没有标明最大子段位置，应如何标明位置？请完善递归程序求解最大子段和。//递归求最大子段和#include#include#includeinti1,i2,j1,sum,a[1000];voidmain(){inti,n,s,t; intms(intm1,intm2);t=time(0)%1000;srand(t);//随机数发生器初始化printf("序列中n个正负项,请确定n:");scanf("%d",&n);printf("序列的%d个整数为：n",n);for(i=1;i<=n;i++){t=rand()%(4*n)+10;//随机产生n个整数if(t%2==1)a[i]=-1*(t-1)/2;//把奇数变为负数，大小减半elsea[i]=t/2;//把偶数大小减半printf("%d,",a[i]);}s=ms(1,n);printf("n最大子段和为：%dn",s);if(a[i2]==s)printf("最大子段为序列的第%d项。n",i2);elseprintf("最大子段从序列的第%d项到第%d项。n",i1,j1);}intms(intm1,intm2)//定义递归函数ms(){inti,m,sm1,sm2,s1,s2,ts;sum=0;if(m1==m2)//递归出口{if(a[m1]>0)sum=a[m1];elsesum=0;}else{m=(m1+m2)/2;//序列分解sm1=ms(m1,m);//对应情形①，递归求解sm2=ms(m+1,m2);//对应情形②，递归求解s1=0;for(ts=0,i=m;i>=m1;i--){ts+=a[i];if(ts>s1){s1=ts;i1=i;}//s1为求到第m项的最大值}s2=0;for(ts=0,i=m+1;i<=m2;i++){ts+=a[i];if(ts>s2) {s2=ts;j1=i;}//s2为求到第m+1项的最大值}sum=s1+s2;if(sumintk,n,m,x1,y1,z,d[20][20]={0};voidmain(){intg,q,x,y;inttr(intg,intx,inty);printf("棋盘为n行m列，请输入n,m:");scanf("%d,%d",&n,&m);printf("指定障碍位置(x1,y1)，请输入x1,y1:");scanf("%d,%d",&x1,&y1);g=2;z=0;x=1;y=1;//起点约定为(1,1)d[x][y]=1;q=tr(g,x,y);//调用tr(g,x,y)if(z>0)printf("共有以上%d个指定马步路径.n",z);elseprintf("未找到指定路径!n");}//马步路径递归函数inttr(intg,intx,inty){inti,j,u,v,k=0,q=0;inta[9]={0,2,1,-1,-2,-2,-1,1,2};//按可能8位给a,b赋初值intb[9]={0,1,2,2,1,-1,-2,-2,-1};while(q==0&&k<8){k=k+1;u=x+a[k];v=y+b[k];//探索第k个可能位置if(u>0&&u<=n&&v>0&&v<=m&&d[u][v]==0&&!(u==x1&&v==y1)) {d[u][v]=g;//所选位走第g步if(g==m*n-1){z++;printf("第%d个指定障碍的马步路径为:n",z);for(i=1;i<=n;i++)//以二维形式输出一个解{for(j=1;j<=m;j++)if(i==x1&&j==y1)printf("×");elseprintf("%4d",d[i][j]);printf("n");}g=g-1;}elseq=tr(g+1,u,v);if(q==0)d[u][v]=0;//实施回溯if(g==2&&k==8)q=1;//回溯完,则返回}}returnq;}9-3回溯设计探求一个n行m列马步哈密顿圈//马步哈密顿圈回溯程序设计#includevoidmain(){inti,j,k,q,u,v;intn,m,d[20][20]={0},x[400]={0},y[400]={0},t[400]={0};inta[9]={0,2,1,-1,-2,-2,-1,1,2};//按可能8位给a,b赋初值intb[9]={0,1,2,2,1,-1,-2,-2,-1};printf("棋盘为n行m列，请输入n,m:");scanf("%d,%d",&n,&m);i=1;u=1;v=1;x[i]=u;y[i]=v;d[u][v]=1;//起始位置赋初值while(i>0){q=0;//尚未找到第i+1步方向for(k=t[i]+1;k<=8;k++){u=x[i]+a[k];v=y[i]+b[k];//探索第k个可能位置if(u>0&&u<=n&&v>0&&v<=m&&d[u][v]==0)//所选位为空可走 {x[i+1]=u;y[i+1]=v;d[u][v]=i+1;//则走第i+1步t[i]=k;//记录第i+1步方向q=1;break;}}if(q==1&&i==m*n-1){if(u==2&&v==3||u==3&&v==2){printf("此哈密顿圈的一个解为:n");for(j=1;j<=n;j++)//以二维形式输出遍历解{for(k=1;k<=m;k++)printf("%4d",d[j][k]);printf("n");}return;}t[i]=d[x[i]][y[i]]=d[x[i+1]][y[i+1]]=0;i--;//实施回溯,寻求新的解}elseif(q==1)i++;//继续探索else{t[i]=d[x[i]][y[i]]=0;i--;}//实施回溯}}9-4纵向双拼哈密顿圈设计用起点为（1,1），终点为（2,2）或（1,3）的遍历，实现纵向双拼哈密顿圈.1.纵向双拼设计要点设一个起点为(1,1)的n行m列马步遍历路径的终点为(2,2)或(1,3)，则可拼接成纵向双拼为一个2n行m列的组合哈密顿圈。同时要实现左上角置“1”的习惯，注意到A的每一项在B基础上增加m*n，左上角实为元素d(n,1),因而可设c=d(n,1)-1，组合圈的每一项均减去c，这样左上角置“1”，非正项每项加2mn。2.程序实现//纵向双拼组合哈密顿圈#includeintk,m,n,z,d[20][20]={0};voidmain(){intc,i,j,g,q,x,y;intt(intg,intx,inty); printf("组合元素为n行m列，请确定n,m:");scanf("%d,%d",&n,&m);g=2;z=0;x=1;y=1;d[x][y]=1;//起始位置赋初值q=t(g,x,y);//调用t(g,x,y)if(z>0){printf("一个%d行%d列组合型哈密顿圈：n",2*n,m);c=d[n][1]-1;for(i=n;i>=1;i--){for(j=1;j<=m;j++)//输出倒行遍历if(d[i][j]-c>0)printf("%4d",d[i][j]-c);elseprintf("%4d",d[i][j]-c+2*m*n);printf("n");}for(i=1;i<=n;i++){for(j=1;j<=m;j++)//输出原遍历printf("%4d",d[i][j]+m*n-c);printf("n");}}elseprintf("未找到指定路径!n");}//指定马步路径递归函数intt(intg,intx,inty){intu,v,k=0,q=0;inta[9]={0,2,1,-1,-2,-2,-1,1,2};//按可能8位给a,b赋初值intb[9]={0,1,2,2,1,-1,-2,-2,-1};while(q==0&&k<8){k=k+1;u=x+a[k];v=y+b[k];//探索第k个可能位置if(u>0&&u<=n&&v>0&&v<=m&&d[u][v]==0)//所选位为空可走{d[u][v]=g;//则走第g步if(g==m*n){if(u==2&&v==2||u==1&&v==3)//原遍历终点为(2,2)或(1,3){z++;q=1;returnq;}g=g-1;}elseq=t(g+1,u,v); if(q==0)d[u][v]=0;//实施回溯if(g==2&&k==8)q=1;//回溯完,则返回}}returnq;}'