自动化求解问题的算法.pptVIP

算法说明：如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A-B、A -C、B-C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。 * * “斐波那契数列”的发明者，是意大利数学家列昂纳多·斐波那契 * * 汉高祖刘邦曾问大将韩信：“你看我能带多少兵？”韩信斜了刘邦一眼说：“你顶多能带十万兵吧！”汉高祖心中有三分不悦，心想：你竟敢小看我！“那你呢？”韩信傲气十足地说：“我呀，当然是多多益善啰！”刘邦心中又添了三分不高兴，勉强说：“将军如此大才，我很佩服。现在，我有一个小小的问题向将军请教，凭将军的大才，答起来一定不费吹灰之力的。”韩信满不在乎地说：“可以可以。”刘邦狡黠地一笑，传令叫来一小队士兵隔墙站队， 刘邦转脸问韩信：“敢问将军，这队士兵有多少人？ 韩信发令：“每三人站成一排。”队站好后，小队长进来报告：“最后一排只有二人。”“ 又传令：“每五人站成一排。”小队长报告：“最后一排只有三人。” 再传令：“每七人站成一排。”小队长报告：“最后一排只有二人。“ 韩信脱口而出：“二十三人。” 刘邦大惊，心中的不快已增至十分，心想：“此人本事太大，我得想法找个岔子把他杀掉，免生后患。 最初记述这类算法的是一本名叫《孙子算经》的书中的“物不知数”问题，后来在宋朝经过数学家秦九韶的推广，又发现了一种算法，叫做“大衍求一术”。这在数学史上是极有名的问题，外国人一般把它称为“中国剩余定理”。 /v_show/id_XNTMwNTMyNzky.html 最初记述这类算法的是一本名叫《孙子算经》的书中的“物不知数”问题，也就是解同余方程组的问题。 后来在宋朝经过数学家秦九韶的推广，又发现了一种算法，叫做“大衍求一术”。这在数学史上是极有名的问题，外国人一般把它称为“中国剩余定理”。 至于它的算法，在《孙子算经》上就已经有了说明，而且后来还流传着这么一道歌诀： 三人同行七十稀， 五树梅花廿一枝， 七子团圆正半月， 除百零五便得知。 1×70＋2×21＋2×15－105 ＝142－105 ＝37 70：能被5和7整除，且 除 3 余 1; 21：能被3和7整除，且 除 5 余 1; 15：能被3和5整除，且 除 7 余 1; 105：是3×5×7，最小公倍数。 《孙子算经》的“物不知数”题虽然开创了“一次同余式”研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得。到了南宋时期的数学家秦九韶，在他的《数书九章》中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。可以推广到对任意n个数mi的情形，国外称此定理为“中国剩余定理”。 一个有趣的猜数游戏。如果你随便拿一把蚕豆（数目约在100粒左右），先3粒3粒地数，直到不满3粒时，把余数记下来；第二次再5粒5粒地数，最后把余数记下来；第三次是7粒一数，把余数记下来。然后根据每次的余数，就可以知道你原来拿了多少粒蚕豆了。例如，假如3粒一数余1粒，5粒一数余2粒，7粒一数余2粒，那么，有蚕豆有多少粒呢？ 在西方，直到十八世纪，瑞士的欧拉与法国的拉格朗日才对同余式问题进行系统的研究。十九世纪的第一年，德国的高斯在《算术探究》一书中，才提出解决这类问题的方法——剩余定理，并给出了严格证明，被后人称为“高斯定理”。 请学生回答此图中的控制结构？ * * 欧几里得算在西方被人们认为是史上第一个算法。 公元前300年左右，欧几里德在其著作中阐述了关于求解两个数最大公因子的过程。 这就是著名的欧几里德算法：给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。 亚历山大里亚的欧几里得，古希腊数学家，被称为“几何之父”。他最著名的著作《几何原本》是欧洲数学的基础，提出五大公设，是几何学的奠基人。 欧几里得是希腊亚历山大大学的数学教授。著名的古希腊学者阿基米德（古希腊哲学家、数学家、物理学家。发现浮力-阿基米德定律），是他“学生的学生”——卡农是阿基米德的老师，而欧几里得是卡农的老师。 * 请同学回答此算法中的控制结构？ 关于辗转相除法, 在我国古代的《九章算术》中就有记载： 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。 第1步，任意给两个正整数，如果它们都是偶数，用2约简；若不是，执行第2步。 第2步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数。 继续这个操作，直到它们相等为止，则这个“相等的数”就是所求的最大公约数；如果操作过程有约分，还要在“等数”上乘以约掉的因数。 98和63不可半，故更相减损。 《九