Easy Tutorial
❮ Android Tutorial Audiomanager Verilog2 Random ❯

Python Hanoi Tower

Category Programming Technology

There are three pillars A, B, and C. Pillar A has N disks of different sizes, with larger disks at the bottom and smaller disks at the top. The task is to move all the disks from pillar A to pillar C, maintaining the rule that larger disks are below smaller ones (with the help of pillar B). Each move can only move the top disk of one pillar to the top of another pillar. Please output the process of moving the disks.

Solution

This is a type of dynamic programming problem, which is simpler and more convenient to implement using recursion.

For the problem "move moveSum disks from pillar from to pillar to (with the help of pillar by)", we can achieve this through the following three steps:

Execution process is as follows:

>

Original link: https://blog.51cto.com/myunix/2399892

#

-

** hhhhhh

* 242**[email protected]

  1. Define three types of moves: A2C(n), B2C(n), A2B(n), where n disks from A to B, n disks from A to C, and n disks from A to B are essentially the same in terms of method and steps, just using different temporary storage points, so the number of steps required for these three moves can all be represented by func(n).

PS: Once the largest disk is moved to the destination, it no longer interferes with the movement of the other disks, as they are all smaller, so we can directly exclude the largest disk from our considerations without affecting subsequent moves.

  1. Now, let's look at the specific situation: what steps are needed to move n disks from A to C, i.e., to solve func(n);

First step: Move n-1 disks from A to B, represented by func(n-1);

Second step: Move the remaining largest disk from A to C, which is 1 move;

Third step: Move n-1 disks from B to C, which can still be represented by func(n-1).

  1. Conclusion: func(n) = 2*func(n-1) + 1

  2. Boundary condition: 0 disks need 0 moves, so func(0) = 0.

Code:

def func(n):
    if n == 0:
        return 0
    return 2*func(n-1) + 1

** hhhhhh

* 242**[email protected]

** Click to Share Notes

Cancel

-

-

-

❮ Android Tutorial Audiomanager Verilog2 Random ❯