算法与数学实用教案

1、 牧羊人的谜语：一个牧羊人想过河，他带着一只羊、一只狼和卷心菜，一次只能(zh nn)有两个先过河，（比如：牧羊人和羊或者牧羊人和卷心菜）不能让羊吃了卷心菜也不能让狼吃了羊，请问，他要怎样过河？ 算法（Algorithm）是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。 第1页/共20页第一页，共20页。1.穷举法（枚举法）穷举法（枚举法）2.递归法递归法3.回溯回溯(hu s)法法4.模拟法模拟法5.分治分治(fn zh)法法6.贪心法贪心法第2页/共20页第二页，共20页。穷举法（枚举法）穷举法（枚举法） 穷举法是一种(y zhn)针对于密码的破译方法。这种方法很

2、像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。第3页/共20页第三页，共20页。递归法递归法 一个函数、过程、概念或数学结构，如果在其定义或说明内部直接或间接地出现有其本身的引用，或者是为了描述(mio sh)问题的某一状态，必须用到它的上一状态，而描述(mio sh)上一状态，又必须用到它的上一状态这种用自己来定义自己的方法，称之为递归或者是递归定义。第4页/共20页第四页，共20页。递归法递归法斐波那契数列斐波那契数列汉诺塔阶乘阶乘(ji chn)n!=1*2*3*（n-1）*nn!=n*(n-1)!,n0;1, n=0。斐

3、波那契数列(shli)0，1，1，2，3，5，8，13，21，34，55，,从第三项开始，每一项是前两项的和汉诺塔的由来汉诺塔的原理汉诺塔的原理汉诺塔的实现汉诺塔的实现源代码第5页/共20页第五页，共20页。 河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根

4、石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。 第6页/共20页第六页，共20页。n阶Hanio塔问题 假设有3个分别命名为X,Y和Z的塔座，在塔座X上插有n个直径大小各不相同，依小到大编号为1，2，.，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列规则：(1)每次只能移动一个圆盘；(2)圆盘可以插在X、Y和Z中的任一塔座上；(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。第7页/共20页第七页，共20页。 当n=1时，问题比较简单，只要将编号为

5、1的圆盘从塔座X直接移至塔座Z上即可；当n1时，需利用塔座Y作辅助塔座，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X移至塔座Y上，则可先将编号为n的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个转盘移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1,因此可以用同样的方法求解。第8页/共20页第八页，共20页。原理原理Diagram 2Diagram3Diagram 2Diagram 3源代码源代码游戏游戏第9页/共20页第九页，共20页。回溯回溯(hu s)法法 回溯法(探索与回溯法)是一种选优搜索法，按选优

6、条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新(chngxn)选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。第10页/共20页第十页，共20页。回溯回溯(hu s)法法典型的问题典型的问题八皇后问题：八皇后问题：该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 源代码骑士周游问题：骑士周游问题：给定一个n*n的方阵，共有n2个区域，有一个国际象棋的马置于一个区域上，要求找到一条路径，使马按

7、国际象棋的规则，从开始区域出发，不重复地把n2个区域都恰好经过一次。源代码第11页/共20页第十一页，共20页。模拟法模拟法 模拟法和类比法很近似。它是在实验室里先设计出于某被研究现象或过程（即原型）相似的模型(mxng)，然后通过模型(mxng)，间接的研究原型规律性的实验方法。 第12页/共20页第十二页，共20页。模拟法模拟法 日本一位中学生发现一个奇妙的“定理(dngl)”，请角谷教授证实，而教授无能为力，于是产生角谷猜想。猜想的内容是：任给一个自然数，若为偶数除以2，若为奇数则乘3加1，得到一个新的自然数后按照上面的法则继续演算，若干次后得到的结果必然为1。源代码第13页/共20页第

8、十三页，共20页。分治分治(fn zh)(fn zh)法法 分治法字面上的解释是“分而治之(fn r zh zh)”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。第14页/共20页第十四页，共20页。连连看（连连看（1） 连通(lintng)算法： 1.直连型 2.一折型 第15页/共20页第十五页，共20页。 3.两折型连连看（连连看（2）第16页/共20页第十六页，共20页。贪心贪心(tnxn)(tnxn)法法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前(dngqin)看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。第17页/共20页第十七页，共20页。贪心贪心(tnxn)(tnxn)法法 背包问题有一个背包，背包容量是M=150。有7个物品，物品不可以(ky)分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品