c语言-递归算法

计算机语言与程序设计谌卫军清华大学软件学院IntroductiontoComputerProgramming第八章递归算法132基本概念基于回溯策略的递归基于分治策略的递归从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，老和尚正在给小和尚讲故事。讲的是什么故事呢？他说，从前……Recursion-See

"Recursion".

"Inordertounderstandrecursion,onemustfirstunderstandrecursion."C语言允许嵌套地调用函数，也就是说，在调用一个函数的过程中，又去调用另一个函数。函数的嵌套调用voidmain(){…

study_english();

…}voidstudy_english(){reading();listening();

writing()}voidlistening(){

………}函数的嵌套调用有一个特例，即递归调用，也就是说，在调用一个函数的过程中，又出现了直接或间接地去调用该函数本身。voidtell_story(){intold_monk,young_monk;tell_story(); //tell_story函数的递归调用}函数的递归调用?voidtell_story(){staticintold_monk,young_monk;old_monk=old_monk+1;//年龄大了一岁

young_monk=young_monk+1;if(old_monk<=60) //递归形式

tell_story();elseprintf("对不起，已退休！");//递归边界}在语法上（简单）递归即为普通的函数调用。在算法上（难）如何找到递归形式？如何找到递归边界？如何编写递归程序？递归算法的类型递归算法可以分为两种类型：基于分治策略的递归算法；基于回溯策略的递归算法。第八章递归算法132基本概念基于回溯策略的递归基于分治策略的递归分而治之（divide-and-conquer）的算法设计思想：Divide：把问题划分为若干个子问题；Conquer：以同样的方式分别去处理各个子问题；Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。8.2.1

分而治之玛特露什卡……调用调用……调用调用……调用调用如何编写基于分治策略的递归程序？在算法分析上，要建立分治递归的思维方式。在编程实现上，要建立递归信心（Totursttherecursion,JerryCain,stanford）。 如何建立分治递归的思维方式？基本原则：目标驱动！计算n!：n!=n*(n-1)!，且1!=1。递归形式递归边界调用调用fact(3)fact(2)fact(1)voidmain(){intn;printf("请输入一个整数：");scanf("%d",&n);printf("%d!=%d\n",n,fact(n));}intfact(intn){if(n==1)return(1);else return(n*fact(n-1));}请输入一个整数：33!=6调用和返回的递归示意图

如何建立递归信心？函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是的话，那么大家会不会相互干扰、相互妨碍？main的栈帧m3voidmain(){intm;printf("请输入一个整数：");scanf("%d",&m);printf("%d!=%d\n",m,fact(m));}intfact(intn){if(n==1)return(1);else return(n*fact(n-1));}3nfact的栈帧2nfact的栈帧1nfact的栈帧8.2.2

寻找最大值问题描述： 给定一个整型数组a，找出其中的最大值。如何设计相应的递归算法？如何来设计相应的递归算法？目标：max{a[0],a[1],…a[n-1]}可分解为：max{a[0],max{a[1],…a[n-1]}}另外已知max{x}＝x这就是递归算法的递归形式和递归边界，据此可以编写出相应的递归函数。intMax(inta[],intfirst,intn){intmax;if(first==n-1)returna[first];max=Max(a,first+1,n);if(max<a[first])returna[first];elsereturnmax;}Max(a,0,n)调用Max(a,1,n)调用…调用

Max(a,n-1,n)返回返回返回8.2.3

折半查找法问题描述： 查找（Searching）：根据给定的某个值，在一组数据（尤其是一个数组）当中，确定有没有出现相同取值的数据元素。顺序查找、折半查找。前提：数据是有序排列的；基本思路：将目标值与数组的中间元素进行比较；若相等，查找成功。否则根据比较的结果将查找范围缩小一半，然后重复此过程。412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874请问：4565926是否在此列表当中？412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874请问：4565926是否在此列表当中？数组正中间的元素。412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874请问：4565926是否在此列表当中？不予考虑412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874请问：4565926是否在此列表当中？正中间的元素412024342760134328968439770044627184466240447557944789644480332449476344990434508710454924345636974564531456592645660884572874请问：4565926是否在此列表当中？正中间的元素不予考虑4565925？voidmain(){intb[]={05,13,19,21,37,56,64,75,80,88,92};intx=21;printf("x位于数组的第%d个元素\n",bsearch(b,x,0,10));}如何用递归来实现？函数原型：

intbsearch(intb[],intx,intL,intR);递归的形式？递归的边界？问题分析intbsearch(intb[],intx,intL,intR){intmid;if(L>R)return(-1);mid=(L+R)/2;if(x==b[mid])returnmid;elseif(x<b[mid])returnbsearch(b,x,L,mid-1);elsereturnbsearch(b,x,mid+1,R);}8.2.4

汉诺(Hanoi)塔问题相传在古印度Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上（简单吗？若每秒移动一只盘子，需5800亿年）ABC怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。1、在A柱上只有一只盘子，假定盘号为1，这时只需将该盘直接从A搬至C，记为

move

from

A

to

CABC12、在A柱上有二只盘子，1为小盘2为大盘。 分三步进行：ABC21movefromA

toB;movefromA

to

C;moveformB

toC;3、在A柱上有3只盘子，从小到大分别为1号，2号，3号。怎么移？ABC213分七步！

分三步进行：

move

2

discsfrom

A

to

Busing

C；

movefrom

A

to

C；

move

2

discsfrom

B

to

Cusing

A；ABC2134、在A柱上有n个盘子,从小到大分别为1号、2号、3

号、…、n号。第1步：将1号、2号、…、n-1号盘作为一个整体，

在C的帮助下，从A移至B；第2步：将n号盘从A移至C；第3步：再将1号、2号、…、n-1号盘作为一个整

体，在A的帮助下，从B移至C；

这三步记为：

move

n-1

discsfrom

A

to

Busing

C；

move

1

discsfrom

A

to

C；

move

n-1

discsfrom

B

to

Cusing

A；递归形式！定义函数move(intn,charL,

charM,

char

R);表示move

n

discsfrom

L

to

R

using

M；如果n=1，即表示movefrom

L

to

R；移动的是谁？#include<stdio.h>voidmove(intn,charL,charM,charR);voidmain(){intn;printf("请输入一个整数：");scanf("%d",&n);move(n,'A','B','C');}//L:Leftpost,M:Middlepost,R:Rightpostvoidmove(intn,charL,charM,charR){if(n==1)printf("move#1from%cto%c\n",L,R);else{move(n-1,L,R,M);

printf("move#%dfrom%cto%c\n",n,L,R);move(n-1,M,L,R);}}请输入一个整数：3move#1fromAtoCmove#2fromAtoBmove#1fromCtoBmove#3fromAtoCmove#1fromBtoAmove#2fromBtoCmove#1fromAtoC一次运行结果8.2.5

青蛙过河一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S根石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？ 这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。思路：1、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。2.定义函数

Jump(S,y)——最多可跳过河的青蛙数其中： S——河中柱子数

y——荷叶数

2

说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两只青蛙，1#在2#上面。第一步：1#跳到荷叶上；第二步：2#从L直接跳至R上；第三步：1#再从荷叶跳至R上。如下图：3.先看简单情况，河中无柱子：S=0，

Jump(0,y)

当y=1时，Jump(0,1)=；

3

说明：河中有两片荷叶时，可以过3只青蛙。起始时：

1#，2#，3#3只青蛙落在L上，第一步：1#从L跳至叶1上，第二步：2#从L跳至叶2上，第三步：3#从L直接跳至R上，第四步：2#从叶2跳至R上，第五步：1#从叶1跳至R上，采用归纳法：Jump(0,y)=当y=2时，

Jump(0,2)=；

y+1；意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。再看Jump(S,y)

先看一个最简单情况：S=1，y=1。从图上看出需要步，跳过只青蛙。

94

1#青蛙从L－>Y；

2#青蛙从L－>S；

1#青蛙从Y－>S；

3#青蛙从L－>Y；

4#青蛙从L－>R；

3#青蛙从Y－>R；

1#青蛙从S－>Y；

2#青蛙从S－>R；

1#青蛙从Y－>R；对于S=1，y=1的情形，从另外一个角度来分析若没有石柱S，最多可过y+1

=

2只青蛙。有了石柱S后，最多可过2*2=4只青蛙。步骤1：

1#和2#从L－>S；步骤2：

3#和4#从L－>R；步骤3：

1#和2#从S－>R；YSLR①:1#,2#②:3#,4#③:1#,2#YYY对于S=1，y>1的情形若没有石柱S，最多可过y+1

只青蛙。有了石柱S后，最多可过2*(y+1)只青蛙。步骤1：

前y+1只从L－>S；步骤2：

后y+1只从L－>R；步骤3：

前y+1只从S－>R；YSLR①:前y+1只②:后y+1只③:前y+1只YYY对于S=2，y>1的情形若只有石柱S1，最多可过2*(y+1)

只青蛙。有了石柱S2后，最多可过 只青蛙。YS1LR4*(y+1)S2步骤1：

前2*(y+1)只从L－>S2；步骤2：

后2*(y+1)只从L－>R；步骤3：

前2*(y+1)只从S2－>R；Y,S1Y,S1Y,S1采用归纳法，可得出如下的递归形式：Jump(S,y)=2*Jump(S-1,y)；意思是：先让一半的青蛙利用y片荷叶和S-1根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用y片荷叶和S-1根石柱，落在右岸的R上面；最后再让先前的一半青蛙，利用y片荷叶和S-1根石柱，落在右岸的R上面。递归边界：Jump(0,y)=y+1voidmain(){intS,y;printf("请输入石柱和荷叶的数目：");scanf("%d%d",&S,&y);printf("最多有%d只青蛙过河\n",Jump(S,y));}intJump(intS,inty){if(S==0)return(y+1);return(2*Jump(S-1,y));}8.2.6

快速排序快速排序的基本思路：1、在数组a中，有一段待排序的数据，下标从l到r。2、取a[l]放在变量value中，通过由右、左两边对value的取值的比较，为value选择应该排定的位置。这时要将比value大的数放右边，比它小的数放左边。当value到达最终位置后（如下标m），由它划分了左右两个集合[l..m-1]、[m+1..r]。然后转第1步，再用相同的思路分别去处理左集合和右集合。令qsort(l,r)表示将数组元素从下标为l到

下标为r的共r-l+1个元素进行从小到大的

快速排序。目标：1、让value=a[l]2、将value放在a[m]中，lmr3、使a[l],a[l+1],…,a[m-1]<=a[m]4、使a[m]<a[m+1],a[m+2],…,a[r]例子：数组a当中有7个元素等待排序。5261734lr首先，让value=a[l]=a[0]=5value5a0123456下标5261734l第二步，从r=6开始，将a[r]与value进行比较。

若a[r]value，则r--，继续比较。否则，

a[l]=a[r]，l++。value5ra0123456下标4l4261734第三步，从l=1开始，将a[l]与value进行比较。

若a[l]value，则l++，继续比较。否则，

a[r]=a[l]，r--。value5ra0123456下标ll6r4261736又回到第二步，从r=5开始，将a[r]与value进行比较。若a[r]value，则r--，继续比较。否则

a[l]=a[r]，l++。value5a0123456下标lr3l4231736又回到第三步，从l=3开始，将a[l]与value进行比较。若a[l]value，则l++，继续比较。否则，a[r]=a[l]，r--。value5a0123456下标rll7r4231776现在l＝

r，已经找到了value的正确位置，把value中的值放回到数组当中。value5a0123456下标lr54231576下面的任务：用刚才介绍的方法，对5左、右两侧的两段数据，分别进行排序。a0123456下标×××1324a0123456下标lr67×××××a0123456下标lr1234567最后的结果：a0123456下标具体实现：几重循环语句？参考程序：略……第八章递归算法132基本概念基于回溯策略的递归基于分治策略的递归在程序设计当中，有相当一类求一组解、或求全部解或求最优解的问题，不是根据某种确定的计算法则，而是利用试探和回溯（Backtracking）的搜索技术求解。回溯法也是设计递归算法的一种重要方法，它的求解过程实质上是一个先序遍历一棵“状态树”的过程，只不过这棵树不是预先建立的，而是隐含在遍历的过程当中。8.3.1

分书问题有五本书，它们的编号分别为1，2，3，4，

5，现准备分给A,B,C,D,E五个人，每个

人的阅读兴趣用一个二维数组来加以描述：希望编写一个程序，输出所有的分书方案，

让人人皆大欢喜。假定这5个人对这5本书的阅读兴趣如下表：

1 2 3 4 5ABCDE0011011001011010001001001人书解题思路：1、定义一个整型的二维数组，将上表中的阅读喜好

用初始化的方法赋给这个二维数组。

可定义：intLike[6][6]={{0},{0,0,0,1,1,0},{0,1,1,0,0,1}, {0,0,1,1,0,1},{0,0,0,0,1,0},

{0,0,1,0,0,1}};2、定义一个整型一维数组BookFlag[6]用来记录书

是否已被选用。用后五个下标作为五本书的标号，

被选用的元素值为1,未被选用的值为0,初始化皆为0.intBookFlag[6]={0};3、定义一个整型一维数组BookTaken[6]用来记录

每一个人选用了哪一本书。用数组元素的下标来作

为人的标号，用数组元素的值来表示书号。如果某

个人还没有选好书，则相应的元素值为0。初始化

时，所有的元素值均为0。intBookTaken[6]={0};4、循环变量i表示人，j表示书，i,j{1,2,3,4,5}一种方法：枚举法。

把所有可能出现的分书方案都枚举出来，然后逐一判断它们是否满足条件，即是否使得每个人都能够得到他所喜欢的书。缺点：计算量太大。i=1j=1j=2i=2j=3j=5i=3j=1i=3j=2j=4i=4j=2j=4i=4j=5i=5j=4j=5j=5j=2i=5j=4j=2j=1j=4i=4j=5j=1i=5j=4j=1i=3j=5…i=2j=4…如何抽取出

递归形式？voidperson(inti);intLike[6][6]={{0},{0,0,0,1,1,0},{0,1,1,0,0,1}, {0,0,1,1,0,1},{0,0,0,0,1,0}, {0,0,1,0,0,1}};intBookFlag[6]={0};intBookTaken[6]={0};voidmain(){person(1);}voidperson(inti) //尝试给第i个人分书{

intj,k;

for(j=1;j<=5;j++) //尝试把每本书分给第i个人

{

if((BookFlag[j]!=

0)||(Like[i][j]==0))continue;//失败

BookTaken[i]=j;//

把第j本书分给第i个人

BookFlag[j]=1;

if(i==5){ //已找到一种分书方案

for(k=1;k<=5;k++)printf("%d",BookTaken[k]);

printf("\n");}

else{

person(i+1); //给第i+1个人分书

}

BookTaken[i]=0; //回溯，把这一次分得的书退回

BookFlag[j]=0;

}}8.3.2

下楼问题从楼上走到楼下共有h个台阶，每一步有三种

走法：走一个台阶；走二个台阶；走三个台阶。问可以走出多少种方案，希望用递归思想来

编程。数据的定义：

j=1,2,3——表示在每一步可以试着走

的台阶数

s——表示步数

i——表示当前的高度；

pace[s]——保存第s步走过的台阶数基本思路：让i先取h值，然后在下楼时，试着一步一步地走，从高到低。每走一步

i的值就会减去这一步所走的台阶数

j，即

i=h（初值），以后i=i-j，(j=1,2,3)，当

i=0时，说明已走到楼下。每一步都要试

j的三种不同取值，即或者为1，或者为2，或者为3。这时可用for循环结构。每一步走法都用相同的策略，故可以用递归算法。i=4i=3j=1

s=1i=2j=2

s=1i=2j=1

s=2i=1j=2

s=2i=1j=3

s=1i=1j=1

s=3j=1

s=4i=0j=2j=3j=2

s=3i=0j=3j=1

s=3i=0j=2j=3j=3

s=2i=0i=1j=1

s=2

j=1

s=3i=0j=2j=3j=2

s=2i=0j=3

j=1

s=2i=0j=2j=3定义TryStep(i,s)——站在第i级台阶上往下试

走第s步的过程如何实现？

第一步：j=1；第二步：如果j>i,表明这一步不可能走j级台阶,函

数返回；否则，转第三步；第三步：这一步走j级台阶，即pace[s]=j;

如果i-j=0，说明已经到达地面了，也就是

已经找到一种方案了，把它显示出来；否则

的话，接着走下一步，TryStep(i-j,s+1)；第四步：j=j+1，如果j3，转第二步；否则函数

结束。能否用分治策略？8.3.3

八皇后问题在8×8的棋盘上，放置8个皇后（棋子），使两两之

间互不攻击。所谓互不攻击是说任何两个皇后都要

满足：（1）不在棋盘的同一行；

（2）不在棋盘的同一列；

（3）不在棋盘的同一对角线上。因此可以推论出，棋盘共有8行，故至多有8个皇后，

即每一行有且仅有一个皇后。这8个皇后中的每一个

应该摆放在哪一列上是解该题的任务。………数据的定义（1）：

i——第i行（个）皇后，1i8；

j——第j列，1j8；

Queen[i]——第i行皇后所在的列；

Column[j]——第j列是否安全，{0,1}；

1234567812345678数据的定义（2）：

Down[-7..7]——记录每一条从上到下的对

角线，是否安全，{0,1}Up[2..16]——记录每一条从下到上的对角

角线，是否安全，{0,1}利用以上的数据定义：当我们需要在棋盘的(i,j)位置摆放一个皇后的时候，可以通过Column数组、Down

数组和Up数组的相应元素，来判断该位置是否安全；当我们已经在棋盘的(i,j)位置摆放了一个皇后以后，就应该去修改Column数组、Down数组和Up数组的相应元素，把相应的列和对角线设置为不安全。voidTryQueen(inti);intQueen[9]={0};intColumn[9]={0};intDown[15]={0};intUp[15]={0};voidmain(){TryQueen(1);}voidTryQueen(inti) //摆放第i行的皇后{intj,k;for(j=1;j<=8;j++) //尝试把该皇后放在每一列

{if(Column[j]||Down[i-j+7]||Up[i+j-2])continue;//失败

Queen[i]=j;//把该皇后放在第j列上

Column[j]=1;Down[i-j+7]=1;Up[i+j-2]=1;if(i==8) //已找到一种解决方案

{for(k=1;k<=8;k++)printf("%d",Queen[k]);printf("\n");}elseTryQueen(i+1); //摆放第i+1行的皇后

Queen[i]=0; //回溯，把该皇后从第j列拿起

Column[j]=0;Down[i-j+7]=0;Up[i+j-2]=0;

}}共92组解，部分答案如下：方案1：15863724方案2：16837425方案3：17468253方案4：17582463方案5：24683175方案6：25713864方案7：25741863方案8：26174835方案9：26831475方案10：27368514假设在棋盘上事先已经摆放了一个国王，位置为<X,Y>，即第X行第Y列，在摆放八个皇后时，要求皇后间不能互相攻击且不能被国王攻击。国王的攻击范围如下图所示：思考题：对题目做如下的修改先输入某一个皇后所在的位置<X,Y>，即第X行第Y列，在此情形下，如何摆放其余的7个皇后，要求找到所有解决方案。8.3.4

过河问题问题描述：

M条狼和N条狗（N≥M）渡船过河，从河西到河东。在每次航行中，该船最多能容纳2只动物，且最少需搭载1只动物。安全限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。请问：能否找到一种方案，使所有动物都能顺利过河。如果能，移动的步骤是什么？如何描述系统的当前状态？位置：河西岸、河东岸、河；对象：船、狼、狗。问题分析三元组（W、D、B）WolfDogBoat例如：(2,2,W)若M＝2、N＝2(2,2,W)(0,2,E)(1,2,W)(0,0,E)(2,0,W)(1,0,E)问题实质：在一个有向图中寻找一条路径；状态转换：如何从一个结点跳转到另一个结点；状态树？问题分析如何避免访问重复的结点？如何用简练的语句实现状态的转换？如何将5种情形归纳为同一种形式？技术难点#include<stdio.h>#defineMAX_M20#defineMAX_N20intM,N;structStatus{intW,D,B;}steps[1000];ints=0,num=0;intflags[MAX_M][MAX_N][2]={0};voidCrossRiver(intW,intD,intB);intIsValid(intw,intd,intb);voidmain(){scanf("%d%d",&M,&N);flags[M][N][0]=1;steps[0].W=M;steps[0].D=N;steps[0].B=0;s=1;CrossRiver(M,N,0);}voidCrossRiver(intW,intD,intB) {inti,j,f;intw,d,b;if(B==0)f=-1;elsef=1;for(j=1;j<=5;j++){switch(j){case1:w=W+f*1;d=D;break;case2:w=W+f*2;d=D;break;case3:d=D+f*1;w=W;break;case4:d=D+f*2;w=W;break;case5:w=W+f*1;d=D+f*1;break;}b=1-B;if(IsValid(w,d,b))

{flags[w][d][b]=1;steps[s].W=w;steps[s].D=d;steps[s].B=b;s++;if(w==0&&d==0&&b==1){num++;printf("Solutions%d:\n",num);for(i=0;i<s;i++)printf("%d%d%d\n",steps[i].W,steps[i].D,steps[i].B);}elseCrossRiver(w,d,b);flags[w][d][b]=0;s--;}}}intIsValid(intw,intd,intb){if(w<0||w>M)return0;if(d<0||d>N)return0;if(flags[w][d][b]==1)return0;if(d>0&&w>d)return0;if((N-d>0)&&(M-w>N-d))return0;return1;}22Solutions1:220021120101200001Solutions2:220021120101110001Solutions3:220111120101200001Solutions4:2201111201011100018.3.5

排列问题n个对象的一个排列，就是把这

n个不同的对象放在同一行上的一种安排。例如，对于三个对象

a,b,c，总共有6个排列：

abc acb bac bca cab cban个对象的排列个数就是

n!。如何生成排列？基于分治策略的递归算法：假设这n

个对象为1,2,3,…,n；对于前n-1个元素的每一个排列a1a2…an-1，1ai

n-1，通过在所有可能的位置上插入

数字n，来形成n

个所求的排列，即：

n

a1a2…an-1

a1n

a2…an-1

……

a1a2…n

an-1

a1

a2…an-1n例如：生成1,2,3的所有排列permutation(3)permutation(2)permutation(1)permutation(1)：1permutation(2)：21，12permutation(3)：321，231，213，

312，132，123基于回溯策略的递归算法：基本思路：每一个排列的长度为N，对这N个不同的位置，按照顺序逐一地枚举所有

可能出现的数字。定义一维数组NumFlag[N+1]用来记录1-N之间的每一个数字是否已被使用，1表示已使用，0表示尚未被使用，初始化皆为0；定义一维数组NumTaken[N+1]，用来记录每一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字，则相应的数组元素值为0。初始化时，所有元素值均为0；循环变量i表示第i个位置，j表示整数j，

i,j{1,2,…,N}。i=1[]i=2j=1

[1]j=1i=3j=2[12]j=3i=3[13]j=1j=2j=3[123]j=1j=2[132]j=3i=2j=2[2]i=3j=1[21]j=2j=3i=3[23]j=1j=2j=3[213]j=1[231]j=2j=3i=2j=3

[3]i=3j=1[31]j=3j=2i=3[32]j=1j=2[312]j=3j=1[321]j=2,3假定N=3#define N 3voidTryNumber(inti);intNumFlag[N+1]={0};intNumTaken[N+1]={0};main(){TryNumber(1);}voidTryNumber(inti) {intj,k;for(j=1