算法設(shè)計(jì)與分析課后習(xí)題

1、1、 實(shí)驗(yàn)內(nèi)容 遞歸求n的二次方各項(xiàng)的系數(shù)。2、 程序設(shè)計(jì)代碼如下：#include"stdio.h"void 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 &quo

2、t;,ai);printf("n");3、 運(yùn)行結(jié)果1、 實(shí)驗(yàn)內(nèi)容寫(xiě)出計(jì)算ackerman函數(shù)ack(m,n)的遞歸計(jì)算函數(shù)。2、 程序設(shè)計(jì)代碼如下：#include "stdio.h"int 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,&a

3、mp;n);if(m<0 && n<0)printf("error input!");elsez=ack(m,n);printf("%dn",z);3、 運(yùn)行結(jié)果第四章例15 求數(shù)列的最大子段和給定n個(gè)元素的整數(shù)列（可能為負(fù)整數(shù)）a1,a2,.,an。求形如： ai,ai+1,aj i,j=1,.,n,i<=j的子段，使其和為最大。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0.程序：#include<stdio.h>int maxsum2(int a,int left,int right)int center,

4、i,left_sum,right_sum,s1,s2,lefts,rights;if(left=right)if(aleft>0)return aleft;elsereturn 0;elsecenter=(left+right)/2;left_sum=maxsum2(a,left,center);right_sum=maxsum2(a,center+1,right);s1=0;lefts=0;for(i=center;i>=left;i-)lefts=lefts+ai;if(lefts>s1)s1=lefts;s2=0;rights=0;for(i=center+1;i<

5、;=right;i+)rights=rights+ai;if(rights>s2)s2=rights;if(s1+s2<left_sum)&&(right_sum<left_sum)return left_sum;if(s1+s2<right_sum)return right_sum;return(s1+s2);int maxsum1(int a,int n)return(maxsum2(a,1,n);void main()int a100,n;printf("enter a number:");scanf("%d"

6、;,&n);printf("enter the number of a:");for(int i=1;i<=n;i+)scanf("%d",&ai);printf("%d",maxsum1(a,n);printf("n");運(yùn)行結(jié)果：回溯法N皇后問(wèn)題例如：8皇后問(wèn)題：要在8×8的國(guó)際象棋棋盤(pán)中放8個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。規(guī)則是皇后能吃掉同一行、同一列、同一對(duì)角線的任意棋子。下圖為一種方案，求所有的解。00000000模型建立：不妨設(shè)8個(gè)皇后為xi,他們分別在第i行（i=

7、1,2,3,4,5,6,7,8）,這個(gè)問(wèn)題的解空間，就是一個(gè)8個(gè)皇后所在的序號(hào)，為n元一維向量（x1,x2,x3,x4,x5,x6,x7,x8）,搜索空間是1<=xi<=8(i=1,2,3,4,5,6,7,8),共88個(gè)狀態(tài)。約束條件是8個(gè)點(diǎn)（1，x1）,（2,x2）,（3,x3）,（4,x4）,（5,x5）,（6,x6）,（7,x7）,（8,x8）不在同一列和同一對(duì)角線上。算法設(shè)計(jì)：用回溯法從開(kāi)始結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)出，搜索向縱深方向移動(dòng)至一個(gè)活結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成

8、為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)出不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，病史這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法即以這種工作方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已沒(méi)有活結(jié)點(diǎn)時(shí)為止。程序設(shè)計(jì)：#include <stdio.h>#include <math.h>void backdate(int n);int check(int k);int a20,n;void main()printf("Please input a number N>3:n");scanf(&q

9、uot;%d",&n);backdate(n);void backdate(int n)int k;a1=0;k=1;while(k>0)ak=ak+1;while(ak<=n)&&(check(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

10、;i+)if(abs(ai-ak)=abs(i-k)|(ai=ak)return(0);return(1);運(yùn)行結(jié)果：例12獄吏問(wèn)題算法1程序：#include<stdio.h>#include<malloc.h>void main()int *a,i,j,n;scanf("%d",&n);a=(int *)calloc(n+1,sizeof(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(

11、ai=0)printf("%d is free.",i);printf("n");運(yùn)行結(jié)果：算法2程序：#include<stdio.h>void 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");運(yùn)行結(jié)果：算法3程序：#include <stdio.h

12、>void main()int i,n;scanf("%d",&n);for(i=1;i<=n;i+)if(i*i<=n)printf("%d is free.",i*i);printf("n");elsebreak;運(yùn)行結(jié)果：貪婪法例4.22 貨幣統(tǒng)計(jì)問(wèn)題某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨時(shí)兌換零錢(qián)，且取款的張數(shù)最少，取工資前要統(tǒng)計(jì)出所有職工的工資所需各種幣值（100,50,20,10,5,2,1共7種）的張數(shù)，請(qǐng)編程完成。源程序如下：#include"stdio.h"v

13、oid 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("請(qǐng)輸入人數(shù)：");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,張數(shù)%5dn&q

14、uot;,Bi,Si);運(yùn)行結(jié)果：習(xí)題4.3問(wèn)題描述：54張撲克牌，兩人輪流拿，每人每次最少拿一張，最多納四張，誰(shuí)拿最后一張誰(shuí)輸。編寫(xiě)模擬計(jì)算機(jī)先拿牌且必勝的算法。原代碼如下：#include<stdio.h>main() int i,a10; printf("甲4n"); for(i=0;i<10;i+) scanf("%d",&ai); if(ai>=1&&ai<=4) printf("n乙%dt甲%dn",ai,5-ai); else printf("n你輸入的數(shù)據(jù)

15、有誤n"); return 0; printf("甲勝n");運(yùn)行結(jié)果：資源分配#include <stdio.h>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; 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+