Инструменты пользователя
basics_of_algorithms:recursion
Различия
Здесь показаны различия между двумя версиями данной страницы.
| Предыдущая версия справа и слева Предыдущая версия Следующая версия | Предыдущая версия | ||
|
basics_of_algorithms:recursion [2023/10/04 21:13] werwolf [Рекурсивный алгоритм для Ханойской башни] |
basics_of_algorithms:recursion [2023/10/04 21:22] (текущий) werwolf [Достоинства и недостатки рекурсии] |
||
|---|---|---|---|
| Строка 474: | Строка 474: | ||
| Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»: | Только мы знаем, что рекурсия должна где-то останавливаться. В нашем случае минимальная задача, которую мы можем решить — перенос башни из одного кольца. Она решается тривиально: одно кольцо мы можем перенести безо всяких условий, поэтому нам достаточно просто вывести номера стержней «откуда» и «куда»: | ||
| - | <code> | + | <code javascript> |
| const hanoi = (height, from, to) => { | const hanoi = (height, from, to) => { | ||
| if (height === 1) { | if (height === 1) { | ||
| Строка 505: | Строка 505: | ||
| </code> | </code> | ||
| - | Python | ||
| - | <code> | + | <details> |
| + | <summary>Python</summary> | ||
| + | |||
| + | <code python> | ||
| def hanoi(height, start, to): | def hanoi(height, start, to): | ||
| if height == 1: | if height == 1: | ||
| Строка 535: | Строка 537: | ||
| # => с 3 на 2 | # => с 3 на 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 571: | Строка 575: | ||
| // => с 3 на 2 | // => с 3 на 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| class App { | class App { | ||
| public static void hanoi(int height, int from, int to) { | public static void hanoi(int height, int from, int to) { | ||
| Строка 606: | Строка 612: | ||
| // => с 3 на 2 | // => с 3 на 2 | ||
| </code> | </code> | ||
| + | </details> | ||
| https://replit.com/@hexlet/hanoi | https://replit.com/@hexlet/hanoi | ||
| Строка 615: | Строка 622: | ||
| Чтобы определить номер вспомогательного стержня, надо написать сложное условие: | Чтобы определить номер вспомогательного стержня, надо написать сложное условие: | ||
| - | <code> | + | <code javascript> |
| if (from === 1 && to === 2 || from === 2 && to === 1) { | if (from === 1 && to === 2 || from === 2 && to === 1) { | ||
| temporary = 3; | temporary = 3; | ||
| Строка 625: | Строка 632: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if (start == 1 and to == 2) or (start == 2 and to == 1): | if (start == 1 and to == 2) or (start == 2 and to == 1): | ||
| temporary = 3 | temporary = 3 | ||
| Строка 636: | Строка 644: | ||
| </code> | </code> | ||
| - | PHP | + | </details> |
| + | |||
| + | <details> | ||
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 649: | Строка 660: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (from == 1 && to == 2 || from == 2 && to == 1) { | if (from == 1 && to == 2 || from == 2 && to == 1) { | ||
| temporary = 3; | temporary = 3; | ||
| Строка 661: | Строка 674: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы: | Несмотря на то, что логика этого кода понятна, само условие выглядит громоздким. Разберем по шагам, как оно работает. В коде используют три константы: | ||
| Строка 672: | Строка 686: | ||
| Обратите внимание, что сумма ''from'', ''to'' и ''temporary'' всегда равна 6. Можно взять число 6 и вычесть из него номера стержней ''from'' и ''to'', и тогда мы узнаем номер вспомогательного стержня: | Обратите внимание, что сумма ''from'', ''to'' и ''temporary'' всегда равна 6. Можно взять число 6 и вычесть из него номера стержней ''from'' и ''to'', и тогда мы узнаем номер вспомогательного стержня: | ||
| - | <code> | + | <code javascript> |
| const temporary = 6 - from - to; | const temporary = 6 - from - to; | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| temporary = 6 - start - to | temporary = 6 - start - to | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| $temporary = 6 - $start - $to; | $temporary = 6 - $start - $to; | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| var temporary = 6 - from - to; | var temporary = 6 - from - to; | ||
| </code> | </code> | ||
| + | </details> | ||
| Этот код гораздо проще, но требует разъяснений. В начале каждой рекурсивной функции мы должны проверить **граничное условие** — оно помогает не войти в бесконечный вызов. В задаче о ханойской башне граничное условие — это башня из одного кольца. | Этот код гораздо проще, но требует разъяснений. В начале каждой рекурсивной функции мы должны проверить **граничное условие** — оно помогает не войти в бесконечный вызов. В задаче о ханойской башне граничное условие — это башня из одного кольца. | ||
| Строка 700: | Строка 720: | ||
| Если встретилась такая башня, надо перенести кольцо и завершить работу: | Если встретилась такая башня, надо перенести кольцо и завершить работу: | ||
| - | <code> | + | <code javascript> |
| if (height === 1) { | if (height === 1) { | ||
| console.log("с %d на %d", from, to); | console.log("с %d на %d", from, to); | ||
| Строка 707: | Строка 727: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| if height == 1: | if height == 1: | ||
| print(f'с {start} на {to}') | print(f'с {start} на {to}') | ||
| return | return | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 725: | Строка 748: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| if (height == 1) { | if (height == 1) { | ||
| System.out.println(String.format("с %d на %d", from, to)); | System.out.println(String.format("с %d на %d", from, to)); | ||
| Строка 734: | Строка 759: | ||
| } | } | ||
| </code> | </code> | ||
| + | </details> | ||
| Если высота башни ''height'' больше единицы, мы упрощаем задачу и сводим ее к самой себе. В случае ханойской башни такая задача — перенести башни высотой ''height - 1'' на вспомогательный стержень. После этого можно перенести самое большое кольцо на стержень «куда», а потом — переместить на него маленькую башню со вспомогательного стержня: | Если высота башни ''height'' больше единицы, мы упрощаем задачу и сводим ее к самой себе. В случае ханойской башни такая задача — перенести башни высотой ''height - 1'' на вспомогательный стержень. После этого можно перенести самое большое кольцо на стержень «куда», а потом — переместить на него маленькую башню со вспомогательного стержня: | ||
| - | <code> | + | <code javascript> |
| hanoi(height - 1, from, temporary); | hanoi(height - 1, from, temporary); | ||
| console.log("с %d на %d", from, to); | console.log("с %d на %d", from, to); | ||
| Строка 743: | Строка 769: | ||
| </code> | </code> | ||
| - | Python | + | <details> |
| + | <summary>Python</summary> | ||
| - | <code> | + | <code python> |
| hanoi(height - 1, start, temporary) | hanoi(height - 1, start, temporary) | ||
| print(f'с {start} на {to}'); | print(f'с {start} на {to}'); | ||
| hanoi(height - 1, temporary, to) | hanoi(height - 1, temporary, to) | ||
| </code> | </code> | ||
| + | </details> | ||
| - | PHP | + | <details> |
| + | <summary>PHP</summary> | ||
| - | <code> | + | <code php> |
| <?php | <?php | ||
| Строка 760: | Строка 789: | ||
| hanoi($height - 1, $temporary, $to); | hanoi($height - 1, $temporary, $to); | ||
| </code> | </code> | ||
| + | </details> | ||
| - | Java | + | <details> |
| + | <summary>Java</summary> | ||
| - | <code> | + | <code java> |
| hanoi(height - 1, from, temporary); | hanoi(height - 1, from, temporary); | ||
| System.out.println(String.format("с %d на %d", from, to)); | System.out.println(String.format("с %d на %d", from, to)); | ||
| hanoi(height - 1, temporary, to); | hanoi(height - 1, temporary, to); | ||
| </code> | </code> | ||
| + | </details> | ||
| ===== Достоинства и недостатки рекурсии ===== | ===== Достоинства и недостатки рекурсии ===== | ||
| Строка 775: | Строка 807: | ||
| Еще один плюс — знания о рекурсии открывают программисту новые возможности. Многие задачи можно решить и с помощью циклов, но есть и те, в которых не обойтись без рекурсии. Например, синтаксический разбор арифметических выражений можно сделать только рекурсивно. Вот так выглядит сложное арифметическое выражение, если решать его через рекурсивный алгоритм: | Еще один плюс — знания о рекурсии открывают программисту новые возможности. Многие задачи можно решить и с помощью циклов, но есть и те, в которых не обойтись без рекурсии. Например, синтаксический разбор арифметических выражений можно сделать только рекурсивно. Вот так выглядит сложное арифметическое выражение, если решать его через рекурсивный алгоритм: | ||
| - | <code> | + | <code javascript> |
| sin(a) + (3 + 2 * b ** 7 - cos (a / b)) | sin(a) + (3 + 2 * b ** 7 - cos (a / b)) | ||
| </code> | </code> | ||
basics_of_algorithms/recursion.1696443233.txt.gz · Последние изменения: 2023/10/04 21:13 — werwolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Share Alike 4.0 International
