Лабораторная работа №7

Использование рекурсивных процедур и функций

Цель работы: получение навыков описания и использования рекурсивных подпрограмм.

Задания для подготовки к работе

1. Изучите правила организации рекурсивных процедур и функций.

2. Опишите математическое решение задачи, если необходимо.

3. Опишите блок-схему алгоритма решения задачи в укрупненных блоках

4. Опишите используемые структуры данных, если необходимо.

5. Опишите спецификацию и блок-схему итеративной подпрограммы.

6. Опишите спецификацию и блок-схему рекурсивной подпрограммы,

7. Если список параметров рекурсивной подпрограммы отличается от списка параметров итеративной подпрограммы, то опишите подпрограмму с таким же заголовком, как и у итеративной подпрограммы, которая вызывает рекурсивную с необходимыми ей параметрами. При этом сама рекурсивная подпрограмма может быть описана в основной подпрограмме или вне ее.

8. Закодируйте алгоритмы

9. Подберите наборы тестовых данных с обоснованием их выбора.

Задания к работе

1. Наберите программы, отладьте их, протестируйте.

2. Выполните анализ ошибок, выявленных при отладке программы

Содержание отчет а

1. Формулировка задачи.

2. Ответы на пункты 2 – 9 заданий для подготовки к работе.

3. Описание ошибок, выявленных при отладке программы с указанием вида ошибки, и почему она была сделана.

Варианты заданий

1. Определить количество цифр в тексте, вводимом с клавиатуры. Текст заканчивается символом «конец файла».

2. Дан знаменатель и первый член геометрической прогрессии. Вычислить n -й член прогрессии.

3. Дана упорядоченная по убыванию последовательность целых чисел. Определить, есть ли среди членов данной последовательности число x, и если есть, найти номер этого члена.

4. С клавиатуры вводятся целые числа. Признак конца ввода – ноль. Найти произведение введенных нечетных чисел.

5. Вывести данное натуральное число в восьмеричном виде.

6. Определить, является ли данное слово палиндромом.

7. Найти номер последнего вхождения минимального значения в последовательность длины n

8. Даны натуральные числа a и b. Определить, могут ли эти числа быть соседними членами последовательности Фибоначчи. Последовательность Фибоначчи задается следующим образом: f ₁= f ₂=1, f_i = f_{i- 1}+ f_{i -2} для i >2.

9. Вывести двоичное представление данного натурального числа.

10. Даны две последовательности:

для i ³2.

Вычислить n -е члены этих последовательностей.

11. С клавиатуры вводится последовательность символов. Признак конца ввода – конец файла. Вывести цифры из введенной последовательности сначала в порядке ввода, а затем в обратном порядке.

12. Дана последовательность неотрицательных целых чисел. Вывести сначала все четные, а затем все нечетные числа. Последовательность заканчивается нулем.

13. Вывести в обратном порядке символы данного текста, вводимого с клавиатуры, которые не являются цифрами. Признак конца ввода – конца файла.

14. Найти номер первого вхождения минимального значения в последовательность длины n.

15. С клавиатуры вводятся целые числа. Признак конца ввода – ноль. Найти сумму введенных четных чисел.

16. Дано натуральное число S. Определить, может ли число S быть суммой некоторого числа первых членов последовательности Фибоначчи. Последовательность Фибоначчи задается следующим образом: f ₁= f ₂=1, f_i = f_{i -1}+ f_{i -2} для i >2.

17. Найти номер первого вхождения максимального значения в последовательность длины n.

18. С клавиатуры вводятся слова. Признак конца ввода – конец файла. Вывести символы каждого слова в обратном порядке. Порядок слов изменить на обратный.

19. Дан первый член арифметической прогрессии и ее разность. Вычислить n -й член прогрессии.

20. Дан n -й член арифметической прогрессии и ее разность. Вычислить первый член прогрессии.

21. Дана последовательность ненулевых целых чисел. Вывести сначала все положительные, а затем все отрицательные числа. Последовательность заканчивается нулем.

22. Определить количество букв в тексте, вводимом с клавиатуры. Текст заканчивается символом «конец файла».

23. Найти наибольший общий делитель натуральных чисел n и m.

24. Дана последовательность символов. Вывести сначала строчные, затем прописные буквы. Последовательность заканчивается символом «конец файла».

25. Дан знаменатель и n -й член геометрической прогрессии. Вычислить первый член прогрессии.

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

<формула>::=<цифра>½(<формула><знак><формула>)

<знак>::=+½-½*

<цифра>::=0½1½2½3½4½5½6½7½8½9.

27. С клавиатуры вводятся положительные вещественные числа
a ₁, a ₂, …, a_n. Признак конца ввода – отрицательное число. Вывести следующие значения:

28. Найти номер последнего вхождения максимального значения в последовательность длины n.

29. С клавиатуры вводятся целые числа. Признак конца ввода – ноль. Вывести подряд идущие числа одного знака в обратном порядке. Например, на входе: 1 2 3 –1 –2 –3 4 5 6 0,

на выходе: 3 2 1 –3 –2 –1 6 5 4.

30. С клавиатуры вводятся слова, разделенные пробелами. Признак конца ввода – конец файла. Вывести символы каждого слова в обратном порядке. Порядок слов не изменять.

Контрольные вопросы

1. Какая подпрограмма называется рекурсивной?

2. Какие условия должны выполняться при описании рекурсивных подпрограмм?

3. Назовите преимущества и недостатки рекурсивных подпрограмм по сравнению с итеративными.

4. Всегда ли рекурсивная подпрограмма может быть заменена итеративной?

5. Что такое неявная рекурсия? Как описываются подпрограммы с неявной рекурсией?

6. Почему, если список параметров рекурсивной подпрограммы отличается от набора исходных данных задачи, которую решает рекурсивная подпрограмма, рекомендуется создавать подпрограмму-надстройку, в которой рекурсивная подпрограмма вызывается?