清华大学C语言教学课件(共16个PPT)第7个教学内容.ppt

《清华大学C语言教学课件(共16个PPT)第7个教学内容.ppt》由会员分享，可在线阅读，更多相关《清华大学C语言教学课件(共16个PPT)第7个教学内容.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、清华大学C语言教学课件(共16个PPT)第7个递递 归归 算算 法法 举举 例例青蛙过河青蛙过河2讨论问题讨论问题青蛙过河青蛙过河该题是该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：年全国青少年信息学奥林匹克的一道试题。叙述如下：一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，

2、用们将青蛙从小到大，用1，2，n编号。规定初始时这队青蛙编号。规定初始时这队青蛙只能趴在左岸的石头只能趴在左岸的石头L上，当然是一个落一个，小的落在大的上上，当然是一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有面。不允许大的在小的上面。在小溪中有S个石柱，有个石柱，有y片荷叶，片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱允许多只在其上。对于右岸的石柱R，与左岸的石

3、柱，与左岸的石柱L一样允许一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙多个青蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸的从左岸的L上跳走后就不允许再跳回来；同样，从左岸上跳走后就不允许再跳回来；同样，从左岸L上跳至上跳至右岸右岸R，或从溪中荷叶或溪中石柱跳至右岸，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许上的青蛙也不允许再离开。问在已知溪中有再离开。问在已知溪中有S根石柱和根石柱和y片荷叶的情况下，最多能跳片荷叶的情况下，最多能跳过多少只青蛙？过多少只青蛙？3这题看起来较难，但是如果我们认真分析，理出思路，就可化这题看起来较难，但是如果我们认真分析，理出

4、思路，就可化难为易。难为易。思路：思路：1 1、简化问题，探索规律。先从个别再到一般，要善于对多个、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。因素作分解，孤立出一个一个因素来分析，化难为易。2.2.定义函数定义函数 Jump(S,y)Jump(S,y)最多可跳过河的青蛙数最多可跳过河的青蛙数 其中：其中：S S 河中柱子数河中柱子数 y y 荷叶数荷叶数43.先看简单情况，河中无柱子：先看简单情况，河中无柱子：S=0，Jump(0,y)当当y=1时，时，Jump(0,1)=2；说明：河中有一片荷叶，可以过两只青蛙，起始时说明：河中有一片荷

5、叶，可以过两只青蛙，起始时L上有两上有两只青蛙，只青蛙，1#在在2#上面。上面。第一步：第一步：1#跳到荷叶上；跳到荷叶上；第二步：第二步：2#从从L直接跳至直接跳至R上；上；第三步：第三步：1#再从荷叶跳至再从荷叶跳至R上。上。如下图：如下图：5当当y=2时，时，Jump(0,2)=3；说明：河中有两片荷叶时，可以过说明：河中有两片荷叶时，可以过3只青蛙。起始时：只青蛙。起始时：1#，2#，3#3只青蛙落在只青蛙落在L上，上，第一步：第一步：1#从从L跳至叶跳至叶 1上，上，第二步：第二步：2#从从L跳至叶跳至叶 2上，上，第三步：第三步：3#从从L直接跳至直接跳至R上，上，第四步：第四步：

6、2#从叶从叶2跳至跳至R上，上，第五步：第五步：1#从叶从叶1跳至跳至R上，上，采用归纳法：采用归纳法：Jump(0,y)=y+1Jump(0,y)=y+1；意思是：在河中没有石柱的情意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数叶数，数目是荷叶数+1+1。6再看再看Jump(S,y)Jump(S,y)先看一个最简单情况：先看一个最简单情况：S=1，y=1。从图上看出需要从图上看出需要9 9步，跳过步，跳过4 4只青蛙。只青蛙。1#1#青蛙从青蛙从 L L Y Y；2#2#青蛙从青蛙从 L L S S；1#1#青蛙从青蛙从 Y Y S S；

7、3#3#青蛙从青蛙从 L L Y Y；4#4#青蛙从青蛙从 L L R R；3#3#青蛙从青蛙从 Y Y R R；1#1#青蛙从青蛙从 S S Y Y；2#2#青蛙从青蛙从 S S R R；1#1#青蛙从青蛙从 Y Y R R；7t tL LS SY YR RL4L4L3L3L2L2L1L1S2S2S1S1R4R4 R3R3 R2R2 R1R10 01 12 23 34 45 56 67 78 89 94 44 44 44 44 43 33 33 33 32 22 21 12 22 22 22 22 21 11 11 11 11 13 31 11 14 44 44 44 44 43 33 33

8、 33 32 22 21 1表一表一8 为了将过河过程描述得更清楚，我们给出了表为了将过河过程描述得更清楚，我们给出了表1 1。表中。表中L1 L2 L1 L2 L3 L4L3 L4表示左岸石柱上落在一起的青蛙的高度位置。表示左岸石柱上落在一起的青蛙的高度位置。L1 L1 在在最上面，最上面，L4 L4 在最下面的位置。引入这个信息就可比较容易在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理地看出对青蛙占位的约束条件。同理R1 R2 R3 R4R1 R2 R3 R4也是如此。也是如此。对水中石柱对水中石柱S S，也分成两个高度位置，也分成两个高度位置S1 S2S1 S2

9、。对荷叶。对荷叶Y Y无须分无须分层，因为它只允许一只青蛙落在其上。层，因为它只允许一只青蛙落在其上。t=0t=0为初始时刻，青为初始时刻，青蛙从小到大落在石柱蛙从小到大落在石柱L L上。上。t=1t=1为第一步：为第一步：1#1#从从L L跳至荷叶跳至荷叶Y Y上；上；L L上只剩上只剩2#3#4#2#3#4#。T=2 T=2 为第二步；为第二步；2#2#从从L L跳至石柱跳至石柱S S上，上，处在处在S2S2位置上，位置上，L L上只剩上只剩3#3#和和4#4#。T=3T=3为第三步，为第三步，1#1#从从Y Y跳至跳至S S，将，将Y Y清空。这时你看，清空。这时你看，S S上有上有1#

10、1#、2#2#，L L上有上有3#3#、4#4#，好，好象是原来在象是原来在L L上的上的4 4只青蛙，分成了上下两部分，上面的只青蛙，分成了上下两部分，上面的2 2只只通过荷叶通过荷叶y y转移到了转移到了S S上。这一过程是一分为二的过程。即上。这一过程是一分为二的过程。即将将L L上的一队青蛙，分解为两个队，每队各二只，且将上面上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了的二只转移到了S S上。这是我们可以考虑形成两个系统，一上。这是我们可以考虑形成两个系统，一个是个是L L，Y Y，R R系统，一个是系统，一个是S S，Y Y，R R系统。前者二只青蛙号系统。前者二只

11、青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。五步到第九步可以看出的确是这么做的。9对于对于LYRLYR系统，相当于系统，相当于Jump(0,1)Jump(0,1)对于对于SYRSYR系统，相当于系统，相当于Jump(0,1)Jump(0,1)两个系统之和为两个系统之和为2*Jump(0,1)2*Jump(0,1)，因此有：因此有：Jump(1,1)=2*Jump(0,1)=2*2=4Jump(1,1)=2*Jump(0,1)=2*2=4。现在再看现在再看S=2S=2，y=1 Jump(2,1)y=

12、1 Jump(2,1)我们将河中的两个石柱称作我们将河中的两个石柱称作S1S1和和S2S2，荷叶叫荷叶叫y y，考虑先将，考虑先将L L上的青蛙的一半上的青蛙的一半借助于借助于S2S2和和y y转移到转移到S1S1上，当然是一上，当然是一半小号的青蛙在半小号的青蛙在S1S1上，大的留在上，大的留在L L上。上。10这样这样 L S1 S2 y R 系统分解为系统分解为：（L S2 y R L S2 y R 系统）系统）+（S1 S2 y R S1 S2 y R 系统）系统）=2*=2*（L S2 y R L S2 y R 系统）系统）=2*Jump(1,1)=2*Jump(1,1)用归纳法用归

13、纳法Jump(S,y)=2*Jump(S-1,y)Jump(S,y)=2*Jump(S-1,y)115.将上述分析出来的规律写成递归形式的与或结点图为：将上述分析出来的规律写成递归形式的与或结点图为：12举例：S=3，y=4，算 Jump(3,4)13#include/预编译命令预编译命令int Jump(int,int);/声明有被调用函数声明有被调用函数void main()/主函数主函数/主程序开始主程序开始int s,y,sum;/整型变量整型变量,s为河中石柱数为河中石柱数,y为荷叶数为荷叶数printf(请输入石柱数请输入石柱数s=);/提示信息提示信息scanf(%d,&s);/

14、输入正整数输入正整数sprintf(请输入荷叶数请输入荷叶数y=);/提示信息提示信息scanf(%d,&y);/输入正整数输入正整数ysum=Jump(s,y);/Jump(s,y)为被调用函数为被调用函数printf(“Jump(%d,%d)=%dn,s,y,sum);/输出结果输出结果/主程序结束主程序结束/以下函数是被主程序调用的函数以下函数是被主程序调用的函数int Jump(int r,int z)/整型自定义函数整型自定义函数,r,z为形参为形参/自定义函数体开始自定义函数体开始int k;/整型变量整型变量if(r=0)/如果如果r为为0,则为直接可解结点则为直接可解结点,k=

15、z+1;/直接可解结点直接可解结点,k值为值为z+1else/如果不为如果不为1,则要调用则要调用Jump(r-1,z)k=2*Jump(r-1,z);/计算计算Jump(r-1,z)再乘以再乘以2赋给赋给kreturn(k);/将将k的值返回给的值返回给Jump(s,y)/自定义函数体结束自定义函数体结束14递递 归归 算算 法法 举举 例例快速排序快速排序15快速排序的思路：快速排序的思路：1 1、将待排序的数据放入数组、将待排序的数据放入数组a a中，下标从中，下标从l l到到r r；2 2、取、取alal放变量放变量k k中，通过由右、左两边对中，通过由右、左两边对k k的大小的大小的

16、比较，为的比较，为k k选择应该排定的位置。这时要将比选择应该排定的位置。这时要将比k k大大的数放右边，比的数放右边，比k k小的数放左边。当小的数放左边。当k k到达最终位置到达最终位置后，由后，由k k划分了左右两个集合。然后再用同样的思划分了左右两个集合。然后再用同样的思路处理左集合与右集合。路处理左集合与右集合。3 3、令、令sort(l,r)sort(l,r)为将数组元素从下标为为将数组元素从下标为l l到下标为到下标为r r的的r-l+1r-l+1个元素从小到大排序。个元素从小到大排序。16我们画出与或图来阐述快速排序的思路：我们画出与或图来阐述快速排序的思路：17分区处理：分区

17、处理：1 1、让、让k=alk=al2 2、将、将k k放在放在amam3 3、使、使al,al+1,am-1=amal,al+1,am-1=am4 4、使、使amam+1,am+2,aram=rl=r，则什么也不做。这是直接可解，则什么也不做。这是直接可解结点。结点。C C结点是在结点是在lrlr情况下情况下A A结点的解。结点的解。C C是一个与结点。要是一个与结点。要对对C C求解需分解为三步。依次为：求解需分解为三步。依次为：181 1、先解、先解D D结点，结点，D D结点是一个直接可解结点，功能是结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是进行所谓的分区

18、处理，规定这一步要做的事情是（1 1）将）将alal中的元素放到它应该在的位置上，比中的元素放到它应该在的位置上，比如如m m位置。这时位置。这时amamalal；（2 2）让下标从）让下标从l l到到m-1m-1的数组元素小于等于的数组元素小于等于amam；（3 3）让下标从）让下标从m+1m+1到到r r的数组元素大于的数组元素大于amam；比如比如a a数组中数组中al=5al=5，经分组处理后，经分组处理后，5 5送至送至a4a4。5 5到位后，其左边到位后，其左边a0a0a3a3的值都小于的值都小于5 5；其右边；其右边a5a6a5a6大于大于5 5。（见下图）（见下图）195 52

19、 26 61 17 73 34 4a0 01 12 23 34 45 56 6lr4 42 23 31 15 57 76 6a0 01 12 23 34 45 56 6m下标：下标：下标：下标：lm-1rm+1202 2、再解、再解E E结点，这时要处理的是结点，这时要处理的是a0a0a3a3；3 3、再解、再解F F结点，处理结点，处理a5a6a5a6。下面按照这种思路构思一个快速排序的程序框图。下面按照这种思路构思一个快速排序的程序框图。void sort(int array,int ll,int rr)void sort(int array,int ll,int rr)int l,r,i

20、,k;int l,r,i,k;2122下面举例说明排序过程下面举例说明排序过程图图1 1 a a数组中有数组中有7 7个元素待排序个元素待排序1 1 让让k=al=a0=5k=al=a0=55 52 26 61 17 73 34 40 01 12 23 34 45 56 6lr图图 15 5k232 2 进入直到型循环进入直到型循环执行（执行（1 1）ar=a6=4 ar=a6=4 不满足当循环条件，不满足当循环条件，r r不动。不动。执行（执行（2 2）lrlr，做两件事：，做两件事：al=aral=ar，即，即a0=a6=4a0=a6=4，l=l+1=0+1=1l=l+1=0+1=1，见，

21、见图图2 24 42 26 61 17 73 34 40 01 12 23 34 45 56 6lr图图 25 5k24执行（执行（3 3）图）图2 2中的中的a1ka1k6k满足当循环的条件，满足当循环的条件，r=r-1=6-1=5r=r-1=6-1=5见见图图5 5，之后退出当循环，因为，之后退出当循环，因为ar=3kar=3k4 42 26 61 17 73 36 60 01 12 23 34 45 56 6lr图图 55 5k27执行（执行（2 2）al=aral=ar，并让，并让l=l+1=3l=l+1=3，见，见图图6 6 4 42 23 31 17 73 36 60 01 12

22、23 34 45 56 6lr图图 65 5k28执行（执行（3 3）由于）由于a3=1ka3=1ka4=7k，退出循环。见，退出循环。见图图7 7 4 42 23 31 17 73 36 60 01 12 23 34 45 56 6lr图图 75 5k29执行（执行（4 4）ar=alar=al，a5=7a5=7。见。见图图8 8 这时仍然这时仍然lrlkar=7k，让，让r=r-1=4r=r-1=4。见。见图图9 94 42 23 31 17 77 76 60 01 12 23 34 45 56 6lr图图 95 5k31之后，之后，l=rl=r，退出直到型循环，做，退出直到型循环，做al

23、=kal=k，l=4l=4，a4=5a4=5，这是，这是5 5的最终位置，的最终位置，5 5将整个数据分成左右两将整个数据分成左右两个集合，见个集合，见图图1010。4 42 23 31 15 57 76 60 01 12 23 34 45 56 6lr图图 10左左右右5 5k32用上述思路去排左边的部分用上述思路去排左边的部分从从l=0l=0到到r=3r=3，见，见图图1111。让。让k=al=a0=4k=al=a0=4，然后进到直到，然后进到直到型循环，型循环，执行（执行（1 1）ar=1kar=1k，不满足当循环的条件，不满足当循环的条件，r r不动。不动。执行（执行（2 2）al=a

24、ral=ar，l=l+1=1,l=l+1=1,见见图图12121 12 23 31 10 01 12 23 3lr图图 124 42 23 31 10 01 12 23 3lr图图 114 4k33执行（执行（3 3）alkalk，l=l+1=2l=l+1=2，a2ka2k，l=l+1=3l=l+1=3，这时，这时l=rl=r，不会执行（，不会执行（4 4），同时退出直到型循环，见），同时退出直到型循环，见图图1313。然后做然后做al=kal=k，即，即a3=4a3=4，见图，见图1414，左边也排好了。，左边也排好了。1 12 23 34 40 01 12 23 3图图 141 12 23

25、 31 10 01 12 23 3lr图图 13lr4 4k4 4k344 4、用上述思路去排右边的部分，见、用上述思路去排右边的部分，见图图1515，让，让k=al=a5=7k=al=a5=7，进入直到型循环；，进入直到型循环；执行（执行（1 1）ar=6kar=6k，r r不动不动执行（执行（2 2）al=ar=6al=ar=6，l=l+1=5+1=6l=l+1=5+1=6，见，见图图1616图图 167 76 65 56 6lr图图 156 66 65 56 6lr7 7k35这时这时l=rl=r，不再执行（，不再执行（3 3）（）（4 4），退出直到型循环后，），退出直到型循环后，做做

26、al=kal=k，见图，见图1717。图图 176 67 75 56 6lr7 7k36在有了递归调用函数之后，主程序很容易写，主程序中应在有了递归调用函数之后，主程序很容易写，主程序中应包含包含1 1、定义整型变量：数组定义整型变量：数组a10a10，i i；2 2、用循环结构输入待排序的数，将其放入用循环结构输入待排序的数，将其放入a a数组；数组；3 3、调用调用sortsort函数，使用三个实际参数函数，使用三个实际参数aa将数组将数组a a当实参；当实参；00数组下标下界；数组下标下界；99数组下标上界；数组下标上界；4 4、输出排序结果输出排序结果下面给出参考程序（分两页）下面给出

27、参考程序（分两页）37#include /预编译命令预编译命令void sort(int array,int ll,int rr)/被调用函数，数组被调用函数，数组array，ll,rr为形参为形参 /函数体开始函数体开始 int l,r,i,k;/定义变量定义变量 if(llrr)/如果如果llrr,则做下列则做下列7件事件事:/7件事开始件事开始l=ll;r=rr;k=arrayl;/第第1件事件事do /第第2件事件事(开始开始)while(l=k)r=r-1;/2.1,右边的元素右边的元素=k,让让r往中间移往中间移if(lr)/2.2,右边的元素右边的元素k,让让 arrayl=ar

28、rayr;/arrayr送给送给arrayl，l=l+1;/同时让同时让l往中间移往中间移 while(lr)&(arrayl=k)l=l+1;/2.3,左边的元素左边的元素=k,让让l往中间移往中间移 if(lk,让让arrayl /送给送给arrayr /while(l!=r);/第第2件事件事(结束结束)arrayl=k;/第第3件事件事,k已排到位已排到位for(i=ll;i=rr;i=i+1)/第第4件事，输出件事，输出 printf(a%d=%d;,i,arrayi);/printf(n);/第第5件事，换行件事，换行sort(array,ll,l-1);/第第6件事，排左边部分件

29、事，排左边部分sort(array,l+1,rr);/第第7件事，排右边部分件事，排右边部分 /7件事结束件事结束 /函数体结束函数体结束38void main()/主函数开始主函数开始 int a10,i;/整型变量整型变量printf(请输入请输入10个整数个整数n);/提示信息提示信息for(i=0;i10;i=i+1)/输入输入10个整数个整数scanf(%d,&ai);/sort(a,0,9);/调用调用sort函数函数,实参为数组实参为数组a和和0，9printf(排序结果为排序结果为:);/提示信息提示信息for(i=0;i10;i=i+1)/printf(%d;,ai);/输出

30、排序结果输出排序结果printf(n);/主函数结束主函数结束 39递递 归归 算算 法法 举举 例例分书问题分书问题40教学目标：教学目标：巩固用递归思想编写程序巩固用递归思想编写程序教学内容：教学内容：分书问题分书问题题题 目：目：有编号分别为有编号分别为1 1，2 2，3 3，4 4，5 5的五本书，的五本书，准备分给准备分给A,B,C,D,EA,B,C,D,E五个人，每个人阅读兴趣用一五个人，每个人阅读兴趣用一个二维数组加以描述：个二维数组加以描述：41希望你写一个程序，输出所有分书方案，让人人皆希望你写一个程序，输出所有分书方案，让人人皆大欢喜。假定大欢喜。假定5 5个人对个人对5

31、5本书的阅读兴趣如下表：本书的阅读兴趣如下表：0 1 2 3 4ABCDE0 00 01 11 10 01 11 10 00 01 10 01 11 10 01 10 00 00 01 10 00 01 10 00 01 1人人书书421 1、定义一个整型的二维数组，将表中的阅读喜好用、定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组。可定义初始化方法赋给这个二维数组。可定义int like55=0,0,1,1,0,1,1,0,0,1,int like55=0,0,1,1,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,00,1,0,0,1;0,1,1,0,1,

32、0,0,0,1,00,1,0,0,1;2 2、定义一个整型一维数组、定义一个整型一维数组book5book5用来记录书是否用来记录书是否已被选用。用下标作为五本书的标号，被选过元已被选用。用下标作为五本书的标号，被选过元素值为素值为1 1，未被选过元素值为，未被选过元素值为0 0，初始化皆置，初始化皆置0 0。Int book5=0,0,0,0,0;Int book5=0,0,0,0,0;解题思路：解题思路：433 3、画出思路图、画出思路图定义定义 try(i)try(i)试着给第试着给第i i人分书人分书(i=0,1,4)(i=0,1,4)4445说明：说明：（1 1）试着给第）试着给第i

33、 i个人分书，先试分个人分书，先试分0 0号书，再分号书，再分1 1号书，分号书，分2 2号书号书，因此有一个与结点，让，因此有一个与结点，让j=0,1,2,3,4j=0,1,2,3,4。j j表示书。表示书。（2 2）LPLP为循环结构的循环体。为循环结构的循环体。（3 3）条件）条件C C是由两部分是由两部分“与与”起来的。起来的。“第第i i个人个人喜欢喜欢j j书，且书，且j j书尚未被分走书尚未被分走”。满足这个条件。满足这个条件是是i i人能够得到人能够得到j j书的条件。书的条件。（4 4）如果不满足）如果不满足C C条件，则什么也不做，这是直条件，则什么也不做，这是直接可解结点

34、。接可解结点。46（5 5）满足）满足C C条件，做三件事。条件，做三件事。sh1sh1第一件事：将第一件事：将j j书分给书分给i i，用一个数组，用一个数组takei=jtakei=j，记，记住书住书j j给了给了i i人，同时记录人，同时记录j j书已被选用，书已被选用，booki=1booki=1。sh2sh2第二件事：查看第二件事：查看i i是否为是否为4 4，如果不为，如果不为4 4，表示尚未将，表示尚未将所有所有5 5个人所要的书分完，这时应递归再试下一人，个人所要的书分完，这时应递归再试下一人，即即try(i+1)try(i+1)。如果。如果i=4i=4，则应先使方案数，则应先

35、使方案数n=n+1n=n+1，然，然后输出第后输出第n n个方案下的每个人所得之书。个方案下的每个人所得之书。Sh3Sh3第三件事：回溯。让第第三件事：回溯。让第i i人退回人退回j j书，恢复书，恢复j j书尚未被书尚未被选的标志，即选的标志，即takei=-1takei=-1和和bookj=0bookj=0。这是在已输。这是在已输出第出第n n个方案之后，去寻找下一个分书方案所必需的。个方案之后，去寻找下一个分书方案所必需的。（6 6）在有了上述的与或图之后，我们很容易写出一个程）在有了上述的与或图之后，我们很容易写出一个程序框图。先看被调用函数序框图。先看被调用函数try(i)try(i

36、)的框图。的框图。4748#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;/整型变量整型变量,定义数组，初始化定义数组，初始化下面讨论主程序应该做的事情下面讨论主程序应该做的事情1 1、将分书方案号预置、将分书方案号预置0 02 2、从第、从第0 0号人（号人（A A）开始试分书，调用）开始试分书，调用try(0)try(0)参考程序如下所示参考程序

37、如下所示（分三页）：（分三页）：49void try(int i)/被调用函数，数组被调用函数，数组array，ll,rr为形参为形参/函数体开始函数体开始int j,k;/定义变量定义变量for(j=0;j0)&(bookj=0)/如果满足分书条件作下列事如果满足分书条件作下列事 takei=j;/把把j号书给号书给i bookj=1;/记录记录j书已分书已分if(i=4)/如果如果i=4,输出分书方案输出分书方案 n=n+1;/让方案数加让方案数加1printf(第第%d个方案个方案n,n);/输出分书方案号输出分书方案号for(k=0;k=4;k=k+1)printf(%d号书分给号书分

38、给%c;n,takek,k+65);/输出分书方案输出分书方案printf(n);/换行换行else/如果如果i!=4,继续给下一人分书继续给下一人分书 try(i+1);/递归调用递归调用try(i+1)takei=-1;/让让i把书退还把书退还bookj=0;/记录记录j书待分书待分/50void main()/主函数主函数/主函数开始主函数开始 n=0;/分书方案号预置分书方案号预置0try(0);/调用调用try函数函数,实参为实参为1/主函数结束主函数结束 51结结 束束52此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢