DOC《课后习题》

课后习题 全排列算法(实现4个元素的全排列) 思路:

1、任取4个元素中的一个

2、任取剩余3个元素中的一个

3、剩余的2个元素分别变换顺序得到2种不同排列.

算法缺陷: 最终只得到12种排列,另有12组排列未列出 改进: 逐一取4个元素中的一个 任取剩余3个元素中的一个 剩余的2个元素分别变换顺序得到2种不同排列. 课后思考1: 能否设计出对n个元素的全排列算法? (n为大于2的正整数) 24点算法一 公式法 在有解的牌组中,用得最为广泛的是以下六种解法:(我们用a、b、c、d表示牌面上的四个数) (a―b)*(c+d) 如(10―4)*(2+2)=24等. ②(a+b)÷c*d 如(10+2)÷2*4=24等. ③(a-b÷c)*d 如(3―2÷2)*12=24等. ④(a+b-c)*d 如(9+5―2)*2=24等. ⑤a*b+c―d 如11*3+l―10=24等. ⑥(a-b)*c+d 如(4―l)*6+6=24等. 根据公式法设计程序思路: 实现4个数字的全排列 对每一个排列逐一套用6个公式计算,如果得数为24,则显示该表达式. 算法缺陷:实验结果表明,结果表达式有重复现象,需要进一步剔除掉重复表达式. 改进后的算法思路: 实现4个数字的全排列;

对每一个排列逐一套用6个公式计算,如果得数为24,则将该结果保存在元胞数组中;

对元胞数组元素剔除重复元素;

显示该元胞数组. 提示:学会查询所需系统函数,该程序利用两个函数 perms, unique可大大减少编程难度,提高编程效率 课后思考2: 该程序中有两处会出现重复元素,第一次出现在4个数字的全排列中;

第二次出现在得出24点的表达式中.因而,可考虑分别在第一次或第二次出现重复时剔除重复元素.请利用程序剖析(view----profile)试一试该程序中剔除重复元素到底应在何时进行运行效率会较高? 24点算法二

1、概述 给定4个整数,其中每个数字只能使用一次;

任意使用 构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏.这方面的程序很多,一般都是穷举求解.本文介绍一种典型的算24点的程序算法,并给出两个具体的算24点的程序:一个是面向过程的C实现,一个是面向对象的java实现.

2、基本原理 基本原理是穷举4个整数所有可能的表达式,然后对表达式求值. 表达式的定义: expression = (expression|number) operator (expression|number) 因为能使用的4种运算符 + - * / 都是2元运算符,所以本文中只考虑2元运算符.2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算. 由上所述,构造所有可能的表达式的算法如下: (1) 将4个整数放入数组中 (2) 在数组中取两个数字的排列,共有 P(4,2) 种排列.对每一个排列, (2.1) 对+-*/每一个运算符, (2.1.1) 根据此排列的两个数字和运算符,计算结果 (2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将2.1.1 计算的结果放入数组中 (2.1.3) 对新的数组,重复步骤

2 (2.1.4) 恢复数组:将此排列的两个数字加入数组中,将2.1.1 计算的结果从数组中去除掉 可见这是一个递归过程.步骤

2 就是递归函数.当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束. 在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致.在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列. 括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序.所以在以上算法中,无需考虑括号.括号只是在输出时需加以考虑.