ПРЗ на ЭВМ ( метод рекурсии)

Рекурсия Рекурсия это метод программирования, при котором процедура или функция непосредственно или через другие процедуры или функции обращается сама к себе как ко вложенной процедуре или функции. Это бывает необходимо или удобно для решения целого ряда задач. При использовании рекурсии текст программы и ее алгоритм сокращается и упрощается в несколько раз. Рекурсию следует использовать с осторожностью, так как иногда слишком много рекурсивных вызовов быстро исчерпывают свободную память.Примеры решения задачи с использованием рекурсии Задача 1 Имеется n населенных пунктов, перенумерованных от 1 до n n10. Некоторые пары пунктов соединены дорогами. Определить с применением рекурсии, можно ли попасть по этим дорогам из 1-го пункта в n-й. Информация о дорогах задается в виде пар чисел i и j i j, указывающих, что i-й и j-й пункты соединены дорогой, признак конца этой последовательности пара нулей. uses crt const nn10 var rout,rstring aarray0 nn,0 nn of char i,j,ninteger cchar okboolean procedure routerotkuda,gde ,kudaintegervar okboolean рекурсивная про- var iinteger цедура begin agde,otkuda ставится на время выполнения процедуры для aotkuda,gde исключения зацикливания процедуры if gdekuda then begin strkuda,r oktrue end else for i1 to nn do цикл проверки пути по всем направлениям begin if okfalseandai,gdey then begin routergde,i,kuda,ok рекурсивный вызов процедуры if oktrue then begin strgde,r end end end agde,otkuday y - в данном направлении есть дорога aotkuda,gdey end begin начало программы clrscr writelnВведите пути repeat writeОткуда readlni if i 0 then begin writeКуда readlnj writelni, ,j if j 0 then if i nnorj nn then writeln Неверный ввод else begin ai,jyaj,iyend else end until i0orj0 repeat oktrue repeat writeКуда попасть из 1 rout readlnn if n 0 then writelnНет такого else if n1 then writelnУже здесь else okfalse until okfalse router0,1,n,ok результат okfalse дороги нет, oktrue дорога есть if okfalse then writelnНельзя else writelnМожно creadkey until c end. Введите пути Откуда 1 Куда 2 Откуда 1 Куда 4 Откуда 2 Куда 3 Откуда 4 Куда 6 Откуда 4 Куда 5 Откуда 6 Куда 10 Откуда 00 Куда попасть из 10 Можно Задача 2 Описать рекурсивную функцию powx,n от вещественного x x и целого n, которая вычисляет величину согласно формуле 1 , при n0 1 , при n 0 x , при n 0 uses crt var ninteger xreal function powxreal ninteger real рекурсивная функция begin if n0 then pow1 else if n 0 then pow1powx,absn else powxpowx,n-1 рекурсивный вызов pow end begin начало программы clrscr writeВведите x readx writeВведите n readn writelnpow ,powx,n23 readkey end. x 2 n 0 pow 1.000 x 2 n 3 pow 8.000 x 2 n -3 pow 5 Перечислимые типы Перечислимый тип это тип составленный из множества упорядоченных элементов. Перечислимый тип задается перечислением всех своих элементов, то есть перечисляются все возможные значения переменных этого типа. Над переменными перечислимого типа можно выполнять только операции отношения, поскольку значения перечислимого типа упорядочены, то есть каждому значению ставится в соответствие его порядковый номер.

Задача Type страна Германия, Куба, Лаос, Монако, Непал, Польша континент Азия, Америка, Европа.

По s названию страны определить c название континента. uses crt type kontinentAzia, Amerika,Evropa перечислимые типы stranaGermania,Kyba,Laos,Monako,Nepal,Po lsha var ckontinent sstrana xstring begin начало программы clrscr write Введите название страны ,xreadlnx if xГермания then sGermania if xКуба then sKyba if xЛаос then sLaos if xМонако then sMonako if xНепал then sNepal if xПольша then sPolsha case s of выбор континента по стране Laos,Nepal cAzia Kyba cAmerika Germania,Monako, Polsha cEvropa end if cAzia then writelnКонтинент Азия вывод на экран if cAmerika then writelnКонтинент Америка if cEvropa then writelnКонтинент Европа readln end. введите название страны Куба Континент Америка введите название страны Германия Континент Европа введите название страны Лаос Континент Азия Динамические переменные Динамические переменные это переменные, которые могут создаваться и уничтожаться в процессе работы программы.

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

Задача Работа с динамическими переменными - организация списков USES CRT Type Str string80 Adr Zap Zap Record Inf Integer Ssylka Adr End procedure sortVar Nachadr Сортировка списка Var i,nintegerQBoolean P,XAdr Begin n0 Qfalse If NachNil then writelnСписок отсутствует, введите список else Begin PNach while P Nil do Begin nn1 PP.Ssylka end while not Q do begin QtruePNach if Nach.inf Nach.Ssylka.inf then begin NachNach.Ssylka P.SsylkaNach.Ssylka Nach.SsylkaP Qfalse end xNach.SsylkaPNach for i1 to n-2 do if x.inf x.Ssylka.inf then begin p. Ssylka x.Ssylka x.Ssylkax.Ssylka.Ssylka P.Ssylka.Ssylkax PP.Ssylka Qfalse end else begin Pxxx.Ssylka end end end end Procedure Print PAdr Вывод списка на экран Var RAdr Begin Writeln WritelnПечать списка RP Writeln While R Nil Do Begin WriteR.Inf, RR.Ssylka End WritelnWritelnWritelnСписок окончен End Procedure schNachadr Подсчет числа элементов списка var radr iinteger begin i0 rnach while r nil do begin ii1 rr.ssylka end writelnКоличество элементов ,i end procedure DobKonVar NachAdr Создание списка путем добавления элементов в конец Var R,QAdrAinteger Begin NachNil Repeat writeВведите число, признак конца 999 readlnA if A 999 then Begin if NachNil then Begin NewNachNach.infANach. SsylkaNilQNachend else Begin NewQ.SsylkaQQ.SsylkaQ.infAQ.SsylkaNIL end end Until A999 end procedure DobNachVar NachAdr Создание списка путем добавления элементов в начало Var R Adr A Integer begin nachnil repeat write Введите число, признак конца 999 readlna if a 999 then begin newr r.infa r.ssylkanach nachRend Until a999 end var R integer Function PoiskNachAdrRIntegerAdr Поиск элемента R в списке рекурсивный результат - адрес этого элемента Nil, если элемент не найден Begin If NachNil Then PoiskNil Else If Nach.InfR Then PoiskNach Else PoiskPoiskNach.Ssylka,R end Procedure VstavZNachAdr Вставка в список элемента после элемента с заданным значением Var AZ,AVst,RAdrАдрес заданного элемента и адрес вставленного, рабочий адрес Z Integer Begin WriteВведите элемент, после которого хотите произвести вставку ReadlnZ RNach While R.Ssylka Nil And R.Inf Z do пока не закончится список или не найдется нужный элемент RR.Ssylka продвигаемся по списку If R.Inf Z Then WritelnЗаданного элемента нет Else Begin NewAvst Avst.SsylkaR.Ssylka WriteЧто хотите вставить ReadlnAvst.Inf R.SsylkaAvst End End Procedure IsklNVar NachAdr Исключение из списка элемента с заданным номером Var N, I Integer Номер исключаемого элемента, текущий номер R Adr Текущий адрес Begin WriteВведите номер удаляемого элемента ReadlnN If N1 Then NachNach.Ssylka Else Begin RNach I1 While R.SSylka Nil And I N-1 Do Пока не кончился список или не дошли до элемента с предшествующим номером Begin RR.Ssylka II1 End If R.ssylkaNil Then WritelnЭлемента с таким номером нет Else R.SsylkaR.Ssylka.Ssylka End End Procedure PrintFVar NachAdrVar Sstr Запись списка в файл на диск Var FTextRAdr Begin WriteИмя файла readlns AssignF,s rewriteF If Nach nil then Begin writelnF Список элементов writelnF RNach While r Nil do Begin writeF,R.inf6 RR.Ssylka end writelnFwritelnf WritelnF Список окончен closeF WritelnЗапись списка в файл ,s, произведена end else writelnСписок отсутствует, введите список end function KolichVar NachAdrrintegerinteger Сколько раз встречается заданный элемент var Padr iinteger begin i0 Pnach while P nil do begin if P.infr then ii1 PP.ssylka end Kolichi END procedure Skleikavar Nachadrvar Nach1adr var radr begin rnach while r.ssylka nil do rr.ssylka r.ssylkanach1 end Var F Text x,y,t,Xx Integer s,key Char s1 Str Var Nach,Nach1,q,PPP Adr Const K12Количество вариантов в меню Begin NachNil Repeat x3 y1 ClrScr Writeln 0. Конец работы Writeln 1. Печать списка Writeln 2. Создание списка путем добавления элементов в начало Writeln 3. Есть ли в списке заданный элемент Writeln 4. Вставка элемента после заданного Writeln 5. Удаление элемента с заданным номером Writeln 6. Сколько раз встречается заданный элемент Writeln 7. Подсчитать количество элементов списка Writeln 8. Склеить два списка Writeln 9. Создание списка путем добавления элемента в конец Writeln 10. Запись списка в файл на диск Writeln 11. Сортировка списка Repeat GotoxyX,Y sreadkey if s0 then sreadkey tords Case t of 72if y 1 then yy-1 else yk 80if y k then yy1 else y1 End Until t13 ClrScr Case Y-1 of 1Begin writelnИспользовать PrintNach PrintNach end 2 Begin writelnИспользовать DobNachNachPrintNach DobNachNach PrintNach end 3 Begin writeln Использовать PrintNach,PoiskNach,R repeat PrintNach writeВведите элемент, который надо найти readlnR pppPoiskNach,R if ppp nil then writelnЭлемент найден ,ppp.inf else writelnЭлемент не найден PrintNach writelnwritelnПовторить until readkeyn end 4 Begin writeln Использовать PrintNach,VstavZNach repeat PrintNach VstavZNach PrintNach writelnwritelnПовторить until readkeyn end 5 Begin writeln Использовать PrintNach,IsklNNach repeat PrintNach IsklNNach PrintNach writelnwritelnПовторить until readkeyn end 6 Begin writelnСоздать свою процедуру KolichNach PrintNach writeВведите элемент, который надо найти readlnR writelnЭлемент в списке встречается ,KolichNach,r, раза end 7 Begin writelnИспользовать printNach и schNach printNach schNach end 8 Begin writelnСоздать свою процедуру SkleikaNach,Nach1 writelnВведите второй список dobkonnach1 printnach printnach1 SkleikaNach,Nach1 printnach end 9 Begin writelnИспользовать DobKonNachPrintNach DobKonNach PrintNach end 10 Begin writelnИспользовать PrintFNach,S1 PrintFNach,S1 end 11 Begin writeln Использовать sortNach PrintNach printNach sortNach printNach end End writelnwritelnНажми любую клавишу, кроме Enter repeat keyreadkey until key 13 Until Y1 End. Создание списка путем добавления элемента в конец. Использовать DobKonNachPrintNach Введите число,признак конца 999 1 Введите число,признак конца 999 4 Введите число,признак конца 999 6 Введите число,признак конца 999 2 Введите число,признак конца 999 8 Введите число,признак конца 999 11 Введите число,признак конца 999 2 Введите число,признак конца 999 5 Введите число,признак конца 999 999 Печать списка 1 4 6 2 8 11 2 5 Список окончен Сколько раз встречается заданный элемент Создать свою процедуру KolichNach Печать списка 1 4 6 2 8 11 2 5 Список окончен Введите элемент, который надо найти 2 Элемент в списке встречается 2 раза Есть ли в списке заданный элемент.

Использовать PrintNach,PoiskNach,R Печать списка 1 4 6 2 8 11 2 5 Список окончен Введите элемент, который надо найти 6 Элемент найден 6 Введите элемент, который надо найти 10 Элемент не найден Склеить два списка.

Создть свою процедуру SkleikaNach,Nach1 Введите второй список Введите число,признак конца 999 1 Введите число,признак конца 999 2 Введите число,признак конца 999 3 Введите число,признак конца 999 999 Печать списка 1 2 5 6 3 Список окончен Печать списка 1 2 3 Список окончен Печать списка 1 2 5 6 3 1 2 3 Список окончен.