Рекурсивні алгоритми

Задачі на обчислення елементів послідовності через попередні елементи

Ми обчислювали елементи послідовності за формулою таким чином: підставляли номер елемента послідовності у формулу та отримували значення елемента.

Але таким чином можна обчислити елементи не для всіх послідовностей. Якщо у формулі для обчислення елемента a_i присутній один чи декілька попередніх елементів (a_i-1 або a_i-2), або формула для обчислення елементу послідовності містить піднесення до степеня чи факторіал, або словесно вказується, як обчислюється „наступний” елемент через „попередній”, то цей алгоритм не підходить.

Наприклад, необхідно обчислити 5 чисел: a₁=3, a_i=a_i-1+5, i=2,3,…5. Нам необхідно обчислити елементи послідовності через один попередній (бо у формулі справа від знака „=” тільки a_i-1). Підставляємо значення i=2,3,…5 у формулу. Отримаємо:

a₁=3
a₂=a₁+5=3+5=8
a₃=a₂+5=8+5=13
a₄=a₃+5=13+5=18
a₅=a₄+5=18+5=23

Правило обчислення елементів послідовності через один попередній

Для значень елементів послідовності досить одної змінної (a). Порядкові номери елементів в програмі не використовуються. Перед циклом потрібно присвоїти перше значення змінній (a). Воно буде „попереднім” (для приклада a:=3). У циклі for i:=2 to n+1 do (цикл від 2, бо одне число вже обчислили): виводиться на екран „попередній” елемент (a); за формулою обчислюється „наступний” елемент, і його значення присвоюється тій же самій змінній (для приклада a:=a+5); останній виток циклу для i=n+1, тому що на кожному витку ми виводимо на екран „попередній” елемент та обчислюємо „наступний”. Тобто приi=2 виводимо на екран a1, а обчислюємо a2, при i=3 виводимо на екран a2, а обчислюємо a3 і т.д. Тобто, останній елемент an виведеться на екран при i=n+1.

Приклад 1

Дано натуральне число n . Надрукувати n чисел a_i=5ⁱ , i=1, 2, …, n.

Дано: кількість чисел

Знайти: Надрукувати самі числа

У самій формулі для обчислення елементів послідовності не видно, що кожний елемент обчислюється через попередній. Але це можна легко з’ясувати:

a₁=5¹=5
a₂=5²=25=5*5=a₁*5
a₃=5³=125=25*5=a₂*5
a₄=5⁴=625=125*5=a₃*5
...

Тобто, a₁=5, a_i=a_i-1*5, i=2,3,…,n .

Результат роботи програми

Ввід	Вивід	Пояснення
4	5 25 125 625	Вводимо 4 - кількість чисел. Отримаємо чотири числа, що є степенями 5.

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)

Вихідні:

• a – саме число (цілого типу longint, бо число може бути досить великим)

Проміжні:

• i – параметр циклу (цілого типу)

Алгоритм

1. Спочатку вводимо n – кількість чисел, що потрібно обчислити та вивести на екран.
2. До початку циклу присвоїмо початкове значення змінній a. Воно повинно співпадати з першим числом послідовності a:=5.
3. У циклі for i:=2 to n+1 do у операторних дужках будемо виконувати такі дії:
   • Оператор write(a,' ') виводить на екран «попереднє» число.
   • Оператор a:=a*5 обчислює „наступне” число.

Програма

var i,n:integer;a:longint; begin  read(n); a:=5;  for i:=2 to n+1 do  Begin   write(a,' '); a:=a*5;  end; end.

Приклад 2

Дано натуральне число n. Надрукувати n чисел  для i=1, 2, …n.

Дано: кількість чисел

Знайти: Надрукувати самі числа

У самій формулі для обчислення елементів послідовності не видно, що кожний елемент обчислюється через попередній. Але це можна легко з’ясувати:

...

Для обчислення i-го „наступного” числа до попереднього числа додають дріб, у чисельнику якого 1, а у знаменнику порядковий номер „наступного” числа. Тобто,b₁=1;  , i=2,3,…n.

Результат роботи програми

Ввід	Вивід	Пояснення
4	1.00 1.50 1.83 2.08	Вводимо 4 - кількість чисел. Отримаємо чотири дійсних числа що є елементами послідовності

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)

Вихідні:

• b – саме число (дійсного типу, бо у виразі є ділення)

Проміжні:

• i – параметр циклу (цілого типу)

Алгоритм

1. Спочатку вводимо n – кількість чисел, що потрібно обчислити та вивести на екран.
2. До початку циклу присвоїмо початкове значення змінній b. Воно повинно співпадати з першим числом послідовності b:=1.
3. У циклі for i:=2 to n+1 do у операторних дужках будемо виконувати такі дії:
   • Оператор write(b:1:2,' ') виводить на екран "попереднє" число з двома знаками після крапки.
   • Оператор b:=b+1/i обчислює "наступне" число.

Програма

var i,n:integer; b:real; begin  read(n); b:=1;  for i:=2 to n+1 do  begin    write(b:1:2,' ');b:=b+1/i;  end; end.

Приклад 3

Дано натуральне число n. Надрукувати n чисел, що створюють послідовність Фібоначчі: 

Дано: кількість чисел

Знайти: Надрукувати самі числа

У цій формулі для обчислення елементів послідовності видно, що кожний елемент, починаючи з третього, обчислюється через два попередніх (f_i-1 та f_i-2 ).

Правило обчислення елементів послідовності

через два попередніх

Для значень елементів послідовності потрібно три змінних (a1, a2, a3). Перед циклом потрібно: присвоїти початкові значення першим двом змінним (a1, a2). Вони повинні співпадати з двома першими елементами послідовності. Вивести на екран значення першої змінної (a1). У циклі for i:=2 to n do (цикл від 2, бо одне число вже вивели на екран): Вивести на екран значення другої змінної (a2). За формулою обчислити значення третьої змінної a3, через a1 та a2. Перед переходом на наступний виток циклу переприсвоюємо значення двох „попередніх” елементів: a1:=a2, a2:=a3. Останній виток циклу для i=n, тому що на кожному витку ми виводимо на екран і-й елемент послідовності та обчислюємо і+1-й елемент. Тобто при i=2 виводимо на екран друге число та обчислюємо третє, при i=3 виводимо на екран третє число, та обчислюємо четверте і т.д. Тобто, останній елемент виведеться на екран при i=n.

Результат роботи програми

Ввід	Вивід	Пояснення
6	1 1 2 3 5 8	Вводимо 6 - кількість чисел. Отримаємо шість елементів послідовності Фібоначчи

Змінні:

Вхідні:

• n – кількість чисел (цілого типу)

Вихідні:

• f1 – „перше попереднє” число (цілого типу, за мовою)
• f2 – „друге попереднє” число (цілого типу, за мовою)
• f3 – „наступне число” (цілого типу, за мовою)

Проміжні:

• i – параметр циклу (цілого типу)

Алгоритм

1. Спочатку вводимо n – кількість чисел, що потрібно обчислити та вивести на екран.
2. До початку циклу присвоїмо початкові значення двом попереднім елементам: змінним f1 та f2. Вони співпадають з двома першими числами послідовності та дорівнюють 1.
3. Оператор write(f1,' ') виводить на екран "перше попереднє" число.
4. У циклі for i:=2 to n do у операторних дужках будемо виконувати такі дії:
   • Оператор write(f2,' ') виводить на екран "друге попереднє" число.
   • Оператор f3:=f1+f2 обчислює "наступне" число.
   • Перед переходом на наступний виток циклу, "друге попереднє" число повинно стати "першим попереднім" f1:=f2, а "наступне" число повинно стати "другим попереднім" f2:=f3.

Програма

var i,n:integer; f1,f2,f3:integer; begin  read(n);  f1:=1; f2:=1; write(f1,' ');  for i:=2 to n do  begin     write(f2,' ');     f3:=f1+f2;     f1:=f2; f2:=f3;  end; end.

Варіанти задач

1. Надрукуйте у рядок 10 чисел, якщо перше число 1, а кожне наступне число є добутком попереднього та 0.5.
2. Нехай перший член послідовності чисел a=1, а кожний наступний елемент дорівнює сумі попереднього та числа 1.5. Складіть програму обчислення перших 10 елементів цій послідовності.
3. Нехай перший член послідовності чисел a=10, а кожний наступний елемент дорівнює добутку попереднього та числа 2.5. Складіть програму обчислення перших 10 елементів цій послідовності.
4. Дано натуральні числа N та K. Надрукувати N чисел .
5. Дано натуральне n. Надрукувати n чисел a₁=1, a_i=2*a_i-1+1 , де i=2,3...n
6. Складіть програму обчислення перших 10 членів послідовності, якщо i-ий член послідовності має вигляд :x_i=2ⁱ+3, де i=1,2,...10.
7. Дано натуральне n. Надрукувати n чисел a_i=i! де i=1, 2, ...n. Пояснення: i факторіал -  це добуток чисел від 1 до i:    i!=1*2*3*...*i.
8. Дано натуральне n. Надрукувати n чисел . Пояснення: i факторіал - це добуток чисел від 1 до i: i!=1*2*3*...*i.
9. Послідовність чисел a₁, a₂, a₃, ... утворюється за законом:  . Дано натуральне число n. Надрукуйте послідовність чисел a₁, a₂, a₃,..., a_n .
10. Послідовність чисел a₁, a₂, a₃, ... утворюється за законом:  . Дано натуральне число n. Надрукуйте послідовність чисел a₁, a₂, a₃,..., a_n .
11. Послідовність чисел a₁, a₂, a₃, ... утворюється за законом:  . Дано натуральне число n. Надрукуйте послідовність чисел a₁, a₂, a₃,..., a_n .
12. Послідовність чисел a₁, a₂, a₃, ... утворюється за законом:  . Дано натуральне число n. Надрукуйте послідовність чисел a₁, a₂, a₃,..., a_n .
13. Дано натуральне n. Надрукувати N чисел x₁=0.3; x₂=-0.3; x_i=i+sin(x_i-2),  де i=3, 4, ..., n.
14. Дано натуральне n. Надрукуйте послідовність чисел b₁, b₂, ... b_n, де при i=1, 2, ...n значення b_i=2ⁱ+3ⁱ⁺¹. Наприклад: b₁=2+3²; b₂=2²+3³; b₃=2³+3⁴; ...
15. Дано натуральне n. Надрукувати n чисел . Пояснення: i факторіал - це добуток чисел від 1 до i: i!=1*2*3*...*i.
16. Послідовність u₁, u₂, u₃, ... утворюється за законом u₁=0; u₂=1; u_i=u_i-2+u_i-1+f_i-2 (i=3,4, ...), де f_i-2 - відповідний член послідовності Фібоначчі. Дано натуральне число n. Надрукуйте послідовність u₁, u₂, u₃,..., u_n .