具体的编程就是简单的穷举法了，因为左右对称，所以有两种解法。直接上个Python代码：
# -*- coding:UTF-8 -*-
# 计算青蛙跳石头过河问题：
# 每只青蛙可以向前跳一步到空的石头或越过前面的一只青蛙跳到石头
# 初始状态：>>>+<<<
# 最终状态：<<<+>>>
# +为空石头，>和<为方向相反的青蛙
trace_stack = []
def recursive(frog_list, final_list):
global trace_stack
if frog_list == final_list:
trace_stack.append(frog_list)
return True
index = frog_list.index(‘+’)
# 空石头右边第一只
if index+1 < len(frog_list):
if frog_list[index+1] == ‘<‘:
temp = frog_list[:]
temp[index],temp[index+1] = temp[index+1],temp[index]
if recursive(temp, final_list):
trace_stack.append(frog_list)
return True
# 空石头右边第二只
if index+2 < len(frog_list):
if frog_list[index+2] == ‘<‘:
temp = frog_list[:]
temp[index],temp[index+2] = temp[index+2],temp[index]
if recursive(temp, final_list):
trace_stack.append(frog_list)
return True
# 空石头左边第一只
if index–1 >= 0:
if frog_list[index–1] == ‘>’:
temp = frog_list[:]
temp[index],temp[index–1] = temp[index–1],temp[index]
if recursive(temp, final_list):
trace_stack.append(frog_list)
return True
# 空石头左边第二只
if index–2 >= 0:
if frog_list[index–2] == ‘>’:
temp = frog_list[:]
temp[index],temp[index–2] = temp[index–2],temp[index]
if recursive(temp, final_list):
trace_stack.append(frog_list)
return True
return False
def main():
global trace_stack
frog_count = 3
frog_str = ‘>’*frog_count + ‘+’ + ‘<‘*frog_count
frog_list = [i for i in frog_str]
final_list = frog_list[:]
final_list.reverse()
if recursive(frog_list, final_list):
try:
while True:
line = trace_stack.pop()
print “”.join(line)
except:
pass
if __name__ == “__main__”:
main()
运行结果：
