Рекурсивные вычисления

Рекурсивные подпрограммы основаны на их обращении к самим себе [6]. Описание действий в таких подпрограммах обязательно содержит терминальную ситуацию, в которой результат получается непосредственно без рекурсивного вызова. Покажем пример реализации действий для следующей задачи: методом слияния объединить два вектора из целых чисел, отсортированных по нарастанию значений их элементов.

Метод слияния двух отсортированных массивов A и B из n и m элементов соответственно, что называется, интуитивно понятен. В последнюю позицию результирующего вектора C сначала помещают наибольший из элементов векторов A и B. Номер следующего элемента (n или m) в том векторе, из которого его взяли, уменьшается на 1. Этот элементарный шаг можно повторять рекурсивно. Если один из векторов уже переписан в вектор C, то в C помещают остатки другого. Терминальная ситуация наступает, когда все элементы векторов A и B будут переписаны в C, чему соответствует условие n + m = 0.

Сначала сконструируем основную форму, представленную на рисунке. Затем создадим модуль с рекурсивной процедурой слияния и вспомогательной процедурой перевода строки в вектор. Для этого выполним команду File/New/Unit – Delphi for Win32. В результате появится заготовка модуля с заголовками интер-фейсной секции и секции реализации. Заносим в них код, представленный ниже.

unit Unit2;

 

interface

const

k = 100;

type

vector = array[1..k] of integer;

procedure Sliyanie (n, m : byte; a, b : vector; var c : vector);

procedure StrToVector(s : string; var n : integer; var v : vector);

 

implementation

uses SysUtils;

procedure Sliyanie (n, m : byte; a, b : vector; var c : vector);

{a и b - исходные векторы, c - результат их слияния}

{сначала n - размер вектора a, m - размер вектора b}

begin

if m + n = 0 then exit {Терминальная ситуация - когда все элементы}

else begin {из вектора a и вектора b помещены в вектор c}

if n = 0 then begin {Если из вектора a все элементы взяты в вектор c,}

c[n + m] := b[m]; {то помещаем в него элемент вектора b}

m := m-1

end

else if m = 0 then begin

c[n + m] := a[n]; n := n-1;

end

else if a[n] > b[m] then begin

c[n + m] := a[n]; n := n-1;

end

else begin

c[n + m] := b[m]; m := m-1;

end;

sliyanie(n, m, a, b, c); // Рекурсивный вызов с новыми значениями n и m

end;

end;

 

procedure StrToVector(s : string; var n : integer; var v : vector);

var // Процедура перевода строки s в вектор v из n элементов

element : string[5]; // Элемент строки

i : integer;

begin

i := 1;

repeat // Цикл обработки чисел в строке

element := copy(s, 1, pos(' ', s)-1); // Элемент строки как число

v[i] := StrToInt(element);

delete(s, 1, pos(' ', s));

inc(i);

until pos(' ', s) = 0;

v[i] := StrToInt(s);

n := i;

end;

end.

 

Сообщение об ошибке Undeclared identifier: ' StrToInt ' при компиля-ции потребует добавления строки uses SysUtils; после слова implementation. Созданный модуль необходимо подключить к проекту, для чего выполняют одну из команд: File/Use Unit… или Project/Add to Project…. И наконец, сам обработчик щелчка по кнопке “Объединить” имеет вид:

procedure TForm1.Button1Click(Sender: TObject);

var

v1, v2, v3 : vector; i, n, m : integer;

begin

StrToVector(Edit1.Text, n, v1);

StrToVector(Edit2.Text, m, v2);

Sliyanie(n, m, v1, v2, v3);

for i := 1 to n + m do

Edit3.Text := Edit3.Text + ' ' + IntToStr(v3[i]);

end;

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

Создать проект из двух модулей: первый модуль отвечает за интерфейс приложения, а второй содержит рекурсивную подпрограмму в соответствии с вариантом задания.

1. Вычислить и показать первые 10 чисел Фибоначчи: F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2).

2. Вычислить значения первых 5 полиномов Лежандра для x = 1 и x = 0.6 : , , .

3. С погрешностью 0.001 уточнить методом дихотомии корень уравнения = 0 на отрезке [0; 4].

4. С погрешностью 0.001 уточнить по методу Ньютона корень уравнения ln(x) – x + 1.8 = 0 на отрезке [2; 3].

5. Уточнить корень уравнения ln(x) – x + 1.8 = 0 на отрезке [2; 3] методом простой итерации с погрешностью 0.001.

6. Используя итерационную формулу , вычислить с погрешностью 0.001 и .

7. Найти с погрешностью 0.001 и , по формуле q := (q + n/q)/2, в которой n – исходное число, а q – приближение к результату.

8. Определить наибольший элемент в векторе из n чисел.

9. Методом прямоугольников вычислить с погрешностью 0.001 .

10. С погрешностью 0.001 вычислить .

11. С погрешностью 0.001 вычислить .

12. Для x = 0.8 вычислить значения первых 6 полиномов Эрмита: , , .

13. Вычислить и , использовав следующее представление квадратов чисел: , , , …

14. Вычислить сумму элементов вектора из n чисел.

15. Для x = 0.5 вычислить значения первых пяти полиномов Лагерра: , , .

16. Вычислить значения первых пяти многочленов Чебышева: , , для x = 0.5.

17. Подсчитать количество переносов колец ханойской башни с одного столба на другой. Можно переносить только по одному кольцу, класть меньшее на большее, используя третий столб. Исходная и результирующая башни имеют на вершинах самое маленькое кольцо.

18. Вычислить p + (p + 1) + (p + 2) + … + (p + n) для p = 0.7 и n = 10, а также для p = 0.5 и n = 15.

19. С погрешностью 0.0001 вычислить e = 1 + 1/1! + 1/2! + 1/3! + …

20. Вычислить для n = 7 и n = 10 выражение .