読者です 読者をやめる 読者になる 読者になる

ハノイの塔 ver.2

Ruby/Rails

 円盤がN枚のときのハノイの塔を完全に攻略することができました。前回のものを再帰的手法を用いて洗練させました。
 @towersは3つの塔を配列として表現したもの(@towers[0]が左、@towers[1]が真ん中、@towers[2]が右の塔)、timesは円盤を移動させた回数、nは円盤の枚数、startは最初に円盤が積んである塔の番号、goalは円盤を積んで完成させる塔の番号、tempはそのどちらでもない一時的に円盤を積んでおく塔の番号(start, goal, tempは0, 1, 2のどれかをとる)、をそれぞれ指します。
 ハノイの塔の攻略法は、「n-1枚のハノイの塔を別に作って、n枚目の円盤を右側の塔に移し、その上に再度n-1枚のハノイの塔を作る」というものです。さらに、n-1枚のハノイの塔を作るには、n-2枚のハノイの塔をまたどこかに作って、n-1枚目の円盤をどこかに移し、n-2枚のハノイの塔をその上に作ることが必要です。これが「n-3, n-4,...,1」と続くわけです。数学の漸化式のような発想です。

@towers = [(1..ARGV[0].to_i).to_a, [], []]
@times = 0

def hanoi(n, start, goal)
	temp = 3 - start - goal
	if n == 1
		@towers[goal].unshift(@towers[start].shift)
		result
	else
		hanoi(n - 1, start, temp)
		@towers[goal].unshift(@towers[start].shift)
		result
		hanoi(n - 1, temp, goal)
	end
end

def result
	p @towers
	puts "--"
	@times += 1
end

hanoi(ARGV[0].to_i, 0, 2)
puts "total times: #{@times}"

実行結果

c:\codes\ruby\exercise>ruby hanoi.rb 3
[[2,3],[],[1]]
--
[[3],[2],[1]]
--
[[3],[1,2],[]]
--
[[],[1,2],[3]]
--
[[1],[2],[3]]
--
[[1],[],[2,3]]
--
[[],[],[1,2,3]]
--
total times: 7