アルゴリズムーハノイの塔、9枚の円盤は511回で隣に移動

n 枚の円盤は、2ⁿー1 回で移動

<p>n 枚の円盤のとき
2ⁿー1 回で移動
— 0        [1, 2, 3, 4, 5, 6, 7, 8, 9] [] []
— 511    [] [1, 2, 3, 4, 5, 6, 7, 8, 9] []
Ziel !!
end : None

A = [[1, 2, 3, 4, 5, 6, 7, 8, 9], [], []]
ln = len(A[0])

def hanoi(nn, count):

#  count += 1
  print("---",count, nn, A[0], A[1], A[2])
  
  if count> 100 *ln:
    return "fehler ##"

  if count>0 and (len(A[1]) == ln or len(A[2]) == ln):
    print("Ziel !!")
    return "Ziel !!"

  if len(A[nn]) == 0:
    nn += 1
    if nn > 2 :
      nn = 0
    print("1:", nn)
    hanoi(nn, count)
  else:
    mm =(nn+1) % 3
    print("--mm  ",mm)
    print("2-m:", nn, A[nn], mm, A[mm])
    if len(A[mm]) == 0 or  A[nn][0] < A[mm][0]:
      count += 1
      A[mm].insert(0, A[nn][0])
      A[nn].remove(A[nn][0])
      print(nn, A[nn], mm, A[mm])
      nn = mm
      nn += 1
      if nn>2:
        nn = 0
 #     print("2:", nn, A[nn], mm, A[mm])
      hanoi(nn, count)
    else:
      mm = (nn + 2) % 3
      print("+++m  ",mm)
      print("++2-m:", nn, A[nn], mm, A[mm])
      if len(A[mm]) == 0 or  A[nn][0] < A[mm][0]:
        count += 1
        A[mm].insert(0, A[nn][0])
        A[nn].remove(A[nn][0])
#        print(count, A[nn], A[mm])
        print("2-jmp:", nn, A[nn], mm, A[mm])
        nn = mm
        nn += 1
        if nn>2:
          nn = 0
#       print("2-jmp:", nn, A[nn], mm, A[mm])
        hanoi(nn, count)
      else:
        print("3-skip:", nn,A[nn])
        nn += 1
        if nn>2:
          nn = 0
#        print("3-skip:", nn,A[nn])
        hanoi(nn, count)

ss = hanoi(0, 0)

print(" end :",ss)

コメントを残す

メールアドレスが公開されることはありません。