Читайте также:
|
Приведенные задания могут быть использованы на “обычных” уроках, на контрольных мероприятиях, как задания на дом и т.п. 5
1. Разработать программу для расчета числа сочетаний из n элементов по m (обозначается 
), используя следующее рекурсивное описание: 
Решение
Рекурсивная функция для расчета значения :
Function Cnm(n, m: byte): word;
Begin
If (m = 0) Or (n = m) Then Cnm:= 1
Else Cnm:= Cnm(n — 1, m) + Cnm(n — 1, m — 1)
End;
2. Составить программу для расчета n-го члена заданной арифметической прогрессии.
Решение
Можно сказать, что в определении понятия “арифметическая прогрессия” содержится рекурсивное описание искомого значения.
В приведенной ниже функции, кроме n, используются также параметры а 1 и d — соответственно первый член прогрессии и ее разность:
Function Ar_n(a1, d: real; n:byte): real;
Begin
If n = 1 Then Ar_n:= a1
Else Ar_n:= Ar_n(a1, d, n — 1) + d
End;
3. Составить программу для расчета n-го члена заданной геометрической прогрессии.
Решение
Здесь рекурсивная функция во многом аналогична приведенной в предыдущей задаче:
Function Geo_n(a1, z: real; n: byte): real;
Begin
If n = 1 Then Geo_n:= a1
Else Geo_n:= Geo_n(a1, z, n — 1) * z
End;
— в ней z — знаменатель прогрессии.
4. Составить программу для расчета суммы n первых членов заданной арифметической прогрессии.
Решение
В приведенной ниже функции в качестве вспомогательной используется функция, описанная в задаче 2:
Function Summ_Ar_n(a1, d: real; n: byte): real;
Begin
If n = 1 Then Summ_Ar_n:= a1
Else Summ_Ar_n:= Summ_Ar_n(a1, d, n — 1) + Ar_n(a1, d, n)
End;
5. Составить программу для расчета суммы n первых членов заданной геометрической прогрессии.
Решение
Соответствующая функция:
Function Summ_Geo_n(a1, d: real; n: byte): real;
Begin
If n = 1 Then Summ_Geo_n:= a1
Else Summ_Geo_n:= Summ_Geo_n(a1, d, n — 1) + Geo_n(a1, d, n)
End;
6. Дана строка символов, представляющая собой правильную запись натурального числа в p-ичной системе счисления (2≤p≤9). Составить программу перевода этого числа в десятичную систему счисления.
Решение
Здесь надо вспомнить схему Горнера для расчета десятичного значения числа по его цифрам, которая по сути является рекурсивной. Так, если число в p-ичной системе является четырехзначным (а3а2а1а0), то десятичное значение этого числа определяется следующим образом:
((а 3· p + а 2) · p + а 1) · p + а 0.
Функция, “работающая” по этой схеме, может иметь вид:
Function RevTo10(S: string; p: byte): longint;
Var last: byte; code: integer; {last — последняя цифра в строковой записи числа)
Begin
If length(S) = 1 Then
Begin
{Переводим символ-цифру в число,}
Val(S[Length(S)], last, code);
{которое и будет значением функции}
RevTo10:= last
End
Else
Begin
{Переводим последний символ строки S в число last}
Val(S[Length(S)], last, code);
{и используем схему Горнера}
RevTo10:= RevTo10(Copy(S, 1, Length(S) — 1), p) * p + last
End
End;
Можно также сначала перевести в число всю строку S, а затем “работать” с его цифрами:
Function RevTo10(S: string; p: byte): longint;
Var k: longint; last: byte;
code: integer;
{k — число, соответствующее S)
Begin
{Определяем число k)
Val(S, k, code);
If k < 10 Then RevTo10:= k
Else
Begin
{Определяем последнюю цифру числа k)
last:= k mod 10;
{Переводим число k без его последней цифры в символьное представление}
Str(k div 10, s);
{и используем схему Горнера}
RevTo10:= R_to10(s, p) * p + last
End
End;
7. Разработать программу для определения суммы цифр заданного натурального числа.
Решение
Соответствующая рекурсивная функция во многом аналогична функции, рассмотренной в разделе 3.
Function S(a: longint): byte;
Begin
If a < 10 Then S:= a
Else S:= a mod 10 + S(a div 10)
End;
8. Разработать программу для вычисления произведения элементов одномерного числового массива.
Решение
Функция, с помощью которой можно решить задачу, также аналогична рассмотренной в разделе 3.
Function M(k: byte): real;
Begin
If k = 1 Then M:= a[k — 1]
Else M:= a[k] * M(k — 1)
End;
Примечание. Имеется в виду, что элементы массива а — вещественные числа.
От редакции. Здесь и в других задачах, связанных с использованием массивов, можно учесть замечание, сделанное при обсуждении функции для расчета суммы элементов массива в разделе 3.
9. Разработать программу для расчета среднего арифметического всех элементов числового массива.
Решение
Рекурсивная функция, которая возвращает искомое значение, имеет вид:
Function Aver(k: byte): real;
{k — число элементов обрабатываемого массива}
Begin
If k = 2 Then Aver:= (a[1] + a[k])/2
Else Aver:= (a[k] + Aver(k — 1) * (k — 1))/k
End;
10. Разработать программу для расчета значения an (a — вещественное число, a № 0, n — целое).
Решение
Можно записать:
Рекурсивная функция:
Function Power(a: real; n: integer): real;
Begin
If n = 0 Then Power:= 1
Else
If n > 0 Then Power:= a * Power(a, n — 1)
Else Power:= 1/(Power(a, Abs(n)))
End;
Примечание. Целесообразно обсудить с учащимися последовательность вызовов и использования приведенной функции при отрицательных значениях n, например, n = –3.
11. Разработать программу для нахождения наибольшего общего делителя (НОД) двух заданных натуральных чисел.
Решение
Можно применить алгоритм Евклида нахождения НОД. Его суть в следующем: “Если два заданных числа равны, то в качестве ответа взять любое, иначе большее из чисел заменить разностью большего и меньшего”.
В аналитическом виде алгоритм Евклида выглядит следующим образом:
Рекурсивная функция, реализующая этот алгоритм:
Function NOD(a, b: word): word;
Begin
If a = b Then NOD:= a
Else
If a > b Then NOD:= NOD(a — b, b)
Else NOD:= NOD (a, b — a)
End;
12. Разработать программу для определения значения минимального элемента массива.
Решение
Опишем функцию MinK, которая определяет минимум в массиве а из k элементов. Ясно, что если k = 2, то результат равен минимальному из первых двух элементов массива. Если же k > 2, то результатом является минимальное из двух чисел: последнего элемента такого массива и минимального числа из первых (k – 1) элементов массива. Второе из сравниваемых чисел можно найти с помощью той же функции MinK (рекурсивный вызов).
Соответствующая рекурсивная функция
Function MinK(k: byte): integer;
Begin
If k = 2 Then MinK:= Min(a[1], a[k])
Else MinK:= Min(a[k], MinK(k — 1))
End;
Минимальное из двух чисел определяется с помощью функции Min, параметрами которой являются эти числа:
Function Min(a, b: integer): integer;
Begin
If a > b Then Min:= b
Else Min:= a
End;
Чтобы найти минимум среди всех элементов заданного массива, нужно вызвать функцию MinK, указав в качестве фактического параметра размер массива.
От редакции. Можно в заголовке функции использовать только один параметр — k, а в ее теле значение last заменить на a[k]:
Function MinK(k: byte): integer;
Begin
If k = 2 Then MinK:= Min(a[1], a[2])
Else MinK:= Min(a[k], MinK(k — 1))
End;
13. Разработать программу для определения индекса минимального элемента массива.
Решение
Если в массиве два элемента (k = 2), то результатом является индекс одного из двух первых элементов. Если же n > 2, то результат определяется путем сравнения двух элементов: k-го и того, который является минимальным среди первых (k – 1) элементов массива. Индекс второго из сравниваемых чисел можно найти, используя рекурсию.
Соответствующая рекурсивная функция:
Function IndMinK(k: byte): byte;
Begin
If k = 2 Then IndMinK:= IndMin2(1, k)
Else IndMinK:= IndMin2(k, IndMinK(k — 1))
End;
— где IndMin2 — функция определения индекса минимального из двух элементов массива с заданными индексами:
Function IndMin2(ind1, ind2: byte): byte;
{ind1, ind2 — индексы сравниваемых элементов}
Begin
If a[ind1]< a[ind2] Then IndMin2:= ind1
Else IndMin2:= ind2
End;
Примечание. Целесообразно предложить учащимся подумать над вопросом: “Индекс какого элемента будет найден, если в массиве есть несколько элементов с минимальным значением?”.
14. Используя оператор write(а) лишь при а = 0..9, разработать программу вывода на экран десятичной записи заданного натурального числа n.
Решение
Процедура, обеспечивающая решение задачи:
Procedure Print(n: longint);
Begin
If n < 10 Then
Begin
a:= n;
write(a)
End
Else
Begin
{Рекурсивный вызов процедуры Print}
Print(n div 10);
{Определение и вывод последней цифры числа n}
a:= n mod 10;
write(a)
End
End;
Здесь также имеет место так называемая “Форма рекурсивной процедуры с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате)” — см. раздел 5. — Прим. ред.
15. Разработать программу, которая вычисляет длину заданной строки (стандартную функцию Length не использовать).
Решение
В рекурсивной функции применяется стандартная процедура Delete:
Function Len(s: string): byte;
Begin
If S = '' Then Len:= 0
Else
Begin
Delete(s, 1, 1);
Len:= 1 + Len(s)
End
End;
16. Разработать программу, проверяющую, является ли некоторая строка палиндромом (т.е. читается одинаково слева направо и справа налево).
Решение
Рекурсивная функция, возвращающая результат логического типа, с помощью которой можно решить задачу, имеет вид:
Function Pal(s: string): boolean;
Begin
{Если строка 'пустая' или состоит из одного символа}
If (s = '') Or (Length(s) = 1)
Then Pal:= true
Else
{Сравниваем первый и последний символы строки}
If s[1] <> s[Length(s)] Then Pal:= false
Else
{Удаляем первый и последний символы строки}
Begin
Delete(s, 1, 1);
Delete(s, Length(s), 1);
{и вновь проверяем оставшуюся строку}
Pal:= Pal(s)
End
End;
Эта функция используется в основной части программы при выводе ответа:
If Pal(st)
Then writeln('Строка является палиндромом'}
Else writeln('Строка не является палиндромом'};
— где st — проверяемая строка.
Можно также процедуру Delete не применять, а при рекурсивном вызове использовать функцию Copy.
17. Разработать программу расчета суммы двух натуральных чисел, используя только прибавление единицы.
Решение
Рекурсивная функция Summa1, возвращающая число а как результат сложения а единиц, может быть оформлена в виде:
Function Summa1(a: byte): word;
Begin
If a = 1 Then Summa1:= 1
Else Summa1:= 1 + Summa1(a — 1)
End;
Эта функция используется в основной части программы для подсчета искомого результата rez:
rez:= Summa1(n1) + Summa1(n2);
— где n1 и n2 — складываемые числа.
18. Разработать программу расчета произведения двух натуральных чисел, используя только операцию сложения.
Решение
Рекурсивная функция, возвращающая произведение двух своих параметров a 1 и a 2 как результат многократного сложения, имеет вид:
Function Mult(a1, a2: byte): longint;
Begin
If a2 = 1 Then Mult:= a1
Else Mult:= a1 + Mult(a1, a2 — 1)
End;
Возможен также “симметричный” вариант, в котором происходит a 1 сложений числа a 2, а также “общий” вариант, в котором после сравнения a 1 и a 2 выбирается оптимальный с точки зрения количества операций сложения.
19. Разработать программу для вывода заданной последовательности чисел, оканчивающейся нулем, в обратном порядке.
Решение
В соответствующей рекурсивной процедуре используется локальная переменная n — очередное число последовательности:
Procedure Output;
Var n: integer;
Begin
write('Введите очередное число последовательности');
readln(n);
If n <> 0 Then
Begin
{Рекурсивно вызываем процедуру Output для ввода очередного числа}
Output;
{После 'возвращения' из нее выводим введенное число}
write(n, ' ')
End
Else
write('Числа последовательности в обратном порядке:')
End;
20. Задача “Ханойские башни”.
Имеется три стержня А, В, С. На стержень А нанизаны n дисков таким образом, что диаметр дисков увеличивается при их просмотре сверху вниз. Требуется переместить все диски на стержень В, используя диск С как вспомогательный и соблюдая следующие правила:
1) перекладывать диски можно по одному;
2) снятый диск нельзя отложить — он должен быть надет на один из стержней;
3) диски нельзя размещать на дисках меньшего размера.
Решение
Если диск один — задача решается одним перемещением. Сложнее, если дисков больше. Предположим, что мы умеем перекладывать пирамиду из (n – 1) диска. Тогда для перемещения n дисков необходимо:
1) переместить верхние (n – 1) дисков на стержень С;
2) перенести последний, самый большой, диск со стержня А на стержень В;
3) переместить пирамиду из (n – 1) дисков со стержня С на стержень В.
Решение задачи для (n – 1) дисков аналогично. В результате таких рекурсивных действий можно прийти к ситуации, когда количество перемещаемых дисков равно 1, а такую задачу мы решать умеем.
В программе следует использовать две процедуры, одна из которых — рекурсивная:
1) процедуру перемещения одного диска:
Procedure MoveOneDisk(a, b: char);
Begin
Write(a, '->', b, ' ')
End;
2) процедуру перемещения n дисков:
Procedure MoveDisks(n: byte; a, b, c: char);
Begin
If n = 1 Then
{Используем процедуру MoveOneDisk}
MoveOneDisk(a, b)
Else
Begin
MoveDisks(n — 1, a, c, b);
write(a,'->', b, ' ');
MoveDisks(n — 1, c, b, a)
End
End;
Можно также задачу при n = 1 отдельно не рассматривать:
Procedure MoveDisks(n: byte; a, b, c: char);
Begin
If n > 0 Then
Begin
MoveDisks(n — 1, a, c, b);
write(a,'->', b, ' ');
MoveDisks(n — 1, c, b, a)
End
End;
Дата добавления: 2015-02-16; просмотров: 153 | Поможем написать вашу работу | Нарушение авторских прав |