雙色、三色河內塔
December 1, 2021雙色河內塔與三色河內塔是由〈河內塔〉介紹過的規則衍生而來，雙色河內塔要將下圖左上，移動盤子成為右下：
三色河內塔是將下圖左上，移動盤子成為右上：
解法思路
無論是雙色河內塔或是三色河內塔，解法觀念與之前介紹過的〈河內塔〉類似，不過這次遞迴解法的目的不同。
只有兩個盤子時，只要將第一柱的黃色移動至第二柱，而接下來第一柱的藍色移動至第三柱；若有四個盤子，首先必須用遞迴完成下圖左上至右下的移動：
接下來最底層的就不用管它們了，因為已經就定位，只要再處理第一柱的上面兩個盤子就可以了；六個盤的情況呢？一樣！首先必須用遞迴完成下圖左上至右下的移動：
接下來最底層的就不用管它們了，因為它們已經就定位，只要再處理第一柱上面的四個盤子就可以了，這又與之前只有四盤的情況相同，接下來您就知道該如何 進行解題了，無論是八個盤、十個盤以上等，都是用這個觀念來解題。
三色河內塔呢？類似，直接來看九個盤的情況，首先必須完成下圖的移動結果：
接下來最底兩層的就不用管它們了，因為已經就定位，只要再處理第一柱上面的三個盤子就可以了：
程式實作：雙色河內塔
def hanoi(n, a, b, c):
if n == 1:
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, c))
print('{} to {}'.format(b, c))
else:
hanoi(n - 1, a, b, c)
print('{} to {}'.format(a, b))
hanoi(n - 1, c, a, b)
print('{} to {}'.format(a, c))
hanoi(n - 1, b, c, a)
print('{} to {}'.format(b, c))
hanoi(n - 1, a, b, c)
def two_colors_hanoi(n, a, b, c):
if n == 1:
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, c))
else:
hanoi(n - 1, a, b, c)
print('{} to {}'.format(a, b))
hanoi(n - 1, c, a, b)
print('{} to {}'.format(a, c))
hanoi(n - 1, b, c, a)
two_colors_hanoi(n - 1, a, b, c)
two_colors_hanoi(3, 'A', 'B', 'C')
move(A, B) :- writef("%p to %p\n", [A, B]).
hanoi(1, A, B, C) :-
move(A, B), move(A, C), move(B, C), !.
hanoi(N, A, B, C) :-
M is N - 1,
hanoi(M, A, B, C),
move(A, B),
hanoi(M, C, A, B),
move(A, C),
hanoi(M, B, C, A),
move(B, C),
hanoi(M, A, B, C).
two_colors_hanoi(1, A, B, C) :-
move(A, B), move(A, C), !.
two_colors_hanoi(N, A, B, C) :-
M is N - 1,
hanoi(M, A, B, C),
move(A, B),
hanoi(M, C, A, B),
move(A, C),
hanoi(M, B, C, A).
main(_) :-
two_colors_hanoi(2, a, b, c).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang
def hanoi(n, a, b, c) {
if n == 1 {
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, c))
println('{0} to {1}'.format(b, c))
}
else {
hanoi(n - 1, a, b, c)
println('{0} to {1}'.format(a, b))
hanoi(n - 1, c, a, b)
println('{0} to {1}'.format(a, c))
hanoi(n - 1, b, c, a)
println('{0} to {1}'.format(b, c))
hanoi(n - 1, a, b, c)
}
}
def two_colors_hanoi(n, a, b, c) {
if n == 1 {
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, c))
}
else {
hanoi(n - 1, a, b, c)
println('{0} to {1}'.format(a, b))
hanoi(n - 1, c, a, b)
println('{0} to {1}'.format(a, c))
hanoi(n - 1, b, c, a)
two_colors_hanoi(n - 1, a, b, c)
}
}
two_colors_hanoi(3, 'A', 'B', 'C')
程式實作：三色河內塔
def hanoi(n, a, b, c):
if n == 1:
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, c))
print('{} to {}'.format(b, c))
print('{} to {}'.format(b, c))
else:
hanoi(n - 1, a, b, c)
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, b))
hanoi(n - 1, c, b, a)
print('{} to {}'.format(b, c))
print('{} to {}'.format(b, c))
print('{} to {}'.format(b, c))
hanoi(n - 1, a, b, c)
def three_colors_hanoi(n, a, b, c):
if n == 1:
print('{} to {}'.format(a, c))
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, b))
print('{} to {}'.format(c, a))
print('{} to {}'.format(b, c))
else:
hanoi(n - 1, a, b, c)
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, b))
print('{} to {}'.format(a, b))
hanoi(n - 1, c, b, a)
print('{} to {}'.format(b, c))
print('{} to {}'.format(b, c))
print('{} to {}'.format(b, c))
hanoi(n - 1, a, c, b)
print('{} to {}'.format(c, a))
hanoi(n - 1, b, c, a)
print('{} to {}'.format(c, b))
three_colors_hanoi(n - 1, a, b, c)
three_colors_hanoi(3, 'A', 'B', 'C')
move(A, B) :- writef("%p to %p\n", [A, B]).
hanoi(1, A, B, C) :-
move(A, B),
move(A, B),
move(A, C),
move(B, C),
move(B, C), !.
hanoi(N, A, B, C) :-
M is N - 1,
hanoi(M, A, B, C),
move(A, B), move(A, B), move(A, B),
hanoi(M, C, B, A),
move(B, C), move(B, C), move(B, C),
hanoi(M, A, B, C).
three_colors_hanoi(1, A, B, C) :-
move(A, C),
move(A, B),
move(A, B),
move(C, A),
move(B, C), !.
three_colors_hanoi(N, A, B, C) :-
M is N - 1,
hanoi(M, A, B, C),
move(A, B), move(A, B), move(A, B),
hanoi(M, C, B, A),
move(B, C), move(B, C), move(B, C),
hanoi(M, A, C, B),
move(C, A),
hanoi(M, B, C, A),
move(C, B),
three_colors_hanoi(M, A, B, C).
main(_) :-
three_colors_hanoi(2, a, b, c).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang
def hanoi(n, a, b, c) {
if n == 1 {
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, c))
println('{0} to {1}'.format(b, c))
println('{0} to {1}'.format(b, c))
}
else {
hanoi(n - 1, a, b, c)
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, b))
hanoi(n - 1, c, b, a)
println('{0} to {1}'.format(b, c))
println('{0} to {1}'.format(b, c))
println('{0} to {1}'.format(b, c))
hanoi(n - 1, a, b, c)
}
}
def three_colors_hanoi(n, a, b, c) {
if n == 1 {
println('{0} to {1}'.format(a, c))
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(c, a))
println('{0} to {1}'.format(b, c))
}
else {
hanoi(n - 1, a, b, c)
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, b))
println('{0} to {1}'.format(a, b))
hanoi(n - 1, c, b, a)
println('{0} to {1}'.format(b, c))
println('{0} to {1}'.format(b, c))
println('{0} to {1}'.format(b, c))
hanoi(n - 1, a, c, b)
println('{0} to {1}'.format(c, a))
hanoi(n - 1, b, c, a)
println('{0} to {1}'.format(c, b))
three_colors_hanoi(n - 1, a, b, c)
}
}
three_colors_hanoi(3, 'A', 'B', 'C')
