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


 

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

54163. Додавання та віднімання дробів з різними знаменниками 807.5 KB
  Тема уроку: розвязання вправ за темою Додавання та віднімання дробів з різними знаменниками. Розвивальна мета: розвивати практичні вміння та навички співнавчання та взаємонавчання; розвивати мислення; самостійність. Доданок Доданок Сума 27 Готуючись до уроку я розвязала ваше домашнє завдання але потім картки впали і переплутались. Розвязок.
54164. Розвязування задач на відсотки 195 KB
  Крім того, велика частина інформації, яку ми отримуємо, подана у вигляді відсотків. Кожному фахівцю у всіх сферах людської діяльності треба мати справу з відсотками. Отже, наша задача - мати міцні знання про відсоток.Доповідь учнів про історію виникнення поняття відсотка.
54165. Додатні та від’ємні числа. Додавання та віднімання раціональних чисел 246 KB
  Додатні та відємні числа. Сьогодні ми продовжимо працювати з додатними і відємними числамивдосконалювати вміння додавати...
54166. Означення квадратного рівняння. Неповні квадратні рівняння та їх розв’язки 747.5 KB
  Мета: домогтися свідомого розуміння учнями означення квадратного рівняння зведеного квадратного рівняння неповного квадратного рівняння назви коефіцієнтів квадратного рівняння; сформувати первинні вміння формулювати означення квадратного рівняння та його видів зведеного та неповного визначати коефіцієнти квадратного рівняння та за ними визначити вид квадратного рівняння підготувати учнів до сприйняття розвязування неповних квадратних рівнянь. Чи рівносильні рівняння: а 3х 2 = х...
54167. Математический футбол. Параллельность прямых и плоскостей в пространстве 610 KB
  Прямая а не лежит в плоскости квадрата АВСD и параллельна его стороне АВ. Прямая в не лежит в плоскости квадрата КМLN и параллельна его стороне М L.Каково взаимное расположение прямой и плоскости в пространстве Слайд № 18 Прямая а лежит в плоскости. Прямая а параллельна плоскости .
54168. Множення раціональних чисел 603.5 KB
  Для цього обчислимо приклади усно записані на веслах нашого корабля і прочитаємо імя відомого математика який сформував правила множення ділення віднімання і додавання раціональних чисел. Математика кібернетика...
54169. Новорічна математична ялинка 286.5 KB
  Мета: перевірити якість знань і вмінь учнів з теми; зацікавити математикою; розвивати логічне мислення культуру математичних записів, мовлення. Тип уроку: урок узагальнення та систематизації знань.
54170. Урок-казка. Чарівні слова. Розвязування рівнянь 165 KB
  Таблиці плакати до казки про ІванаЦаревича і Чахлика Невмирущого. Клас розбивається на 3 команди і вибирається ІванЦаревич. Там під дубом вчений кіт Русалонька за принцем плаче КоникГорбоконик на підмогу скаче Привид Кентервільський всіх лякає ІванЦаревич Змія перемагає. Учитель: В деякому царстві живбув ІванЦаревич.
54171. Особливості навчання математиці дітей із затримкою психічного розвитку в умовах якісної освіти 450.5 KB
  Поданий матеріал може бути використаний вчителями математики, які працюють як в спеціалізованих класах корекції для дітей із затримкою психічного розвитку, так і звичайних класах загальноосвітньої школи. В посібнику відображені питання класифікації дітей із затримкою психічного розвитку, зазначені причини затримки розвитку, подана характеристика дітей даної категорії та визначені особливості їх навчальної діяльності на уроках математики.