信息学竞赛3-4回溯法

1、回溯法Page 2用回溯法产生所有3位数 n 从100到999n 设m为当前指向的位置n 当m1，回溯到上一个位置n即：m-;n每次都要am+；n 退出条件a1=10A1A2A3100101102103Page 3八皇后问题n 十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 n 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。n 计算机发明后，有多种方法可以解决此问题。Page 4解决方案n 简化为四皇后n 确

2、定解的表示方法n右图为2413n 确定解的特征2413Page 5四皇后问题n 用数组表示解n 2413为A1=2A2=4A3=1A4=3n 不攻击的条件1. AiAj，不在同一列2. Abs(Ai-Aj) i-k，不在同一斜线2413Page 61Page 71XXPage 81XX3Page 91XX3XXXXPage 101XX4Page 111XX4XXXPage 121XX4X2XXPage 131XX4X2XXXXXXPage 142Page 152XXXPage 162XXX4Page 172XXX41XXXPage 182XXX41XXX3Page 193Page 203XXX

3、Page 2131XXXPage 2231XXXXXXPage 2331XXXXXX4Page 2431XXXXXX42Page 254Page 264XXPage 2742XXPage 2842XXXXXXPage 2941XXPage 3041XXXX3XPage 3141XXXX3XXXXXPage 32回溯法的几个关键条件n 初始条件m=1;am = 1;n 循环条件a1 N + 1n 继续条件m 1/已经测试完这一行的所有列/到达最后一列，且不是第1行n 调整am+; /右移1列Page 33回溯法基本流程初始条件While(循环条件) if(继续条件) 继续 else while

4、(回溯条件) 回溯; 调整; Page 34回溯法演示n 用回溯法产生所有3位数n 初始条件m=1;am = 1;n 循环条件a1 10n 继续条件m 1/已经测试完这一行的所有数字/到达最后一列，且不是第1行n 调整am+; /右移1列Page 35用回溯法解决问题n 八皇后n 桥本方程式Page 36桥本分数式nPage 37八皇后问题n 十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 n 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来

5、有人用图论的方法解出92种结果。Page 38解决方案n 简化为四皇后n 确定解的表示方法n右图为2413n 确定解的特征2413Page 39四皇后问题n 用数组表示解n 2413为A1=2A2=4A3=1A4=3n 不攻击的条件1. AiAj，不在同一列2. Abs(Ai-Aj) i-k，不在同一斜线2413Page 40神奇古尺有一个古尺，总长36寸因年代久远，中间标注的刻度只剩下8个但是这个尺子还是可以一次性度量136之间的任意长度请确定这8个刻度的位置 Page 41神奇古尺可能刻度为1,3,6,13,20,27,31,35,可能刻度为1,5,9,16,23,30,33,35,Pag

6、e 42四大湖泊我国有4大淡水湖。 甲说：洞庭湖最大，洪泽最小。鄱阳湖第三。 乙说：洪泽湖最大，洞庭湖最小，鄱阳湖第二。太湖第三。 丙说：洪泽湖最小，洞庭湖第三。 丁说：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三。 4个人每人仅答对了一个，请你编程给出4个湖从大到小的顺序Page 43四大湖泊甲：a=1,b=4,c=3乙：b=1,a=4,c=2,d=3丙：b=4,a=3丁：c=1,d=4,b=2,a=3洞庭湖洞庭湖 洪泽湖洪泽湖 鄱阳湖鄱阳湖太湖太湖abcdPage 44四大湖泊隐藏条件a b c d，并且a+b+c+d=10结果a=2,b=4,c=1,d=3洞庭湖洞庭湖 洪泽湖洪泽湖 鄱阳

7、湖鄱阳湖太湖太湖abcdPage 45装错信封n 某人给5个朋友写信，同时写了5个朋友的信封，问每个信封和信都不相符的情况有多少？Page 46别出心裁的情侣拍照n 8对情侣，参加聚会后拍照，主持人要求如下：1. 每对情侣不得相邻2. 每对情侣都是男左女右排队3. 编号为1的情侣之间有1个人，编号为2的情侣之间有2个人，依次类推，编号为8的情侣之间有8个人Page 47Page 48Page 49Page 50Page 51Page 52Page 53Page 54Page 55马拦过河卒n 棋盘上A点有一个过河卒,需要走到目标B点.卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方

8、的马，该马所在的点和所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 n 棋盘用坐标表示，A点（0，0）、B点（m,n)(n,m =15），同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 Page 56马拦过河卒Page 57组合的输出n 从n个元素中抽出r个元素（r=n）,可以简单地将n个元素理解为自然数1，2，n，从中任取r个数。 n 要求：不用递归的方法输出所有组合。 n 例如n=5，r=3，所有组合为r1r2r3： n 1 2 3 , 1 2 4 , 1 2 5, 1 3 4

9、, 1 3 5, 1 4 5 , 2 3 4 ,2 3 5,2 4 5 ,3 4 5 Page 58走迷宫n 有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可走，文件读入这m*n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的的行号和列号）。现在要你编程找出所有可行的道路总数，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用 -1表示无路）Page 59走迷宫n Inputn第一行是两个数 m、n（1 m,n 15），接下来是m行n列由10组成的数据，最后两行是起始点和

10、结束点。n Outputn所有可行的路径总数。如果没有一条可行的路则输出 -1.Page 60数字排列问题n 列出所有从数字式1到数字n的连续自然数的排列,要求所产生的任一数字序列中不允许出现重复的数字。Page 61邮票问题n 设有已知面额的邮票m种,每种有n张。问：用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续出现面额数最多有多少？（1=m=100,1=n=100,1=邮票面额=255）Page 62邮票问题n Inputn第一行：m和n的值，中间用一空格隔开。 n第二行：a1.m(面额)，每个数中间用一空格隔开。 n Outputn连续面额数的最大长度。Page 63邮票问题

11、n Sample Inputn3 4n1 2 4n Sample Outputn14n 输出说明： n假设组合结果有：1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 n则其连续面额数的最大长度为14（即1-14一直连续且长度最长）.Page 64置棋问题n 在mn的方格中任意指定x个格子构成一个棋盘(如图)，在任一个构成的棋盘上放置k个棋子，要求任意两个棋子不得位于同一行或同一列上，要求输出满足条件的所有方案。 （注意棋盘是稀疏的，即x(m*n)/2,1 m、n 10） Page 65置棋问题n 编程要求： 1、对给定的一个棋盘，求出该棋盘可放置的最多的棋子数p。 2、记di为该棋盘上放置i个棋子时的方案总数（1=i=p），其中经旋转和镜面反射而得到的方案记为不同的方案，对每一个i，求出相应的di。 3、对每一个棋盘，输出p和d1，d2，dp，只需输出数字，不必输出具体的棋盘方案。 Page 66置棋问题n Inputn第一行是两个数字，代表第一个棋盘的m和n，以下m行为一个仅由0、1组成的mn的矩阵，某一个位置值为1表示相应的格子在这个棋盘上，为0表示相应的格子不在棋盘上。n