Лабораторная работа основана на практических занятиях по дисциплине "Языки программирования"




Скачать 49.31 Kb.
НазваниеЛабораторная работа основана на практических занятиях по дисциплине "Языки программирования"
Дата публикации15.09.2014
Размер49.31 Kb.
ТипЛабораторная работа
shkolnie.ru > Информатика > Лабораторная работа
Лабораторная работа основана на практических занятиях по дисциплине "Языки программирования", разработанных доцентом кафедры ИиВМ Рогачевой Е.В.
Работа 2.
Рекурсия.
Возможность описания рекурсивных (т.е. вызывающих самих себя) процедур и функций, вообще говоря, не является обязательным свойством языка (например, FORTRAN долгое время не поддерживал их). Любая рекурсия принципиально может быть заменена циклом. Простейшим примером тому было вычисление факториала числа. Однако в ряде случаев рекурсивные алгоритмы более изящны, коротки, имеют прозрачную для понимания структуру.

Рекурсивные процедуры и функции активно использовались при описании работы с деревьями. Впрочем, к этому располагала сама структура данных, вследствие чего рекурсивные алгоритмы получались более легкими для восприятия (чтения). Конечно, это не единственная область применения рекурсивных алгоритмов. На лекциях обсуждалась (если помните), задача о Ханойских башнях, приводился пример печати строки в обратном порядке, пример взаимной (косвенной) рекурсии. Один из наиболее быстрых универсальных алгоритмов сортировки - быстрая сортировка, или QuickSort, - также обычно записывается с использованием рекурсивной процедуры.
Когда пишется рекурсивная программа, следует ставить два вопроса [А. Шень]:

1. Почему программа заканчивает работу?

2. Почему она работает правильно, если заканчивает работу?

Ответ на второй вопрос обычно можно найти средствами математической индукции. Для окончания же работы программы, как правило, вводится некий параметр, значение которого уменьшается (можно и увеличивать, конечно) при каждом вызове. По достижении некоторой границы рекурсивная процедура перестает вызывать себя.

Рекурсивный алгоритм принято характеризовать глубиной рекурсии - максимально возможным количеством «нанизанных друг на друга» вызовов.
Пример.
Задача.
Рекурсивно описать функцию C(m, n), где 0 <= m <= n, для вычисления биномиального коэффициента по следующей формуле: , при 0 < m < n.
Решение.
function C(m, n: integer): integer;

begin

// полагаем, что 0 <= m <= n до входа в процедуру

if (m = 0) or (m = n) then result := 1

else result := C(m, n-1) + C(m-1, n-1);

end;

Задачи:

1. Опишите рекурсивную функцию pow(x, n) от вещественного x (x <> 0) и целого n, которая вычисляет xn согласно формуле:



2. Опишите рекурсивную функцию root(f, a, b, eps), которая методом деления отрезка пополам находит с точностью до eps корень уравнения f(x) = 0 на отрезке [a, b]. Считайте, что eps > 0, a < b, f(a) * f(b) < 0, f(x) - непрерывная и монотонная функция на отрезке [a, b].

3. Напишите рекурсивную функцию сложения двух чисел (a + b).

4. Напишите рекурсивную функцию перевода числа из десятичной системы счисления в двоичную

5. Напишите рекурсивную функцию, проверяющую, является ли заданное натуральное число простым

6. Напишите рекурсивную функцию, определяющую наибольший общий делитель

7. Напишите рекурсивную функцию возведения целого числа в целую неотрицательную степень. Глубина рекурсии не должна превосходить , где n - степень. (Указание: воспользуйтесь алгоритмом «быстрого возведения в степень»).

8. Опишите рекурсивную функцию, вычисляющую сумму первых n членов арифметической прогрессии.

9. Используя процедуру write(x) только для x = 0, 1, ..., 9, напишите рекурсивную процедуру печати десятичной записи целого положительного числа x.

10. Описать рекурсивную функцию, отыскивающую минимальный элемент в массиве.

11. Описать рекурсивную (логическую) функцию, проверяющую, является ли симметричной часть строки, начинающаяся i-ым и заканчивающаяся j-ым элементом.

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

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

14. Имеется n населенных пунктов, перенумерованных от 1 до n. Некоторые пары пунктов соединены дорогами. Написать рекурсивную функцию, определяющую, можно ли попасть по этим дорогам из пункта i в пункт j. Информация о дорогах задается в виде последовательности пар чисел m и n (m < n), указывающих, что пункты m и n соединены дорогой. Признак окончания последовательности - пара нулей.

Похожие:

Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconКурсовая работа сложная форма контроля знаний студента, позволяющая...
В соответствии с учебным планом студенты специальности Прикладная информатика (в экономике) выполняют курсовую работу по дисциплине...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconЛабораторная работа №2 по дисциплине «Формальные языки и грамматики» Тема: «Конечные автоматы»
Для заданного в виде графа конечного автомата написать его представление в виде af=(Q, , , q0, F), то есть написать, чему равны...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconКурс «Программирование на С++»
Языки программирования Си и С++ являются универсальными языками программирования высокого уровня, позволяющими создавать различного...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" icon1. Представление о программировании: язык программирования (на примере...
Назначение программирования разработка программ управления компьютером с целью решения различных информационных задач. Для составления...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconПрограмма по дисциплине ен ф. 1 «математика и информатика»
Аксиоматический метод, основные математические структуры, вероятность и статистика, математические модели, алгоритмы и языки программирования,...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconЛабораторная работа №1
Лабораторные работы основаны на лекционном материале и выполняются после изучения соответствующего теоретического раздела. Помимо...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconУрок по информатике и икт в 9 классе на тему: «языки программирования. Язык паскаль»
Цель: познакомить учащихся с языком программирования Паскаль, историей его возникновения и алфавитом
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconРасписание лекций и практических работ по биологии 9 января, воскресенье
Лабораторная работа «Сравнительный анализ хромосом млекопитающих». Профессор О. В. Саблина
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconЗаконченная и правильно оформленная работа сдается в деканат факультета
...
Лабораторная работа основана на практических занятиях по дисциплине \"Языки программирования\" iconЛабораторная работа n5 исследование организации переходов в программе
Абель П. Язык Ассемблера для ibm pc и программирования /Пер c англ. М.: Высш шк., 1992,c 93-115
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница