The recursive programming solution for this problem is defined, at a high level,

Question

The recursive programming solution for this problem is defined, at a high level, as follows:

?     Label your pegs source, helper, target

?     Let n be the total number of discs

?     Number the discs from 1 (smallest, topmost) to n (largest, bottommost)

?     At the start of your program, target and helper are both empty. source has the initial tower: [4,3,2,1]

?   Define a subroutine, hanoi, that takes 4 arguments: number of discs, source, helper, and target.

?     To move n discs from source to target:

a.    Call hanoi recursively to move n?1 discs from source to helper. This leaves disc n alone on source

b.    Move disc n from source to target

c.    Call hanoi recursively to move n?1 discs from helper to target

# Subroutine hanoi

# Moves a tower of size n from source to target

# Uses helper as a temp array to store discs

#

# Arguments:    n = length of source

#               source = array representing the source tower

#               helper = temp array representing the helper tower

#               target = array representing the final tower

def hanoi(n, source, helper, target):

if n > 0

# move tower of size n - 1 from source to helper by recursively

     # calling hanoi. Use target as the temp array.

     # if source is nonempty

# pop a disc off source (use source.pop())

     # append it to target (use target.append())

# move tower of size n-1 from helper to target

# by recursively calling hanoi. Use source as the temp array.

if __name__ == "__main__":

source = [4,3,2,1]

target = []

helper = []

# move the tower from source to target, use helper as helper

hanoi( len(source), source, helper, target)

# Expected result of the following print statement:

# [] [] [4, 3, 2, 1]

print source, helper, target

Explanation / Answer

# your code goes here

def TOH(n,S,D,A):

if n==1:

print 'Move disk 1 from '+S+' to '+D

return

TOH(n-1,S,A,D)

print 'Move disk '+str(n)+' from '+S+' to '+D

TOH(n-1,A,D,S)

"""Assume if there are 4 pegs and S is Source and D is Destination and A is Auxillary

"""

TOH(4,'S','D','A')

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.