C语言汉诺塔算法和骨子里的数据结构

汉诺塔大凡来算法的。

多问题且发解决办法,汉诺塔也无差。如果汉诺塔的算法符合 Introduction
to
algorithms
这按照开之意:在电脑出现以前就发矣算法,只不过计算机的面世带来了再也多的算法,那么汉诺塔[\[1\]](https://www.jianshu.com/p/83b46b1580cd#fn1)的算法肯定不是以计算机出现之后才叫发现的,只不过经过代码,一部分人数好管这个算法描述的再度鲜明,另外一些人口足把此算法看的再次清。

另外,本文适合初大方(我就是是初大家)。

C 实现

咱们事先用 C
语言来落实之算法。但每当描写代码之前,我们而想了解这问题到底怎么解决,这个算法到底是啊。写代码只是写出来而已,思考问题的缓解才是双重要之。

汉诺塔 Towers of
Hanoi![DraggedImage.2c75ad871ac441868fc269717c29c7d5.png](http://upload-images.jianshu.io/upload\_images/1269937-5b2d9d61618714e2.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

倘若用语言描述解决汉诺塔问题之手续,比较自然的会面想到:

  1. 顾念办法把最好要命号圆盘挪至目标柱子上
  2. 思方法把坏大号圆盘挪至目标柱子上
  3. ……

若把最好充分号圆盘挪至目标柱子上之后,次大号圆盘也不怕成了极端老号圆盘,依此类推,后面的圆盘也是如出一辙。所以问题永远是将当下匪以靶柱子上之尽充分圆盘挪至目标柱子上。

另外,为了兑现用最酷圆盘挪到对象柱子上,必须把最特别的圆盘和对象柱子暴露出。所以总是会起如此的局面——目标柱子上是空,或者只有配置好之几乎独大号圆盘(不用再行考虑的圆盘),而眼下休当目标柱子上的最充分圆盘单独暴露出来:

示意图

这里发生一定量独地方值得注意。

率先,在高达图所著之情景遇,把极酷圆盘上面的逐条圆盘挪至中柱子上的题材,就是一个多少框框之汉诺塔问题(问题规模小了
1 级,也就是说,汉诺塔的层数少了 1,下同)。

说不上,一旦把目前莫在对象柱子上之极致充分圆盘挪过来,问题不怕变成了中等柱子上之汉诺塔挪至目标柱子上的题目,又是一个稍稍圈圈之汉诺塔问题。

釜底抽薪的即时有限独稍圈圈之汉诺塔问题,就好解决是大一级的汉诺塔问题,但可想像。解决小圈圈汉诺塔问题之时光,需要解决再有些范围的汉诺塔问题。到此地,递归的身形便已经好明显了。

以至于问题成单纯发生一个圆盘不以靶柱子上不时,直接以圆盘挪过来就是哼了。

脚我们就此 C
代码来实现这递归,关键就是是形成而齐讲述的有限独面小一级的汉诺塔问题。

void hanoi (int disks, char start, char mid, char dest) {
// 用 start, mid, 和 dest 分别代表起始柱子,中间柱子,和目标柱子
int b1 = disks; // 设当前最大的圆盘为 b1,这个圆盘的编号等于当前未妥善安置的圆盘的个数
int sdisks = disks - 1; // smaller disks,代表小一点的圆盘的个数
if (disks == 1) {
    move(b1, start, dest);
}
else {
    hanoi(sdisks,  start, dest, mid); // 借助 dest 柱子,把小一点的圆盘都挪到中间柱子上,这是规模小一级的汉诺塔问题
    move(b1, start, dest); // 将最大圆盘挪到目标圆盘
    hanoi(sdisks, mid, start, dest); // 借助 start 柱子,把小一点的圆盘挪到目标柱子上,这是规模小一级的汉诺塔问题
}
}

本条算法中为表达方便,建立了一定量只变量 b1
sdisks,但为省内存,他们好一直用表达式代替。

    void hanoi(int disks, char start, char mid, char dest) {
    if (disks == 1) {
        move(disks, start, dest);
    }
    else {
        hanoi(disks - 1,  start, dest, mid);
        move(disks, start, dest);
        hanoi(disks - 1, mid, start, dest);
    }
    }

此外定义 main 函数和 move 函数,就可以组合一个完全的次了。

    void move(int disk, char from, char to) {
        printf("Move disk %d from %c to %c \n", disk, from, to);
    }

// void hanoi here ...

    int main() {
        int disks;
        printf("How many disks do you want? \n");
    scanf("%d", disks);
    hanoi(disks, 'X', 'Y', 'Z'); // 设起始,中间,目标柱子分别为 X, Y, Z
    return 0;
    }

乃见面看出类似于下的输出[\[2\]](https://www.jianshu.com/p/83b46b1580cd#fn2)

Terminal 截图

Ruby 实现

脚我们又就此 Ruby 写一一体是算法,核心都是平的:为了递归解决问题,让
#hanoi 函数调用自己。

def hanoi(disks, start, mid, dest)
  if disks == 1
    move(1, start, dest)
    return
  end

  hanoi(disks - 1, start, dest, mid)
  move(disks, start, dest)
  hanoi(disks - 1, mid, start, dest)
end

def move(disk, from, to)
  puts("Move disk #{disk} from #{from} to #{to}")
end

puts "How many towers do you want?"
disks = gets.chomp.to_i
hanoi(disks, 'X', 'Y', 'Z')

数据结构

要是汉诺塔的层数特别多,也就是若受 disks
赋一个特地特别的价值,你认为会怎么?

c 中会说
segmentation fault,这是同内存分配有关的一无是处。
ruby 中会说 stack level too deep (SystemStackError)—— 栈太可怜了,
报错位置就是是 #hanoi 中第一只调用自己的地方
hanoi(disks - 1, start, dest, mid)

会晤出现是似是而非的因由在函数的调用在数据结构上是管一个新函数加载到函数的调用栈中。最先调用的函数(在本例中凡是主函数着之
hanoi
函数)在栈底,如果这个函数又去调用了别的函数,则这函数停在调用位置,新函数被压入栈中。如果新函数又调用了另外一个新函数,则继续压入栈中,以此类推。这便是调用函数进栈的历程。

直到来某个刚刚压入栈中的函数(也就算是高居栈顶位置的函数)不再调用别的函数,而是有了回来结果,则这函数退栈,栈顶位置换至这函数调用者所于的岗位;此调用者继续退栈,向更之前的函数返回结果,然后自己退栈。又盖此类推,这虽是函数返回结果的经过,是一个退栈的历程。

这就是说,返回的结果怎么交调用他的函数呢?也就是是仓的下一层。方法是在新的函数被调用的时节,被压入栈中的,除了参数,还有调用函数的回到地址。这样,他深受调用函数有了回到结果,就可以按照之前封存之返地址找到调用函数,向其传递返回结果。

汉诺塔中之递归,能吃咱们感受及这种调用,尽管每次调用的所谓的初函数,都是他自己。


  1. 这个玩在1883年即使叫发明了

  2. 自,C 需要编译一下, make hanoi 如果你的文书称是 hanoi.c 的话