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


 

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

22827. КАТЕГОРІЙНО-ПОНЯТІЙНИЙ АПАРАТ З БЕЗПЕКИ ЖИТТЄДІЯЛЬНОСТІ, ТАКСОНОМІЯ НЕБЕЗПЕК 92 KB
  Виходячи з сучасних уявлень безпека життєдіяльності є багатогранним обєктом розуміння і сприйняття дійсності, який потребує інтеграції різних стратегій, сфер, аспектів, форм і рівнів пізнання. Складовими цієї галузі є різноманітні науки про безпеку. У всьому світі велика увага приділяється вивченню дисциплін
22828. ВИМІРЮВАННЯ НАПРУЖЕННОСТІ МАГНІТНОГО ПОЛЯ ВЗДОВЖ ОСІ СОЛЕНОЇДА ІНДУКЦІЙНАМ МЕТОДОМ 141 KB
  ВИМІРЮВАННЯ НАПРУЖЕННОСТІ МАГНІТНОГО ПОЛЯ ВЗДОВЖ ОСІ СОЛЕНОЇДА ІНДУКЦІЙНАМ МЕТОДОМ Явище електромагнітної індукції полягає у виникненні е. Напруженість магнітного поля в будьякій точці А що лежить на осі ОО соленоїда чисельно дорівнює алгебраїчній сумі напруженостей магнітних полів створених у точці А всіма витками спрямована вздовж осі за правилом свердлика 3 Де n число витків за одиницю довжини соленоїда І величина струму; кути що утворює радіусвектор проведений з точки А до крайніх витків соленоїда мал....
22829. ЯВИЩЕ ГІСТЕРЕЗИСУ В ФЕРОМАГНЕТИКУ 115 KB
  ЯВИЩЕ ГІСТЕРЕЗИСУ В ФЕРОМАГНЕТИКУ Особливий клас магнетиків становлять феромагнетики речовини здатні мати намагнічення у відсутності зовнішнього магнітного поля.21 наведена залежність модуля вектора намагнічення від напруженості зовнішнього поля для феромагнетика з попереднім магнітним полем рівним нулеві основна або нульова крива намагнічення . При деякому значенні H намагнічення досягає насичення оскільки вектор магнітної індукції та вектора намагнічення звязані співвідношенням то при досягненні вектор стає функцією від:...
22830. ВИЗНАЧЕННЯ КОНЦЕНТРАЦІЇ НОСІЇВ ЗАРЯДУ В НАПІВПРОВІДНИКАХ З ЕФЕКТУ ХОЛЛА 71.5 KB
  ВИЗНАЧЕННЯ КОНЦЕНТРАЦІЇ НОСІЇВ ЗАРЯДУ В НАПІВПРОВІДНИКАХ З ЕФЕКТУ ХОЛЛА В основу вимірювання концентрації електронів покладено явище Холла яке полягає у виникненні поперечної різниці потенціалів при проходженні струму по провіднику напівпровіднику який знаходиться в магнітному полі перпендикулярному до лінії струму. Ефект Холла в електронній теорії пояснюється так. Введемо сталу Холла 7 Тоді 8 Отже згідно з формулою 8 вимірявши силу струму I у...
22831. ДВОПРОВІДНА ЛІНІЯ 95.5 KB
  В таких системах активний опір ємність і індуктивність розподілені рівномірно вздовж лінії. Як правило в двопровідних лініях умова квазістаціонарності виконується щодо відстані між провідниками а сила струму I лінійна густина заряду q і напруга між провідниками U суттєво змінюються вздовж лінії. Застосовуючи до нескінченно малої ділянки двопровідної лінії закон збереження електричного заряду і електромагнітної Індукції нехтуючи активним опором провідників можна отримати такі співвідношення: 1 2 Тут L С ...
22832. Ефект Пельтьє 70.5 KB
  Ефект Пельтьє. Дійсно експериментально така закономірність відома як ефект Пельтьє спостерігається. Встановлено що при проходженні електричного струму через контакт двох провідників напівпровідників виділяється чи поглинається в залежності від напрямку струму деяка кількість теплоти Qn пропорційна величині струму I та часу його протікання t: Qn=It 1 де  коефіцієнт Пельтьє. Ефект Пельтьє тим значніший чим більше відрізняються положення рівнів Фермі у напівпровідниках.
22833. РОЗШИРЕННЯ ШКАЛИ МІКРОАМПЕРМЕГРА ТА ВОЛЬТМЕТРА 73 KB
  Сила струму I обчислюється за формулою: 1 де Ca ціна поділки шкали мікроамперметра в амперах на поділку А под n відхилення стрілки у поділках шкали. Ціну поділки шкали мікроамперметра в одиницях напруги Cu можна обчислити за відомим внутрішнім опором мікроамперметра Rr та ціною поділки в одиницях сили струму Ca за формулою Cu=CaRr 2 При використанні мікроамперметра необхідно звертати увагу на такі характеристики як верхня та нижня межі значень вимірювання величин...
22834. РЕОСТАТ І ПОДІЛЬНИК НАПРУГИ 139.5 KB
  РЕОСТАТ І ПОДІЛЬНИК НАПРУГИ Реостат і подільник напруги це прилади що застосовуються для регулювання сили струму і напруги в електричних схемах. Спад напруги на опорінавантаженні а на реостаті напруга на опорінавантаженні змінюватиметься від до . Подільником напруги може правити реостат з трьома клемами який підключається до електричного кола так як зображено на мал. Переміщуючи точку вздовж подільника напруги можна одержати будьяку напругу від до 0.
22835. МЕТОД КОМПЕНСАЦІЇ В ЕЛЕКТРИЧНИХ ВИМІРЮВАННЯХ 232 KB
  МЕТОД КОМПЕНСАЦІЇ В ЕЛЕКТРИЧНИХ ВИМІРЮВАННЯХ Вимірювання електрорушійної сили джерела струму методом компенсації. джерела струму дорівнює різниці потенціалів на полюсах розімкненого елемента. Вимірювання термоелектрорушійної сили диференціальної термопари за допомогою потенціометра постійного струму. Принцип роботи потенціометра постійного струму такий.