语言-杂谈递归程序

三个齿轮啮合问题

设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。 解:这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设三个齿轮的齿数分别为:na、nb、nc；啮合最小圈数分别为:ma、mb、mc；三齿轮齿数的最小公倍数为k3。计算步骤表示为：开始读入三齿轮齿数求三齿数的最小公倍数k3分别计算啮合的最小圈数输出结果结束计算三齿数的最小公倍数k3。可以把该问题分解成先求两个齿数na与nb的最小公倍数k2，然后再求k2与第三个齿数nc的最小公倍数k3，

k3即为na、nb、nc三个齿轮齿数的最小公倍数。设已经有求两个数的最小公倍数的函数

intlowestcm(intx,inty)则该过程可表示成。求三齿数的最小公倍数k3=lowestcm(lowestcm(na,nb),nc )结束求两个数的最小公倍数的函数lowestcm。

x、y的最小公倍数是x、y的积除以x、y的最大公约数。设已经有求两个数的最大公约数的函数

intgcd(intx,inty)则过程可表示成：

intlowestcm(intx,inty)returnx*y/gcd(x,y)结束def采用展转相除法求两个数的最大公约数，函数

intgcd(intx,inty)定义如下函数gcd可用一个递归函数实现：intgcd(intx,inty)结束y≠0returngcd(y,x%y)returnx最后，分别计算啮合的最小圈数。开始ma=k3/namb=k3/nbmc=k3/nc结束受限排列组合——穷举法与试探法

有这样一类问题，从若干元素的所有排列(或组合)中选取符合某种条件的一些排列(或组合)。八皇后问题Debruijn问题解这类问题有两条途径:1.穷举法;2.试探法。八皇后问题

这是一个古老而有趣的游戏。高斯(C.F.Gauss)最早在1850年提出并研究过这个问题，但是没有完全解决。该问题是： 在一个8*8格的国际象棋棋盘上放置八个皇后，使任意两个皇后都不能互相攻击。按国际象棋规则，两个皇后可以互相攻击。若在同一行上，或在同一列上,或在同一条斜线上（包括左高右低、右高左低）********如图放置的八个皇后便不能互相攻击。编程序,求出所有符合要求的布局。共有92种满足条件的布局，若除去对称的等类同布局,完全不同者有12种。这里不考虑剔除类同布局，求出全部92种布局。八皇后问题的表示方法:用一个一维数组表示棋盘。A[i]表示棋盘的第i列，每列一个皇后，若A[i]中存放有数k表示第i列中第k行上放置了皇后。例: A[3]=6表示在棋盘的第3列第6行上放置一个皇后。A[0]不用

012345678A:八皇后穷举法

本方法思路是，按某种顺序枚举出全部排列或组合。每当枚举出一种排列或组合之后，便用给定条件判断该种排列或组合是否符合条件。若符合条件，则本种排列或组合被选中，可以输出或记录下来。若不符合条件，则把本种排列或组合舍掉。八个皇后的排列问题，最简单的方法是八重循环，可以编出如下穷举法程序。

intmain(void){inta[9]，i1,i2,i3,i4,i5,i6,i7,i8;for(i1=1;i1<=8;i1++)for(i2=1;i2<=8;i2++)for(i3=1;i3<=8;i3++)for(i4=1;i4<=8;i4++)for(i5=1;i5<=8;i5++)for(i6=1;i6<=8;i6++)for(i7=1;i7<=8;i7++)for(i8=1;i8<=8;i8++){a[1]=i1;a[2]=i2;a[3]=i3;a[4]=i4;a[5]=i5;a[6]=i6;a[7]=i7;a[8]=i8;if(check())out();}}八皇后试探法按规律，从一满足条件的初始状态出发，逐步生成满足条件的子排列,不断增加子排列长度。增加子排列长度过程中，每增加一位,生成一个子排列后,便检验它是否满足条件。不满足条件,则换一个子排列－即修改当前位置满足条件,则延长子排列,增加子排列长度。子排列的长度满足要求长度,便找到了一个解。若要求找一个解即可，这时便可以结束。若要求找所有解，这时可以输出或记录本解，然后按前述思路，继续修改排列，继续试探，找下个解在上述试探过程中,修改当前位置时：若当前位置上还有没被试探过的元素，则应该取下一个没被试探过的元素进行试探若当前位置上所有元素都被试探过了，则在当前位置上没办法再修改了这说明前边的某个位置有问题，放置的元素不对，显然应该向回退一位。回溯后,原来的上一个位置变成了当前位置,则又变成修改当前位置的问题了。这时,同样还应该考虑取下一个没被试探过的元素进行试探,以及是否所有元素在当前位置上都被试探过了并回溯的问题。如图所示，设要生成一个n位的串A；在每个位置上可选择的符号有K个；A应该满足条件r；m表示当前试探位置。试探法的算法描述为：1.初始时，从第一个位置开始试探，令m=1;2.然后在第m位逐次取可选符号:B[1],B[2],...,

B[k]。对某一个B[i]有两种可能:012n

A:…B:12…k若B[i]使A[1],A[2],...,A[m]满足r,则进入A的下一个位置。

m=m+1012…mm+1nA:B:12…k若B[i]不能使A[1],A[2],...,A[m]满足r,则有两种情况:i<k，012……mnA:B[i]B:1…ii+1…k若B[i]不能使A[1],A[2],...,A[m]满足r,则有两种情况:i<k，取B中下一个符号继续试探

i=i+1012……mnA:B[i+1]B:1…ii+1…k若i=k说明在当前位置上所有符号都已经被试探过012…m-2m-1mnA:B[w]B[k]B:1…imim+1…k若i=k说明在当前位置上所有符号都已经被试探过应该回溯到上一个位置,作m=m-1后继续试探直到找到解、m=0结束012…m-2m-1mnA:B[i1]B[i2]…B[w+1]B:1…ww+1…k**************以四皇后问题为例，考察试探过程：12341234上述试探法思想描述如下:试探法初值

试探未结束结束

子排列合格够长修正当前位置输出延长修正当前位置修正当前位置取下一个没被试探过的元素回溯结束本位置已经没有没被试探过的元素def延长当前位置赋值第一个元素下一个位置变成当前位置(m=m+1)返回程序如下: intA[9],m;boolcheck(intm);/*检查某格局是否合格的函数*/voidout();/*输出函数*/voidchange(void){/*修正*/while(A[m]==8)m=m-1;A[m]=A[m]+1;}voidextend(void){/*延长*/m=m+1;A[m]=1;}intmain(void){/*主程序*/A[0]=0;A[1]=1;m=1;while(m>0)if(check(m)){if(m==8){out();change();}else extend();}elsechange();}穷举法与试探法的着眼点及主要区别在于:穷举法是举出全部可能的格局，对每种格局进行检验,使合格者入选，不合格者淘汰。试探法是从初始满足条件的格局开始，逐步前进。每前进一步都判断子格局是否合适。若当前子格局合适则进入下一级;若当前子格局不合适则选同一级的下一个子格局;但是若同级子格局已全部试探完毕,则回溯到上一级直到当前子格局够长为止。

显然穷举法的运算量比试探法要大的多。因为它要考虑一切情况的排列，而试探法可以在中间丢掉大量的不合格排列。事实上许多问题的穷举法是不适用的,把每一种情况都排出来，并检验其是否合格显然是不可能的。不论穷举法还是试探法都可以写成递归形式:循环迭代递归

八皇后穷举法的递归实现用穷举法实现八皇后问题,可以抽象的描述为：在数组A的8个位置上分别排列一个1到8的整数。设想,如果有一个函数

queen(r)

能够完成

“在数组A后部的r个位置（从第8-r+1到8）上,分别排列一个1到8的整数”。则八皇后问题便是

queen(8)“在数组A后部的r个位置上,分别排列一个1到8的整数”可以分解成:先在第8-r+1位上分别排列一个1到8的整数；然后再在剩余的后部的r-1个位置上分别排列一个1到8的整数。步骤2便是对queen的递归调用

queen(r-1)。最后考虑递归出口,显然应该在r=1

时检验输出并退出递归。由此得递归实现八皇后问题的穷举算法及递归程序八皇后穷举法结束queen(8)queen(r)结束for(i=1;i<=8;i++)queen(r-1)A[8-r+1]=i;r>1输出检验intA[9];boolcheck();/*检查某格局是否合格的函数*/voidout();/*输出函数,分程序略*/voidqueen(intr){inti;for(i=1;i<=8;i++){A[8-r+1]=i;if(

r>1)queen(r-1);elseif(cheek())out();}}intmain(void){queen(8)}八皇后试探法的递归实现试探方法的思路是，按一定规律，从某一满足条件的初始状态出发，逐步试探生成满足条件的子排列,不断增加子排列长度,直到子排列的长度满足问题的要求长度n为止,便找到了一个解。设想,如果有一个函数

queen(r)

能够“合理的排列数组A后部的r个(从第n-r+1到n)元素” 并保证序列满足给定条件,则八皇后问题便是对queen的调用

queen(8)“合理的排列数组A后部的r个（从第n-r+1到n）元素”可以分解成:首先在第n-r+1位上排列一个合格的元素,然后在合理的排列从n-(r-1)+1开始的后部的r-1个元素。步骤1“在第n-r+1位上排列一个合格的元素”，即是把8个元素顺次的排列在第n-r+1位上,并对每个元素检验是否合格，使合格者入选。步骤2“合理的排列后部的r-1个元素”显然与“合理的排列后部的r个元素”具有相同的特征属性,只是排列的元素个数减少了,也就是说它表现为对queen的递归调用。queen(r)结束for(i=1;i<=8;i++)queen(r-1)A[8-r+1]=i;合理输出r>1

在该算法中,试探法的“延长”体现在继续递归调用上；“修正本位”体现在从1到8作i的循环上；“回溯”则体现在递归出口的返回上。intA[9];boolcheck(intm);/*检查某格局是否合格的函数*/voidout(void);/*输出函数*/voidqueen(intr){/*试探法*/inti;for(i=1;i<=8;i++){A[8-r+1]=i;if(check(8-r+1))if(r>1)queen(r-1);elseout();}}intmain(void){ /*主程序*/queen(8)}分析检验条件:纵向,每列只有一个皇后:由数据结构保证每列只能放一个皇后。横向，每行放置一个皇后:显然要求数组A中不能有重复的数值。设当前为第m步，由于前m-1步是合格的,所以只要检验A[m]不等于所有的A[1]、...、A[m-1]。左高右低对角线(共有2*n-1即15条)：这样对角线上不同位置的行列号之差相等。设当前为第m步，由于前m-1步是合格的，所以只要对一切i<m检验：

A[m]-m≠A[i]-i。左高右低对角线:与左高右低对角线类似。只不过这里该检查

A[m]+m≠A[i]+i。试探法检验函数check如下，

boolcheck(intm){inti;for(i=1;i<m;i++){if(A[m]==A[i])returnfalse;if(A[m]-m==A[i]-i)returnfalse;if(A[m]+m==A[i]+i)returnfalse;}returntrue;}

穷举法的检验函数应该多加一层循环。

boolcheck(){inti,j;for(i=1;i<8;i++){ for(j=i+1;j<=8;j++){if(A[j]==A[i])returnfalse;if(A[j]-j==A[i]-i)returnfalse;if(A[j]+j==A[i]+i)returnfalse;}}returntrue;}

Debruijn问题如图由８个二进制数字0、1组成一个环。使８个3位的二进制数:0000

0011010201131004

1015

11061117正好在环中各出现一次。本例目前的顺序是：0、1、2、5、3、7、6、4。设计生成这样环的程序。环由2n个二进制数字组成，恰好包含2n个互不相同的n位二进制数。00001111

6.6迷宫问题

问题的提出迷宫问题是指在一个m*n的矩阵当中，其中”0”代表可以行走的区域，”1”代表不可行走的区域，当你处在迷宫的任何一个位置，除了不可行走的区域外，其余皆可以往上、下、左、右、左上、左下、右上、右下八个方向行走来找寻迷宫出口。程序实现程序目的运用递归来解迷宫问题程序构思递归结束条件：当已经走到出口时(当出口(6,5),标记为2时)递归执行部分：判断传入坐标是否可走如果可以走的话，则递归调用往上,往右上,往右,往右下,往下,往左下,往左,往左上坐标是否可走。可走的话，返回1。不可走的话，标记改为3(已走过,但为能有通路)。

6.6迷宫问题

程序源代码importConsoleReader.*;//引入已定义的数据输入类

publicclassmaze{publicstaticintMaze[][]={//声明5*4的迷宫,外围不可走

{1,1,1,1,1,1,1},{1,0,1,0,0,0,1},{1,1,0,1,1,0,1},{1,1,0,1,1,0,1},{1,1,1,0,1,1,1},{1,0,0,1,0,1,1},{1,1,1,1,0,0,1},{1,1,1,1,1,1,1}};

6.6迷宫问题

publicstaticvoidmain(Stringargs[]){inti,j;//循环计数变量

System.out.println(“==ProblemofMaze==”);System.out.println(“TheMazesourceis(1,1).”);System.out.println(“TheMazeDestinationis(6,5).”);Way(1,1);

System.out.println(“ThegraphofMaze.”);System.out.println(“0123456“);System.out.println(“+---+---+---+---+---+---+---+”);

for(i=0;i<8;i++){

6.6迷宫问题

System.out.print(“

“+i+”|“);for(j=0;j<7;j++)System.out.print(“-“+Maze[i][j]+”-|”);System.out.println(“

”);System.out.println(“+---+---+---+---+---+---+---+”);}}

//-----------------------------