吴文虎程序设计基础第9章源程序.doc

用递归求解Hanoi问题/ */ * 程 序：9_1.cpp */ * 作 者：wuwh */ * 编制时间：2002年10月13日 */ * 主要功能：用递归求解Hanoi问题 */ *#include / 预编译命令using namespace std;int step=1;/ 整型全局变量,预置1,步数void move(int, char, char, char);/ 声明要用到的被调用函数void main()/ 主函数/ 主程序开始int n;/ 整型变量,n为盘数,cout n;/ 输入正整数ncout 在3根柱子上移/ 输出提示信息 n 只盘的步骤为:endl; move(n,A,B,C);/ 主函数结束/ 以下函数是被主程序调用的函数/ 函数名：move/ 输 入：m，整型变量，表示盘子数目/ p，q，r为字符型变量，表示柱子标号/ 返回值：无void move(int m, char p, char q, char r)/ 自定义函数体开始if (m=1)/ 如果m为1,则为直接可解结点,/ 直接可解结点,输出移盘信息cout step move 1# from p to r endl; step+;/ 步数加1else/ 如果不为1,则要调用move(m-1)move(m-1,p,r,q);/ 递归调用move(m-1)/直接可解结点,输出移盘信息coutstep move m # from p to rendl; step+;/ 步数加1move(m-1,q,p,r);/ 递归调用move(m-1)/自定义函数体结束计算组合数C(m,n)/ */ * 程 序：9_2.cpp * / * 编制时间：2002年10月28日 * / * 主要功能：计算组合数C(m,n) */ *#include / 预编译命令using namespace std;/ 计算C(m,n)，即从m个数中取n个数的组合数int Cmn(int m, int n)if (m0 | n0 | mn)return 0;if (m=n)/ C(m,m)=1return 1;if (n=1)/ C(m,1)=mreturn m;return Cmn(m-1, n)+ Cmn(m-1,n-1);/ C(m,n)=C(m-1,n)+C(m-1,n-1)int main()/ 主函数开始/ 测试一些结果cout C(6,0)= Cmn(6,0) endl;cout C(6,1)= Cmn(6,1) endl;cout C(6,2)= Cmn(6,2) endl;cout C(6,6)= Cmn(6,6) endl; return 0;/ 主函数结束快速排序/ */ * 程 序：9_3.cpp */ * 作 者：wuwh */ * 编制时间：2002年10月28日 */ * 主要功能：快速排序 */ *#include /预编译命令void sort(int array , int zz, int yy)/被调用函数，数组array,zz,yy为形参 /函数体开始int z,y,i,k; /定义变量if ( zzyy ) /如果 zz yy ,则做下列 7 件事: / 7 件事开始z = zz; y = yy; k = array z ; /第1件事do /第2件事(开始)while( z=k) y-; /2.1,右边的元素=k,让 y 往中间移if( z y ) /2.2,右边的元素k,让 array z = array y ; /array y 送给 array z ，z = z+1; /同时让 z 往中间移while( z y) & (arrayz = k) z+; /2.3,左边的元素=k,让 z 往中间移if ( z k, 让 array z array y = array z ; /送给array y while( z!=y ) ; /第2件事(结束)arrayz = k; /第3件事,k已排到位for(i=zz; i=yy; i+) /第4件事，输出coutai=arrayi; ;cout endl; /第5件事，换行sort( array, zz ,z-1 ); /第6件事，排左边部分sort( array ,z+1, yy); /第7件事，排右边部分 /7件事结束 /函数体结束int main() /主函数开始int a10,i; /整型变量cout 请输入10个整数n;/提示信息for (i = 0; i a i ;sort(a,0,9);/调用sort函数,实参为数组a和0，9cout 排序结果为:; /提示信息for (i =0; i10 ;i+ ) cout a i ;/输出排序结果cout endl; return 0;/主函数结束 旋转方块#include using namespace std;#define N 9int PNN;void fill (int number,int begin,int size)if (size = 0) return ;if (size =1)Pbeginbegin = number;return ;int i = 0;int h = begin,v=begin;Phv=number;number+;for (i = 0;isize-1;i+)h+;Phv =number;number+;for (i=0;isize-1;i+)v+;Phv = number;number+;for (i=0;isize-1;i+)h-;Phv = number;number+;for (i=0;isize-2;i+)/修改的地方v-;Phv = number;number+;fill(number,v,size-2);int main ()fill(1,0,N);int h,v;for (h =0;hN;h+)for (v=0;vN;v+)coutPhvt;coutn;return 0;#include using namespace std;#define N 9int PNN;void fill (int number,int begin,int size)if (size = 0) return ;if (size =1)Pbeginbegin = number;return ;int i = 0;int h = begin,v=begin;Phv=number;number+;for (i = 0;isize-1;i+)h+;Phv =number;number+;for (i=0;isize-1;i+)v+;Phv = number;number+;for (i=0;isize-1;i+)h-;Phv = number;number+;for (i=0;isize-2;i+)/修改的地方v-;Phv = number;number+;fill(number,v,size-2);int main ()fill(1,0,N);int h,v;for (h =0;hN;h+)for (v=0;vN;v+)coutPhvt;coutn;return 0;下楼问题/ */ * 程 序：9_5.cpp */ * 作 者：wuwh */ * 编制时间：2002年11月04日 */ * 主要功能：下楼问题 */*#include / coutusing namespace std;/ 定义全局变量：数组take，方案数numint take99; int num = 0;void Try(int i, int s) / 还有i级台阶，从第s步开始for (int j=3; j0; j-)if (i = j)takes = j;/ 记录第s步走j个台阶if (i=j) / 如果已经到了楼下num+;/ 则 方案数加1cout 方案 num ：; / 输出此方案for (int k=1; k=s; k+)cout takek ; cout =j)_ / _FOR_J_ / 函数体结束int main( ) int h = 0;/ h 是楼梯的台阶数cout h;/ 输入楼梯的台阶数 / 从第h级，开始下第一步 Try(h,1);/ 输出总方案数 cout 总方案数： num endl; return 0;跳马问题/*/* 程序名：9_6.cpp */* 作 者：wuwh */* 时 间：2002年11月11日 */* 功 能：跳马问题 */*#include / coutusing namespace std;const int TARGET_X = 8;/ 整型常量const int TARGET_Y = 4;const int MAXSTEP = 9;/ 含起点，最多九步int dx = 1, 2, 2, 1 ;int dy = 2, 1, -1, -2 ;int Num;int pathMAXSTEP2;void jump(int x, int y, int step) for (int k=0; k=0) & (x1=0) & (y1=TARGET_Y); if ( t1 & t2 ) / x1,y1可行 pathstep0 = x1; pathstep1 = y1;bool t4 = (x1=TARGET_X) & (y1=TARGET_Y); / 到达目标if (t4) /测试达目标否 Num+; /方案号加1 cout方案 Num: ;for (int i=0; i=step; i+) cout (pathi0 , ;cout pathi1 ) ; cout endl;elsejump(x1, y1, step+1); /跳下一步 / _if(t1 & t2)_ / _for_k_ int main() / 主函数Num = 0; / 方案号置0path00 = 0; path01 = 0; / 棋盘左下角/ 从(0,0)出发，跳第一步jump(0,0,1);/ 输出总方案数cout 总方案数： Num endl; return 0;分书问题/ */ * 程 序：9_7.cpp */ * 作 者：wuwh */ * 编制时间：2002年10月28日 */ * 主要功能：分书问题 */ *#include /预编译命令int take5,n;/整型变量 int like55 = 0,0,1,1,0, 1,1,0,0,1, 0,1,1,0,1, 0,0,0,1,0, 0,1,0,0,1 ;/整型变量,定义数组，初始化int book5=0,0,0,0,0;/整型变量,定义数组，初始化void Try(int i)/函数体开始int j,k;/定义变量for(j=0;j0)&(bookj=0) /如果满足分书条件作下列事 takei=j;/把j号书给i bookj=1;/记录j书已分if(i=4)/如果i=4,输出分书方案 n+;/让方案数加1 cout 第 n 个方案n;/输出分书方案号 for(k=0; k=4; k+) /输出分书方案 cout takek 号书分给 char(k+65) endl; cout endl;/换行else /如果i!=4,继续给下一人分书 Try(i+1);/递归调用Try(i+1) takei=-1;/让i把书退还bookj=0;/记录j书待分int main()/主函数/主函数开始 n=0;/分书方案号预置0Try(0);/调用Try函数,实参为0return 0;/主函数结束八皇后问题/*/* 程 序：9_8.cpp*/* 作 者：wuwh*/* 编制时间：2002年11月06日*/* 主要功能：八皇后问题*/*#include / 预编译命令 using namespace std;const int Normalize = 9;/ 定义常量，用来统一数组下标int Num;/ 整型变量，记录方案数 int q9;/ 记录8个皇后所占用的列号bool C9;/ C1C8，布尔型变量，当前列是否安全bool L17;/ L2L16，布尔型变量，(i-j)对角线是否安全 bool R17;/ R2R16，布尔型变量，(i+j)对角线是否安全void Try(int i)/ 被调用函数 int j;/ 循环变量，表示列号 int k;/ 临时变量 for (j=1; j=8; j+)/ 循环if ( (Cj=true) & (Ri+j=true) & (Li-j+Normalize=true)/ 表示第i行，第j列是安全的qi = j; Cj = false; Li-j+Normalize = false; Ri+j = false; if ( i8 )Try(i+1); else Num+; / 方案数加1 cout 方案 Num ：; / 输出方案号for ( k=1; k=8; k+) cout qk ;cout endl; Cj = true; Li-j+Normalize = true; Ri+j = true; void main() int i;Num = 0;/ 方案数清零 f