7. Домашнє завдання.
Вправа. «Використання рекурсивних алгоритмів»
Задача. У заданому тексті порахувати кількість знаків "+". Ідея рекурсивного алгоритму: кількість знаків в частині тексту від і-го символу до кінця дорівнює zі, плюс кількість знаків у решті тексту від символу (і + 1) до кінця; zi - допоміжна функція: zi=1, якщо i-й символ є знаком "+", інакше Zi = 0.
Запишіть рекурсивне визначення даної функції.
За рекурсивним визначенням складіть програму. Обчислення рекурсивної функції реалізоване за допомогою двох підпрограм-функцій: Функція К(і) визначає поточний символ рядка S, функція Z (і) визначає значення і-го символу.
Var s : String;
і, N : integer;
Function Z (і : integer) : integer;
Begin
If S[i]=V Then Z:=l Else Z:=0
End;
Function K (і : Integer) : integer;
Begin
if i=Length(S) Then K:=Z(i)
Else K:=Z(i)+K(i+l)
End;
Begi
ReadLn (S)
writeLn (K(l));
End.
Виконайте програму. Проаналізуйте зміну параметрів при рекурсивних викликах функцій.
Задача. Перевірити, чи заданий текст довжиною N символів є симетричним відносно своєї середини, тобто чи співпадає перший символ з останнім, другий — з передостаннім, і т. і.
Ідея рекурсивного алгоритму: текст є симетричним, якщо перший та останній символи однакові, і решта тексту між ними також симетрична (i-й та (N - і + І ) іі символи однакові для і = 1,2, N/2). Запишіть рекурсивне визначення даної функції.
Складіть програму для розв'язування задачі і проаналізуйте її виконання.
Var s : String;
N: Byte;
Function к (і: Byte) : Boolean;
Begin
If i=N Div 2 Then K:= S[i]=S[N-i+l]
Else K:= (S[i] =S[N—і+1]) And K(i+1)
End;
Begin
ReadLn (S);
N:=Length (S);
WriteLn (K(l))
End.
Задача. Переставити всі символи тексту в зворотному порядку. Ідея рекурсивного алгоритму: всі символи тексту перенумеровані від 1 до N; переставлений текст для і-го символу дорівнює переставленому тексту для решти символів від і + 1 до L, об'єднаному з і-м символом; і=1,2, ... ,L.
Запишіть рекурсивне визначення даної функції.
Складіть програму для розв'язування задачі і проаналізуйте її виконання.
Var s : String;
N : Integer;
Function Ps (i: integer) : String;
Begi n
if i=N Then Ps:=S[N]
Else Ps:=Ps(i+l)+S[i]
End;
Begin
ReadLn (S);
N:=Length (S);
WriteLn (Ps(1));
End.
8. Підготуватися до тематичного оцінювання з теми «Функції та процедури».
Заповніть таблицю:
Заповніть пропущені рядки в процедурах обчислення остачі від ділення (Prmod) і неповної частки від ділення (Prdiv) числа А на число В.
Program Dilen; var а, в, м, D : integer;
Procedure Prmod (... ); .........
Procedure Prdiv (... ); .........
Begin
Write ('A,B=>'); Readln(A,B);
Prmod (A, В, M) ; {виклик процедури обчислення остачі від ділення А на В)
Prdiv (А, В, D); (виклик процедури обчислення неповної частки від ділення А на В}
WriteLn ('остача дорівнює ', м);
WriteLn ('частка дорівнює ', D)
End.
Турист пройшов 8 маршрутів. Три маршрути довжиною по R км, К маршрутів - по R1 км 800 м, а інші - по R3 км R2 м. . Визначіть, яку відстань пройшов турист по всіх маршрутах разом. Переведення кілометрів і метрів в кілометри оформіть у вигляді окремої процедури.
Дана процедура, призначена для підрахунку кількості певного символу в рядку.
Procedure Kilk (S: String; C: Char; var K:integer); var I:integer;
Begin
For l:=l To Length(S) Do
If S[I]=C Then K:=K+1;
End;
Складіть програму, яка підраховує сумарну кількість символів 'а', 'б' і 'в' рядку S, який вводиться з клавіатури.
Перепишіть процедуру Kilk із п.4 у вигляді підпрограми-функції. Запишіть оператор, призначений для обчислення сумарної кількості символів 'а', 'б' і 'в' рядку S з використанням цієї функції.
Опишіть функцію для знаходження найбільшого з трьох чисел.
Опишіть функцію, яка визначає, яким степенем числа 2 є її аргумент.
Підрахуйте середнє арифметичне додатних елементів для кожного з масивів А[1..N1], B[1..N2], C[1..N3], якщо N1=6, N2=8, N3=10. Обчислення оформіть у вигляді функції.
Обчисліть Fib (5) для рекурсивної функції:
Function Fib (n: integer): intege;
Begin
If n<=l Then Fib:=1
Else Fib:= Fib (n-1)+Fib (n-2)
End;
Дана арифметична прогресія: a1 = 1.5, d= 2. Запишіть рекурсивне визначення суми n членів даної прогресії. Складіть програму обчислення суми n членів прогресії з використанням рекурсивної функції/
Практичне завдання. Дано алгоритми:
Використовуючи ці алгоритми в якості допоміжних, розв’язати задачі:
а) визначити К-ту цифру числа;
б) визначити суму цифр трицифрового числа;
в) визначити, чи є "щасливим" квиток з даним 6-цифровим номером (номер вважається щасливим, якщо сума перших трьох цифр дорівнює сумі останніх трьох цифр).