看到有人讨论递归,就想起这个用于讨论递归的经典问题:
三根柱子,N个大小不同的盘子,大盘子不能叠到小盘子上,每次只能把某根柱子的最上面的一个盘子移动到另一个柱子的最上面,开始所有盘子都在{dy}根柱子处,求解从把所有盘子移动到另一根柱子的方法。详细内容可参考:
直接贴代码(很简单,我就不写注释了):
hanoi <>function(n) {
tower <>list(1:n, NULL, NULL)
color <>rainbow(n)
bgcolor <>par('bg')
if (bgcolor == 'transparent') bgcolor <>'white'
draw.hanoi <>function() {
for (i in 1:3) {
screen(i)
plot(c(-n, n), c(0, n + 2), type = 'n', xlab = '', ylab = '')
rect(-n, 0, n, n + 2, border = bgcolor, col = bgcolor)
if (length(tower[[i]]) > 0) {
barplot(rev(tower[[i]]), add = TRUE, horiz = TRUE, col = color[rev(tower[[i]])])
barplot(-rev(tower[[i]]), add = TRUE, horiz = TRUE, col = color[rev(tower[[i]])])
}
}
}
move.hanoi <>function(k, from, to, via) {
if (k > 1) {
move.hanoi(k - 1, from, via, to)
move.hanoi(1, from, to, via)
move.hanoi(k - 1, via, to, from)
} else {
cat('Move ', tower[[from]][1], ' from ', LETTERS[from], ' to ', LETTERS[to], '\n')
tower[[to]] <>c(tower[[from]][1], tower[[to]])
tower[[from]] <>tower[[from]][-1]
draw.hanoi()
Sys.sleep(.5)
}
}
close.screen(all = TRUE)
split.screen(c(1,3))
draw.hanoi()
move.hanoi(n, 1, 2, 3)
}
hanoi(7)
tower <>list(1:n, NULL, NULL)
color <>rainbow(n)
bgcolor <>par('bg')
if (bgcolor == 'transparent') bgcolor <>'white'
draw.hanoi <>function() {
for (i in 1:3) {
screen(i)
plot(c(-n, n), c(0, n + 2), type = 'n', xlab = '', ylab = '')
rect(-n, 0, n, n + 2, border = bgcolor, col = bgcolor)
if (length(tower[[i]]) > 0) {
barplot(rev(tower[[i]]), add = TRUE, horiz = TRUE, col = color[rev(tower[[i]])])
barplot(-rev(tower[[i]]), add = TRUE, horiz = TRUE, col = color[rev(tower[[i]])])
}
}
}
move.hanoi <>function(k, from, to, via) {
if (k > 1) {
move.hanoi(k - 1, from, via, to)
move.hanoi(1, from, to, via)
move.hanoi(k - 1, via, to, from)
} else {
cat('Move ', tower[[from]][1], ' from ', LETTERS[from], ' to ', LETTERS[to], '\n')
tower[[to]] <>c(tower[[from]][1], tower[[to]])
tower[[from]] <>tower[[from]][-1]
draw.hanoi()
Sys.sleep(.5)
}
}
close.screen(all = TRUE)
split.screen(c(1,3))
draw.hanoi()
move.hanoi(n, 1, 2, 3)
}
hanoi(7)
这段代码我只在Linux下测试通过,效果凑合,Windows下没测试。