文件名称：递归法字符变换、求24点
文件大小：5KB
文件格式：ZIP
更新时间：2018-11-29 15:39:17
递归法
问题一 字串变换 描述： 已知有两个字串 A, B 及一组字串变换的规则: A1 -> B1 A2 -> B2 规则的含义为：在 A中的子串 A1 可以变换为 B1、A2 可以变换为 B2 … 例如：A＝'abcd' B＝'xyz' 变换规则为： ‘abc’ -> ‘xu’ ‘ud’ -> ‘y’ ‘y’ -> ‘yz’ 则此时，A 可以经过一系列的变换变为 B，其变换的过程为： ‘abcd’ -> ‘xud’ -> ‘xy’ -> ‘xyz’ 共进行了三次变换，使得 A 变换为B。 现在的问题是：对于给定的A，B 及一组字串变换的规则，若A能在10步内（包含10步）变换成B，则输出所需的最短变换步数，否则输出NO ANSWER。 数据范围： 字串A,B长度小于等于20 规则总数小于等于6 输入格式： 从文件convert.in读入 第一行为两个字符串，第二行至文件尾为变换规则 变换规则一行为两个字符串A1 B1用空格分隔，表示 A1 -> B1 A B A1 B1 A2 B2 ... ... 输出格式： 输出到convert.out中 当变换步数在10步（包含10步）内，那么输出这个数字 否则，输出”NO ANSWER" 特别提醒： 这道题目很像WordLadder，用BFS也更为方便。但是，Lab2的主题是递归，所以大家这道题目不允许用BFS，必须是递归形式的。 对于每个测试用例，时间限制为1秒，实在不行，2秒也能接受。 规则没有优先级，所有的规则都是平等的，没有优先顺序。 可能会同时出现 a -> b a -> c这样的规则，就是说a可以转换成b，也可以转换成c。 问题二 24点 描述： 几十年前全世界流行一种叫作“算24点”数字扑克游戏。作为游戏者将得到4个1-13（在扑克牌里用A代替1，J代替11，Q代替12，K代替13）之间的自然数作为操作数，并对这四个数进行适当的算术运算（加，减，乘，除）使得最后结果为24。 例如： 4个数字为3 8 10 Q 那么一个方案可以是Q * ( 10 / ( 8-3 ) ) = 24 现在你的任务是实现一个自动24点计算器，对于任意的4个1-13的自然数，如果可以算出24点则输出一个合理方案，若无解则输出“NO ANSWER”。 数据范围： 4个数字属于S={1,2,3,4,5,6,7,8,9,10,J,Q,K} J,Q,K为字符 输入格式： 从文件calculator.in读入 一行4个数字，以空格分隔 输出格式： 输出到文件calculator.out中 一个字符串，表示最后的运算方案，符号与数字之间、符号与符号之间用空格分隔 如Q * ( 10 / ( 8 - 3 ) ) = 24 （Q与*之间有空格，(与10之间有空格） 或者当没有可行方案时输出“NO ANSWER"。 特别提醒： 这道题目还是用递归。 表达式中的每个子表达式的结果可以是小数，即例如 (3+3/7)*7=24 是合法的。 去除多余的括号。例如，对于2 2 3 8 这四个数字，一个解可以是3 * ( ( 8 + 2 ) - 2 )，但是要求是去除多余的括号，即最后的结果应该是3 * ( 8 + 2 - 2)。就是说，可以不用的括号都要去掉。
【文件预览】：
Lab2_convert.zip
Lab2_24.zip