From Gossip@caterpillar

Algorithm Gossip: 雙色、三色河內塔

說明

雙色河內塔與三色河內塔是由之前所介紹過的河內塔規則衍生而來，雙色河內塔的目的是將下圖左上的圓環位置經移動成為右下的圓環位置：
多色河內塔

而三色河內塔則是將下圖左上的圓環經移動成為右上的圓環：

在移動的過程中，一樣遵守大盤必須在小盤之下的規則，而顏色順序則無限制。

解法

無論是雙色河內塔或是三色河內塔，其解法觀念與之前介紹過的河內塔是類似的，同樣也是使用遞迴來解，不過這次遞迴解法的目的不同，我們先來看只有兩個盤的情況，這很簡單，只要將第一柱的黃色移動至第二柱，而接下來第一柱的藍色移動至第三柱。

再來是四個盤的情況，首先必須用遞迴完成下圖左上至右下的移動：

接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱的上面兩個盤子就可以了。

那麼六個盤的情況呢？一樣！首先必須用遞迴完成下圖左上至右下的移動：

接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的四個盤子就可以了，這又與之前只有四盤的情況相同，接下來您就知道該如何進行解題了，無論是八個盤、十個盤以上等，都是用這個觀念來解題。

那麼三色河內塔呢？一樣，直接來看九個盤的情況，首先必須完成下圖的移動結果：

接下來最底兩層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的三個盤子就可以了。

您也可以看看 Towers of Hanoi Page 中有關於河內塔的討論。

雙色河內塔實作：C Java Python Scala Ruby

三色河內塔實作：C Java Python Scala Ruby

以下Java演算實例由 http://www.javaworld.com.tw 的 T5555 提供，感謝他的協助，我根據他的實例，轉換為C語言、Python與Scala的實作部份，您可以參考這個討論串有關於河內塔的討論。

雙色河內塔 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;
}

雙色河內塔 Java 實作

public class Hanoi2Colors { 
    public static void help() {
        System.out.println("Usage: java Hanoi2Colors number_of_disks");
        System.out.println("\t number_of_disks: must be a even number.");
    }
        
    public static void hanoi(int disks, 
                      char source, char temp, char target) {
        if (disks == 1) {
            System.out.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);
        }
    }
 
    public static void hanoi2colors(int disks) {
        char source = 'A';
        char temp = 'B';
        char target = 'C';
        for (int i = disks / 2; i > 1; i--) {
            hanoi(i-1, source, temp, target);
            System.out.printf("move disk from %c to %c%n", source, temp);
            System.out.printf("move disk from %c to %c%n", source, temp);
            hanoi(i-1, target, temp, source);
            System.out.printf("move disk from %c to %c%n", temp, target);
        }
        System.out.printf("move disk from %c to %c%n", source, temp);
        System.out.printf("move disk from %c to %c%n", source, target);
    }

    public static void main(String[] args) {
        int disks = Integer.parseInt(args[0]);
        if ((disks <= 0) || (disks % 2 != 0)) { 
            help(); 
        }
        else {
            hanoi2colors(disks);
        }
    }
}

雙色河內塔 Python 實作

def hanoi(disks, source, temp, target):
    if disks == 1:
        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 hanoi2Colors(disks):
    source = "A"
    temp = "B"
    target = "C"
    for i in range(disks // 2, 1, -1):
        hanoi(i - 1, source, temp, target)
        print("move disk from ", source, " to ", temp)
        print("move disk from ", source, " to ", temp)
        hanoi(i - 1, target, temp, source)
        print("move disk from ", temp, " to ", target)
    print("move disk from ", source, " to ", temp)
    print("move disk from ", source, " to ", target)
    
number = int(input("number of disks: "))
hanoi2Colors(number)

雙色河內塔 Scala 實作

package cc.openhome

object Main {
    def help() {
        println("Usage: java Hanoi2Colors number_of_disks")
        println("\t number_of_disks: must be a even number.")
    }

    def hanoi(disks: Int, source: Char, temp: Char, target: Char) {
        if (disks == 1) {
            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);
        }
    }

    def hanoi2colors(disks: Int) {
        val source = 'A';
        val temp = 'B';
        val target = 'C';
        var i = disks / 2
        while(i > 1) {
            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);
            i -= 1
        }
        printf("move disk from %c to %c%n", source, temp);
        printf("move disk from %c to %c%n", source, target);
    }
    
    def main(args: Array[String]) {
        val disks = args(0).toInt
        if(disks <= 0 || disks % 2 != 0) {
            help()
        }
        else {
            hanoi2colors(disks)
        }
    }
}

雙色河內塔 Ruby 實作

def hanoi(disks, source, temp, target)
    if disks == 1
        printf("move disk from %s to %s\n", source, target)
    else
        hanoi(disks - 1, source, target, temp)
        hanoi(1, source, temp, target)
        hanoi(disks - 1, temp, source, target)
    end
end
        
def hanoi2Colors(disks)
    source = "A"
    temp = "B"
    target = "C"
    
    (disks / 2).step(2, -1) { |i|
        hanoi(i - 1, source, temp, target)
        printf("move disk from %s to %s\n", source, temp)
        printf("move disk from %s to %s\n", source, temp)
        hanoi(i - 1, target, temp, source)
        printf("move disk from %s to %s\n", temp, target)
    }
    
    printf("move disk from %s to %s\n", source, temp)
    printf("move disk from %s to %s\n", source, target)
end
    
print "number of disks:"
number = gets.to_i
hanoi2Colors(number)

三色河內塔 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);
        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 hanoi3colors(int disks) {
    char source = 'A';
    char temp = 'B';
    char target = 'C';
    int i;

    if(disks == 3) {
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, target);
        printf("move disk from %c to %c\n", temp, target);
        printf("move disk from %c to %c\n", temp, source);
        printf("move disk from %c to %c\n", target, temp);;
    }
    else {
        hanoi(disks/3-1, source, temp, target);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);
        printf("move disk from %c to %c\n", source, temp);

        hanoi(disks/3-1, target, temp, source);
        printf("move disk from %c to %c\n", temp, target);
        printf("move disk from %c to %c\n", temp, target);
        printf("move disk from %c to %c\n", temp, target);

        hanoi(disks/3-1, source, target, temp);
        printf("move disk from %c to %c\n", target, source);
        printf("move disk from %c to %c\n", target, source);

        hanoi(disks/3-1, temp, source, target);
        printf("move disk from %c to %c\n", source, temp);
        
        for (i = disks / 3 - 1; i > 0; i--) {
            if (i>1) {
                hanoi(i-1, target, source, temp);
            }

            printf("move disk from %c to %c\n",
                                 target, source);
            printf("move disk from %c to %c\n",
                                 target, source);

            if (i>1) {
                hanoi(i-1, temp, source, target);
            }
            printf("move disk from %c to %c\n", 
                                   source, temp);
        }
    }
}

int main() {
    int n;
    printf("請輸入盤數：");
    scanf("%d", &n);

    hanoi3colors(n);

    return 0;
}

三色河內塔 Java 實作

public class Hanoi3Colors {    
    public static void help() {
        System.out.println("Usage: java Hanoi3Colors number_of_disks");
        System.out.println(
            "\tnumber_of_disks: must be a number divisible by 3.");
    }
       
    public static void hanoi(int disks, 
                       char source, char temp, char target) {
        if (disks == 1) {
            System.out.printf("move disk from %c to %c%n", source, target);
            System.out.printf("move disk from %c to %c%n", source, target);
            System.out.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);
        }
    }
    
    public static void hanoi3colors(int disks) {
        char source = 'A';
        char temp   = 'B';
        char target = 'C';
        if (disks == 3) {
            System.out.printf("move disk from %c to %c%n", source, temp);
            System.out.printf("move disk from %c to %c%n", source, temp);
            System.out.printf("move disk from %c to %c%n", source, target);
            System.out.printf("move disk from %c to %c%n", temp, target);
            System.out.printf("move disk from %c to %c%n", temp, source);
            System.out.printf("move disk from %c to %c%n", target, temp);
        } else {
            hanoi(disks/3-1, source, temp, target);
            System.out.printf("move disk from %c to %c%n", source, temp);
            System.out.printf("move disk from %c to %c%n", source, temp);
            System.out.printf("move disk from %c to %c%n", source, temp);
            hanoi(disks/3-1, target, temp, source);
            System.out.printf("move disk from %c to %c%n", temp, target);
            System.out.printf("move disk from %c to %c%n", temp, target);
            System.out.printf("move disk from %c to %c%n", temp, target);
            hanoi(disks/3-1, source, target, temp);
            System.out.printf("move disk from %c to %c%n", target, source);
            System.out.printf("move disk from %c to %c%n", target, source);
            hanoi(disks/3-1, temp, source, target);
            System.out.printf("move disk from %c to %c%n", source, temp);
        
            for (int i = disks / 3 - 1; i > 0; i--) {
                if (i>1) { 
                    hanoi(i-1, target, source, temp); 
                }
                System.out.printf(
                    "move disk from %c to %c%n", target, source);
                System.out.printf(
                    "move disk from %c to %c%n", target, source);
                if (i>1) { 
                    hanoi(i-1, temp, source, target); 
                }
                System.out.printf("move disk from %c to %c%n", source, temp);
            }
        }
    }

    public static void main(String[] args) {
        int disks = Integer.parseInt(args[0]);
        if ((disks <= 0) || (disks % 3 != 0)) { 
            help(); 
        }
        else {
            hanoi3colors(disks);
        }
    }
}

三色河內塔 Python 實作

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 range(disks // 3 - 1, 0, -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)
    
    
number = int(input("number of disks: "))
hanoi3Colors(number)

三色河內塔 Scala 實作

object Main {
    def help() {
        println("Usage: java Hanoi3Colors number_of_disks");
        println("\tnumber_of_disks: must be a number divisible by 3.");
    }

    def hanoi(disks: Int, source: Char, temp: Char, target: Char) {
        if (disks == 1) {
            printf("move disk from %c to %c%n", source, target);
            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);
        }
    }

    def hanoi3colors(disks: Int) {
        val source = 'A'
        val temp   = 'B'
        val target = 'C'
        if (disks == 3) {
            printf("move disk from %c to %c%n", source, temp);
            printf("move disk from %c to %c%n", source, temp);
            printf("move disk from %c to %c%n", source, target);
            printf("move disk from %c to %c%n", temp, target);
            printf("move disk from %c to %c%n", temp, source);
            printf("move disk from %c to %c%n", target, temp);
        } else {
            hanoi(disks/3-1, source, temp, target);
            printf("move disk from %c to %c%n", source, temp);
            printf("move disk from %c to %c%n", source, temp);
            printf("move disk from %c to %c%n", source, temp);
            hanoi(disks/3-1, target, temp, source);
            printf("move disk from %c to %c%n", temp, target);
            printf("move disk from %c to %c%n", temp, target);
            printf("move disk from %c to %c%n", temp, target);
            hanoi(disks/3-1, source, target, temp);
            printf("move disk from %c to %c%n", target, source);
            printf("move disk from %c to %c%n", target, source);
            hanoi(disks/3-1, temp, source, target);
            printf("move disk from %c to %c%n", source, temp);

            var i = disks / 3
            while(i > 0) {
                if (i>1) {
                    hanoi(i-1, target, source, temp);
                }
                printf("move disk from %c to %c%n", target, source);
                printf("move disk from %c to %c%n", target, source);
                if (i>1) {
                    hanoi(i-1, temp, source, target);
                }
                printf("move disk from %c to %c%n", source, temp);
                i -= 1
            }
        }
    }
    
    def main(args: Array[String]) {
        val disks = args(0).toInt
        if(disks <= 0 || disks % 3 != 0) {
            help()
        }
        else {
            hanoi3colors(disks)
        }
    }
}

Ruby

def hanoi(disks, source, temp, target)
    if disks == 1
        print "move disk from ", source, " to ", target, "\n"
        print "move disk from ", source, " to ", target, "\n"
        print "move disk from ", source, " to ", target, "\n"
    else
        hanoi(disks - 1, source, target, temp)
        hanoi(1, source, temp, target)
        hanoi(disks - 1, temp, source, target)
    end
end
        
def hanoi3Colors(disks)
    source = "A"
    temp = "B"
    target = "C"
    if disks == 3
        print "move disk from ", source, " to ", temp, "\n"
        print "move disk from ", source, " to ", temp, "\n"
        print "move disk from ", source, " to ", target, "\n"
        print "move disk from ", temp, " to ", target, "\n"
        print "move disk from ", temp, " to ", source, "\n"
        print "move disk from ", target, " to ", temp, "\n"
    else
        hanoi(disks / 3 - 1, source, temp, target)
        print "move disk from ", source, " to ", temp, "\n"
        print "move disk from ", source, " to ", temp, "\n"
        print "move disk from ", source, " to ", temp, "\n"
        hanoi(disks / 3-1, target, temp, source)
        print "move disk from ", temp, " to ", target, "\n"
        print "move disk from ", temp , " to ", target, "\n"
        print "move disk from ", temp, " to ", target, "\n"
        hanoi(disks / 3-1, source, target, temp)
        print "move disk from ", target, " to ", source, "\n"
        print "move disk from ", target, " to ", source, "\n"
        hanoi(disks / 3-1, temp, source, target)
        print "move disk from ", source, " to ", temp, "\n"
    end
    
    (disks / 3 - 1).step(1, -1) { |i|
        if i > 1
            hanoi(i - 1, target, source, temp)
        end
        print "move disk from ", target, " to ", source, "\n"
        print "move disk from ", target, " to ", source, "\n"
        
        if i > 1
            hanoi(i - 1, temp, source, target)
        end
        print "move disk from ", source, " to ", temp, "\n"
    }
end

print "number of disks: "
number = gets.to_i
hanoi3Colors(number)