78181

Разработка рекурсивных алгоритмов и программ

Лабораторная работа

Информатика, кибернетика и программирование

Задачи для индивидуального решения Вычислить значение выражения используя рекурсивный метод: y= Для данного N вычислить значение выражения используя рекурсию: P= Написать программу с рекурсивной функцией вычисляющей разность элементов одномерного массива. Написать рекурсивную функцию сложения целых чисел двумерного массива. Написать рекурсивную процедуру которая считывает вводимые с клавиатуры числа до тех пор пока не будет обнаружен нуль. Написать рекурсивную процедуру которая считывает вводимые с клавиатуры числа до тех пор...

Русский

2015-02-07

115.5 KB

3 чел.

Тема: Разработка рекурсивных алгоритмов и программ

Цель работы: Сформировать знания и умения по работе с подпрограммами. Приобрести навыки написания программ с использованием рекурсивных процедур и функций.

Время выполнения: 2 часа

Лабораторная работа №12

Порядок выполнения работы:

  1.  Изучить основные приемы программирования по написанию программ с использованием рекурсивных процедур и функций
  2.  Согласно своему варианту разработать программу с использованием рекурсивных процедур и функций по условиям задач, приведенным в разделе «Задачи для индивидуального решения».
  3.  Показать работающую программу преподавателю. Уметь ответить на вопросы.
  4.  Получить у преподавателя индивидуальное задание в качестве домашнего упражнения. Самостоятельно разработать алгоритм решения задачи, составить и отладить программу.
  5.  Индивидуальное задание сдать преподавателю на следующем практическом занятии.

Теоретические сведения

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

Примером программы с использованием рекурсии может быть программа вычисления факториала числа. Факториалом натурального числа n называют произведение чисел 1*2*...*n.

{Вычисление факториала числа п с использованием рекурсивной функции}

program Demo_Rekurs;

var     N : integer;

F : longint;

{Описание функции, N — формальный параметр-значение типа integer, результат выполнения функции типа longint}.

function Fakt(N : integer): longint;

begin   {Начало вычисления функции}

if N=1 then Fakt:=1   {Проверка условия завершения рекурсии}

else Fakt:=N*Fakt(N-1); {Рекурсивное вычисление N!}

end;

begin  {Начало главной программы}

Writeln('Введите число N : ') ;

Read(N) ;

F:=Fakt(N);  {Вызов функции для фактического параметра N}

Writeln('Для числа ',N,' значение факториала= ', F);

end.

После запуска программы на экран выводится запрос: "Введите число N: ", затем с клавиатуры считывается значение целого числа N и в выражении F:=Fakt(N) вызывается функция Fakt с параметром-значением N. В подпрограмме-функции вычисления факториала проверяется условие N=1. Если оно выполняется, то функции Fakt присваивается значение 1, на этом выполнение подпрограммы-функции завершается. Если условие N=1 не соблюдается, то выполняется вычисление произведения N*Fakt(N-1). Вычисление произведения носит рекурсивный характер, так как при этом осуществляется вызов функции Fakt(N-1), значение которой вычисляется, в свою очередь, через вызов функции Fakt, параметром которой также будет функция Fakt,   и т. д., до тех пор, пока значение формального параметра N=1. Так как базовая часть описания рекурсивной функции Fakt определяет значение Fakt для N=1, равным единице, то рекурсивные вызовы функции Fakt больше не выполняются, а наоборот, выполняется вычисление функции Fakt для чисел, возрастающих от 1 до N, причем функция Fakt всякий раз возвращает значение, равное произведению очередного k-гo числа на факториал от k-1-го числа. Последнее возвращение результата вычисления функции Fakt присвоит переменной F значение произведения всех чисел от 1 до N, т. е. факториал числа N.

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

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

Косвенная рекурсия

В Турбо Паскале есть случаи нетрадиционного объявления подпрограмм, когда в объявлении процедуры содержится директива interrupt (прерывание), external (внешняя) или inline (встроенная) или вместо блока в объявлении процедуры или функции написано forward (опережающая).

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

procedure MyInt(Flags, CS, IP, AX, BX, CX, DX, SI, DI, DS, ES, BP:Word) ;interrupt;

где CS, IP, AX, BX, CX, DX, SI, DI, DS, ES, BP — регистры процессора.

Внешние объявления (external). Внешние объявления позволяют связывать отдельно скомпилированные процедуры и функции, написанные на языке ассемблера. С помощью директивы {$L имя файла} внешнюю программу можно связать с программой или модулем, написанным на Паскале. Пример объявления внешней процедуры:

procedure MoveWord(var Source, Dest; Count: Word); external;

В тексте программы при объявлении внешних подпрограмм нужно задать директиву компилятору $L, аргументом которой является имя OBJ-файла, содержащего код подключаемой подпрограммы, например: {$L BLOCK. OBJ}

Inline (встроенная). Директива inline позволяет записывать инструкции в машинном коде, не используя блок операторов. При вызове обычной процедуры компилятор создает код, в котором параметры процедуры помещаются в стек, а затем для вызова процедуры генерируется инструкция call. Когда вызывается внутренняя процедура, компилятор генерирует код из директивы inline вместо call. Таким образом, inline-процедура "расширяется" при каждом обращении к ней аналогично макрокоманде на языке ассемблера. (Макрокоманда- macro- предложение языка программирования, вместо которого компилятор при трансляции записывает несколько машинных команд.)

Опережающие объявления (forward). Помимо прямых рекурсий, рассмотренных ранее, рекурсивный вызов может быть и косвенным, т. е. одна процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую процедуру.    А так как до вызова процедуры она обязательно должна быть описана, то используется опережающее объявление: процедура содержит описание только своего заголовка, вслед за которым ставится зарезервированное слово forward (опережающий), а описание текста процедуры помещается далее в тексте программы гуже без повторения описания списка формальных параметров и называется определяющим объявлением.

Опережающее объявление и определяющее объявление должны находиться в одной и той же части объявления процедур и функций. Между ними могут быть объявлены другие процедуры и функции, и они могут вызывать процедуру с опережающим объявлением. Таким образом, возможна взаимная рекурсия. Определяющее объявление процедуры может быть external или assembler.  Однако оно не может быть near-; far-; inline- или другим forward-объявлением. Определяющее объявление также не может содержать директивы interrupt, near или far. Опережающие объявления не допускаются в интерфейсной части модуля.

Примером программы с использованием вложенных подпрограмм-процедур может быть программа Demo_Tower, в которой реализован алгоритм древней игры "Ханойские башни". Имеются три стержня, на одном из них (например, на левом) засажены диски разных размеров, причем диски располагаются так, чтобы стержень с дисками напоминал башню, т. е. внизу располагаются самые большие диски, а вверху маленькие. Цель игры - перенести башню с правого стержня на левый, причем за один раз можно переносить только один диск и при этом можно насаживать только диск с меньшим диаметром на диск с большим диаметром. Средний стержень является вспомогательным для временного хранения дисков.

program Demo_Tower; {Ханойские башни: перенести кольца с правого стержня  на левый}

Type

Position = (Left, Centre, Right) ;

var N : integer;       

procedure MoveDisk(From, Tol : Position); {Перемещение диска}

 procedure WritePos(P : Position); {процедура WritePos внутри процедуры MoveDisk}

begin

case P of

Left : Write('1') ;

Centre : Write('2') ;

Right : Write('3');

end;

end;

begin  {начало процедуры MoveDisk}

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,Тоl, From);

end ;

end;

Begin  {Основная программа}

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

Readln(N) ;

MoveTower(N,Right,Left,Centre); {Вызов процедуры с передачей ей фактических параметров}

end.

Задачи для индивидуального решения 

  1.  Вычислить  значение выражения, используя рекурсивный метод: y=
  2.  Для данного N вычислить значение выражения, используя рекурсию: P=
  3.  Написать программу с рекурсивной функцией, вычисляющей разность элементов одномерного массива.
  4.  Написать рекурсивную функцию сложения целых чисел двумерного массива.
  5.  Написать рекурсивную процедуру, которая считывает вводимые с клавиатуры числа до тех пор, пока не будет обнаружен нуль. Затем введенные числа распечатываются в обратном порядке.
  6.  Написать рекурсивную процедуру, которая считывает вводимые с клавиатуры числа до тех пор, пока не будет обнаружен нуль. Затем введенные числа распечатываются в обратном порядке. Нуль не печатать.
  7.  Написать рекурсивную процедуру, переводящую целое число из десятичной системы счисления в восьмеричную.
  8.  Написать рекурсивную процедуру, переводящую целое число из десятичной системы счисления в шестнадцатеричную.
  9.  Написать рекурсивную функцию для поиска максимального элемента в одномерном массиве.
  10.  Написать программу с рекурсивной функцией, вычисляющей количество цифр заданного натурального числа n.
  11.  Написать программу с рекурсивной функцией, вычисляющей сумму цифр заданного натурального числа n.
  12.  Написать программу с рекурсивной функцией, вычисляющей сумму элементов одномерного массива.
  13.  Написать программу с рекурсивной функцией, вычисляющей:

.

  1.  Написать программу с рекурсивной функцией, вычисляющей:
  2.  Вычислить  значение выражения, используя рекурсивный метод: y=
  3.  Для данного N вычислить значение выражения, используя рекурсию: P=
  4.  Написать программу с рекурсивной функцией, вычисляющей  количество цифр заданного натурального числа n.
  5.  Написать рекурсивную функцию для поиска минимального элемента в одномерном массиве.
  6.  Написать рекурсивную функцию умножения вещественных чисел.
  7.  Составить программу определения является ли введенное число простым с использованием рекурсивной функции.
  8.  Написать рекурсивную процедуру, которая считывает вводимые с клавиатуры числа до тех пор, пока не будет обнаружен нуль. Затем введенные числа распечатываются в обратном порядке. Нуль тоже печатать.
  9.  Написать рекурсивную процедуру, переводящую целое число из восьмеричной системы счисления в десятичную.
  10.  Написать рекурсивную процедуру, которая считывает вводимые с клавиатуры числа до тех пор, пока не будет обнаружена единица. Затем введенные числа распечатываются в обратном порядке.
  11.  Написать рекурсивную процедуру, переводящую целое число из шестнадцатеричной системы счисления в десятичную.
  12.  Написать рекурсивную функцию вычитания целых чисел.
  13.  Написать программу с рекурсивной функцией, вычисляющей:
  14.  Написать программу с рекурсивной функцией, вычисляющей произведение цифр заданного натурального числа n.
  15.  Написать программу с рекурсивной функцией, вычисляющей произведение элементов одномерного массива.
  16.  Написать программу с рекурсивной функцией, вычисляющей разность цифр заданного натурального числа n.
  17.  Написать рекурсивную функцию, вычисляющую указанное число Фибоначчи. Последовательность Фибоначчи задается следующими соотношениями: .


 

А также другие работы, которые могут Вас заинтересовать

81724. Тема русского бунта в произведениях отечественной литературе 32.18 KB
  Дубровский Глава 6 Пожар в Кистеневке эпизод Эпизод – начало стихийного крестьянского бунта возникшего от страстного желания крепостных Дубровских отомстить за барина и нежелания служить новому хозяину – Кирилле Троекурову которому по решению суда переходило имение Дубровских. Глава 7 появились разбойники и распространили ужас по всем окрестностям Грабительства одно другого замечательнее следовали одно за другим. Рассказывали о нем чудеса; имя Дубровского было во всех устах все были уверены что он а никто другой...
81725. Природа и любовь в поэзии А. А. Фета 38.59 KB
  Ктото учит маленьких несмышленышей делающих первый в жизни шаг твердо стоять на ногах с трудом произносить первые слова. Нас восхищают слова поэта выражающие его огромную любовь к своей родине к ее необъятным просторам к ее тихим уголкам: Какое дикое ущелье Ко мне навстречу ключ бежит Он в дол спешит на новоселье. Травы цветы деревья болотца ручейки перелески зори грозы облака во всем открывает чародей слова живую душу всем поверяет свои заветные думы. Итак мир природы для Тютчева был тем неисчерпаемым источником...
81726. Путь исканий Григория Мелехова в романе М. Шолохова «Тихий Дон». Смысл финала шолоховской эпопеи 32.97 KB
  Герои Шолохова – люди простые но незаурядные а Григорий не только храбр до отчаяния честен и совестлив. Влияние Чубатого Предчувствие беды ранение Григорий и его дети желание конца войны На стороне большевиков. 6 Разговор с Петром Злоба к большевикам Ссора с отцом изза награбленного Самовольный отъезд домой Красные у Мелеховых Пьянство мысли о смерти Григорий убивает матросов Разговор с дедом Гришакой и с Натальей Встреча с Аксиньей Книга четвертая ч. 7 Григорий в семье.
81727. Образ «маленького человека» и его воплощение в произведениях отечественной классики 19 века 31.14 KB
  Тема маленького человека впервые была затронута в творчестве А. обратился к теме бесправного безмерно униженного и забитого маленького человека живущего своей внутренней жизнью в условиях грубо попирающих достоинство человека. И чтобы их раздобыть он идет на преступление под влиянием выдуманной теории о необыкновенных личностях Созданные писателем образы маленьких людей проникнуты духом протеста против социальной несправедливости против унижения человека и верой в его высокое призвание.
81728. Герои и тематика лирики Н. А. Некрасова 33.13 KB
  Особенно трудным для Н оказался конец 60 гг нравственный компромисс на который он пошел во имя спасения журнала вызвал упреки со всех сторон реакционная публика уличала поэта в корыстолюбии а духовные единомышленники в отступничестве Тяжелые переживания Н отразились в цикле так называемых покаянных стихов Ликует враг 1866 Умру я скоро 1867. Зачем меня на части рвете 1867 Однако эти стихи не вписываются в однозначное определение покаянных в них звучит мужественный голос поэта исполненный сложной внутренней борьбы не...
81729. Тема борьбы добра и зла в романе М. Булгакова «Мастер и Маргарита» 31.92 KB
  В романе слово черт употребляется около 60 раз. В романе подробно и образно описано окружение сатаны присутствует дьявольская атрибутика оборотни его свита ведьмы боров как верховое животное ведьмы разлагающиеся трупы гробы черная месса в которой искажается перевертывается Божественная литургия Он лишает людей голов разума. В романе нет героев способных подняться на духовную борьбу против него.
81730. Образ скучающего героя в произведениях отечественной классики 19 века 32.94 KB
  Лермонтов Герой нашего времени В романе Л. но и многих молодых людей того времени: жизнь была только цепь грустных и неудачных противоречий сердцу и рассудку Герой романа не всегда был циником скептиком духовно черствым человеком. Причину превращения Печорина в нравственного калеку автор видит в социальных условиях в которых воспитывался герой. И вот на страницах своего дневника герой приходит к страшному выводу: во мне душа испорчена светом Судьбу талантливого человека не нашедшего себе достойного применения в обществе его...
81731. Идейное содержание поэмы Н. А. Некрасова «Кому на Руси жить хорошо». Язык и стиль поэмы 33.13 KB
  Некрасова Кому на Руси жить хорошо. Достойным финалом эпического творчества Н явилась эпопея Кому на Руси жить хорошо; 1865 1877 Композиция этого произведения строится по законам классического эпоса оно состоит из отдельных относительно автономных частей и глав Пролог Часть первая. Внешне эти части связаны темой дороги: семь мужиковправдоискателей странствуют по просторам Руси пытаясь разрешить не дающий им покоя вопрос Кому на Руси жить хорошо В Прологе намечена и первоначальная схема путешествия встречи с попом помещиком.
81732. Нравственная проблематика прозы А. Солженицына (по рассказам «Один день Ивана Денисовича» или «Матренин двор») 34.36 KB
  Шухов не желая потерять человеческое достоинство вовсе не склонен принимать на себя все удары лагерной жизни – иначе просто не выжить. помогает ему выжить и сохранить себя человеком – не ставя перед собой вечных вопросов не стремясь обобщить опыт своей военной и лагерной жизни куда он попал после плена. островок естественной русской жизни а народный характер сумевший в этой смуте себя сохранить. В чем суть праведности Матрены В жизни не по лжи.