我试图用堆栈解决河内塔的问题。这里是我的代码：使用堆栈的河内Python解决方案的递归塔

Init_stack = [0,1,2,3] 
Buffer_stack = [] 
Final_stack = [] 
n = len(Init_stack) 
def move_disks(Init_stack, Buffer_stack, Final_stack, n): 
    if n == 0: 
     return 
    elif n == 1: 
     Final_stack.append(Init_stack.pop()) 
    elif n == 2: 
     Buffer_stack.append(Init_stack.pop()) 
     Final_stack.append(Init_stack.pop()) 
     Final_stack.append(Buffer_stack.pop()) 
    else: 
     move_disks(Init_stack, Final_stack, Buffer_stack, n-1) 
     Final_stack.append(Init_stack.pop()) 
     move_disks(Buffer_stack, Init_stack, Final_stack,n-1)

这工作完全正常的时候Init_stack的尺寸很小，比如< 10.但是，当我在一个大小为100 Init_stack运行这段代码，程序花了很长的时间才能完成。你能告诉我为什么需要这么长时间吗？

来源

2015-07-18 JonAmen

使用100个盘意味着你必须做'2^100 - 1 = 1.27e30'移动。对于Python来说这可能太多了？ – Delgan

河内问题的塔有指数时间complexit O（2^n）具体它需要2^n - 1个移动。这可能是http://stackoverflow.com/questions/12383044/complexity-for-towers-of-hanoi的副本 –

河内的塔需要(2^n)-1其中n是环的数量。即使极其高效的解决方案也需要很长时间才能完成Python中的许多操作。

(2^10)-1等于1023（正如每位计算机科学家所知道的），但(2^100)-1是一个31位十进制数。

来源

2015-07-18 21:39:51

-1

您也可以解决使用递归

这需要时间，因为问题的复杂性是指数型都需要大量的时间来解决的。

Click here for recursive code

来源

2017-01-08 17:52:57

这个样本不是那么长，请把它包含到你的答案中。 – ppasler

使用堆栈的河内Python解决方案的递归塔

回答

您也可以解决使用递归

相关问题