Презентация на тему: "Рекурсия на примере игры "Ханойские башни" "

Рекурсия. Рекурсия. На примере игры «Ханойские башни» На примере игры «Ханойские башни»

Задача «Ханойские башни» Задача «Ханойские башни» Рассмотрим пример на Рассмотрим пример на рекурсивные алгоритмы — игру рекурсивные алгоритмы — игру «Ханойские башни», «Ханойские башни», придуманную ещё в 1883 году придуманную ещё в 1883 году Эдуардом Люка. Эдуардом Люка. Есть три стержня и 64 кольцаа́, Есть три стержня и 64 кольцаа́, нанизанных на них. В начале нанизанных на них. В начале все коа́льца находятся на все коа́льца находятся на первом стержне, причём все первом стержне, причём все коа́льца разного диаметра, и коа́льца разного диаметра, и меньшие коа́льца лежат на меньшие коа́льца лежат на боа́льших. За ход разрешается боа́льших. За ход разрешается взять верхнее кольцо с любого взять верхнее кольцо с любого стержня и положить на другой стержня и положить на другой стержень сверху, при этом стержень сверху, при этом запрещается класть большее запрещается класть большее кольцо на меньшее. Цель игры кольцо на меньшее. Цель игры состоит в том, чтобы состоит в том, чтобы переместить всю пирамиду с переместить всю пирамиду с первого стержня на второй. первого стержня на второй.

Пример программы на языке Паскаль: Пример программы на языке Паскаль: первая башня; y­ y­вторая башня; Program Recurs1; Program Recurs1; Var n, i:integer; Var n, i:integer; Procedure Move(n:integer; x,y,z:char); Procedure Move(n:integer; x,y,z:char); {x­{x­первая башня; Begin Begin     ifif    n>=1 then  begin n>=1 then  begin                        Move(n­1,x,z,y) { Move(n­1,x,z,y) {шаг 1шаг 1}}           write(x,’­>’,z,’  ‘);  { write(x,’­>’,z,’  ‘);  {шаг 2шаг 2}}                      inc(i); inc(i);                     if i mod 8 =0 then writeln; if i mod 8 =0 then writeln;                       move(n­1,y,x,z); move(n­1,y,x,z);                          end;    end;                 вторая башня; z­ z­третья башня третья башня}} Тело  рекурсивной  подпрограммы

{{главная программа главная программа}} write(‘введите количество дисков: введите количество дисков:‘);‘); Begin Begin     write(‘      Readln(n); Readln(n); Move(n,’x’,’y’,’z’);    {{вызов процедуры Move(n,’x’,’y’,’z’); вызов процедуры}} Readln; Readln; End.End.

Задача Задача У некоторого исполнителя, обрабатывающего числа, есть три команды: +1, +2, *3. Исполнитель получает на вход некоторое число и программу, представляющую собой некоторую последовательность вышеназванных команд. На выходе он выдает новое число - результат применения программы к исходному числу. Вам предлагается написать программу - анализатор данного исполнителя. На вход программе подаются два числа х и у, каждое из которых лежит в диапазоне от 0 до 200 (включая границы) и при этом гарантируется, что х меньше, либо равно у. Ваша программа должна подсчитать, сколько возможно построить различных программ для исполнителя, которые преобразуют число х в у. В качестве ответа нужно вывести одно целое число.