算法与数学学习教案

1、会计学1算法算法(sun f)与数学与数学第一页，共20页。1.穷举法（枚举法）穷举法（枚举法）2.递归法递归法3.回溯回溯(hu s)法法4.模拟法模拟法5.分治分治(fn zh)法法6.贪心法贪心法第2页/共20页第二页，共20页。第3页/共20页第三页，共20页。归定义。第4页/共20页第四页，共20页。斐波那契数列斐波那契数列汉诺塔阶乘阶乘(ji chn)n!=1*2*3*（n-1）*nn!=n*(n-1)!,n0;1, n=0。斐波那契数列(shli)0，1，1，2，3，5，8，13，21，34，55，,从第三项开始，每一项是前两项的和汉诺塔的由来汉诺塔的原理汉诺塔的原理汉诺塔的实现

2、汉诺塔的实现源代码第5页/共20页第五页，共20页。 河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。 第6页/

3、共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时，问题比较简单，只要将编号为1的圆盘从塔座X直接移至塔座Z上即可；当n1时，需利用塔座Y作辅助塔座，若能设法将压在编号为n的圆盘之上的n-1个圆盘从塔座X移至塔座Y上，则可先将编号为n

4、的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个转盘移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1,因此可以用同样的方法求解。第8页/共20页第八页，共20页。原理原理Diagram 2Diagram3Diagram 2Diagram 3源代码源代码游戏游戏第9页/共20页第九页，共20页。第10页/共20页第十页，共20页。典型的问题典型的问题八皇后问题：八皇后问题：该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 源代码骑士周游问题：骑士周游问题：给定一个n*n的方阵，共有n2个区域，有一个国际象棋的马置于一个区域上，要求找到一条路径，使马按国际象棋的规则，从开始区域出发，不重复地把n2个区域都恰好经过一次。源代码第11页/共20页第十一页，共20页。第12页/共20页第十二页，共20页。源代码第13页/共20页第十三页，共20页。第14页/共20页第十四页，共20页。第15页/共20页第十五页，共20页。连连看（连连看（2）第16页/共20页第十六页，共20页。第17页/共20页第十七页，共20页。第