Как я могу избежать бесконечного количества операций в Башнях Ханоя - PullRequest
Новая
       38

Как я могу избежать бесконечного количества операций в Башнях Ханоя

0 голосов
/ 14 октября 2019

Мне нужно рассчитать количество шагов, необходимых для решения проблемы Ханойских башен (с помощью рекурсии). Мой сценарий работает только с меньшим количеством дисков, но если я попробую что-то вроде 12, это показывает, что мне нужно бесконечное количество операций для вычисления результата. Я не могу понять, где моя ошибка: 

steps = 0

def req_steps(num_disks):
    global steps
    if num_disks >= 1:
        req_steps(num_disks - 1)
        #steps += 1
        req_steps(num_disks - 1)
        steps += 1
        return steps
    return -1

if __name__ == '__main__':
    print(3, req_steps(12))

1 Ответ

1 голос
/ 14 октября 2019

Чтобы рассчитать количество ходов для Ханойских башен, есть (как минимум) три подхода.

1.) Решите Ханойские башни и используйте глобальную переменную для подсчета

  • добавить глобальную переменную в качестве счетчика
  • реализовать решение для Ханойских башен,
  • удалить все операторы печати
  • увеличить глобальный счетчик в каждом месте, гдеВы бы переместили диск

Теперь, чтобы запустить это решение. сбросьте глобальную переменную в 0, запустите ваш скрипт и проверьте результат глобального в конце

2.) Реализуйте Ханойские башни и позвольте функции возвращать количество ходов для каждого решения (и просто удалитеоператоры печати)

Это решение, на мой взгляд, чище, поскольку не требует глобального.

3.) Не пишите программу, а просто сделайте математическое доказательство того, чторешение 2 ** n -1 (подход называется математической индукцией)

Attached Решение для 2.) 

def req_steps(num_disks):
    if num_disks > 1:
        steps = req_steps(num_disks - 1)
        steps += req_steps(num_disks - 1)
        steps += 1
        return steps
    return 1

if __name__ == '__main__':
    for i in range(1,13):
        print("%2d %4d %4d" % (i, req_steps(i), 2 ** i - 1))

Вывод должен выглядеть так: 

 1    1    1
 2    3    3
 3    7    7
 4   15   15
 5   31   31
 6   63   63
 7  127  127
 8  255  255
 9  511  511
10 1023 1023
11 2047 2047
12 4095 4095
...