利用栈实现汉诺塔的调用。并在主函数中进行测试。要求: (1)定义栈以及栈的型。 (2)定义栈的各种操作。 (3)实现函数hanoi0。 (4)在main西数中,通过调用函数hanoi(3,a.b,c)
时间: 2023-05-17 08:05:05 浏览: 34
以下是利用栈实现汉诺塔的调用的代码:
```lua
-- 定义栈
local Stack = {}
Stack.__index = Stack
function Stack.new()
return setmetatable({data = {}}, Stack)
end
function Stack:push(value)
table.insert(self.data, value)
end
function Stack:pop()
return table.remove(self.data)
end
function Stack:top()
return self.data[#self.data]
end
function Stack:isempty()
return #self.data == 0
end
-- 定义汉诺塔函数
function hanoi0(n, a, b, c)
if n == 1 then
print("Move disk 1 from " .. a .. " to " .. c)
else
hanoi0(n-1, a, c, b)
print("Move disk " .. n .. " from " .. a .. " to " .. c)
hanoi0(n-1, b, a, c)
end
end
function hanoi(n, a, b, c)
local s = Stack.new()
s:push({n, a, b, c})
while not s:isempty() do
local item = s:pop()
local n, a, b, c = item[1], item[2], item[3], item[4]
if n == 1 then
print("Move disk 1 from " .. a .. " to " .. c)
else
s:push({n-1, b, a, c})
s:push({1, a, b, c})
s:push({n-1, a, c, b})
end
end
end
-- 测试
hanoi(3, "A", "B", "C")
```
输出结果为:
```
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
```