Make your own free website on Tripod.com

יסודות  מדעי  המחשב. יסודות- 2. מחברים: פרופ'  מרדכי  בן-ארי,  דר'  ארנה  ליכטנשטיין,  חנה  מחלב, אלה  צור,  נורית  רייך.   צוות  הפיתוח: פרופ'  מרדכי  בן-ארי, דר' דוד  גינת, דר'  ארנה  ליכטנשטיין,  חנה  מחלב, אלה  צור, יפעת  קוליקנט, נורית  רייך.  מהדורה  ניסויית, 1998

 Основания  компьютерных  наук. Основания-2. Разработчики: проф. Мордехай Бен-Ари, д-р Давид Гинат, д-р Орна Лихтенштейн, Хана Махлев, Эла Цур, Ифат Куликант, Нурит Райх.      Пробное издание, 1998

 

Глава  5. Рекурсия

Ключевые  слова. Рекурсия, рекурсивная  процедура, рекурсивная  функция, шаг  рекурсии, условие  останова.

5.1.Что  такое  рекурсия?

На  секунду  задумаемся ... Посмотри  на  рисунки  следующей  страницы  и  дай  наиболее  меткое  определение  тому, что  ты  видишь. (Рис.)

Общим  для  всех  приведенных  набросков  является  тот  факт, что  каждый  предмет  содержит  последовательность  одинаковых  предметов - один  меньше  предыдущего. На  рисунке  a’  - художник, рисующий  картину, и  на  ней - художник, рисующий  картину, на  которой  художник, рисующий  картину, на  которой  художник  и  т.д. Описание  наброска  b’: коробка, внутри  которой  коробка, внутри  которой коробка, внутри  которой - часы.   Описание  наброска  c’: яйцо, внутри  которого  яйцо, внутри  которого  яйцо, внутри  которого - ципленок.  Сущность, определяемая  в  терминах  самой  себя,  называется  рекурсивной.    На  рисунке  a’   процессу  уменьшения   картин  нет  конца, а  на  рисунках   b’ и c’  -  процесс  уменьшения  останавливается. В  этой  главе  мы  научимся  разрабатывать  рекурсивные  алгоритмы  и  реализовать  их  на  Паскале. Рекурсивный  алгоритм  снова  и  снова  осуществляет  одно  и  то  же  задание  над  уменьшающимися  данными  до  тех  пор, пока  вычисления  не  прекратятся  над  определенным  данным.

Вопрос  5.1. Найди  дополнительные  предметы  из  повседневной  жизни, похожие  по  своей природе  на  те, что  представлены  на  набросках  a’ - c’ .

 

5.2. Рекурсивные  алгоритмы

Давайте  опишем  себе  робота, который  берет  в  свои  рукм  коробку, описанную  в  наброске  b’. Нам  нужно, чтобы  робот  нашел  часы  и  надел  их.

На  секунду  задумаемся ... Какие  действия  осуществит  робот, чтобы  найти  часы?

kЕсли  робот  нашел  часы - ему  следует  их  надеть  и  сказать  “спасибо”

     иначе  он  должен  открыть  коробку  и  извлечь  ее  содержимое.

             если  содержимое ящика - часы, роботу  надо  их  надеть  и  сказать  “спасибо”

             иначе  он  должен  открыть  коробку  и  извлечь  ее  содержимое.

                    если  содержимое ящика - часы, роботу  надо  их  надеть  и  сказать  “спасибо”

                    иначе  он  должен  открыть  коробку  и  извлечь  ее  содержимое.

                            если  содержимое ящика - часы...

На  секунду  задумаемся ... Когда  процесс  завершается?

Процесс завершится, когда  часы  будут  найдены. Если  число  коробок  неизвестно  заранее, мы  не  можем  написать  алгоритм  в  виде  последовательности  условных  операторов. Вместо  использования  цикла  разработаем  алгоритм, базирующийся  на  том  факте, что  вскрытие  внутренней  коробки  есть  задание, тождественное  вскрытию  внешней  коробки.

Обрати  внимание: последовательность  команд  повторяет  себя, а  при  каждом  повторении  она  действует  с  меньшей  по  размеру  коробкой  до  тех  пор, пока  часы  не  обнаружатся. Нахождение  часов  приводит  к  остановке  процесса  и  останову  алгоритма:

если  нашел  часы  то

          надень  их

          скажи  “спасибо”

На  секунду  задумаемся ... Если  робот  обнаруживает  не  часы, а  коробку, то  какую  последовательность  заданий  ему  надо  выполнить, чтобы  продолжить  поиск  часов?

Последовательность  заданий  такая:

           открой  коробку

           достань  ее  содержимое

           повтори  эти  же  операции, но в  этот раз  с  содержимым  коробки

Ниже  дан  алгоритм  нахождения  часов, соответствующий  любому размеру  ввода:

k АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(ПРЕДМЕТА)

             если  предмет  это  часы  то

                       надеть  их

                       сказать  “спасибо”

             иначе  {предмет  есть  коробка}

                       открыть  коробку 

                       извлечь  ее  содержимое.

                       запустить  АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(в  содержимом  коробки)

Мы  можем  проследить  за  исполнением  алгоритма  с  помощью  следующей  схемы. Каждый  прямоугольник  представляет  приведение  в  действие  алгоритма.

АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(ПРЕДМЕТА)

если  предмет  есть  часы  то

иначе {часы  не  обнаружили}

  вскрой  коробку {№1}

  достань  содержимое  этой  коробки{т.е. коробку  №2} 

  задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {коробки  №2}

    _________________________________________________________________________

      если  предмет  есть  часы  то

      иначе {часы  не  обнаружили}

        вскрой  коробку {№2}

        достань  содержимое  этой  коробки{т.е. коробку  №3} 

        задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {№3}

           __________________________________________________________________     

           если  предмет  есть  часы  то

           иначе {часы  не  обнаружили}

              вскрой  коробку {№3}

              достань  содержимое  этой  коробки{т.е. часы} 

              задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {часы}

                  ______________________________  

                   если  предмет  есть  часы {да!}

                     надень  их

                     скажи  спасибо

                  -------------------------------------------------

          -------------------------------------------------------------------------------------------------------------

    -----------------------------------------------------------------------------------------------------------------------

Добавим   требование: в  момент  нахождения  часов  надо  закрыть  каждую  коробку  ее  крышкой. Порядок  закрытия  - от  меньшей  к  большей, т.е. сперва  закроем  наименьшую  коробку  наименьшей  крышкой, затем  - коробку, которая  побольше, крышкой, которая  побольше, и  т.д.  до  закрытия  наибольшей  коробки  наибольшей  крышкой. 

На  секунду  задумаемся ... Как  изменить  алгоритм  обнаружения  часов, чтобы  было  выполнено  также  требование  закрытия  коробок?

Закрытие  коробок  дожно  быть  осуществлено  только  после   нахождения  часов, т.е  после  завершения  задания   ЗАПУСТИТЬ_АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ. Ясно, что  место  задания  ЗАКРЫТЬ_КОРОБКУ_СООТВЕТСТВУЮЩЕЙ_КРЫШКОЙ  будет  после  задания   ЗАПУСТИТЬ_АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ.

Алгоритм, включающий  закрытие  коробок  таков:

k АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(ПРЕДМЕТА)

             если  предмет  это  часы  то

                       надеть  их

                       сказать  “спасибо”

             иначе  {предмет  есть  коробка}

                       открыть  коробку 

                       извлечь  ее  содержимое.

                       запустить  АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(в  содержимом  коробки)

                       закрыть  коробку  соответствующей  крышкой

 

 

После  открытия  коробки  повторное  задействование  задания  ЗАПУСТИТЬ_АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ  производит  ряд  заданий, в  которых  внутренние  коробки  открываются  одна  за  другой, а  затем  они  закрываются. После  завершения  действия  мы  можем  закрыть  коробку,  как  это  можно  увидеть  из  следующей  схемы. 

АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(ПРЕДМЕТА)

если  предмет  есть  часы  то

иначе {часы  не  обнаружили}

  вскрой  коробку {№1}

  достань  содержимое  этой  коробки{т.е. коробку  №2} 

  задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {коробки  №2}

    _________________________________________________________________________

      если  предмет  есть  часы  то

      иначе {часы  не  обнаружили}

        вскрой  коробку {№2}

        достань  содержимое  этой  коробки{т.е. коробку  №3} 

        задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {№3}

           __________________________________________________________________     

           если  предмет  есть  часы  то

           иначе {часы  не  обнаружили}

              вскрой  коробку {№3}

              достань  содержимое  этой  коробки{т.е. часы} 

              задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {часы}

                  ______________________________  

                   если  предмет  есть  часы {да!}

                     надень  их

                     скажи  спасибо

                  -------------------------------------------------

                  закрой  коробку  соответствующей  крышкой{коробка  №3}

          -------------------------------------------------------------------------------------------------------------

          закрой  коробку  соответствующей  крышкой{коробка  №2}

    -----------------------------------------------------------------------------------------------------------------------

    закрой  коробку  соответствующей  крышкой{коробка  №1}

Обрати  внимание  на  два  очень  важных  явления: a).всякий  раз, когда  алгоритм  обнаружения  часов  снова  задействует  самого  себя(обращается  к  самому  себе), он  выполняет  те  же  задания, но  всегда  над  коробкой  меньших  размеров;    b).задание  ЗАКРОЙ_КОРОБКУ_СООТВЕТСТВУЮЩЕЙ_КРЫШКОЙ  выполняется  только  после  завершения  выполнения  алгоритма, задействованного  над  самой  маленькой  коробкой.

Для  разъяснения  идеи  рассмотрим  следующую  схему  в  ее  внешних  рамках. Мы  описали  только  операторы, занятые  коробкой  номер  1: ее  открытием  и  закрыванием. Пустой  прямоугольник  обозначает  место  внутренних  операторов  .

АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(ПРЕДМЕТА)

если  предмет  есть  часы  то

иначе {часы  не  обнаружили}

  вскрой  коробку {№1}

  достань  содержимое  этой  коробки{т.е. коробку  №2} 

  задействуй  алгоритм_обнаружения_часов(содержимого  коробки) {коробки  №2}

  _________________________________________________________________________

  |                                                                                                                                                |

   закрой  коробку  соответствующей  крышкой{коробка  №1}

Можно  представить  процесс  исполнения  рекурсивного  алгоритма  в  такой  форме: робот  a’  берет  коробку. Он  не  извлекает  часы  и  поэтому  открывает  коробку, извлекает  ее  содержимое  и  передает  его  роботу  b’.  Действия  робота  b’  не  интересуют  робота  a’(“пустой”  прямоугольник  на  схеме)  и  поэтому  он  терпеливо  ждет, пока  робот  b’  не  удостоверит  его, что  завершил  свои  задания. А  пока  робот  b’  проверяет, не  находятся  ли  в  его  руках  часы. Посколько  часов  нет, а  только  еще  одна  коробка, он  открывает  ее, достает  содержимое  и  передает  его  роботу  c’ , который  действует  точно  также  и  передает  содержимое  коробки  роботу  d’. 

Робот  d’  обнаруживает  часы, надевает  их, говорит  “спасибо”  и  извещает  робота  c’  о  завершении  своего  задания. Только  теперь  робот  c’    продолжает  последнее  задание - закрывает  соответствующей  крышкой  коробку, которая  находится  в  его  руках,  и  извещает  робота  b’,  что  завершил  свое  задание.  Аналогичным  образом  робот  b’  закрывает  свою  коробку  и  извещает  робота  a’  о  завершении  своего  задания. Робот  a’  закрывает  свою  коробку  и  весь  процесс  завершается.

1 Алгоритм, в  котором  одно(или  более)  из  его  заданий  есть  повторное  задействование   этого  же  алгоритма  над  более  простым  вводом, называется  рекурсивным  алгоритмом.

Компонентами  рекурсивного  алгоритма  являются:

1 Условие  останова - последовательность  подзаданий, выполнение  которой  останавливает  алгоритм.    Шаг  рекурсии - последовательность  подзаданий, включающая  повторное  задействование  алгоритма.

В задаче  обнаружения  часов  условие  останова  есть:

             если  предмет  это  часы  то

                       надеть  их

                       сказать  “спасибо”

А  шаг  рекурсии  это:

                       открыть  коробку 

                       извлечь  ее  содержимое

                       запустить  АЛГОРИТМ_ОБНАРУЖЕНИЯ_ЧАСОВ(над содержимом  коробки)

                       закрыть  коробку  соответствующей  крышкой

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

 

5.3. Рекурсивная  процедура

В  этом  параграфе  мы  разработаем  три  программы  с  рекурсивными  процедурами.

 

5.3.1. Решение  задачи  баланса  скобок

? Разработай  и  реализуй  рекурсивный алгоритм, на  вводе  которого  строка  сбалансированных  скобок  вида  (((...w...))). А  вывод  есть  последовательность  сообщений  вида: открываю  коробку 

                              открываю  коробку

                              ........

                              спасибо 

                              .......

                              закрываю  коробку 

                              закрываю  коробку

В  случае  несбалансированности  скобок  или  ввода  ошибочных  символов  программа  выводит  слово  'Ошибка'(один  раз  или  более).

Обрати  внимание: задача  уподобляется  раскрытию  подарка  таким  образом: левая(открывающая)  скобка  представляет  открытие  коробки, правая(закрывающая)  скобка  представляет  закрытие  коробки,  а  w  это  часы(watch  по-английски).

Структура  алгоритма  задачи  скобок  очень  похожа  на  алгоритм  обнаружения  часов. Условие  останова  задачи  обнаружения  часов: если  нашел  часы, то  надень  их  и  скажи  спасибо. А  в  этой  задаче  условие  останова  это  обнаружение  буквы  w. Шаг  рекурсии  нахождения  часов     состоит  из  открытия  коробки, повторного  запуска  алгоритма  над  содержимым  коробки  и  закрытия  коробки. А  здесь  шаг  рекурсии  состоит  из  нахождения  символа  '(', повторного  запуска  алгоритма  и  нахождения  символа  ')'.

k АЛГОРИТМ  ПРОВЕРКА_СКОБОК

              Прочти  символ 

             если  символ =  'w'  то   скажи  “спасибо”

             иначе 

                     если  символ =  '('  то   выведи  “открываю”  иначе  выведи  “ошибка”

                     задействуй  алгоритм  ПРОВЕРКА_СКОБОК

                     прочти  символ 

                     если  символ =  ')'  то   выведи  “закрываю”  иначе  выведи  “ошибка”

(Не  беспокойся  о  поведении  алгоритма  при  неисправном  вводе. Мы  заинтересованы  изучить  только  способ  исполнения  алгоритма  при  исправном  вводе).

Реализация. Реализуем  алгоритм  в  виде  рекурсивной  процедуры  Open  на  языке  Паскаль. Переменная  С  будет  содержать  вводимый  символ. См.  илл. 5.1. Обрати  внимание  на  то, что структура  процедуры  тождественна  структуре  алгоритма: повторное  обращение  к  процедуре  Open  в  виде  одного  из  операторов  самой  процедуры  параллельно  повторному  задействованию  процедуры.

program FindTheWatch;{Ввод: сбалансированная  строка  вида ((w)).}

{Вывод: если  ввод  исправен, выводится  ряд  уравновешенных  сообщений  вида: }

{открываю_коробку открываю_коробку спасибо  закрываю_коробку  закрываю_коробку }

{иначе - выводится  сообщение  об  ошибке(одно  или  более).}

procedure Open;{на  выходе: как  предложение  вывода }

var C: char; {вводимый  символ}

begin

  read(C);

  if C = 'w' then writeln('Спасибо')

  else

  begin

    if C = '('  then writeln('Открываю  коробку') else  writeln('Ошибка');

    Open;

    read(C);

    if C = ')'  then writeln('Закрываю  коробку')  else writeln('Ошибка')

  end;

end{Open};

begin

  writeln('Введи (..(w)..)');

  Open

end.

                     Илл. 5.1. Процедура  нахождения  часов

Проследим  за  ходом  исполнения  процедуры  для  ввода  ((w))  в  таблице  слежения (илл.  5.2). Символы  ‘>’ , добавленные  в  таблицу, помогут  тебе  разобраться  с  обращениями: все  операторы, обозначенные  одинаковым  числом  символов   ‘>’  относятся  к  одному  обращению. Обрати  внимание  на  то, что  рекурсивное  обращение  процедуры  к  самой  себе  выполняется  точно  так  же  как  обращение  к  обычной  процедуре. При  каждом  повторном  обращении  к  нашей  процедуре  выделяется  новая  ячейка  для  локальной  переменной  С, которая  знакома  только  той  процедуре, в  которой  она  находится. Эта  ячейка  “исчезает”  с  повторением  процедуры. 

Следующий  исполняемый  оператор

С

 

 

Вывод

read(C);

if C = 'w'  then ...

else   if C = '('  then writeln('Открываю  коробку')

Open;

?

‘(‘

 “

 “

 

 

 

 

 

Открываю  коробку

 

 

С

 

 

>read(C);

>if C = 'w'  then ...

>else   if C = '('  then writeln('Открываю  коробку')

>Open;

 “

 “

 “

“

?

‘(‘

 “

 “

 

 

 

 

Открываю  коробку

 

 

 

 

 

С

 

>>read(C);

>>if C = 'w'  then ...

>>else   if C = '('  then ...writeln('Спасибо')

>>выход  из  обращения;

 “

 “

 “

 “

  “

  “

  “

  “

?

‘w‘

 “

 “

 

 

 

Спасибо

>read(C);

>if C = ')'  then ... writeln('Закрываю  коробку')

>выход  из  обращения;

 “

 “

 “

  “

  ‘)’

  “

 

 

 

Закрываю  коробку

read(C);

if C = ')'  then ... writeln('Закрываю  коробку')

выход  из  обращения;

 “

 ‘)’

 “

 

 

 

 

 

 

Закрываю  коробку

                    Илл. 5.2. Таблица  слежения  за  Open

 

5.3.2. Решение  задачи  обращения  порядка  символов

? Разработай  и  реализуй  рекурсивный алгоритм, который  вводит  последовательность  символов, завершающуяся  точкой,  и  печатает  ее  в  обратном  порядке(без  точки).

Вывод  для  последовательности  символов  abc.  будет  cba

На  секунду  задумаемся ... Каким  будет  условие  останова  алгоритма?

Первый  шаг  в  начале  алгоритма  есть  чтение  символа. Чтение  символов  завершается  в  момент  прочтения  символа   '.' .  Поэтому  условие  останова  будет  таким:

если  прочитанный  символ  есть  '.'  то  остановись

На  секунду  задумаемся ... Каков  рекурсивный  шаг  алгоритма?

После  чтения  первого  символа  мы  выводим  остальные  символы  ввода  в  обратном  порядке и  только  затем  выводим  первый  символ  в  конце  символов, выведенных  до  сих  пор.  Вывод  остальных  символов  в  обратном  порядке  осуществится  посредством  рекурсивного  обращения  к  тому  же  алгоритму. Например, рекурсивный  шаг  действия  алгоритма  Reverse(обратный)  над  строкой  ‘abc  будет  задействование  алгоритма  над  ‘bc.’ , чтобы  напечатать  ‘cb’, а  затем и  ‘a’ .

Reverse(‘abc.’) ® Reverse(‘bc.’) + ‘a’ ®  ‘cb’ + ‘a’ ®  ‘cba’

Отсюда  следует, что  шаг  рекурсии  будет  таким:

             Задействуй  алгоритм_обрати_порядок_символов

             выведи  символ

Ниже  дан  рекурсивный  алгоритм  решения  нашей  задачи:

k АЛГОРИТМ  ОБРАТИ_СИМВОЛЫ

             Прочти  символ  и  подставь  его  в  С

             если  С =  '.'  то   {завершили  чтение  символов, делать  более  нечего}

             иначе 

                      задействуй  алгоритм  ОБРАТИ_СИМВОЛЫ

                      напечатай  содержимое  С

Вопрос  5.2. Проследи за  исполнением  алгоритма  для  ввода  ‘defg.

Реализация. Реализуем  алгоритм_обращения_символов  в  виде  процедуры  Reserve  на  Паскале. См. илл. 5.3. 

Проследим за  исполнением  процедуры  посредством  таблицы  слежения  для  ввода  ‘abc.’ (илл. 5.4). Обрати  внимание  на  то, что  обращение  к  процедуре  Reverse  приводит  к  еще  одному  обращению  к  ней  еще  до  вывода  введенного  символа. Вывод  символов  осуществляется  только  на  этапе  возвращения  из  обращений. В  таблице  слежения  можно  видеть  создание  новой  переменной  с  каждым  обращением. В  этой  переменной  мы  “запоминаем”  значение  С  до  того, как  воспользуемся  им  в  операторе  write. 

program  Rev;{Ввод: последовательность  символов  в  конце '.'}

{Вывод: представление  введенных  символов  в  обратном  порядке }

procedure  Reverse;

{На  выходе: представление  введенных  символов  в  обратном  порядке }

var  C: char; {введенный  символ}

begin

  read(C);

  if C = '.' then      {нечего  делать}

  else

  begin

    Reverse;

    write(C)

  end

end{Reverse};

begin

  writeln('Введи  символы, в  конце - точка');

  Reverse;

  writeln

end.

                 Илл. 5.3. Программа  вывода  символов  в  обратном  порядке                      

Следующий  исполняемый  оператор

С

 

 

 

Вывод

read(C);

if C = '.'  then ...

Reverse

?

‘a‘

 “

 

 

 

 

 

 

 

 

С

 

 

 

>read(C);

>if C = '.  then ...

>Reverse

 “

 “

 “

?

‘b’

 “

 

 

 

 

 

 

С

 

 

>>read(C);

>>if C = 'w'  then ...

>> Reverse

 “

 “

 “

  “

  “

  “

?

‘c’

 “

 

 

 

 

 

 

 

 

 С

 

>>>read(C);

>>>if C = '.'  then ...

>>> нечего  делать

>>> возвращение  из  обращения

 “

 “

 “

 “

  “

  “

  “

  “

 “

 “

 “

 “

 ?

 ‘.’

  “

  “

 

 

 

>>write(C);

>>возвращение  из  обращения

 “

 “

  “

  “

 “

 “

 

 

‘c’

>write(C);

>возвращение  из  обращения

 “

 “

  “

  “

 

 

 

 

‘b’

write(C);

возвращение  из  обращения

 “

 “

 

 

 

 

 

 

‘a’

                    Илл. 5.4. Таблица  слежения  за  Reverse

 

5.3.3. Решение  задачи  вывода  числа

? Разработай  и  реализуй  рекурсивный алгоритм, который  вводит  целое  число  больше  или  равное  нулю, а  выводит  его  как  строчку  символов  слева  направо.

Для  ввода  2749  выводом  будет  ряд  символов(слева  направо): ‘2’   ‘7’   ‘4’   ‘9’

Обрати  внимание  на  то, что  оператор  Паскаля  write  выполняет  в  точности  то, что  требует  эта  задача. Здесь  мы  изучим  рекурсивный  алгоритм, с  помощью  которого  компилятор  Паскаля  осуществляет  реализацию  этого  оператора.

На  секунду  задумаемся ... Каким  будет  условие  останова  алгоритма?

Наиболее  простой  случай, когда  число  состоит  из  одной  цифры и  его  можно  простым  вычислением  превратить  в  символ. Условие  останова  таково: если  дошли  до  одной  цифры, то  выведи  символ, соответствующий  ей.

На  секунду  задумаемся ... А  каким  будет  шаг  рекурсии?

Цель  программы - вывести  число  как  последовательность  символов, это  можно  сделать  только  с  помощью  разложения  числа  на  его  цифры. Мы  умеем  отделить  цифру  с  наименьшим  значением(самую  правую  цифру),          но  вывод  числа  должен  выполняться  слева  направо, т.е. от  самой   содержательной  цифры  и  до  цифры  единиц.    Итак, надо  выводить  остающуюся  часть  числа, а  затем  отделенную  цифру. Как  это  осуществить?  Ясно, что  с  помощью  того  же  алгоритма, действующего  рекурсивно. Например, число  12345  получается  выводом  числа  1234  рекурсивным  исполнением  алгоритма  и  после  этого  выводом  отдельной  цифры  5:

PrnNum(12345)  ®  PrnNum(1234) + ‘5’  ®  ‘1234’ + ‘5’  ®  ‘12345’

k АЛГОРИТМ  ВЫВЕДИ_ЧИСЛО(число)

             если  можно  вывести  число  как  один  символ  то   

                        выведи  его

             иначе 

                      отдели  последнюю  цифру  числа

                      задействуй  алгоритм  ВЫВЕДИ_ЧИСЛО(над  оставшейся  частью  числа)

                      выведи  символ, соответствующий  последней  цифре  числа

Вопрос  5.3. Проследи  за  алгоритмом  для  5678.

Выберем  переменные  и  с  их  помощью  детализируем  алгоритм:

N  хранит  введенное  число.

Rest  хранит  число, остающееся  после  обрезания  последней  цифры.

C  хранит  отдельный  символ, изображающий  цифру.

Обрати  внимание: чтобы  превратить  отдельную  цифру  в  символ, мы  воспользуемся  функцией  по  имени DigitToChar (цифра_в_символ), которая  принимает  в  качестве  параметра  цифру  и  возвращает  соответствующий  ей  символ. Например,

DigitToChar(6) = ‘6’.  Для  простоты  положим, что эта  функция  нам  дана.

k АЛГОРИТМ  ВЫВЕДИ_ЧИСЛО(N)

             если   N £ 9   то   

                        вычисли DigitToChar(N)  и  подставь  результат  в  С

                        выведи  С  

             иначе 

                      вычисли  N div 10  и  подставь  в  Rest

                      задействуй  алгоритм  ВЫВЕДИ_ЧИСЛО(Rest)

                      вычисли  DigitToChar(N mod 10)  и  подставь  в  С

                      выведи  С

Реализуем  этот  алгоритм  как  процедуру  на  языке  Паскаль(илл. 5.5). Функция  DigitToChar  использует  две  предопределенные  функции.

R Для  символа  С:  ord(C)  возвращает  место  символа  в  ряду  символов  ASCII.

Для  целого  N(цифры):  chr(N)  возвращает  вместо  N соответствующий  ему  символ.

program  PrintNumber;{Ввод: целое  N > 0.  Вывод: печать  числа  N}

var I: integer; {введенное  число}

function DigitToChar(N: integer): char; {На  входе: 0<=N<=9}

{На  выходе: возвращает  символ, изображающий  N}

begin

  DigitToChar := chr(ord('0') + N)

end{DigitToChar};

procedure PrnNum(N: integer); {На  входе N>=0. На  выходе  N  напечатано}

var C:      char;                              {одиночный  символ}

     Rest:  integer;                          {оставшееся  число}

begin

  if N <= 9 then                              {одиночная  цифра}

  begin

    C := DigitToChar(N);

    write(C)

  end

  else

  begin

    Rest := N div 10;

    PrnNum(Rest);

    C := DigitToChar(N mod 10);

    write(C)

  end

end{PrnNum};

begin

  writeln('Введи  целое  неотрицательное  число');

  readln(I);     PrnNum(I);     writeln

end.

                         Илл. 5.5. Процедура  вывода  числа

Проследим  за  исполнением  процедуры  PrnNum  для  ввода  N = 123  в таблице  слежения(илл. 5.6). В  таблице  имя  функции  DigitToChar  сокращено  до  DTC,  а  имя  переменной  Rest  -  до  R.

Следующий  исполняемый  оператор

  N        C        R

 

 

Вывод

if  N <= 9 then ...

else  R := N div 10

PrnNum(R)

123      ?         ?

   “        “          “

   “        “          “

 

 

 

 

 

 

 

 N       C        R

 

Вывод

>if  N <= 9 then ...

>else  R := N div 10

>PrnNum(R)

   “        “         “

   “        “          “

   “        “          “

12      ?         ?

 “        “          “

 “        “          1

 

 

 

 

 

 

 

N       C      R

Вывод

>>if  N <= 9 then ...

>>C := DTC(N)

>>write(C)

>>возвращение  из  обращения

   “        “         “

   “        “          “

   “        “          “

   “        “          “

 “        “          “

 “        “          “

 “        “          “

 “        “          “

 1      ?     ?

  “       “      “

  “       ‘1’    “

  “         “     “

 

 

 

  ‘1’

>>C := DTC(N mod 10)

>>write(C)

>>возвращение  из  обращения

   “        “         “

   “        “          “

   “        “          “

 “        “          “

 “       ‘2’          “

 “        “          “

 

 

 

  ‘2’

>>C := DTC(N mod 10)

>>write(C)

>>возвращение  из  обращения

   “        “         “

   “     ‘3’          “

   “        “          “

 

 

 

 

  ‘3’

                            Илл. 5.6. Таблица  слежения  за  PrnNum(123)

begin {PrnNum(12345)}

PrnNum(1234) {обращение}

|     begin {PrnNum(1234)}

|     PrnNum(123) {обращение}

|     |     begin {PrnNum(123)}

|     |     PrnNum(12) {обращение}

|     |     |     begin {PrnNum(12)}

|     |     |     PrnNum(1) {обращение}

|     |     |     |     begin {PrnNum(1)}

|     |     |     |     ‘1’ {вывод}

|     |     |     |     end {PrnNum(1)}

|     |     |     ‘2’ {вывод}

|     |     |     end {PrnNum(12)}

|     |     ‘3’ {вывод}

|     |     end {PrnNum(123)}

|     ‘4’ {вывод}

|     end {PrnNum(1234)}

‘5’ {вывод}

end {PrnNum(12345)}

                        Илл. 5.7. Таблица  обращений  к  PrnNum

Другим  способом  слежения  за ходом исполнения  процедуры  является  таблица  обращений. В  такой  таблице записывают  любой  вход  в  процедуру  со  сдвигом  вправо  и  каждый  выход  из  нее  соответственно  под   входом               (обозначается  пунктирной  линией). Слежение  за  исполнением  процедуры  является  легким  и  удобным, поскольку  можно  отнести  каждое  обращение  к  возвращению  из  него.  Одно  из  преимуществ  таблицы  обращений  состоит  в  том, что  можно  ее  напечатать  на  компьютере. Таблица  обращений  к  процедуре PrnNum  находится  на  илл. 5.7.

"Мы  воспользовались  несколькими  видами  таблиц  и  схем  для  слежения  за  рекурсивным  исполнением. Нет  нужды  пользоваться  ими  всеми. Выбери  способ, который  тебе  удобнее.

Вопрос  5.4. a).Напиши  процедуру  PrnNum2, принимающую  в  качестве  параметра  целое  число  ³ 0  и  выводящую  число  в  виде  строки  символов  слева  направо  без  использования  локальных  переменных  С  и  Rest.    

b).Покажи  таблицу  слежения  за    процедурой  PrnNum2.

Вопрос  5.5. Слово, которое  одинаково  читается  справо  налево  и  слева  направо,  называется  палиндромом. Палиндром, в  центре  которого  находится  символ  ‘*’ , называется  обозначенным  палиндромом.

Слова  примеров  a’, b’, c’  это  обозначенные  палиндромы, а  слова   примеров  d’, e’, f’  обозначенными  палиндромами  не  являются.

a).hon*noh           b).abaama*amaaba          c).*

d).hon*hon           b).abaamaamaaba          c).shalomalisrael

a).Разработай и  реализуй рекурсивный  алгоритм, который  принимает  на  вводе  последовательность  символов  и  выдает  сообщение, является  ли  эта  последовательность  обозначенным  палиндромом. Каково  условие  останова  алгоритма?  Каков  шаг  рекурсии  алгоритма?  Замечание. Подобно  программе  проверки  баланса  скобок  здесь  также  не  важно  точное  поведение  программы, когда  ввод  не  есть  обозначенный  полиндром, достаточно  хотя  бы одного  сообщения  об  ошибке.

b).Проследи  за  ходом  исполнения  алгоритма  для  выражения  abg*gba .

c).Проследи  за  ходом  исполнения  алгоритма  для  выражения  abg*abg .

 

5.3.4.Рекурсивная  функция

Дан, Гад, Рахель, Дина  и  Йоси  решили  преподнести  своей  любимой  маме  цепочку  собственного  изготовления. У  каждого  из  детей  было  по  одному  звену  и  он  мог  соединить  это  звено  с  другим  звеном. Как  собрать  всю  цепочку? Сидели  дети, думали, думали  и  в  конце  концов  нашли  рецепт.

Дани  объявил: Если  у  меня  будет  цепочка  из  4-х  звеньев, то  я  соединю  ее  с  моим  звеном,  мы  получим  цепочку  из  5  звеньев  и  дадим ее  маме. Гад, позаботься, пожалуйста,  о  цепочке  из  4-х  звеньев.

      Гад  объявил: Если  у  меня  будет  цепочка  из  3-х  звеньев, то  я  соединю  ее  с  моим 

      звеном,  мы  получим  цепочку  из  4  звеньев,  и  ее  я  отдам  Дану. Рахель, 

      позаботься, пожалуйста,  о  цепочке  из  3-х  звеньев.

            Рахель  объявила: Если  у  меня  будет  цепочка  из  2-х  звеньев, то  я   соединю  ее

            с  моим  звеном,  мы  получим  цепочку  из  3  звеньев,  и  ее  я  отдам   Гаду. Дина, 

            позаботься, пожалуйста,  о  цепочке  из  2-х  звеньев.

                  Дина  объявила: Если  у  меня  будет  цепочка  из  одного  звена, то  я   соединю

                  ее  с  моим  звеном,  мы  получим  цепочку  из  2  звеньев,  и  ее  я  отдам

                  Рахели.  Йоси,  позаботься, пожалуйста,  о  цепочке  из  одного  звена.

                        Йоси  объявил: Если  у  меня  будет  цепочка  из  одного  звена ... но она

                        есть  у  меня!  Дина, дай, пожалуйста,  цепочку  из  одного  звена.

                  Дина  рада: соединила  свое  звено  с  цепочкой  из  одного  звена  и  произвела

                  цепочку  из  2-х  звеньев. Ее  она  отдала  Рахели.

            Рахель  рада: соединила  свое  звено  с  цепочкой  из  2-х  звеньев  и  произвела 

            цепочку  из  3-х  звеньев. Ее  она  отдала  Гаду.

      Гад  рад: соединил  свое  звено  с  цепочкой  из  3-х  звеньев  и  произвел  цепочку  из 

      4-х  звеньев. Ее  он  отдал  Дану.

Дан  рад: соединил  свое  звено  с  цепочкой  из  4-х  звеньев  и  произвел  цепочку  из        5-и  звеньев. Ее  он  отдал  маме  от  имени  всех  детей.

На  секунду  задумаемся ...  Каково  условие  останова  рекурсивного   создания  цепочки?

Условием  останова  является  просьба  о  цепочке  с  одним  звеном.

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

? Разработай  рекурсивный  алгоритм  создания  цепочки  длиной  N  из  N  отдельных  звеньев.

 

k ПОСТРОЙ_ЦЕПОЧКУ_ДЛИНОЙ(N)

             если   N = 1   то   

                      возврати  звено  

             иначе 

                      ПОСТРОЙ_ЦЕПОЧКУ_ДЛИНОЙ(N-1)  и  помести  ее  в  частичную_цепочку

                      соедини  частичную_цепочку  и  звено  и  помести  ее  в  частичную_цепочку                    

                      возврати  частичную_цепочку

Проследим  за  исполнением  алгоритма  для  цепочки  из  четырех  звеньев(см. далее).

ПОСТРОЙ_ЦЕПОЧКУ_ДЛИНОЙ(N)

если  N = 1  то

иначе {4 <> 1}

    построй_цепочку_длиной(3)  и  помести  в  частичную  цепочку

        -------------------------------------------------------------------------------------------------------------------

         если  N = 1  то

         иначе {3 <> 1}

             построй_цепочку_длиной(2)  и  помести  в  частичную  цепочку

                ------------------------------------------------------------------------------------------------------      

                 если  N = 1  то

                 иначе {2 <> 1}

                     построй_цепочку_длиной(1)  и  помести  в  частичную  цепочку

                         ----------------------------------------------

                           если  N = 1  то   { да! 1 = 1}

                               возврати  звено  ¡

                         ----------------------------------------------

                  соедини  частичную_цепочку  и  звено  и  помести  в  частичную_цепочку

                  возврати  частичную_цепочку  ¡ ® ¡

               --------------------------------------------------------------------------------------------------------

             соедини  частичную_цепочку  и  звено  и  помести  в  частичную_цепочку

             возврати  частичную_цепочку  ¡ ® ¡® ¡                  

          -----------------------------------------------------------------------------------------------------------------

    соедини  частичную_цепочку  и  звено  и  помести  в  частичную_цепочку

    возврати  частичную_цепочку  ¡ ® ¡® ¡® ¡

У  описанного  нами  рекурсивного  алгоритма  есть  структура  функции  на  языке  Паскаль: получение  параметра, вычисления, основанные  на  значении  параметра,  и  возвращение  значения. Воспользуемся  теперь  этими  идеями, чтобы  реализовать  рекурсивный  алгоритм  как  рекурсивную  функцию  на  Паскале.

 

5.4. Решение  задачи  вычисления  факториала 

1 N-факториал(factorial)  есть  функция, вычисляющая  произведение  всех  положительных  целых  чисел  меньше  или  равных  N. На  математическом  языке  она  обозначается  N! .

1! = 1       2! = 1×2 = 2            3! = 1×2×3 = 6              4! = 1×2×3×4 = 24

Вопрос  5.6. a).Каково  значение  5! ?      b).Каково  значение  6! ?

В  действительности  можно  немного  “обмануть”  вычисления  в  подвопросе   b).  и  воспользоваться  вычислениями, которые  были  осуществлены  в  подвопросе  a).  вместо  вычисления  произведения  всех  чисел  меньше  или  равных  6:

6! =  1×2×3×4×5×6 = (1×2×3×4×5)×6 = 5!×6 = 120×6 = 720

Приведенная  ниже  схема  демонстрирует  вычисление  5!  в  рекурсивной  форме:

чтобы  вычислить  N!,  мы вычисляем  (N-1)!   и  множим  результат  на  N.  

5! = 4!×5 = 24×5 = 120

       ¯                ã

       4! = 3!×4 = 6×4 = 24

              ¯                ã

              3! = 2!×3 = 2×3 = 6

                     ¯               ã

                     2! = 1!×2 = 1×2 = 2

                            ¯               ã

                     1!    =              1

? Разработай  рекурсивный  алгоритм  вычисления  факториала N(N!).

УСЛОВИЕ  ОСТАНОВА: 1! = 1.

ШАГ  РЕКУРСИИ:  N! = (N-1)×N

k АЛГОРИТМ  ВЫЧИСЛИ(N!)

             если   N = 1   то   

                      возврати  1  

             иначе 

                      ВЫЧИСЛИ((N-1)!)  и  помести  в  Temp

                      возврати  результат  произведения  Temp×N

Реализация. Ниже  дана  программа, реализующая  алгоритм  в  виде  рекурсивной  функции  на  языке  Паскаль. Слово  факториал по-английски  factorial, поэтому  функция  факториала  названа  Fact, а  выражение N!  на  Паскале  записывается  как  Fact(N).

program  Factorial;{Ввод: целое  N > 0 (<8). Вывод: программа выводит N!}

var I: integer; {введенное  число}

function  Fact(N: integer): integer; {На  входе: целое N>= 1(<8)}

{На  выходе: функция  возвращает   N!}

var  Temp:  integer;

begin

  if  N = 1 then Fact := 1

  else

  begin

    Temp := Fact(N-1);

    Fact := Temp*N

  end

end{Fact};

begin

  writeln('Введи  целое  положительное  число(<8)');   readln(I);

  writeln(I:1,'! = ', Fact(I))

end.

Вопрос  5.7. Имя  Fact  трижды  появляется  в теле  функции. Объясни  цель  каждого  его  появления.

Проследи  за  ходом  исполнения  функции  Fact(5)  на  схеме  прямоугольников(илл. 5.8).

                               (Илл. 5.8. Вычисление  5!)

Другой  способ  слежения  за  рекурсивной  функцией  состоит  в  использовании  схемы  стрелок. Идея  такой  схемы  заключается  в  показе  направления  хода(потока)  функции. Объясним  эту  идею  посредством  схемы  стрелок  для  обращения  к  функции  Fact(5) (илл. 5.9).

                              (Илл. 5.9. Схема  стрелок  для  вычислоения  5!)

Шаг  рекурсии  функции  Fact(N)  состоит  из  двух  подзаданий : Temp := Fact(N-1)  и     Fact := Temp*N. Два  этих  подзадания  представлены  на  схеме  стрелок  с  помощью  двух  стрелок  на  одном  уровне -  к  каждой  команде  так, чтобы  команда, исполняемая  сначала  находилась  на  левой  стрелке, а  команда, выполняемая  второй, находилась  бы  на  правой  стрелке.

Обрати  внимание  на  то, что  пока  нет  значения  Temp,  нет  и  возможности  переходить  к  следующей  команде(находится, как  уже  было  сказано  справа). В    момент  получения значения  переменной  Temp  на  некотором  уровне, осуществляется  команда  справа  на  этом  уровне.

Таблица  обращений  для  Fact(5)  находится  на  илл. 5.10:     

begin {Fact(5)}

Fact(4) {обращение}

|     begin {Fact(4)}

|     Fact(3) {обращение}

|     |     begin {Fact(3)}

|     |     Fact(2) {обращение}

|     |     |     begin {Fact(2)}

|     |     |     Fact(1) {обращение}

|     |     |     |     begin {Fact(1)}

|     |     |     |     Fact := 1

|     |     |     |     end {Fact(1)}

|     |     |     Fact := 1*2 = 2

|     |     |     end {Fact(2)}

|     |     Fact := 2*3 = 6

|     |     end {Fact(3)}

|     Fact := 6*4 = 24

|     end {Fact(4)}

Fact := 24*5 = 120

end {Fact(5)}

         Илл. 5.10. Таблица  обращений  к  Fact(5)

Вопрос  5.8. Построй  таблицу  слежения  для  Fact(4).

Вопрос  5.9.

1 Степень  nk  (n, k  - целые  и  k  положительная) определена  как  произведение  n  самого  на  себя  k  раз.

n1 = n

n2 = n1×n

n3 = n2×n

n4 = n3×n

..........

nk = nk-1×n

a).Каким  будет  шаг  рекурсии  для  этой  формулы? Каково  условие  останова?    b).Напиши  рекурсивный  алгоритм  вычисления  степени  nk .    с).Реализуй  алгоритм,  написанный  тобой  в  подвопросе  b’,  в  виде  функции  на  языке  Паскаль  в  соответствии  со  следующим  заголовком:   

function  Exp(N,K: integer): integer;  {На  входе:  целое N, целое  K >= 0}

{На  выходе:  функция  возвращает  N  в  степени  K}

d).Проследи  удобным  тебе  образом  за  исполнением  функции  Exp(3, 4).

Вопрос  5.10. Разработай  и  реализуй  рекурсивный  алгоритм, вводящий  целое  число  и  выводящий  его  длину(количество  цифр). Например, длина  числа  12345  будет  5. Заголовок  этой  рекурсивной  функции  будет  таким:

function  FindLength(N: integer): integer;  {На  входе:  целое N >= 0}

{На  выходе:  функция  возвращает  число  цифр  в  N}

Резюме

РЕКУРСИВНЫЙ  АЛГОРИТМ. Это  алгоритм, у  которого  одно  или  более  его  заданий  есть  повторное  задействание  этого  же  алгоритма  над  более  простым  вводом.

РЕКУРСИВНАЯ  ФУНКЦИЯ(ИЛИ  ПРОЦЕДУРА). Это  функция(или  процедура), один  или  более  шагов  которой   есть  обращение  к  этой  же  функции  или  процедуре  над  более  простым  вводом.

ШАГ  РЕКУРСИИ. Это  последовательность  операторов  функции  или  процедуры, содержащих  обращение  к  той  же  функции  или  процедуре.

УСЛОВИЕ  ОСТАНОВА. Это  последовательность  операторов, приводящая  к  останову  рекурсии. Без  такого  условия  рекурсивная  программа  не  завершится. 

Резюме  языка  Паскаль. В  Паскале  не  существует  специальной  структуры, связанной  с  рекурсией.

Каждому  символу  соответствует  число, которое  означает  его  место  в  последовательности  символов  ASCII.  Функция  ord(C)  возвращает  местоположение  символа  С, а  функция  char(N)  возвращает  символ, находящийся  на  месте  N.

 

Дополнительные  упражнения

Вопрос  5.11. Перед  тобой  рекурсивная  программа, исполняющая  некоторое  задание. Проследи  за  исполнением  программы  удобным  тебе  методом  и  дополни  предложение  выхода  функции.

program  P;

var K, Size: integer;

procedure  GuessWhat(J,N: integer); {На  входе: J,N - целые  числа > 0}

{На  выходе: ???    }

var Temp:  integer;

begin

 if J = N then write(N)

 else

 begin

  write(J);

  GuessWhat(J+1,N);

  write(J)

 end

end;

begin

 write('Введи  размер  фигуры(>0,<10): ');   readln(Size);

 for K := 1 to Size do

 begin

  GuessWhat(1,K);  writeln

 end

end.

Вопрос  5.12. Перед  тобой  функция  по  имени  Stam. 

a).Чему  равно  значение Stam(1)? Stam(3)? 

b).Дополни  предложения  входа  и  выхода  этой  функции.

function Stam(N: integer): integer;   {На  входе: ???      .   На  выходе: ???     }

begin

 if N = 0 then Stam := 1

 else Stam := Stam(N-1) + 2

end;

Вопрос  5.13. Целью  этой  рекурсивной  функции  является  получение  произведения  двух  чисел  только  с  помощью  действий  сложения. Например:  3*4 = 3 + 3 + 3 + 3 = 12.

Можно  рекурсивно  вычислить  произведение  P*Q  в  такой  форме:

Условие  останова:  P*1 = P

Шаг  рекурсии(если  Q > 1): P*Q = P*(Q - 1) + P

a).Вычисли  указанным  методом  произведение  3*4.

b).Дополни  отсутствущие  команды  функции  Multiply.

function Multiply(P,Q: integer): integer;

{На входе: целые  Р  и  Q, Q > 0.  На  выходе:  функция  возвращает  произведение  P*Q}

begin

 if ____________ then  _____________

 else  _________________

end;

Вопрос  5.14. Перед  тобой  рекурсивный  алгоритм  по  имени What.

a).Каково  значение  What(3, -2)?

b).Дополни  предложения  входа  и  выхода  этой  функции.

function  What(P,Q: integer): integer;  {На  входе: ???      .    На  выходе: ???     }

begin

 if Q = 1 then  What := P

 else  What := What(P, Q+1) - P

end;

Вопрос  5.15. Дана  последовательность  чисел  0, 3, 6, 9, 12 ... Разработай  и  реализуй рекурсивный   алгоритм  вычисления  N-го  элемента  последовательности.

Вопрос  5.16.

1 Наибольший  общий  делитель(Greatest  Common  Divider)  двух  чисел  a  и  b  определен  как  наибольшее  число, на  которое  делится  и  a  и  b. Для  сокращения  обозначим  максимальный  общий  делитель  через  GCD.

GCD  чисел  21  и  14  есть  7.    GCD  чисел  12  и  5  есть  1.

Эвклид  получил  алгоритм  определения  наибольшего  общего  делителя  согласно  следующей  формулы:

GCD(a, a) = a

GCD(a, b) = GCD(a-b, b)      для  a > b

GCD(a, b) = GCD(a, b-a)      для  b > a

GCD(35, 14) = GCD(21, 14) = GCD(7, 14) = GCD(7, 7) = 7

      GCD(12, 5) = GCD(7, 5) = GCD(2, 5) = GCD(2, 3) = GCD(2, 1) = GCD(1, 1) = 1

Напиши  рекурсивную  функцию  определения  наибольшего  общего  делителя  с  заголовком:

function  GCD(A,B: integer): integer;  {На  входе: целые  положительные  А, В}

{На  выходе: функция  возвращает  наибольший  общий  делитель  А  и  В}

 

Глава  6. Структуры  данных

Ключевые  слова. Струкура  данных,  двумерный  массив, запись.

 

6.1.Двумерные  массивы

Одной  из  важнейших  форм  представления  информации  являются  таблицы.  Успех  электронного  листа(на  экране)  есть  доказательство  удобной работы  с  таблицами. Отсюда  следует  важность  двумерного  массива, который  является  структурой  данных  для  реализации  таблиц.

 

6.1.1.Решение  задачи  средних  оценок

? Разработай  и  реализуй  алгоритм  вычисления  средних  оценок. 

Ввод - последовательность  из  6  строк, каждая  из  них  содержит  отметки  ученика  по   пяти  экзаменам.    Вывод - таблица, которая  содержит:  a).строчку  на  каждого  ученика  с  его  отметками  и  с  его  средней  отметкой; b).среднюю  отметку  по  каждому  экзамену.

Ввод:

67

87

89

61

78

99

100

89

92

98

76

88

79

69

88

99

94

89

84

98

67

77

95

61

88

87

79

100

89

92

Вывод:

Ученик

ТАНАХ

Литература

Химия

История

Математ.

Средняя

1

67

87

89

61

78

76.4

2

99

100

89

92

98

95.6

3

76

88

79

69

88

80.0

4

99

94

89

84

98

92.8

5

67

77

95

61

88

77.6

6

87

79

100

89

92

89.4

------------        -------------          ---------------      --------------      ------------        --------------               

Средняя         82.5                 87.5                 90.2                76.0               90.3

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

На  секунду  задумаемся ... Как  будем  вычислять  среднее  по  каждому  экзамену?

Нам  предстоит  просуммировать  первые  элементы  в  каждой  строке  и  поделить  сумму  на  число  строк(учеников), затем  вычислить  среднее  элементов , находящихся  на  втором  месте  в  каждой  строке  и  т.д. Отсюда  ясно, что  надо  ввести  все  данные  и  запомнить  их, и  только  после  этого  вычислять  среднее  по  предметам. Есть  возможность  запоминать  все  данные  в  одном  большом  массиве  G, в  котором  каждые  5  элементов  хранят  экзаменационные  оценки  одного  ученика:

G[1..5]

G[6..10]

G[11..15]

G[16..20]

G[21..25]

G[26..30]

                                                        ä                                          ã

G[11]

G[12]

G[13]

G[14]

G[15]

На  секунду  задумаемся ... Что  проблематично  в такой  структуре  данных?

Основная  проблема  такой  структуры  данных  в  том, что  нет  прямой  связи  между  неким  данным  и  индексом  элемента  массива, в  котором  хранится  данное. В  какой  ячейке  хранится  отметка  второго  экзамена  четвертого  ученика? Вторая  проблема  состоит  в  утере  структуры  экзаменов.

На  секунду  задумаемся ... Опиши  вычисление  среднего  по  четвертому  предмету,  когда  данные  хранятся  в  таком  массиве?

Нам  нужен  будет  цикл  while, прыгающий  по  индексам  4, 9, 14, ...

Структурой  данных, подходящей  решению  этой  задачи, будет  двумерный  массив:

 

T[1]

T[2]

T[3]

T[4]

T[5]

S[1]

 

 

 

 

 

S[2]

 

 

 

 

 

S[3]

 

 

 

 

[3,5]

S[4]

 

 

 

 

 

S[5]

 

 

 

 

 

T[6]

 

 

 

 

 

Двумерный массив  представляет  собой  математическую  структуру, которая  называется  матрицей (matrix)  и  знакома  вам  по  клеткам  на  шахматных  досках. Чтобы  идентифицировать  элемент  матрицы, надо  определить  его  строку  и  столбец. У  шахматных  игроков  принято  обозначать  ряды  номерами  от  1  до  8, а  столбцы  буквами  от  а  до  h.  Подобная  ситуация  знакома  тебе  по  билетам  в кино, на  которых  напечатан  номер  ряда  и  номер  кресла в  ряду.

Чтобы  решить  задачу  о  средних  оценках, объявим  тип-массив  GradeArrayType  с  двумя  индексами. Пусть первый  индекс  есть  номер  ученика, а  второй  -  номер  оценки. Grade  есть  переменная  указанного  типа, которая  будет  содержать  отметки.

const  Students = 6;   {число  учеников}

           Tests = 5;         {число  экзаменов}

type  GradeArrayType = array[1..Students,1..Tests] of integer; {таблица - двумерный  массив}

var    Grade:      GradeArrayType;                {таблица  оценок}

Чтобы  указать  одиночный  элемент  двумерного  массива, надо  написать  два  его  индекса, сначала  индекс  строки, а  затем  индекс  столбца. На  илл. выше  обозначен  элемент Grade[3,5], который  находится  в  третьей  строке  и  пятом  столбце.

Вопрос  6.1. Покажи  клетку  элемента  Grade[5,3] .

Сперва  назначим  структуры  данных:

Двумерный  массив  Grade  для  данных  ввода.

Одномерный  массив  StudentAvg  для  средних  оценок  учеников.

Одномерный  массив  estAvg  дляч  средних  оценок  по   предметам.

k АЛГОРИТМ  ВЫЧИСЛИ_СРЕДНИЕ

             ВВЕДИ_ДАННЫЕ(Grade)

             ВЫЧИСЛИ_СРЕДНИЕ_УЧЕНИКОВ(Grade, StudentAvg)

             ВЫЧИСЛИ_СРЕДНИЕ_ЭКЗАМЕНОВ(Grade, TestAvg)

             ВЫВЕДИ_РЕЗУЛЬТАТЫ(Grade, StudentAvg, TestAvg)

 

k АЛГОРИТМ  ВВЕДИ_ДАННЫЕ(Grade)

             Для  каждого  ученика  номер  S  исполни

                     для  каждого  экзамена  номер  T  исполни

                            введи  значение  в  Grade[S,T]

 

k АЛГОРИТМ  ВЫЧИСЛИ_СРЕДНИЕ_УЧЕНИКОВ(Grade, StudentAvg)

             Для  каждого  ученика  номер  S  исполни

                      обнули  накопитель  оценок  Sum

                      для  каждого  экзамена  номер  T  исполни

                              добавь  Grade[S,T]  в  Sum

                      подставь  Sum/Tests  в  StudentAvg[S]

Обрати  внимание  на  место  команды  обнуления  накопителя  Sum. Для  каждого  ученика  обнуление  накопителя  требуется  до  начала  суммирования!

k АЛГОРИТМ  ВЫЧИСЛИ_СРЕДНИЕ_ЭКЗАМЕНОВ(Grade, TestAvg)

             Для  каждого  экзамена  номер  T  исполни

                      обнули  накопитель  оценок  Sum

                      для  каждого  ученика  номер  S  исполни

                              добавь  Grade[S,T]  в  Sum

                      подставь  Sum/Students  в  TestAvg[T]

Обрати  внимание  на  разницу  в  вычислениях  средних: после  суммирования  элементов  определенной  строки  мы  делим  сумму  на  число  столбцов  в  строке,

чтобы  получить  среднее  в  ней,   а  после  суммирования  элементов  определенного  столбца  мы  делим  сумму  на  число  строк  в  столбце, чтобы  получить  среднее  в  нем.

k АЛГОРИТМ  ВЫВЕДИ_РЕЗУЛЬТАТЫ(Grade, StudentAvg, TestAvg)

             Выведи  соответствующий  заголовок

             для  каждого  ученика  номер  S  исполни

                     выведи  номер  ученика  S

                      для  каждого экзамена  номер  T  исполни

                              выведи  Grade[S,T]

                      выведи  StudentAvg[S]

             для  каждого  экзамена  номер  T  исполни

                     выведи  TestAvg[T]

Реализация. Многие  алгоритмы, работающие  с  двумерными  массивами, используют  гнезда  циклов, чтобы  пройти  по  всем  столбцам  всех  строк. Ниже  дана  процедура  для  ввода  данных  в  массив:

procedure  ReadGrade(var Grade: GradeArrayType);

{На  выходе: оценки, введенные  в  массив  Grade}

var  S, T: integer;   {счетчики}

begin

  for S := 1 to Students do

    for T := 1 to Tests do read(Grade[S,T])

end{ReadGrade};

Тело  процедуры  состоит  из  одного  оператора  for,  в  котором  индекс  пробегает  по  всем  строкам(ученикам).  Для  каждой  строки  тело  цикла  состоит  также  из  оператора for,  где  теперь  индекс пробегает  по  всем  столбцам(экзаменам) в  этой  строке. Тело  этого  внутреннего  оператора  for  состоит  только  из  оператора  read.

Вычисление  средних  включает  оператор  for, суммирующий  элементы  массива. Чтобы  просуммировать  оценки  некоторого  ученика(№3, например), напишем  оператор  for,  в  котором  индекс  пробегает  по  столбцам  строки  3:

for T := 1 to Tests do Sum := Sum + Grade[3, T];

Аналогично, чтобы  просуммировать  оценки  определенногоэкзамена(пусть  №2), напишем  оператор  for,  в  котором  индекс  пробегает  по  строкам  столбца  2:

for S := 1 to Students do Sum := Sum + Grade[S, 2];

  оригинале)Декларации  и  главная  программа  находятся  на  илл. 6.1, процедуры  вычисления  средних  - на  илл. 6.2, а  процедуры  ввода-вывода  - на  илл. 6.3.

 

program  GradeAverage;{Ввод: отметки  пяти  учеников  по  шести  дисциплинам }

{Вывод: таблица  отметок  учеников, их  средние  и  средние  по  дисциплинам }

const  Students = 6;   {число  учеников}

           Tests = 5;         {число  экзаменов}

type  GradeArrayType = array[1..Students,1..Tests] of integer; {таблица - двумерный  массив}

          StudentArrayType = array[1..Students] of real;                  {массив  учеников}

          TestArrayType = array[1..Tests] of real;   {массив  экзаменов}

var     Grade:      GradeArrayType;                {таблица  оценок}

           StudentAvg: StudentArrayType;         {средние  оценки}

           TestAvg:    TestArrayType;                 {средние  по  предметам}

  оригинале: см. отдельную  иллюстрацию  для  ReadGrade,WriteGrade;}

{см. отдельную  иллюстрацию  для  ComputeStudentGrade,ComputeTestAvg;}

procedure  ReadGrade(var Grade: GradeArrayType);

{На  выходе: оценки, введенные  в  массив  Grade}

var  S, T: integer;   {счетчики}

begin

  for S := 1 to Students do

    for T := 1 to Tests do read(Grade[S,T])

end{ReadGrade};

 

procedure WriteGrade(Grade: GradeArrayType; StudentAvg: StudentArrayType;

 TestAvg: TestArrayType);   {На  входе: таблица  оценок  Grade, средние  для  учеников}  

                                             {StudentAvg, средние  по  предметам  TestAvg}

 {На  выходе: вывод  таблицы  оценок  и  средних}

var S, T: integer;   {счетчики}

begin

  writeln('Ученик   ТАНАХ  Литерат.   Химия  История  Математ.  Средняя');

  for S := 1 to Students do

  begin

    write(S:5);

    for T := 1 to Tests do write(Grade[S,T]:8);

    writeln(StudentAvg[S]:8:1)

  end;

  writeln('-------    ------   -------     -----    ------   -------');

  write('средн.');

  for T := 1 to Tests do write(TestAvg[T]:8:1);

  writeln

end{WriteGrade};

procedure ComputeStudentAvg(Grade: GradeArrayType; var StudentAvg: StudentArrayType);

{На  входе: таблица  оценок  Grade}

{На  выходе: средние  оценки  учеников  в   StudentAvg}

var  Sum, S, T: integer;   {накопитель  и  счетчики}

begin

  for S := 1 to Students do

  begin

    Sum := 0;

    for T := 1 to Tests do Sum := Sum + Grade[S, T];

    StudentAvg[S] := Sum/Tests;

  end

end{ComputeStudentAvg};

procedure  ComputeTestAvg (Grade: GradeArrayType; var TestAvg: TestArrayType);

{На  входе: таблица  оценок  Grade. На  выходе: средние  оценки  по предметам в TestAvg}

var Sum, S, T: integer; {накопитель  и  счетчики}

begin

  for T := 1 to Tests do

  begin

    Sum := 0;

    for S := 1 to Students do Sum := Sum + Grade[S, T];

    TestAvg[T] := Sum/Students;

  end

end{ComputeTestAvg};

begin

  writeln('Введи  отметки: ‘, Students, ’  учеников, ‘, Tests, ‘ предметов');

  ReadGrade(Grade);

  ComputeStudentAvg(Grade, StudentAvg);

  ComputeTestAvg(Grade, TestAvg);

  WriteGrade(Grade, StudentAvg, TestAvg);

end.

          Илл. 6.1-6.3. Вычисление  средних  в  двумерном  массиве(с  продолжениями)

6.1.2. Объявление  двумерного  массива

R При  объявлении  типа - двумерного  массива  надо  записать  два  диапазрга  для  индексов: первый  для  строк, второй  для  столбцов. Диапазоны  не  обязаны  быть  одного  типа. Доступ  к  элементу  двумерного  массива  осуществляется  с  помощью  сдвоенного  индеса: A[Row, Column].

 

(На  число  измерений  массива  в  Паскале  нет  ограничений, но  мы  удовольствуемся  двумя  измерениями). Ниже  дана  задача, ее  цель - продемонстрировать, что  индекс  массива  не  обязан  быть  целого  типа.   

? Разработай  и  реализуй  алгоритм  заказа  мест  в  самолете. 

Ввод - последовательность  заказов  мест  в самолете. Каждая  просьба  состоит  из  номера  ряда(число)  и  имени  сидения(буква  от  ‘a’   до  ‘f’).

Вывод - после  каждой  просьбы  выводятся  места  с  буквой  ‘v’, означающей  свободное  место, и  с  буквой  ‘e’, обозначающей  заказанное  место.

Вопрос  6.2. Мы  не  охарактеризовали  условие  завершения  ввода. Опиши  возможный  способ.

Назначение  постоянных, типов  и  переменных:

const  Row = 20;        

type  SeatType = array[1..Rowsa’..’f’] of  boolean; {true, если  место  заказано, иначе  false}

var    Seats:      SeatType;                {данные  о  местах}

k АЛГОРИТМ  ЗАКАЗ_МЕСТА

             ПРИВЕДЕНИЕ_МАССИВА_В_НАЧАЛЬНОЕ_СОСОЯНИЕ(Seats)

             ВВОД_ПРОСЬБ_И_ВЫВОД_МАССИВА(Seats)

 

k АЛГОРИТМ  ПРИВЕДЕНИЕ_МАССИВА_В_НАЧАЛЬНОЕ_СОСОЯНИЕ(Seats)

             Для  каждой  строки  R  выполняй

                    для  каждого  места  С  выполняй

                            подставь  значение  false  в  Seats[R,C]

 

k АЛГОРИТМ  ВВОД_ПРОСЬБ_И_ВЫВОД_МАССИВА(Seats)

             До  тех  пор  пока  есть  просьба  выполняй

                             введи  номер  строки  R    

                             введи  номер  сидения  С

                            если  место Seats[R,C]  свободно  то

                                      подставь  значение  true  в  Seats[R,C]

                            иначе  

                                      выведи: место  не  свободно

                             ВЫВЕДИ_МАССИВ(Seats)

Реализация. Процедура  реализации  алгоритма  ВВОД_ПРОСЬБ_И_ВЫВОД_МАССИВА  представлена  на  илл. 6.4.

procedure  RequestSeats(var  Seats: SeatType);  

{На  входе: в  каждом  элементе  Seats  значение  false}  

{На  выходе: на  заказанных  местах - значенеие  true}

var  R: integer;   {ряд}

        C: char;      {сидение}

begin

  writeln('Набери  номер  ряда  от  1  до  20(для  останова 0)');  readln(R);

  while  R > 0  do

  begin

    writeln(‘Набери  место  от  a  до  f ’);  readln(C);

    if Seats[R,C] then  writeln(‘Место  не  свободно’)

    else Seats[R,C] := true;

    Print(Seats);  {процедура  печати  всего  салона}

    writeln('Набери  номер  ряда  от  1  до  20(для  останова 0)');  readln(R); 

end{ReqiestSeats};

                               Илл. 6.4. Процедура  заказа  мест  в  самолете

Вопрос  6.3. Разработай  алгоритм  вывода  массива  сидений.

Вопрос  6.4. Напиши  программу  реализации  алгоритма  вывода  массива  сидений.

Вопрос  6.5. Напиши  объявление  типа  для  шахматной  доски.

Вопрос  6.6. Дана  квадратная  таблица:

const  Max = 100;        

var  Table = array[1..Max,1..Max] of  integer;

 

a).Напиши  цикл, суммирующий  диагональные  элементы  от  Table[1,1] до Table[100,100].

b).Напиши  цикл, суммирующий  диагональные  элементы  от  Table[1,100] до Table[100,1].

 

6.1.3. Массив  массивов - расширение

Вернемся  к  задаче  средних  оценок. Вместо  того, чтобы  хранить  данные  в  одном  большом  массиве  с  30-ю  оценками  или  в  двухмерном  массиве, можно  для  этого  использовать  массив  массивов:

S[1]

S[2]

S[3]

S[4]

S[5]

S[6]

                                                        ä                           ã

T[1]

T[2]

T[3]

T[4]

T[5]

В  массиве  S  каждому  из  шести  учеников  соответствует  один  элемент, а  каждый  элемент  в  себе  содержит  массив  из  пяти  целых  чисел. В  Паскале  мы  можем  объявить  эту  структуру  данных  так: 

const        Tests = 5;         {число  экзаменов}

                  Students = 6;   {число  учеников}

type   TestArrayType = array[1..Tests] of real;   {массив  экзаменов}

           GradeArrayType = array[1..Students] of TestArrayType;

                                   {массив  масивов  экзаменов  всех  учеников}

var     Grade:      GradeArrayType;                           {таблица  оценок}

Каждый  элемент  массива  Grade  сам  по  себе  является  массивом. Например Grade[3], обозначающий  третий  элемент  в  массиве Grade, есть  массив  из  пяти  элементов, как  можно  видеть  на  иллюстрации  выше.

На  секунду  задумаемся ... Какой  тип  у  выражения Grade[3]?

Grade[3]  имеет  тип TestArrayType, т.е.  тип-массив! Подобно  любому  другому  массиву  к  нему  можно  присоединять  индекс. Grade[3][5]  есть  последний  элемент  этого  “элемента-массива”. В программе  вычисления  средних  единственное  различие  состоит  в  том, что  надо  заменить Grade[S, T]  на  Grade[S][T]. (Примечание. В  действительности  Паскаль  разрешает  писать Grade[S, T]  и  для  массива  массивов).

Преимущество  массива  массивов  в  том, что  он  позволяет  писать  один  индекс  и  получать  массив. И  если  есть  у  нас  процедура, принимающая  параметр  типа TestArrayType, к  ней  можно  обращаться  и  со  значением  вроде Grade[I]:

procedure PrintTests(Test: TestArrayType); 

begin

  .......

end;

 

for S := 1 to Students do  PrintTests(Grade[S]);

Вопрос  6.7.Напиши  программу,  вводящую  список  номеров  удостоверений  личности  и  сортирующую  ее  по  контрольной(последней) цифре. Номер  удостоверения  личности  состоит  из  9  цифр, хранить  его  надо  в  (типе)  массиве  символов:

const        Max = 10;        

                 IDLen = 9;  

type   IDType = array[1..IDLen] of char;  

          ListType = array[1..Max] of IDType;

var     Liste:      ListType;                         

 

6.2. Записи

? Твоя  команда  разрабатывет  компьютерную  систему  для  нового  ресторана. В  нем  будет  продаваться  еда, составленная  из  гамбургеров, чипсов  и  колы (илл. 6.5), которые можно  заказывать  разного  веса. Электронные  весы  будут  взвешивать  компоненты  еды  и  вычислять  ее  цену, согласно  веса  и  цены  единицы  каждого  продукта. Твоя  задача  разработать  функцию, определяющую  цену  еды  на  основе  ее  компонент.

 

 

           |  ОСОБАЯ  |

    ¦                                 U

гамбургер    чипсы             кола

    Илл. 6.5. Еда  на  подносе

Из  илл.  мы  видим, что  удобно  “паковать”  компоненты  трапезы  на  поднос, чтобы  облегчить  перенос  еды  от  стойки  к  столу.

Вопрос  6.8.Напиши  другие  примеры  упаковок, содержащих  разрозненные  предметы  в  одном  модуле.

Чтобы  решить  эту  задачу, нам  нужен  тип, который  мы  определим  как  “трапеза(еда)”, тогда  мы  сможем  объявить  функцию, которая  принимает  одиночный  параметр  этого  типа.

type MealType = ???

function ComputePrice(M: MealType): real; {На  входе: еда  в  М}

                                                                      {На  выходе: возвращает  цену  еды}

На  секунду  задумаемся ... Знаком  ли  тебе  способ  “упаковки”  нескольких  данных  в  составной  тип?

Конечно. Массив  есть  тип  для  содержания  более  простых  значений  в  составных  переменных. Например, поместили  в  массив  количество  очков, набранных  баскетболистами  одной  команды, и так  смогли  передать  этот  массив  полностью  процедуре  для  вычисления  максимума:

type PointType = array[1..Max] of integer;

function Max(Points: PointType): integer;

На  секунду  задумаемся ... Годится  тип - массив  для  хранения  описания  трапезы?

Прежде  чем  ответить  на  этот  вопрос  сформулируем, какие  значения  составят  описание  трапезы. Есть  у  нас  строка  с  именем  трапезы(например, ‘  ОСОБАЯ  ’), вес  компонент, вроде  250  грамм  гамбургера, и  цены  компонент  за  единицу  веса, пусть  28.70  шекелей  за  кг  гамбургера. Ясно, что  массив  это  не  тот  тип, который  может  хранить  такие  значения, т.к.  массив  состоит  их  элементов  одного  типа.

Тип, соответствующий  помещению  значений  разных  типов, называется  запись. Запись  есть  тип, составленный  из  элементов, называемых  полями(fields):

type NameType = array[1..10] of char;

       MealType =

       record

        Name: NameType;                    {название  трапезы}

        Hamburger: integer;                  {вес гамбургера  в  граммах}

        HPrice: real;                              {цена  в  шек. за  кг  гамбургера}

        Chips: integer;                           {вес  чипсов  в  граммах}

        CPrice: real;                              {цена  в  шек. за  кг  чипсов}

      end;

Чтобы  прочесть  из  поля  или  записать  в  поле  некоей  записи  надо  осуществить  операцию  выбора, которая  обозначается  точкой.

Дано  объявление  переменной  М  типа  MealType, имя  M.Hamburger  дает  вес  гамбургера  в граммах, а  имя M.HPrice  дает  его  цену  в  шекелях  за  кг  и  т.д. Ниже  приведено  выражение, вычисляющее  цену  трапезы: 

ComputePrice := (M.Hamburger/1000.0)*M.HPrice + (M.Chips/1000.0)*M.CPrice

Решение  задачи, представленной  в  начале  подпараграфа, находится  на  илл. 6.6.

program MealPrice;{Ввод: название  трапезы, вес гамбургера  и  чипсов, их  цена  за  кг}

{Вывод: программа  печатает  окончательную  цену  еды}

const NameLength = 10;

type NameType = array[1..10] of char;

       MealType =

       record

        Name: NameType;                    {название  трапезы}

        Hamburger: integer;                  {вес в  граммах}

        HPrice: real;                              {цена  в  шек. за  кг}

        Chips: integer;                           {вес  в  граммах}

        CPrice: real;                              {цена  в  шек. за  кг}

      end;

 

var M: MealType;                    {для  ввода  имени  трапезы}

      Price: real;                         {для  вычисления  цены}

      I: integer;                           {счетчик}

procedure  GetMeal(var M: MealType);{На  выходе: описание  еды, введенное  в  М}

begin

  writeln('Имя  трапезы -',NameLength,' букв');

  for I := 1 to NameLength do read(M.Name[I]);    readln;

  writeln('Вес  гамбургера  в  граммах');               readln(M.Hamburger);