枚举、递归和动态规划.doc

枚举、递归和动态规划李文新北京大学信息科学技术学院利用计算机编写程序进行问题求解时，有两种不同于用数学方法解决问题的最常用的思想：枚举和递归。枚举的基本思想是在可能的解空间中逐一尝试，通过判定尝试的值是否与已知条件矛盾来确定其是否是问题的解。这种思想通常不需要知道输入条件与问题的解之间的函数关系。递归的基本思想是假设对于输入x，问题的解是f(x)，则试图找到函数g，使得f(x) = g(f(x-1)。也就是找到一种将原问题缩小规模的方法，并且如果当规模缩小到一定程度时，问题的解是已知的。那么我们就可以通过函数的递归调用获得在不知道函数f的情况下获得问题的解。在递归调用过程中，有时候可能会出现重复计算的现象，我们可以将递归的过程翻转过来考虑，从小规模问题的已知解推向要求解的较大规模问题的解，这个过程需要保留中间计算结果，我们称这种解决问题的方法是动态规划。在计算机上使用枚举和递归的思想解决问题是利用了计算机的高速度和不知疲惫的特性，它所求解的问题通常是不容易找或者找不到求解方程的问题。动态规划可以看作是进行时间效率优化的一种方法。例1. 枚举 - 熄灯问题1222问题描述：有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。在下图1中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在图2中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。根据上面的规则，我们知道：1) 第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次。2) 各个按钮被按下的顺序对最终的结果没有影响。3) 对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。 图1图2对矩阵中的每盏灯设置一个初始状态。请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。输入：第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。输出：对每个案例，首先输出一行，输出字符串“PUZZLE #m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。输入样例2 0 1 1 0 1 01 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 输出样例PUZZLE #1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0PUZZLE #2 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1例2. 枚举 - 恼人的青蛙问题描述：在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。 稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图1所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图2所示。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图3所示。当然，农民所见到的是图4中的情形；既看不到图3中的直线，也见不到别人家田里被踩踏的水稻。 根据图4，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图4中，格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定：在一条青蛙行走路径中，最多有多少颗水稻被踩踏。例如，图4的答案是7，因为第6行上全部水稻恰好构成一条青蛙行走路径。输入：从标准输入设备上读入数据。第一行上两个整数R、C，分别表示稻田中水稻的行数和列数，1R、C5000。第二行是一个整数N，表示被踩踏的水稻数量， 3N5000。在剩下的N行中，每行有两个整数，分别是一颗被踩踏水稻的行号(1R)和列号(1C)，两个整数用一个空格隔开。而且，每棵被踩踏水稻只被列出一次。输出：从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走路径，则输出包含最多水稻的青蛙行走路径中的水稻数量，否则输出0。输入样例6 714 2 1 6 6 4 2 2 5 2 6 2 7 3 4 6 1 6 2 2 3 6 3 6 4 6 5 6 7 输出样例7例3. 递归 - 红与黑有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。输入要求包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下 1）.：黑色的瓷砖； 2）#：白色的瓷砖； 3）：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时，表示输入结束。输出要求对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。输入样例6 9 .#. .# . . . . . #.# .#.#. 0 0输出样例45例4. 递归 - 炮兵阵地司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 输入要求第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符(P或者H)，中间没有空格。按顺序表示地图中每一行的数据。N = 100；M = 10。输出要求仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。输入样例5 4PHPPPPHHPPPPPHPPPHHP输出样例6例5. 递归 - 木棍问题乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过50个长度单位。然后他又想把这些木棒恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棒的长度都用大于零的整数表示。输入要求由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，是零。 输出要求为每个案例，分别输出木棒的可能最小长度，每个案例占一行。 输入样例95 2 1 5 2 1 5 2 141 2 3 40输出样例65例6. 动态规划 - 陪审团在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。输入描述输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1=n=200, 1=m=20 而且 m=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0输出描述对每组数据，先输出一行，表示答案所属的组号