腾讯云开发者社区

1. 汉诺塔问题的非递归解法（python语言类解法）

#!/usr/bin/env python#coding:utf-8import sysimport timereload(sys)sys.setdefaultencoding('utf-8')class Mycolumns(object):    val=0    #__slots__ = ['plates','name']    def __init__(self,name='',plates_num=0):        self.name = name        self.plates = []        if plates_num > 0 :            for i in range(0,plates_num):                self.plates.append(n-i)    @staticmethod    def fun():        Mycolumns.val +=1        print"this is the %d th time to move" %(Mycolumns.val)复制

【这段可以用类方法代替】

【

@classmethod

    def fun(cls):

        cls.val +=1

        print"this is the %d th time to move" %(cls.val)

】

def initialize(n):    stack = []    mycolumn1 = Mycolumns('A',n)    if n%2 == 0:        mycolumn2 = Mycolumns('B')        mycolumn3 = Mycolumns('C')        index = 2    else:        mycolumn2 = Mycolumns('C')        mycolumn3 = Mycolumns('B')        index = 1    stack.append(mycolumn1)    stack.append(mycolumn2)    stack.append(mycolumn3)    return stack,indexdef nowcolumn(i,stack):    for item in stack:        if i in item.plates:            return itemdef nextcolumn(i,stack):    for item in stack:        if i in item.plates:            if i%2!=0:                next = (stack.index(item)+1)%3            else:                next = (stack.index(item)+2)%3            #print "%d next column is %s"%(i,stack[next].name)            return stack[next]def move(nowcolumn,nextcolumn):    n = nowcolumn.plates.pop()    nextcolumn.plates.append(n)    print "move plate %d from %s to %s" %(n,nowcolumn.name,nextcolumn.name)    Mycolumns.fun()def hannuoyi(n):    stack,index = initialize(n)    #max = pow(2,n)-1    #k =0    #while(k<max):复制

　　 FINAL = []　　 for i in range(0,n):    　　FINAL.append(n-i)　　 while(stack[index].plates!=FINAL):复制

        for i in range(1,n+1):            #print "i value is %d" %(i)            if(nowcolumn(i,stack).plates.index(i)==len(nowcolumn(i,stack).plates)-1 and (nextcolumn(i,stack).plates==[] or i< nextcolumn(i,stack).plates[-1])):                move(nowcolumn(i,stack),nextcolumn(i,stack))                #k = k+1            else:                pass                #print"can not move plate %d" %(i)    print stack[0].plates,stack[0].name    print stack[1].plates,stack[1].name    print stack[2].plates,stack[2].nameif __name__=="__main__":    n=3    hannuoyi(n) 复制

　　2. 汉诺塔问题的非递归解法（python语言过程式解法）

#!/usr/bin/env python

#coding:utf-8

 

import sys

import time

reload(sys)

sys.setdefaultencoding('utf-8')

global a

a =0

def fun():

    global a

    a = a+1

    print"this is the %d th time to move" %(a)

 

def nowcolumn(i,stackA,stackB,stackC):

    if i in stackA:

        return stackA

    elif i in stackB:

        return stackB

    else:

        return stackC

 

def nextcolumn(n,i,stackA,stackB,stackC):

    if n%2==0:

        if i in stackA:

            if i%2!=0:

                newcolumn = stackB

            else:

                newcolumn = stackC

        if i in stackB:

            if i%2!=0:

                newcolumn = stackC

            else:

                newcolumn = stackA

        if i in stackC:

            if i%2!=0:

                newcolumn = stackA

            else:

                newcolumn = stackB

    else:

        if i in stackA:

            if i%2==0:

                newcolumn = stackB

            else:

                newcolumn = stackC

        if i in stackB:

            if i%2==0:

                newcolumn = stackC

            else:

                newcolumn = stackA

        if i in stackC:

            if i%2==0:

                newcolumn = stackA

            else:

                newcolumn = stackB

    return newcolumn

def move(nowcolumn,nextcolumn):

    n = nowcolumn.pop()

    nextcolumn.append(n)

    print "move plate %d" %(n)

    fun()

 

 

def hannuoyi(n):

    stackA = []

    stackB = []

    stackC = []

    FINAL = []

    for i in range(0,n):

        stackA.append(n-i)

        FINAL.append(n-i)

    print stackA,stackB,stackC,FINAL

 

    while(stackC!=FINAL):

        for i in range(1,n+1):

            print "i value is %d" %(i)

            if(nowcolumn(i,stackA,stackB,stackC).index(i)==len(nowcolumn(i,stackA,stackB,stackC))-1 and (nextcolumn(n,i,stackA,stackB,stackC)==[] or i< nextcolumn(n,i,stackA,stackB,stackC)[-1])):

                move(nowcolumn(i,stackA,stackB,stackC),nextcolumn(n,i,stackA,stackB,stackC))

            else:

                print"can not move plate %d" %(i)

            print stackA,stackB,stackC

if __name__=="__main__":

    n=6

    hannuoyi(n)

2. 汉诺塔问题的递归解法（python语言）

#!/usr/bin/env python

#coding:utf-8

 

import sys

 

reload(sys)

sys.setdefaultencoding('utf-8')

global a

a =0

def fun():

    global a

    a = a+1

 

def hannuoyi(n,A,B,C):

    if n==1:

        move(1,A,C)

    else:

        hannuoyi(n-1,A,C,B)

        move(n,A,C)

        hannuoyi(n-1,B,A,C)

 

def move(n,tempA,tempB):

    print "move plate %d from column %s to column %s" %(n,tempA,tempB)

    fun()

if __name__=="__main__":

    hannuoyi(3,'A','B','C')

    print "total:we need %d steps"%(a)