搜索与回溯算法C学习教案.pptx

《搜索与回溯算法C学习教案.pptx》由会员分享，可在线阅读，更多相关《搜索与回溯算法C学习教案.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1搜索搜索(susu)与回溯算法与回溯算法C第一页，共45页。递归回溯法算法框架递归回溯法算法框架 一一intSearch(intk)for(i=1;i=算符种数算符种数;i+)if(满足条件满足条件)保存结果保存结果(jigu)if(到目的地到目的地)输出解输出解;elseSearch(k+1);恢复：保存结果恢复：保存结果(jigu)之前的状态之前的状态回溯一步回溯一步递归回溯法算法框架递归回溯法算法框架 二二intSearch(intk)if(到目的地到目的地)输出解输出解;elsefor(i=1;i=算符种数算符种数;i+)if(满足条件满足条件)保存结果保存结果(jigu);S

2、earch(k+1);恢复：保存结果恢复：保存结果(jigu)之前的状态之前的状态回溯一步回溯一步第2页/共45页第二页，共45页。【例【例1】素数环】素数环:从从1到到20这这20个数摆成一个环，要求相邻的两个数的和是一个素个数摆成一个环，要求相邻的两个数的和是一个素数。数。【算法分析】【算法分析】非常明显，这是一道回溯的题目。从非常明显，这是一道回溯的题目。从1开始，每个空位有开始，每个空位有20种可能，只要填进去种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还个数还要判断和第要判断和第1个

3、数的和是否个数的和是否(shfu)素数。素数。【算法流程】【算法流程】1、数据初始化；、数据初始化；2、递归填数：判断第、递归填数：判断第i个数填入是否个数填入是否(shfu)合法；合法；A、如果合法：填数；判断是否、如果合法：填数；判断是否(shfu)到达目标（到达目标（20个已填完）：是，打印结个已填完）：是，打印结果；不是，递归填下一个；果；不是，递归填下一个；B、如果不合法：选择下一种可能；、如果不合法：选择下一种可能；【参考程序】【参考程序】#include#include#include#includeusingnamespacestd;boolb21=0;inttotal=0,a

4、21=0;intsearch(int);/回溯过程回溯过程intprint();/输出方案输出方案boolpd(int,int);/判断素数判断素数第3页/共45页第三页，共45页。intmain()search(1);couttotalendl;/输出总方案数输出总方案数system(pause);intsearch(intt)inti;for(i=1;i=20;i+)/有有20个数可选个数可选if(pd(at-1,i)&(!bi)/判断与前一个判断与前一个(y)数是否构成素数及该数是否可用数是否构成素数及该数是否可用at=i;bi=1;if(t=20)if(pd(a20,a1)print(

5、);elsesearch(t+1);bi=0;intprint()total+;couttotal;for(intj=1;j=20;j+)coutaj;coutendl;boolpd(intx,inty)intk=2,i=x+y;while(ksqrt(i)return1;elsereturn0;第4页/共45页第四页，共45页。【例【例2】设有】设有n个整数的集合个整数的集合1,2,n，从中取出任意，从中取出任意(rny)r个数进行排列个数进行排列（rn），试列出所有的排列。），试列出所有的排列。#include#include#includeusingnamespacestd;intnum

6、=0,a10001=0,n,r;boolb10001=0;intsearch(int);/回溯过程回溯过程intprint();/输出方案输出方案intmain()coutnr;search(1);coutnumber=numendl;/输出方案总数输出方案总数第5页/共45页第五页，共45页。int search(int k)int i;for(i=1;i=n;i+)if (!bi)/判断i是否(sh fu)可用 ak=i;/保存结果 bi=1;if(k=r)print();else search(k+1);bi=0;int print()num+;for(int i=1;i=r;i+)co

7、utsetw(3)ai;coutendl;第6页/共45页第六页，共45页。【例【例3】任何一个】任何一个(y)大于大于1的自然数的自然数n，总可以拆分成若干个小，总可以拆分成若干个小于于n的自然数之和。的自然数之和。当当n=7共共14种拆分方法：种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14第7页/共45页第七页，共45页。【参考程序】【参考程序】#include#incl

8、ude#includeusingnamespacestd;inta10001=1,n,total;intsearch(int,int);intprint(int);intmain()cinn;search(n,1);/将要拆分的数将要拆分的数n传递给传递给scouttotal=totalendl;/输出输出(shch)拆分的方案数拆分的方案数system(pause);intsearch(ints,intt)inti;for(i=at-1;i=s;i+)if(i0时，继续递归 s+=i;/回溯：加上拆分的数，以便产分所有可能的拆分 int print(int t)coutn=;for(int

9、i=1;i=t-1;i+)/输出一种拆分方案 coutai+;coutatendl;total+;/方案数累加1第8页/共45页第八页，共45页。【例【例4】八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后】八皇后问题：要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子棋子(qz)。）。）放置第个放置第个(行行)皇后的算法为：皇后的算法为：intsearch(i)；intj;for(第第i个皇后的位置个皇后的位置j=1;j=8;j+)/在本行的在本行的8列中去试列中

10、去试if(本行本列允许放置皇后本行本列允许放置皇后)放置第放置第i个皇后；个皇后；对放置皇后的位置进行标记；对放置皇后的位置进行标记；if(i=8)输出输出/已经放完个皇后已经放完个皇后elsesearch(i+1)；/放置第放置第i+1个皇后个皇后对放置皇后的位置释放标记，尝试下一个位置是否可行；对放置皇后的位置释放标记，尝试下一个位置是否可行；第9页/共45页第九页，共45页。【算法分析【算法分析(fnx)】显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则

11、行号相同；如果在同一列上，则列可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在号相同；如果同在斜线上的行列值之和相同；如果同在斜线上的行列值之和相同；如果同在斜线上的行列值之差相斜线上的行列值之差相同；从下图可验证：同；从下图可验证：考虑每行有且仅有一个皇后，设一维数组1.8表示皇后的放置(fngzh)：第行皇后放在第列，用ij来表示，即下标是行数，内容是列数。例如：A3=5就表示第3个皇后在第3行第5列上。第10页/共45页第十页，共45页。判断皇后是否(sh fu)安全，即检查同一列、同一对角线是否(sh fu)已有皇后，建立标志数组1.8控制同一

12、列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组1.16、-7.7控制同一对角线上只能有一个皇后。如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下，要表示两个皇后I和J不在同一列或斜线上的条件可以描述为：AIAJ AND ABS(I-J)ABS(AI-AJ)I和J分别表示两个皇后的行号【参考程序】#include#include#include#includeusing namespace std;bool d100=0,b100=0,c100=0;int sum=0,a100;int search(in

13、t);int print();int main()search(1);/从第1个皇后开始放置 system(pause);第11页/共45页第十一页，共45页。int search(int i)int j;for(j=1;j=8;j+)/每个皇后都有8位置(列)可以试放if(!bj)&(!ci+j)&(!di-j+7)/寻找放置皇后的位置 /由于C+不能操作负数组，因此考虑(kol)加7 /放置皇后,建立相应标志值 ai=j;/摆放皇后 bj=1;/宣布占领第j列 ci+j=1;/占领两个对角线 di-j+7=1;if(i=8)print();/个皇后都放置好,输出 else search(i

14、+1);/继续递归放置下一个皇后 bj=0;/递归返回即为回溯一步,当前皇后退出 ci+j=0;di-j+7=0;int print()int i;sum+;/方案数累加1 coutsum=sumendl;for(i=1;i=8;i+)/输出一种方案 coutsetw(4)ai;cout2,1-3,3-1,4-3,5-2,7-4,8【算法分析】【算法分析】如图如图4（b）,马最多有四个方向，若原来的横坐标为马最多有四个方向，若原来的横坐标为j、纵坐标为、纵坐标为i,则四个方则四个方向的移动可表示为：向的移动可表示为：1:（i,j）（i+2,j+1）；）；(i3,j8)2:（i,j）（i+1,j

15、+2）；）；(i4,j0,j1,j8)搜索搜索(susu)策略：策略：S1:=(0,0);S2:从从1出发，按移动规则依次选定某个方向，如果达到的是（出发，按移动规则依次选定某个方向，如果达到的是（4,8）则）则转向转向S3,否则继续搜索否则继续搜索(susu)下一个到达的顶点；下一个到达的顶点；S3:打印路径。打印路径。第13页/共45页第十三页，共45页。【参考程序】【参考程序】#include#include#includeusingnamespacestd;inta100100,t=0;/路径总数和路径路径总数和路径intx4=2,1,-1,-2,/四种移动规则四种移动规则y4=1,2

16、,2,1;intsearch(int);/搜索搜索(susu)intprint(int);/打印打印intmain()/主程序主程序a11=0;a12=0;/从坐标从坐标(0,0)开始往右跳第二步开始往右跳第二步search(2);system(pause);第14页/共45页第十四页，共45页。int search(int i)for(int j=0;j=0&ai-11+xj=0&ai-12+yj=8)/判断马不越界 ai1=ai-11+xj;/保存当前(dngqin)马的位置 ai2=ai-12+yj;if(ai1=4&ai2=8)print(i);else search(i+1);/搜索

17、下一步 int print(int ii)t+;coutt:;for(int i=1;i=ii-1;i+)coutai1,ai2;cout4,8endl;第15页/共45页第十五页，共45页。【例【例6】设有】设有A，B，C，D，E五人从事五人从事J1，J2，J3，J4，J5五项工作，每人只五项工作，每人只能能(zhnn)从事一项，他们的效益如下。从事一项，他们的效益如下。每人选择五项工作中的一项，在各种选择的组合中，找到效益(xioy)最高的的一种组合输出。【算法分析】【算法分析】用数组储存工作选择用数组储存工作选择(xunz)的方案；数组存放最优的工作选择的方案；数组存放最优的工作选择(x

18、unz)方案；数组用于表示某项工作有没有被选择方案；数组用于表示某项工作有没有被选择(xunz)了。了。(1)选择选择(xunz)(i)=0的第的第i项工作；项工作；(2)判断效益是否高于判断效益是否高于max已记录的效益，若高于则更新数组及已记录的效益，若高于则更新数组及max的值。的值。搜索策略搜索策略:回溯法（深度优先搜索回溯法（深度优先搜索dfs）。）。第16页/共45页第十六页，共45页。【参考程序】【参考程序】#include#include#include#includeusingnamespacestd;intdata66=0,0,0,0,0,0,0,13,11,10,4,7,

19、0,13,10,10,8,5,0,5,9,7,7,4,0,15,12,10,11,5,0,10,11,8,8,4;intmax1=0,g10,f10;boolp6=0;intgo(intstep,intt)/step是第几个人，是第几个人，t是之前已得的效益是之前已得的效益for(inti=1;i=5;i+)if(!pi)/判断判断(pndun)第第i项工作没人选择项工作没人选择fstep=i;/第第step个人，就选第个人，就选第i项工作项工作pi=1;/标记第标记第i项工作被人安排了项工作被人安排了t+=datastepi;/计算效益值计算效益值if(stepmax1)/保存最佳效益值保存

20、最佳效益值max1=t;for(intj=1;j=5;j+)gj=fj;/保存最优效益下的工作选择方案保存最优效益下的工作选择方案t-=datastepi;/回溯回溯pi=0;第17页/共45页第十七页，共45页。intmain()go(1,0);/从第从第1个人个人(grn)，总效益为，总效益为0开始开始for(inti=1;i=5;i+)coutchar(64+i):Jgisetw(3);/输出各项工作安排情输出各项工作安排情况况coutendl;coutsupply:max1endl;/输出最佳效益值输出最佳效益值第18页/共45页第十八页，共45页。【例【例7】选书】选书学校放寒假时，

21、信息学竞赛辅导老师有学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培五本书，要分给参加培训训(pixn)的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。【算法分析】【算法分析】可用穷举法，先不考虑可用穷举法，先不考虑(kol)“每人

22、都满意每人都满意”这一条件，这样只剩这一条件，这样只剩“每人选一每人选一本且只能选一本本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有共有5！=120种。然后在种。然后在120种可行解中一一删去不符合种可行解中一一删去不符合“每人都满意每人都满意”的解，留下的解，留下的就是本题的解答。的就是本题的解答。为了编程方便，设为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如是五本书的一种分发。例如54321就表示第就表示第5本书（

23、即本书（即E）分给张，第）分给张，第4本书（即本书（即D）分给王，分给王，第，第1本书（即本书（即A）分给李。）分给李。“喜爱书表喜爱书表”可以用二维数组来表示，可以用二维数组来表示，1表表示喜爱，示喜爱，0表示不喜爱。表示不喜爱。第19页/共45页第十九页，共45页。算法设计：S1：产生5个数字的一个全排列；S2：检查是否符合“喜爱(x i)书表”的条件，如果符合就打印出来；S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1；S4：结束。int Search(i)for(j=1;j=5;j+)if(第i个同学分给第j本书符合条件)记录(jl)第i个数 if(i=5)打印一个解;el

24、se Search(i+1);删去第i 个数 上述算法有可以改进(gijn)的地方。比如产生了一个全排列 12345，从表中可以看出，选第一本书即给张同学的书，1是不可能的，因为张只喜欢第 3、4本书。这就是说，1一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不必选了，这样就减少了运算量。换句话说，第一个数字只在3、4中选择，这样就可以减少 3/5的运算量。同理，选定了第一个数字后，也不应该把其他 4个数字一次选定，而是选择了第二个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，

25、就应另选第二个数。这样就把 34一类的分法在产生前就删去了。又减少了一部分运算量。综上所述，改进后的算法应该是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的，所以可以用回溯算法。算法设计如下：第20页/共45页第二十页，共45页。【参考程序】【参考程序】#include#include#includeusingnamespacestd;intbook6,c;boolflag6,like66=0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,0,0,1,1,0,0,0,0

26、,0,0,1,0,0,0,1,0,0,1;intsearch(int);intprint();intmain()for(inti=1;i=5;i+)flagi=1;search(1);/从第从第1个开始选书，递归。个开始选书，递归。system(pause);intsearch(inti)/递归函数递归函数for(intj=1;j=5;j+)/每个人都有每个人都有5本书可选本书可选if(flagj&likeij)/满足满足(mnz)分书的条件分书的条件flagj=0;/把被选中的书放入集合把被选中的书放入集合flag中，避免重复被选中，避免重复被选booki=j;/保存第保存第i个人选中的第个

27、人选中的第j本书本书if(i=5)print();/i=5时，所有的人都分到书，输出结果时，所有的人都分到书，输出结果elsesearch(i+1);/i5时，继续递归分书时，继续递归分书flagj=1;/回溯：把选中的书放回，产生其他分书的方案回溯：把选中的书放回，产生其他分书的方案booki=0;第21页/共45页第二十一页，共45页。int print()c+;/方案数累加1 cout answer c:n;for(int i=1;i=5;i+)cout i:char(64+booki)endl;/输出分书(fn sh)的方案输出结果：zhang:Cwang:Aliu:Bsun:Dli:

28、E第22页/共45页第二十二页，共45页。【例【例8】跳马问题。在】跳马问题。在5*5格的棋盘上，有一只中国象棋的马，从（格的棋盘上，有一只中国象棋的马，从（1,1）点出发，按日字跳）点出发，按日字跳马，它可以马，它可以(ky)朝朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋个方向跳，但不允许出界或跳到已跳过的格子上，要求在跳遍整个棋盘。盘。输出前输出前5个方案及总方案数。个方案及总方案数。输出格式示例：输出格式示例：11621102520112415221721969127423143181385#include#include#include#includeusingna

29、mespacestd;intu8=1,2,2,1,-1,-2,-2,-1,/8个方向上的个方向上的x,y增量增量v8=-2,-1,1,2,2,1,-1,-2;inta100100=0,num=0;/记每一步走在棋盘的哪一格和棋盘的每一格有记每一步走在棋盘的哪一格和棋盘的每一格有/没有被走过没有被走过boolb100100=0;intsearch(int,int,int);/以每一格为阶段，在每一阶段中试遍以每一格为阶段，在每一阶段中试遍8个方向个方向intprint();/打印方案打印方案第23页/共45页第二十三页，共45页。int main()a11=1;b11=1;/从(1,1)第一步开

30、始走 search(1,1,2);/从(1,1)开始搜第2步该怎样走 coutnum25)print();return 0;/达到最大规模打印、统计方案 for(k=0;k=7;k+)/试遍8个方向 x=i+uk;y=j+vk;/走此方向，得到的新坐标 if(x=1&y=1&(!bxy)/如果新坐标在棋盘上，并且这一格可以走 bxy=1;axy=n;search(x,y,n+1);/从(x,y)去搜下一步该如何走 bxy=0;axy=0;第24页/共45页第二十四页，共45页。int print()num+;/统计(tngj)总方案 if(num=5)/打印出前5种方案 for(int k=1

31、;k=5;k+)/打印本次方案 for(int kk=1;kk=5;kk+)coutsetw(5)akkk;coutendl;第25页/共45页第二十五页，共45页。【例【例【例【例9 9】数的划分】数的划分】数的划分】数的划分(NOIP2001)(NOIP2001)【问题描述】【问题描述】【问题描述】【问题描述】将整数将整数将整数将整数n n分成分成分成分成k k份，且每份不能为空，任意两种分法不能相同份，且每份不能为空，任意两种分法不能相同份，且每份不能为空，任意两种分法不能相同份，且每份不能为空，任意两种分法不能相同(不不不不考虑顺序考虑顺序考虑顺序考虑顺序)。例如。例如。例如。例如:n

32、=7,k=3,:n=7,k=3,下面三种分法被认为下面三种分法被认为下面三种分法被认为下面三种分法被认为(rnwi)(rnwi)是相同是相同是相同是相同的。的。的。的。1 1，1 1，5 5；1 1，5 5，1 1；5 5，1 1，1 1；问有多少种不同的分法。问有多少种不同的分法。问有多少种不同的分法。问有多少种不同的分法。【输入格式】【输入格式】【输入格式】【输入格式】n,k (6n200 n,k (6n200，2k6)2k6)【输出格式】【输出格式】【输出格式】【输出格式】一个整数，即不同的分法。一个整数，即不同的分法。一个整数，即不同的分法。一个整数，即不同的分法。【输入样例】【输入样

33、例】【输入样例】【输入样例】7 3 7 3【输出样例】【输出样例】【输出样例】【输出样例】4 4 4 4种分法为：种分法为：种分法为：种分法为：1,1,51,1,5；1,2,41,2,4；1,3,3;2,2,3 1,3,3;2,2,3 说明部分不必输出说明部分不必输出说明部分不必输出说明部分不必输出 第26页/共45页第二十六页，共45页。【算法分析【算法分析【算法分析【算法分析(fnx)(fnx)】方法方法方法方法1 1、回溯法，超时，参考程序如下。、回溯法，超时，参考程序如下。、回溯法，超时，参考程序如下。、回溯法，超时，参考程序如下。#include#include#include#in

34、clude#include#includeusing namespace std;using namespace std;int n,i,j,k,rest,sum,total;int n,i,j,k,rest,sum,total;int s7;int s7;int main()int main()cout Input n k;cout n k;cin n k;total=0;s1=0;total=0;s1=0;i=1;i=1;while(i)while(i)si+;si+;if(si n)i-;if(si n)i-;else if(i=k)else if(i=k)sum=0;sum=0;for

35、(j=1;j=k;j+)sum+=sj;for(j=1;j=k;j+)sum+=sj;if(n=sum)total+;if(n=sum)total+;else else rest-=si;rest-=si;i+;i+;si=si-1-1;si=si-1-1;cout total;cout total;system(pause);system(pause);return 0;return 0;第27页/共45页第二十七页，共45页。n n方法方法方法方法2 2、递归，参考程序、递归，参考程序、递归，参考程序、递归，参考程序(chngx)(chngx)如下。如下。如下。如下。n n#include

36、#includen n#include#includen n#include#includen nusing namespace std;using namespace std;n nint n,k;int n,k;n nint f(int a,int b,int c)int f(int a,int b,int c)n n n n int g=0,i;int g=0,i;n n if(b=1)g=1;if(b=1)g=1;n n else for(i=c;i=a/b;i+)else for(i=c;i=a/b;i+)n n g+=f(a-i,b-1,i);g+=f(a-i,b-1,i);n n

37、 return g;return g;n n n nint main()int main()n n n n cout Input n,k:;cout n k;cin n k;n n cout f(n,k,1);cout f(n,k,1);n n system(pause);system(pause);n n return 0;return 0;n n 第28页/共45页第二十八页，共45页。n n方法方法方法方法(fngf(fngf)3)3、用动态循环穷举所有不同的分解，要注意剪枝，参考程序如下。、用动态循环穷举所有不同的分解，要注意剪枝，参考程序如下。、用动态循环穷举所有不同的分解，要注意剪

38、枝，参考程序如下。、用动态循环穷举所有不同的分解，要注意剪枝，参考程序如下。n n#include#includen n#include#includen n#include#includen nusing namespace std;using namespace std;n nint n,k,total;int n,k,total;n nint min(int x,int y)int min(int x,int y)n n n n if(x y)return x;if(x=rest/dep;i-)else for(i=min(rest-dep+1,last);i=rest/dep;i-)n

39、 n select(dep-1,rest-i,i);select(dep-1,rest-i,i);n n n nint main()int main()n n n n cout Input n,k:;cout n k;cin n k;n n total=0;total=0;n n select(k,n,n);select(k,n,n);n n cout total;cout total;n n system(pause);system(pause);n n return 0;return 0;n n 第29页/共45页第二十九页，共45页。n n方法方法方法方法4 4、递推法、递推法、递推法、

40、递推法n n首先将正整数首先将正整数首先将正整数首先将正整数n n分解成分解成分解成分解成k k个正整数之和的不同分解方案总数等个正整数之和的不同分解方案总数等个正整数之和的不同分解方案总数等个正整数之和的不同分解方案总数等于将正整数于将正整数于将正整数于将正整数n-kn-k分解成任意分解成任意分解成任意分解成任意(rny)(rny)个不大于个不大于个不大于个不大于k k的正整数之和的的正整数之和的的正整数之和的的正整数之和的不同分解方案总数不同分解方案总数不同分解方案总数不同分解方案总数(可用可用可用可用ferrorferror图证明之图证明之图证明之图证明之),),后者的递推公式不难后者的

41、递推公式不难后者的递推公式不难后者的递推公式不难得到得到得到得到,参考程序如下。参考程序如下。参考程序如下。参考程序如下。n n#include#includen n#include#includen n#include#includen n#include#includen nusing namespace std;using namespace std;n nint i,j,k,n,x;int i,j,k,n,x;n nint p2017;int p2017;n nint main()int main()n n n n cin n k;cin n k;n n memset(p,0,size

42、of(p);memset(p,0,sizeof(p);n n p00=1;p00=1;n n for(i=1;i=n;i+)pi1=1;for(i=1;i=n;i+)pi1=1;n n for(i=1;i=n-k;i+)for(i=1;i=n-k;i+)n n for(j=2;j=min(i,k);j+)for(j=2;j=min(i,k);j+)n n for(x=1;x=min(i,j);x+)for(x=1;x=min(i,j);x+)n n pij+=pi-xmin(i-x,x);pij+=pi-xmin(i-x,x);n n cout pn-kk;cout pn-kk;n n sys

43、tem(pause);system(pause);n n return 0;return 0;n n 第30页/共45页第三十页，共45页。【课堂练习课堂练习】1、输出自然数1到n所有不重复(chngf)的排列，即n的全排列。【参考过程】int Search(int i)Int j;for(j=1;j=n;j+)if(bj)ai=j;bj=false;if(In)Search(i+1);else print();bj=true;第31页/共45页第三十一页，共45页。2、找出n个自然数(1,2,3,n)中r个数的组合。例如，当n=,r=3时，所有组合为：1 2 31 2 41 2 51 3 4

44、1 3 51 4 52 3 42 3 52 4 53 4 5total=10 /组合的总数【分析】：设在b1,b2,bi-1中已固定地取了某一组值且bi-1=k的前提下，过程Search(i,k)能够列出所有可能的组合。由于此时bi只能取k+1至n-r+i，对j=k+1,k+2,n-r+i，使bi:=j，再调用过程Search(i+1,j)，形成递归调用。直至i的值大于r时，就可以(ky)在b中构成一种组合并输出。第32页/共45页第三十二页，共45页。3、输出字母a、b、c、d，4个元素全排列的每一种排列。4、显示从前m个大写英文字母中取n个不同字母的所有种排列。5、有A、B、C、D、E五本

45、书，要分给张、王、刘、赵、钱五位同学(tng xu)，每人只能选一本，事先让每人把自已喜爱的书填于下表，编程找出让每人都满意的所有方案。【答案(d n)】四种方案张 王 刘 赵 钱 C A B D E D A C B E D B C A E D E C A B第33页/共45页第三十三页，共45页。6、有红球4个，白球3个，黄球3个，将它们排成一排共有多少种排法？【分析】：可以用回溯法来生成所有的排法。用数组b1.3表示尚未排列的这3种颜色球的个数。设共有I-1个球已参加(cnji)排列，用子程序Search(i)生成由第I个位置开始的以后n-I+1位置上的各种排列。对于第I个位置，我们对3种

46、颜色的球逐一试探，看每种颜色是否还有未加入排序的球。若有，则选取一个放在第I个位置上，且将这种球所剩的个数减1，然后调用Search(I+1),直至形成一种排列后出。对第I个位置上的所有颜色全部试探完后，则回溯至前一位置。第34页/共45页第三十四页，共45页。【上机练习【上机练习【上机练习【上机练习(linx)(linx)】1、全排列问题、全排列问题(Form.cpp)【问题描述】【问题描述】输出自然数输出自然数1到到n所有不重复的排列，即所有不重复的排列，即n的全排列，要求所产生的全排列，要求所产生(chnshng)的任一数字序列中不允许出现重复的数字。的任一数字序列中不允许出现重复的数字

47、。【输入格式】【输入格式】n(1n9)【输出格式】【输出格式】由由1n组成的所有不重复的数字序列，每行一个序列。组成的所有不重复的数字序列，每行一个序列。【输入样例】【输入样例】Form.in3【输出样例】【输出样例】Form.out123132213231312321第35页/共45页第三十五页，共45页。2、组合的输出、组合的输出(Compages.cpp)【问题描述】【问题描述】排列与组合是常用的数学方法，其中组合就是从排列与组合是常用的数学方法，其中组合就是从n个元素中抽出个元素中抽出r个元素个元素(不不分顺序且分顺序且rn)，我们可以简单地将，我们可以简单地将n个元素理解为自然数个元

48、素理解为自然数1，2，n，从中，从中任取任取r个数。个数。现要求现要求(yoqi)你用递归的方法输出所有组合。你用递归的方法输出所有组合。例如例如n5，r3，所有组合为：，所有组合为：l23l24125l34l35145234235245345【输入】【输入】一行两个自然数一行两个自然数n、r(1n21，1rn)。【输出】【输出】所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。元素占三个字符的位置，所有的组合也按字典顺序。【样例】【样例】compages.incom

49、pages.out53123124125134135145234235245345第36页/共45页第三十六页，共45页。3、N皇后问题皇后问题(Queen.cpp)【问题描述】【问题描述】在在N*N的棋盘上放置的棋盘上放置N个皇后（个皇后（n=10）而彼此不受攻击（即在棋盘的任一行）而彼此不受攻击（即在棋盘的任一行(yxng)，任一列和任一对角线上不能放置，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。个皇后），编程求解所有的摆放方法。八皇后(hunghu)的两组解【输入格式】【输入格式】输入：输入：n【输出格式】【输出格式】每行输出一种方案，每种方案顺序输出皇后每行输出一

50、种方案，每种方案顺序输出皇后(hunghu)所在的列号，各个数之间有空格隔开。若无方案，则输出所在的列号，各个数之间有空格隔开。若无方案，则输出nosolute!【输入样例】【输入样例】Queen.in4【输出样例】【输出样例】Queen.out24133142第37页/共45页第三十七页，共45页。4、有重复、有重复(chngf)元素的排列问题元素的排列问题【问题描述】【问题描述】设设R=r1,r2,rn是要进行排列的是要进行排列的n个元素。其中元素个元素。其中元素r1,r2,rn可能相可能相同。试设计一个算法，列出同。试设计一个算法，列出R的所有不同排列。的所有不同排列。【编程任务】【编程