Geek Answers Handbook

Hanoi Modified Tower

We all know that the minimum number of moves required to solve the classic towers of the Hanoi problem is 2 n -1. Suppose now that some of the disks are the same size. What will be the minimum number of steps to solve the problem in this case.

Suppose there are three drives. In the classical problem, the minimum number of necessary moves should be 7. Now suppose that the size of disk 2 and disk 3 is the same. In this case, the minimum number of moves required should be:

  • Move disc 1 from a to b.
  • Move disc 2 from a to c.
  • Move disc 3 from a to c.
  • Move disc 1 from b to c.

which is 4 moves. Now, given the total number of drives n and sets of drives with the same size, find the minimum number of moves to solve the problem. This is a friend’s challenge, so calls for a solution are welcome. Thank you

+4
source share
3 answers

Consider a tower of size n. The upper disk must be moved 2 n-1 times, the second disk 2 n-2 times and so on, until the lower disk is moved only once, a total of 2 n -1 moves. Moving each drive takes exactly one revolution.

   1      moved 8 times
  111     moved 4 times
 11111    moved 2 times
1111111   moved 1 time   => 8 + 4 + 2 + 1  ==  15

, x- , , , , , x . , "" "", .

   1
  111                       1      moved 8 times
  111       collapse       222     moved 4 times, taking 2 turns each
 11111    ----------->    11111    moved 2 times
1111111                  3333333   moved 1 time, taking 3 turns
1111111                            => 8 + 4*2 + 2 + 1*3  ==  21
1111111

, .

Python . , "" , disks[i] i - ,

disks = [1, 2, 1, 3]           # weight of collapsed disks, top to bottom
print sum(d * 2**i for i, d in enumerate(reversed(disks)))

, , , :

disks = [1, 3, 3, 5, 7, 7, 7]  # size of disks, top to bottom
last, t, s = disks[-1], 1, 0
for d in reversed(disks):
    if d < last: t, last = t*2, d
    s = s + t
print s

21, .

+4

. n = 7 , , 7 ( n). , , 2 n -1.

tobias_k, . . , .

< >

1

n=7   //disc sizes (1,2,3,3,4,5,5)
g=5   //group sizes (1,1,2,1,2)
      //group index (1,2,3,4,5)

number of moves = sum( g-size * 2^( g-count - g-index ) )

in this case
moves = 1*2^4 + 1*2^3 + 2*2^2 + 1*2^1 + 2*2^0
      = 16 + 8 + 8 + 2 + 2
      = 36

2

n=7   //disc sizes (1,1,1,1,1,1,1)
g=1   //group sizes (7)
      //group index (1)

number of moves = sum( g-size * 2^( g-count - g-index ) )

in this case
moves = 7*2^0
      = 7

3

n=7   //disc sizes (1,2,3,4,5,6,7)
g=7   //group sizes (1,1,1,1,1,1,1)
      //group index (1,2,3,4,5,6,7)

number of moves = sum( g-size * 2^( g-count - g-index ) )

in this case
moves = 1*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0
      = 64 + 32 + 16 + 8 + 4 + 2 + 1
      = 127

: sum (2 n-1) = 2 n - 1

+1

Github Gist C . , , - , .

n . . arr . A, B C - .

swap(int, int), partition(int, int) qSort(int, int) .

toh(char, char, char, int, int) - .

: , . , . , , , .

+1

More articles:


All Articles