Программирование с использованием рекурсии
Организация вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Способы программирования алгоритмов с использованием рекурсии. Преимущества и недостатки использования рекурсии.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 28.05.2012 |
| Размер файла | 27,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лабораторная работа
Программирование с использованием рекурсии
Задание к лабораторной работе
Цель работы: освоить способы программирования алгоритмов с использованием рекурсии.
Общие сведения рекурсия - способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Перед выполнением работы необходимо изучить способы описания и использования рекурсивных процедур и функций.
Пример. Написать программу, содержащую подпрограммы, вычисляющий
с использованием и без использования рекурсии.
Решение
Program SUMIR;
Var n: Integer; SUM:Real;
{------- Рекурсивная процедура-функция -------------}
Function S_REC(n:word):Real;
Begin
if n=1 then S_REC:=4
else S_REC:=S_REC(n-1)+(n+1)*(n+1)/n
End;
{------- Процедура-функция без рекурсии ------------}
Function S(n:word):Real;
Var i: byte; Sum: Real;
Begin
Sum:=4;
For i:=2 to n do Sum:=Sum+(i+1)*(i+1)/i;
S:=Sum
End;
{----------- Рекурсивная процедура ----------------}
Procedure REC(n:word; Var S:Real);
Begin
if n=1 then S:=4
else Begin
REC(n-1,S);
S:=S+(n+1)*(n+1)/n
End
End;
{------------ Процедура без рекурсии ------------}
Procedure SS(n:word; Var S:Real);
Var i: byte;
Begin
S:=4;
For i:=2 to n do S:=S+(i+1)*(i+1)/i;
End;
{----------- Основная программа ----------------}
Begin
Write('n='); Readln(n);
Writeln('Сумма равна');
Writeln('1. Функция с рекурсией: ',S_REC(n):0:5);
Writeln('2. Функция без рекурсии: ',S(n):0:5);
REC(n,SUM);
Writeln('3. Процедура c рекурсией: ',SUM:0:5);
SS(n,SUM);
Writeln('4. Процедура без рекурсии: ',SUM:0:5);
End.
рекурсия алгоритм вычислительный
Контрольные вопросы
1. Что такое «рекурсия»?
2. В чем преимущества и недостатки использования рекурсии?
Задачи
Решить поставленные задачи различными способами: с применением рекурсии и без нее.
1. Для заданного целого десятичного числа N получить его представление в p-ичной системе счисления (p<10).
2. В упорядоченном массиве целых чисел ai, i=1...n найти номер элемента c используя метод двоичного поиска. Предполагается, что элемент c находится в массиве.
3. Найти наибольший общий делитель чисел M и N. Используйте теорему Эйлера: Если M делится на N, то НОД (N, M)=N, иначе НОД (N, M)=
=НОД (M mod N, N).
4. Вычислить число Фибоначчи Fb(n). Числа Фибоначчи определяются следующим образом: Fb(0)=1; Fb(1)=1; Fb(n)=Fb(n-1)+Fb(n-2).
5. Найти значение функции Аккермана A(m, n), которая определяется для всех неотрицательных целых аргументов m и n следующим образом:
A(o, n)=n+1;
A(m, o)=A(m-1, 1); (m>o);
A(m, n)=A(m-1, A(m, n-1)); (m>o; n>o).
6. Вычислить m-ю производную полинома степени n
7. Вычислить значение , используя рекуррентную формулу
в качестве начального приближения использовать значение x0=0.5(1+a).
8. Найти максимальный элемент в массиве a1...an, используя очевидное соотношение max (a1...an)=max (max (a1...an-1), an).
9. Найти максимальный элемент в массиве a1...an, используя соотношение (метод деления пополам) max (a1...an)=max (max (a1...an/2), max (an/2+1, an)).
10. Вычислить .
11. Вычислить
12. Вычислить произведение n2 (n-четное) сомножителей
13. Вычислить по следующему алгоритму: , если N четное; , если N нечетное.
14. Вычислить n!.
15. Выполнить сортировку массива целых чисел ai, i=1, n с помощью разделения (QuickSort). См. Вирт Н., Алгоритмы и структура данных.
Размещено на Allbest.ru
Подобные документы
Использование рекурсии в предметных областях. Рекурсивные процедуры и функции в программировании. Создание алгоритмов для рисования графических изображений с использованием рекурсии в среде программирования Pascal ABC. Примеры рекурсии в графике.
творческая работа [6,7 M], добавлен 01.02.2014Исследование понятия рекурсии в программировании. Описание метода, который позволяет разбить задачу на части все меньшего и меньшего размера. Изучение схемы работы рекурсивной процедуры. Способы изображения древовидных структур. Избавление от рекурсии.
презентация [486,1 K], добавлен 22.10.2013Обзор рекурсивных алгоритмов с позиции теории алгоритмов, теории сложности, с точки зрения практического программирования. Имитация работы цикла с помощью рекурсии. Способы изображения древовидных структур. Синтаксический анализ арифметических выражений.
курсовая работа [432,2 K], добавлен 16.01.2013Обратная трассировка лучей: ограничения при реализации, достоинства и недостатки. Математические и физические предпосылки алгоритма, блок-схема. Выбор языка программирования. Зависимость времени генерации от глубины рекурсии, количества источников.
курсовая работа [503,0 K], добавлен 27.05.2013Краткая характеристика интегрированной среды Turbo Pascal. Принципы программирования разветвляющихся алгоритмов, циклических структур, задач обработки символьных данных, множеств. Правила записи данных в текстовый файл. Понятие явной и косвенной рекурсии.
учебное пособие [1,5 M], добавлен 10.12.2010Обработка сложных структур данных как одна из наиболее распространенных возможностей применения языка программирования С++. Преимущества использования подпрограмм. Передача параметров, одномерных и двумерных массивов, функции и их возврат в функцию.
курсовая работа [1,1 M], добавлен 24.11.2013Классификация и стек рекурсивных функций. Методика распознавания формулы, записанной в строке. Реализация салфетки Серпинского и задачи о Ханойских башнях. Алгоритм быстрой сортировки. Создание функции, сортирующей массив с использованием рекурсии.
лабораторная работа [160,8 K], добавлен 06.07.2009Решение задач прикладного программирования. Оформление разработанных алгоритмов в виде графических схем. Написание программ с использованием подпрограмм, их отладка. Блок-схемы и листинг программ. Наборы тестов для отладки разработанных программ.
курсовая работа [575,8 K], добавлен 06.12.2013Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.
курсовая работа [38,9 K], добавлен 15.11.2009Изучение элементов языка С++, программирование разветвлений и циклов с использованием операторов условного и перехода. Обработка одномерных массивов. Поиск максимального элемента массива с заданной размерностью. Листинги программы и результатов.
курсовая работа [647,7 K], добавлен 05.02.2013
