前言

This Series aritcles are all based on the book 《经典算法大全》; 对于该书的所有案例进行一个探究和拓展，并且用python和C++进行实现; 目的是熟悉常用算法过程中的技巧和逻辑拓展。

提出问题

12.Algorithm Gossip: 双色、三色河内塔

基本说明

双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来，就是每层是两种颜色交替。而三色河内塔则是每层是三种颜色交替。

解法

无论是双色河内塔或是三色河内塔，其解法观念与之前介绍过的河内塔是类似的，同样也是使用递回来解，不过这次递回解法的目的不同，同样对待递归问题, 解法非常单一， 注意到递归的出口，午后效性(就是递归深度的上下级联系); 我们先来看只有两个盘的情况，这很简单 ，只要将第一柱的黄色移动至第二柱，而接下来第一柱的蓝色移动至第三柱。再来是四个盘的情况，首先必须用递回完成。

双色河内塔 C 实作

#include <stdio.h> void hanoi(int disks, char source,char temp, char target){ if (disks == 1) { printf("move disk from %c to %c\n",source,target); printf("move disk from %c to %c\n",source,target); } else { hanoi(disks-1,source,target,temp); hanoi(1,source,temp, target); hanoi(disks-1,temp, source,target); } } void hanoi2colors(int disks){ char source = 'A'; char temp = 'B'; char target = 'C'; int i; for(i = disks / 2; i > 1; i--) { hanoi(i-1, source,temp, target); printf("move disk from %c to %c\n",source,temp); printf("move disk from %c to %c\n",source,temp); hanoi(i-1, target,temp, source); printf("move disk from %c to %c\n",temp, target); } printf("move disk from %c to %c\n",source,temp); printf("move disk from %c to %c\n",source,target); } int main() { int n; printf("请输入盘数："); scanf("%d", &n); hanoi2colors(n); return 0; }

三色河内塔 C#include

代码

三色塔 python 实现

#include <stdio.h> def hanoi(disks, source,temp, target): if disks == 1: print('move disk from',source,'to', target) print('move disk from',source,'to', target) print('move disk from',source,'to', target) else: hanoi(disks-1,source,target,temp) hanoi(1,source,temp, target) hanoi(disks-1,temp, source,target) def hanoi3colors(disks): source = 'A' temp = 'B' target = 'C' if(disks == 3): print('move disk from',source,'to', temp) print('move disk from',source,'to', temp) print('move disk from',source,'to', target) print('move disk from',temp,'to', target) print('move disk from',temp,'to', source) print('move disk from',target,'to', temp) else: hanoi(disks/3-1,source,temp, target) print('move disk from',source,'to', temp) print('move disk from',source,'to', temp) print('move disk from',source,'to', temp) hanoi(disks/3-1,target,temp, source) print('move disk from',temp,'to', target) print('move disk from',temp,'to', target) print('move disk from',temp,'to', target) hanoi(disks/3-1,source,target,temp) print('move disk from',target,'to', source) print('move disk from',target,'to', source) hanoi(disks/3-1,temp, source,target) print('move disk from',source,'to', temp) for i in [disks/3 -1 - i for i in range(int(disks/3-1))]: if (i>1): hanoi(i-1, target,source,temp) print('move disk from',target,'to', source) print('move disk from',target,'to', source) if (i>1): hanoi(i-1, temp, source,target) print('move disk from',source,'to', temp) hanoi3colors(6)

拓展和关联

后记

参考书籍

《经典算法大全》维基百科