Подкуп охранника при рекурсии с помощью python - PullRequest
Новая
       38

Подкуп охранника при рекурсии с помощью python

0 голосов
/ 02 мая 2020

Мне задают следующую проблему: «Есть девять охранников, каждый охраняет дверь. Я заперт в хранилище с монетами. Чтобы пройти охранника и соответствующую дверь, я могу подкупить его монетой. Я не разрешено брать с собой более 4 монет. Мне также нужно подкупить охранника на обратном пути. Однако охранник может хранить столько монет, сколько я хочу. Сколько монет должно быть хотя бы в хранилище, чтобы я мог передать всех девяти охранников? "

Я думал о том, как решить эту проблему с помощью рекурсии, например, как в случае с башней Ханоя, но не смог найти решение. Кто-нибудь знает, как это решить?

1 Ответ

0 голосов
/ 08 мая 2020

Вам не нужно писать код для этого. Попробуй разобраться в обратном направлении:

  • Чтобы пройти охранника № 9, тебе нужна 1 монета, чтобы подкупить его
  • Чтобы пройти охранников 8-9, тебе нужно 2 монеты
  • Чтобы пройти охранников 6-9, вам нужно 4 монеты

Но пройти охранника № 5 будет сложно, потому что вы не можете нести 5 монет одновременно, поэтому вы:

  • Подойдите к охраннику № 5 с 4 монетами
  • Подкупите его 1, чтобы он пропустил 3 монеты
  • Скажите, чтобы он хранил 2 монеты для Вы
  • Используйте последнюю монету для возврата через дверь № 5
  • Затем вы снова подходите к охраннику № 5 с 3 fre sh монетами
  • Используйте одну, чтобы подкупить его
  • Таким образом, вы берете с собой 2 монеты, а в сочетании с 2 сохраненными монетами вы получаете охранников 6-9

Поэтому вы видите, что вам нужно 7 монет , чтобы пройти мимо охранников 5-9

Вы используете тот же подход, чтобы выяснить, как пройти мимо охранников 1-4

...