《算法设计与分析课后习题(共17页).doc》由会员分享,可在线阅读,更多相关《算法设计与分析课后习题(共17页).doc(17页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上1、 实验内容 递归求n的二次方各项的系数。2、 程序设计代码如下:#includestdio.hvoid coeff(int a,int n)if(n=1)a1=1;a2=1;elsecoeff(a,n-1);an+1=1;for(int i=n;i=2;i=i-1)ai=ai+ai-1;a1=1;void main()int a100,i,n;printf(输入n的值:);scanf(%d,&n);coeff(a,n);for(i=1;i=n+1;i+)printf( %d ,ai);printf(n);3、 运行结果1、 实验内容写出计算ackerman函数ac
2、k(m,n)的递归计算函数。2、 程序设计代码如下:#include stdio.hint ack(int m,int n)if(m=0)return n+1;else if(n=0)return ack(m-1,1);elsereturn ack(m-1,ack(m,m-1);void main()int m,n,z;printf(input m and n:);scanf(%d %d,&m,&n);if(m0 & n0)printf(error input!);elsez=ack(m,n);printf(%dn,z);3、 运行结果第四章例15 求数列的最大子段和给定n个元素的整数列(可能
3、为负整数)a1,a2,.,an。求形如: ai,ai+1,aj i,j=1,.,n,i=j的子段,使其和为最大。当所有整数均为负整数时定义其最大子段和为0.程序:#includeint maxsum2(int a,int left,int right)int center,i,left_sum,right_sum,s1,s2,lefts,rights;if(left=right)if(aleft0)return aleft;elsereturn 0;elsecenter=(left+right)/2;left_sum=maxsum2(a,left,center);right_sum=maxsu
4、m2(a,center+1,right);s1=0;lefts=0;for(i=center;i=left;i-)lefts=lefts+ai;if(leftss1)s1=lefts;s2=0;rights=0;for(i=center+1;is2)s2=rights;if(s1+s2left_sum)&(right_sumleft_sum)return left_sum;if(s1+s2right_sum)return right_sum;return(s1+s2);int maxsum1(int a,int n)return(maxsum2(a,1,n);void main()int a1
5、00,n;printf(enter a number:);scanf(%d,&n);printf(enter the number of a:);for(int i=1;i=n;i+)scanf(%d,&ai);printf(%d,maxsum1(a,n);printf(n);运行结果:回溯法N皇后问题例如:8皇后问题:要在88的国际象棋棋盘中放8个皇后,使任意两个皇后都不能互相吃掉。规则是皇后能吃掉同一行、同一列、同一对角线的任意棋子。下图为一种方案,求所有的解。00000000模型建立:不妨设8个皇后为xi,他们分别在第i行(i=1,2,3,4,5,6,7,8),这个问题的解空间,就是一个
6、8个皇后所在的序号,为n元一维向量(x1,x2,x3,x4,x5,x6,x7,x8),搜索空间是1=xi=8(i=1,2,3,4,5,6,7,8),共88个状态。约束条件是8个点(1,x1),(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。算法设计:用回溯法从开始结点出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点出,搜索向纵深方向移动至一个活结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点出不能再向纵深方向移动,则当前扩展结点就
7、成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,病史这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。程序设计:#include #include void backdate(int n);int check(int k);int a20,n;void main()printf(Please input a number N3:n);scanf(%d,&n);backdate(n);void backdate(int n)int k;a1=0;k=1;while(k0)ak=ak+1;while(ak=n)&(c
8、heck(k)=0)ak=ak+1;if(ak=n) if(k=n) int i; printf(%d皇后的解为:n,n); for(i=1;i=n;i+) printf(%dn,ai);elsek+;ak=0;elsek-;int check(int k)int i;for(i=1;i=k-1;i+)if(abs(ai-ak)=abs(i-k)|(ai=ak)return(0);return(1);运行结果:例12狱吏问题算法1程序:#include#includevoid main()int *a,i,j,n;scanf(%d,&n);a=(int *)calloc(n+1,sizeof(
9、int); for(i=1;i=n;i+)ai=1;for(i=1;i=n;i+)for(j=i;j=n;j=j+i)aj=1-aj;for(i=1;i=n;i+)if(ai=0)printf(%d is free.,i);printf(n);运行结果:算法2程序:#includevoid main()int s,i,j,n;scanf(%d,&n);for(i=1;i=n;i+)s=1;for(j=2;j=i;j+)if(i%j=0)s=s+1;if(s%2=1)printf(%d is free.,i);printf(n);运行结果:算法3程序:#include void main()in
10、t i,n;scanf(%d,&n);for(i=1;i=n;i+)if(i*i=n)printf(%d is free.,i*i);printf(n);elsebreak;运行结果:贪婪法例4.22 货币统计问题某单位给每个职工发工资(精确到元)。为了保证不要临时兑换零钱,且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1共7种)的张数,请编程完成。源程序如下:#includestdio.hvoid main()int i,j,n,GZ,A,B8=0,100,50,20,10,5,2,1,S8=0,0,0,0,0,0,0,0;printf(请输
11、入人数:);scanf(%d,&n);for(i=1;i=n;i=i+1)printf(输入工资:);scanf(%d,&GZ);for(j=1;j=7;j=j+1)A=GZ/Bj;Sj=Sj+A;GZ=GZ-A*Bj;for(i=1;i=7;i=i+1)printf(币值%5d,张数%5dn,Bi,Si);运行结果:习题4.3问题描述:54张扑克牌,两人轮流拿,每人每次最少拿一张,最多纳四张,谁拿最后一张谁输。编写模拟计算机先拿牌且必胜的算法。原代码如下:#includemain() int i,a10; printf(甲4n); for(i=0;i=1&ai=4) printf(n乙%dt
12、甲%dn,ai,5-ai); else printf(n你输入的数据有误n); return 0; printf(甲胜n);运行结果:资源分配#include void main( ) int i,j,k,m,n,rest;int a100100,gain100; float q100,f100,temp100; printf(How many item? ); scanf(%d,&m); printf(How much money? ); scanf(%d,&n); printf(input gain table:);for( j=0;j=n;j+) scanf(%f,&qj); fj=qj
13、; for( j=0;j=n;j+) a1j=j;for( k=2;k=m;k+) printf(input another item gain tablen); for(j=0;j=n;j+) tempj=qj; scanf(%f,&qj); akj=0; for( j=0;j=n;j+) for( i=0 ;itempj) tempj=fj-i+qi; akj=i; for(j=0;j=1;i-) gaini=airest; rest=rest-gaini; for(i=1;i=m;i+) printf(第%d个项目分配资源%dn,i,gaini); printf(最大利润为%fn,fn);专心-专注-专业