.RU

Занятие 2. Примеры задач рекурсивного решения в текстовом и графическом режимах


^ Занятие 2. Примеры задач рекурсивного решения в текстовом и графическом режимах.
Задача 1. Нахождение n-го члена арифметической прогрессии

(an=a1+d*(n-1)-формула n-го члена арифметической прогрессии).

Program Progressiy;

Var

a1, d, k: real;

n: integer;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Function Arif (a1, d: real; n: integer): real;

Begin

if n = 1

then

Arif := a1

else

Arif := Arif(a1, d, n - 1) + d;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin

writeln('Задайте первый член прогрессии');

readln(a1);

writeln('Задайте разность арифметической прогрессии');

readln(d);

writeln('Арифметическая прогрессия ', Аrif(a1, d, n) : 4 : 2);

End.

Задание. Составьте программу

a) нахождения n-го члена геометрической прогрессии,

б) нахождения суммы членов арифметической прогрессии,

в) нахождения суммы членов геометрической прогрессии,

г) нахождения n-го члена ряда Фибоначчи.

Задача 2. Вложенность квадратов.

Program KaparovS;

Uses

Crt, Graph;

Var

x, y, x1, y1, x2, y2, x3, y3, n, d, a, b : integer

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure Pic(x, y, x1, y1, x2, y2, x3, y3, n, d : integer);

Var

k, j : integer;

Begin

if n >=1

then

begin

Line(x, y, x1, y1);

Line(x1, y1, x2, y2);

Line(x2, y2, x3, y3);

Line(x3, y3, x, y);

j := x;

k := y;

x := (x1-x) div 2 + x;

y := (y1-y) div 2 + y;

x1 := (x2-x1) div 2 + x1;

y1 := (y2-y1) div 2 + y1;

x2 := (x3-x2) div 2 + x2;

y2 := (y3-y2) div 2 + y2;

x3 := (j-x3) div 2 + x3;

y3 := (k-y3) div 2 + y3;

Pic(x, y, x1, y1, x2, y2, x3, y3, n-1, d);

end;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin

ClrScr;

write ('Введите количество повторений: ');

readln (n);

x := 0;

y := 0;

x1:= 400;

y1 := 0;

x2:= 400;

y2 := 400;

x3:= 0;

y3 := 400;

a : Detect;

InitGraph(a, b, 'D:\TP7\BGI');

ClearDevice;

Setcolor(Green);

Pic(x, y, x1, y1, x2, y2, x3, y3, n, d);

readln;

CloseGraph;

End.

Задание. Наберите программу и просмотрите ее действие. Дополните программу комментарием. По желанию улучшите алгоритм.

Творческое задание. Придумайте и решите задачу на демонстрацию рекурсии в графическом режиме.

^ Занятие 3. Косвенная рекурсия.
Рассмотренные выше программы использовали так называемую прямую рекурсию, когда в теле некоторой процедуры содержался непосредственный вызов самой себя. В языке Паскаль допускается также и косвенная рекурсия, когда, например, процедура, процедура А вызывает процедуру В, а та, в свою очередь,– процедуру А. Длина таких цепочек вызовов может быть произвольной, однако при разработке программы необходимо тщательно следить за тем, чтобы рекурсивный алгоритм был сходимым, то есть не приводил к бесконечным взаимным вызовам подпрограмм.

Образно косвенную рекурсию можно описать так. Перед зеркалом 1 стоит зеркало 2, в котором отражается само зеркало 1. В последнем видно зеркало 2 и т.д.

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

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

Program KosvRecurs;

Var

A : integer;


Procedure Rec2 (Var Y:integer); Forward;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure Rec1 (Var X:integer);

Begin

X := X-1;

if X>0

then

Rec2;

writeln (X)

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure Rec2 (Var Y:integer);

Begin

Y := Y div 2;

if Y>2

then

Rec1;

writeln (Y)

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin

A := 15;

Rec1(A);

End.

Творческое задание. Придумайте и решите задачу на демонстрацию косвенной рекурсии в графическом режиме.
^ Занятие 4. Решение задач
1. Определите члены последовательность Фибоначчи.

2. Найдите максимальный элемент в одномерном массиве.

3. Составьте алгоритм вычисления суммы .

Указание. Обозначьте и используйте соотношения



4. Вычислите

5. Определите n–й член последовательности, в которой каждый следующий член равен сумме обратных величин всех предыдущих.

6. Определите n–й член последовательности, в которой каждый следующий член равен сумме квадратов всех предыдущих.

7. При положительном а решением уравнения х=х/2+а/(2х) служит х=. Рекуррентное соотношение

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

8. Составьте алгоритм для вычисления , используя соотношение



9. Составьте алгоритм, вычисляющий n–й член последовательности, заданной соотношениями:



10. Составить рекурсивную программу ввода с клавиатуры последовательности чисел (окончание ввода - 0) и вывода ее на экран в обратном порядке.

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

^ Для любознательных. Ханойские башни. Задача о разрезании прямоугольника
Ханойские башни – это древняя игра. Заключается она в следующем. Имеются три стержня, на одном из них (например, на правом) насажены диски разных размеров, причем диски располагаются так, чтобы стержень с дисками напоминал башню, т.е. внизу располагаются самые большие диски, а вверху – маленькие. Цель игры – перенести башню с правого стержня на левый, причем за один раз можно переносить только один диск и при этом можно насаживать только диск с меньшим диаметром на диск с большим диаметром. Средний стержень является вспомогательным для временного хранения дисков.

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

Пронумеруем стержни слева направо и договоримся переносить диски с правого (3) стержня на левый(1).

Program Tower;

Type

Position = (Left, Centre, Right);

Var

N : integer;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure MoveDisk (From, Tol : Position);

Procedure writePos (P : Position);

Begin

case P of

Left : write ('1');

Centre : write ('2');

Right : write ('3');

end;

End;

Begin

writePos (From);

write('->');

writePos (Tol);

writeln

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Procedure MoveTower(Hight : integer; From, Tol, Work : Position);

Begin

if Hight>0

then

begin

MoveTower(Hight-1, From, Work, Tol);

MoveDisk (From, Tol);

MoveTower(Hight-1, Work, Tol, From);

end;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin

writeln('Введите количество колец ');

readln(N);

MoveTower(N, Right, Left, Centre);

End.

Задание. Изучите текст программы. Введите текст программы, запишите файл на диск и откомпилируйте его. после того, как компиляция выполнится успешно, задайте для просмотра в окне отладчика переменные Hight, From, Tol, Work. Установите видимыми одновременно окно редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в процедуры и пронаблюдайте за рекурсивным вызовом процедуры MoveTower. Дополните программу операторами графического режима, чтобы наглядно можно было представить перенос дисков со стержня на стержень. Дополните текст программы комментариями.

Рассмотрим задачу о разрезании прямоугольника.

Задача. Дан прямоугольник со сторонами А и В, где А, В – натуральные числа. Начинаем отсекать от него квадраты. Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?



Для решения этой задачи нам нужны будут функции Max и Min для переопределения длины и ширины прямоугольника. А также введем вспомогательные переменные Х и У (У>=Х), соответствующие уменьшающимся сторонам прямоугольника, и вспомогательную переменную D, которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как Х:=Min(D, X) и продолжаем цикл.

В программе нам нужно организовать цикл, в котором сторона У уменьшается каждый раз на Min(D, X) до тех пор, пока не останется последний квадрат или У не станет меньше Х. В последнем случае переименовываем стороны оставшегося прямоугольника как Y := Max(D, X) и X := Min(D, Х) и продолжаем цикл.


Program OtsehKvadr;

Var

A, B, D, K, X, Y : integer;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Function Min(I,J : integer) : integer;

Begin

If I
Then

Min := I

Else

Min := J;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Function Max(I,J : integer) : integer;

Begin

if I>J

then

Max := I

else

Max := J;

End;

{- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -}

Begin

repeat

writeln ('Введите два натуральных числа ');

readln(A,B);

until (A>0) and (B>0);

K := 1;

X := Min(A, B);

Y := Max(A, B);

while XY do

begin

K := K+1;

D := Y-X;

Y := Max(D, X);

X := Min(D, X);

end;

writeln('Искомое число квадратов : ',K);

End.

Задание. Наберите текст программы. Проверьте ее работоспособность. Дополните программу комментариями. Если у Вас возникло желание, то усовершенствуйте эту программу своими дополнениями. Результат покажите учителю для оценки.
^ Анализ рекурсивных алгоритмов
При изучении темы "Рекурсия" полезно проанализировать рекурсивные алгоритмы с точки зрения последовательности их выполнения. Под последовательностью выполненного рекурсивного алгоритма будем понимать последовательность вызовов алгоритма с различными значениями аргументов и очередью определения результатов.

Рассмотрим сначала функцию расчетов факториала числа (см. выше)

Для алгоритма определения 5-го члена ряда Фибоначчи схема нахождения изображена на рисунке:



Чтобы определить значение 5-го элемента Фибоначчи, для этого необходимо определить значения fib(2), fib (1), fib (3), fib (2). Из схемы видно также , что в рассматриваемом случае значения fib (1), fib (3), fib (2) определяются дважды. При нахождении члена последовательности с большим номером число повторных вычислений значительно увеличивается. В результате при определения значения fib (17) компьютер выполнит свыше 1000, значения fib (31) свыше 1000000, значения fib (45) свыше 1000000000 операций сложения. В тоже время при использовании не рекурсивного алгоритма для вычисления 45-го члена потребуется всего 43 операции сложения.

Это позволяет сделать вывод о неэффективности использования рекурсии для решения рассматриваемой задачи. Аналогичный вывод можно сделать для решения других задач.
^ Особенности отладки и компиляции программ, содержащих процедуры и функции
При пошаговой отладке программ, содержащих процедуры и функции, при нажатии клавиши F7 в строке, которая содержит вызов подпрограммы, мы переходим в начало (на слово begin) данной подпрограммы. При завершении работы подпрограммы – если подсвечена конечная строка end или exit. При следующем нажатии F7 мы возвращаемся в ту строку основной программы, с которой попали в подпрограмму. Постоянный заход в подпрограммы часто бывает не нужен. Для пошагового исполнения основной программы без захода в подпрограммы используйте клавишу F8.

В меню Debug предусмотрено специальное окно для просмотра последовательности вызываемых функций и процедур. Это окно открывается клавишами Ctrl+F4 или через пункт меню Debug/Call stack. В этом окне прослеживается текущее, то есть изменяющееся при пошаговой отладке, состояние стека вызова подпрограмм. В верхней строке – исполняемая в данный момент подпрограмма, в нижней – основная программа, в промежутке между ними – последовательность вызовов подпрограмм от основной программы до текущей программы.

При выходе из подпрограммы стек программы освобождается от ее вызова, и верхняя строка в окне стека убирается. Это окно следует применять при сложной иерархии взаимных вызовов подпрограмм, когда не очевидно, каким путем выполнение алгоритма привело к данной подпрограмме.

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

Пункты этого меню позволяют выбрать расположение окон на экране, переключаться между окнами, закрывать окна. Пункт Tile разделяет экран на отдельные кусочки, в каждом из которых находится свое окно. Такой способ разбиения имеет смысл применить, если открыто 2-4 окна. Пункт Cascade накладывает окна одно на другое таким образом, что край нижних окон виден из-под верхних. При таком раскладе окон каждое из них имеет достаточно большой размер и легко может быть активизировано.



Переключение между окнами производится нажатием клавиш, указанными в меню. Для изменения размера и положения окна нужно нажатием клавиш Ctrl+F5 вызвать пункт Size/Move. Размеры окна изменяются клавишами перемещения курсора. Когда требуемый размер установлен, нужно нажать Enter для фиксации положения окна. Если Вы забудете нажать Enter, все действия будут блокированы. Для перемещения окна при нажатии клавиш управления курсором надо держать нажатой клавишу Shift.

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

По нажатию клавиш Alt+F9 компилируется программа или модуль, находившиеся в активном окне. Используемые этой программой модули должны быть предварительно откомпилированы.

Компиляцию проектов, состоящих из нескольких модулей, удобно производить, установив основной файл – это, как правило, файл с основной программой. Для этого выбирается пункт Primary file и вводится имя файла. Уничтожение этой записи производится путем выбора пункта Clear primary file. Если начальный файл установлен, компиляция или компиляция с исполнением происходит всегда так, как будто активным окном являлось окно основной программы. Это позволяет вносить изменения в отдельных модулях и сразу запускать компиляцию и исполнение всего проекта, не переключаясь специально к основной программе.

Для подключения к основной программе модулей компилятор ищет их прежде всего в рабочем каталоге, а затем в каталогах, указанных в строке Units окна настройки, которое появляется при выборе пункта меню Options/Directories.

При нажатии клавиши F9 (Make) прежде всего происходит компиляция начального файла, заданного в строке Primary file. Если эта строка пуста, компиляция начинается с активного окна. когда в процессе компиляции программы или модуля встречаются ссылки на другие модули, проверяется необходимость перекомпиляции подключаемых модулей. Проверка заключается в сверке изменений файла с текстом модуля на Паскале и откомпилированного модуля (по времени внесения последних изменений в файл). Если в текст были внесены изменения, данный модуль компилируется вновь. Если файл модуля с текстом не найден , берется откомпилированный файл без проверки. Эта опция компилятора оптимальна по затратам времени на компиляцию, так как компилируется только то, что нужно. Компиляция и запуск на исполнение, вызываемые клавишами Ctrl+F9, производит компиляцию по данной логике.

В ряде случаев нам необходима обязательная перекомпиляция всех файлов (Build). В частности, это необходимо, если мы изменили опции компиляции в меню Options/Compiler. Изменение опций компиляции через окно не прослеживается далее автоматически, то есть среда не определяет, откомпилирован файл с новыми или старыми опциями, и не производит автоматически перекомпиляцию. Для полной компиляции всех файлов вызывается пункт Build.

Пункт Target устанавливает, для какой платформы – реального режима, защищенного режима или Windows – должны компилироваться файлы.

yunie-talanti-moskovii.html
yunih-spasatelej-proveli-ekskursiej-po-glavku-mchs-v-habarovske-informacionnoe-agentstvo-primamedia-27062011.html
yunij-patriot.html
yunij-vilgelm-tell-povest-skazka.html
yunoj-novgorodke-s-tyazhelim-zabolevaniem-trebuetsya-pomosh-blagotvoritelnij-fond-absolyut-pomosh-otprazdnoval-10-letie.html
yunosheskie-chteniya-proizvedeniya-f-m-dostoevskogo-v-vospriyatii-chitatelej-hh-iveka.html
  • lecture.largereferat.info/analiz-proizvodstvenno-hozyajstvennoj-deyatelnosti-predpriyatiya.html
  • studies.largereferat.info/analiz-sebestoimosti-tovarnoj-produkcii-na-primere-oao-nizhnekamskshina.html
  • reading.largereferat.info/kvartalnij-otchet-10-v-ramkah-konchinopochitaniya-kakie-sobitiya-2006-goda-okazali-naibolshee-vliyanie-na-ekonomiku-rossii-igroki-stranica-2.html
  • vospitanie.largereferat.info/zarabotnaya-plata-ezhegodnie-dopolnitelnie-otpuska-zabastovka-kommentarij-k-trudovomu-kodeksu-rossijskoj-federacii.html
  • education.largereferat.info/20092010-uchebnij-god-voprosi-k-gosekzamenam.html
  • turn.largereferat.info/odnoklassniki-aleksandr-fedorov.html
  • portfolio.largereferat.info/polozhenie-o-sorevnovaniyah-po-preodoleniyu-prepyatstvij.html
  • lesson.largereferat.info/sahalinskie-korejci.html
  • ekzamen.largereferat.info/sovremennogo-istorika-uchebnoe-posobie-po-speckursu-dlya-studentov-obuchayushihsya-po-specialnosti-istoriya.html
  • knigi.largereferat.info/sergiev-posad-gorod-masterov-sergiev-posad-ves-sergiev-posad-2000-24-s.html
  • predmet.largereferat.info/shkolnij-centr-aerokosmicheskih-issledovanij-dlya-uchastiya-v-konkursnom-otbore-proektov.html
  • thescience.largereferat.info/gribi-kbr-uchebno-metodicheskij-kompleks-po-discipline-ds-02-1-botanika-sostavleni-v-sootvetstvii-s-trebovaniyami.html
  • learn.largereferat.info/glava-ii-opitno-prakticheskoe-issledovanie-po-viyavleniyu-osobennostej-kulturno-dosugovoj-deyatelnosti-socialnogo-pedagoga-v-sovremennih-usloviyah.html
  • university.largereferat.info/glava-14-za-steklyannoj-stenoj-inka-ne-verila-v-astrologiyu-ipravda-kak-mozhno-zayavlyat-chto-millioni-lyudej-na.html
  • vospitanie.largereferat.info/zhiteli-kostromi-kontroliruyut-kachestvo-remonta-dorog-administraciya-kostromskoj-oblasti-kontrolnoe-upravlenie-informacionnij.html
  • notebook.largereferat.info/karta-berham-springs-11-berham-springs1.html
  • spur.largereferat.info/metodicheskaya-deyatelnost-analiz-raboti-mbou-toguchinskogo-rajona-gornovskaya-sosh-za-2009-2010-uchebnij-god.html
  • znaniya.largereferat.info/razdel-2-soblyudenie-osnovnih-grazhdanskih-svobod-tatarstan.html
  • notebook.largereferat.info/klassifikaciya-erlangera-gassera-priroda-membrannogo-potenciala-pokoya.html
  • exchangerate.largereferat.info/fizicheskaya-kultura-rabochie-programmi-cikla-obshih-gumanitarnih-i-socialno-ekonomicheskih-disciplin-anglijskij.html
  • teacher.largereferat.info/glava-iii-marketing-kak-rinochnaya-teoriya-upravleniya-ekonomicheskaya-teoriya.html
  • shkola.largereferat.info/obshie-voprosi-estestvennih-nauk-udk-50-byulleten.html
  • grade.largereferat.info/nalogovij-kodeks-rossijskoj-federacii-stranica-25.html
  • thesis.largereferat.info/pravitelstvo-sverdlovskoj-oblasti-postanovlenie-ot-11-oktyabrya-2010-g-n-1479-pp-ob-utverzhdenii-oblastnoj-celevoj-programmi-stranica-9.html
  • essay.largereferat.info/dannoj-kursovoj-raboti-ekonomiko-pravovoj-mehanizm-i-organizaciya-upravleniya-proektom-na-primere-predpriyatiya-oao-avisma-g-berezniki.html
  • klass.largereferat.info/avtor-sostavitel-d-k-samin-izdatelstvo-veche-2002-stranica-3.html
  • otsenki.largereferat.info/shkola-molodih-uchenih-po-analiticheskoj-mehanike-i-processam-upravleniya-v-ramkah-h-chetaevskoj-mezhdunarodnoj-konferencii-po-analiticheskoj-mehanike-ustojchivosti-i.html
  • institut.largereferat.info/uchebnij-plan-cikl-disciplin-naimenovanie-disciplini-v-sootvetstvii-s-uchebnim-planom-sostavitel-rpd-stranica-6.html
  • tasks.largereferat.info/13-ocenka-ekonomicheskogo-potenciala-domashnih-hozyajstv-kak-elementa-nacionalnogo-bogatstva.html
  • zanyatie.largereferat.info/sekretar-kervnika.html
  • zanyatie.largereferat.info/socialnoe-obsluzhivanie-naseleniya-programma-krasnoyarskogo-kraya-po-okazaniyu-sodejstviya-dobrovolnomu-pereseleniyu.html
  • assessments.largereferat.info/e-a-shalfeeva1.html
  • control.largereferat.info/chast-2-lekcii-lugacheva-mi-otveti-na-voprosi-k-ekzamenu-po-ekonomicheskoj-informatike.html
  • lecture.largereferat.info/analiz-upominaemosti-v-smi-romir-i-konkurentov-za-3-iyunya-2010-god.html
  • essay.largereferat.info/dlya-kogo-v-kremle-gotovyat-lobnoe-mesto-upravlyayushij-delami-prezidenta-rf-vladimir-kozhin-o-dvorcah-migalkah-i-chervyakah.html
  • © LargeReferat.info
    Мобильный рефератник - для мобильных людей.