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.  Написать рекурсивную функцию, вычисляющую указанное число Фибоначчи. Последовательность Фибоначчи задается следующими соотношениями: .


 

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

12901. Виховна година. Ти і твої друзі 26.51 KB
  Виховна година Ти і твої друзі Мета: розкрити значення дружби в житті людини; навчити дітей правильно вибирати друзів знайомитися спілкуватись і товаришувати. Обладнання: Фігурки феї Уваги і чаклунки Доброти аркуші –€œусмішки€ м’ячик пелюстки €œчарівної квітки...
12902. Україна наш спільний дім 27.87 KB
  Виховний урок Україна наш спільний дім Тема: Україна наш спільний дім Мета: поглибити знання учнів про незалежну Україну та її державні символи проаналізувати етапи здобуття українським народом державної самостійності; розвивати логічне мислення вміння порівню
12903. ДЕСЯТЬ МІФІВ ПРО ТОРГІВЛЮ ЛЮДЬМИ 27.19 KB
  Виховна година ДЕСЯТЬ МІФІВ ПРО ТОРГІВЛЮ ЛЮДЬМИ Олександр зі Львова нелегально виїхав до Іспанії разом з дружиною і працював там на будівництві. Одного разу він упав з драбини і сильно забився. Звичайно ніякої страховки у нього не було а працедавець умив руки. Коли чол...
12904. Дружба єднає щирі серця 28.2 KB
  Виховна година у 6 класі Тема. Дружба єднає щирі серця. Навчальна мета: : Поглибити і розширити поняття у дітей про дружбу навчити учнів сприймати ситуації аналізувати їх та знаходити шляхи виходу; допомогти усвідомити значимість слова друг; сприяти виникненню др
12905. Однокласник, товариш, друг. Способи вирішення суперечок та конфліктів. 20.01 KB
  Тема: однокласник товариш друг. Способи вирішення суперечок та конфліктів. Мета: розглянути товариськість як об’єктивне явище нашого життя як спосіб співіснування людей; формувати уявлення учнів про різні варіанти людського спілкування; учити уникати конфліктних си
12906. ПОДОРОЖ ЗА КОРДОН: ЗА І ПРОТИ 26.84 KB
  Виховна година ПОДОРОЖ ЗА КОРДОН: ЗА І ПРОТИ Останніми роками громадяни України все частіше подорожують за кордон. Подорож – це пізнання культури та традицій інших країн знайомство з новими людьми маса позитивних вражень. Проте ноземні дежави для мандрівника можуть...
12907. Знавці дитячих пісень 15.44 KB
  Виховна година для 2 класу Тема: Знавці дитячих пісень. Мета: ознайомити дітей з найвідомішими дитячими композиторами піснями пробудити цікавість до музичного мистецтва розвивати музичний смак дітей виховувати товариськість колективізм. Форма проведення: конк
12908. Книга – джерело грамотності, вихованості, всебічного розвитку особистості 26.17 KB
  Виховна година на тему: Книга – джерело грамотності вихованості всебічного розвитку особистості Мета: Допомогти учням осягнути значення книжки в житті людини викликати інтерес до цього порадника; сприяти розвитку мовлення та формувати пізнавальний інтерес; вихов...
12909. Виховна година на тему Дружба 20.95 KB
  Виховна година на тему Дружба Мета: розкрити зміст понять дружба дійсний друг; показати його відмінність від понять приятель і знайомий; прищепити учням повагу до цінностей дружби; сприяти розвиткові критичного ставлення до себе і своїх особистих якостей те