学习网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 36229|回复: 0
收起左侧

高级语言程序设计 - 吉林大学-9.4.1 实例-汉诺塔

[复制链接]
发表于 1-26 01:41 | 显示全部楼层 |阅读模式
刚才我们引进了递归程序设计思想现在咱们  
再讲一个递归程序的例子这个例子 用递归写出来  
很容易要用循环写出来  
很难我是没写出来别人写的程序  
我也看了但是我没看懂程序是什么汉诺塔游戏  
这个程序这个问题又被称作  
世界末日问题是什么问题呢相传  
古印度有一个布拉玛婆罗门神庙那里的僧侣们在做一种游戏叫做汉诺塔游戏这个游戏就是这个规则有一个平板在平板上  
有3根钻石针这针挺贵  
钻石磨出来的在一根针上  
成塔形落放着 64 片金片要求  
把这 64 片金片从一根针上  
移到另一根针上去怎么移  
不能端过来放  
那就完事了它有规则移动规则是这样的第一条  
每次只允许移动一片金片比如说  
拿出一个来放到那去这是可以的第二条  
移动过程中  
任何时刻  
都不允许有较大的金片  
在较小的上面  
倒塔形落着比如  
这个底下小  
上头大这是错的第三个  
除了 3 个针以外其它地方  
不允许再放金片比如这放一个  
那是不行的这样  
不论白天黑夜  
都有一个憎侣在那移动当时说  
这64片金片真的从一个针  
都移到另一个针上之后那天就是世界末日到那时候  
它们教的虔诚信徒  
可以升天其它人下地狱当然这只是个传说这个问题按照规则  
把64片金片都移过去总的移动次数是多少能不能移过去  
能移过去总的移次数是  
2 的 64 次方 减 12 的 64 次方 减 1 是多少次写出来好写这数多大呢如果一秒钟  
移动一次  
不发生错误日夜不停的移要移 5800 多亿年亿年  
不是一年  
是亿年咱们太阳系的寿命  
才100到150亿年而已所以它移完了  
真的就会世界末日了太阳系都没了当然这只是个传说真的要移  
是移不完的要我们做什么呢问题描述出来了要我们  
编程序  
打印金片的移动次序怎么打印这程序怎么编真的不好编现在  
假设把这个问题给它编上号三根针  
编上号 a  
b  
c这样  
好描述问题也就是说把 a 针上的 64 片金片  
移动到 b 针上去c 针可以用移动  
怎么移动真的想不出来开始  
拿出一片金片  
从 a 针上拿下来放 b 针上  
放 c 针上去没有什么规律没什么原则可以做这个决定来不好移怎么办呢下面咱们  
换一个角度来想这个问题怎么想呢  
这么想现在不是要把a 针上 64 片金片  
移到 b 针上去吗要想做到这点在移动过程中必须能够把顶上那 6 3片金片  
移到 c 针上去因为它一次  
只能移一次最底下那片  
要移到 b 针上去所以  
必须能够做到这一点这时候  
才能把 a 针上的一片金片  
移 b 针上去这是容易了  
一片金片  
是吧那么刚才  
既然有办法把 a 针的 63片 金片  
移到 c 针上去现在  
用同样的办法把 c 针 63 片金片  
移到 b 针上去这问题就解决了解决没有没解决移动 63 片  
跟移动 64 片  
没什么区别两片一片的  
移动 1 片  
再移动一片  
那行64 片 63 片  
没什么区别  
都是一堆所以  
问题没解决但是  
它却向解的方向  
前进了一步64 变成 63 片了规模小了这一步  
虽然很小甚至是  
微不足道的但是  
也很重要咱们重新观察一下  
这个过程a 针  
不是 64 片金片吗先移动 63 片  
到 c 针上去再移动一片  
到 b 针上去c 针上的 63 片  
再移到 b 针上去这 b 针 64 片了  
就这样一个过程按照这个想法移动 64 片金片问题是不是  
就可以分解成  
下面三个了先移动 63 片  
再移动 1 片  
再移动 63 片分解成  
这个问题刚才说了  
虽然没解决但是  
向解的方向  
前进一步64 片  
变 63 片了  
这一步虽然很小甚至是微不足道的  
但是确实很重要的重要在哪呢我们可以按照这个思路  
继续往下想63 片问题  
变成 62 片问题62 片  
变成 61 片的问题一点点减最后  
变成一片  
问题不就解决了吗这个步骤  
虽然小  
也很重要现在  
咱们把 64 片金片问题  
分解成这个了我们设想一下如果  
有一个函数 move可以把 n 片金片  
从 x 针挪到 y 针上去其中  
z 针可用如果  
有这个函数的话那么  
原始问题是啥就是  
对这个 move 函数的调用调用一下 move 函数  
问题就解决了刚才  
那 63 片金片问题也是对 move 函数的调用现在  
关键的关键是 move 函数  
怎么编move 函数是什么关键问题在这下面  
就来编 move 函数move 函数是什么把 x 针上的 n 片金片  
移到 y 针上去移动过程中  
z 针可用按照刚才 64 片金片的问题同样思路  
分解可以先把 x 针上 n-1 片金片  
移到 z 针上去移动过程中  
y 针可以用然后  
再把 x 针上的 1 片金片  
移到 y 针上去然后  
再把 z 针上 n-1 片金片  
移到 y 针上来这时候  
x 针可以用分解成  
这样三步就  
可以写出来这 move 函数移动 n-1 片  
调用move移动 1 片另写一个函数 move_one再移动 n-1 片  
再调用 move 函数这程序  
写出来了就这么做移动 n 片金片问题  
就是这三步这程序  
就编出来了编出来  
就往下执行吧这么执行不行啊得有递归出口move 都是递归  
得有出口考虑递归出口显然  
只 0 片金片的时候  
就没法再移动了就可以说是  
递归出口n 大于零的时候  
移动n 等于零的时候  
就不移动了这个函数  
就这么编编出来了在函数里  
咱们考虑移动一片  
移动一片很简单就是一个函数然后  
再给它配上主程序64 片金片  
就是 move(64, a, b, c)就能解决这个问题然后  
配上主程序执行主程序输入一个 n输入 64 就是说 move(64, a, b, c)完了  
程序编出来了这程序  
就这么的汉诺塔问题的程序  
就这样程序很简单这程序对不对呀对不对  
咱执行一下执行  
输入金片个数比如说 10 片10 片太大  
得1000多次  
咱们执行不起5 片  
这就是移动次序这给出来了从 a 针到 b 针从 a 针到 c 针等等这是移动次序可以看出来  
这程序对吧执行完了再执行一遍太多  
也看不出  
个数来比如说 3 片3 片少  
就这几个移过去了a 针到 b 针一个然后 a 针到 c 针一个完了 b 针到 c 针一个然后 a 针到 b 针  
就是最底下的  
到 b 针了就这样一个过程然后  
再把 n-1 个  
再移到 b 针上去不就完事了吗这个程序  
就编出来刚才执行  
也看出对了[此为课程内容大纲,相关资源下载地址请在论坛搜索标题名称]

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|小黑屋|学习资源网 ( 粤ICP备16100991号-2 )

GMT+8, 12-9 12:36 , Processed in 0.168280 second(s), 31 queries .

Powered by Discuz! X3.4 Licensed

© 2001-2017 Comsenz Inc. Template By ¡¾Î´À´¿Æ¼¼¡¿¡¾ www.wekei.cn ¡¿

快速回复 返回顶部 返回列表