Дата конвертації03.07.2017
Розмір62.68 Kb.
Типдипломна робота

Скачати 62.68 Kb.

рекурсія

> Рішення. Функція dec_p (a, p, k) вирішує поставлене завдання, здійснюючи переклад десяткового числа a в p-ічную систему числення. Результат обчислень формується у вигляді складеного вектора. Компоненти цього вектора знову вектори, що містять відповідно цифри цілої і дробової частин числа a в p-ічной системі числення. Цифри цілої і дробової частини a повертаються, починаючи зі старших розрядів і далі. У дробової частини присутні не більше ніж k (k = 1,2, ...) цифр. При обчисленнях функція dec_p () звертається до двох рекурсивним функціям dec_p_i () і dec_p_f ().

Контрольні приклади.

Завдання 4. Нехай m = (v 0 v 1... v n 1) 10 ціле десяткове невід'ємне число, цифри якого від старшої і далі задані послідовними компонентами вектора v = (v 0, v 1,..., v n 1) T. Скласти програму-функцію перекладу m в систему числення за основою p.

Рішення. Функція dec_p_iv (v, p) здійснює переклад v в p-ічную систему числення. Результат обчислень формується, починаючи від старших розрядів і далі, у вигляді вектора, компоненти якого суть p-ічние цифри вихідного числа. Функція dec_p_iv (v, p) відрізняється від раніше розглянутої функції dec_p_i (v, p) лише формою представлення першого аргументу. Тому її обчислення можна звести до обчислення dec_p_i (v, p) з попереднім зверненням до рекурсивної функції dv_norm (v), що переводить десяткове число з векторного уявлення в нормальну форму. Це і зроблено нижче.

Контрольні приклади.

Завдання 5. Нехай y = (. V 0 v 1... v n 1) 10 правильна неотрицательная десяткова дріб, цифри якої від старшої і далі задані послідовними компонентами вектора v = (v 0, v 1,..., v n 1) T. Скласти програму-функцію перекладу y в систему числення за основою p.

Рішення. Функція dec_p_fv (v, p, k) здійснює переклад v в p-ічную систему числення. Результат обчислень формується, починаючи від старших розрядів і далі, у вигляді вектора довжини не більше k, компоненти якого суть p-ічние цифри вихідного числа. Функція dec_p_fv (v, p, k) відрізняється від раніше розглянутої функції dec_p_f (v, p, k) лише формою представлення першого аргументу. Тому її обчислення можна звести до обчислення dec_p_f (v, p, k) з попереднім зверненням до рекурсивної функції dv_normf (v), що переводить десяткову дріб з векторного уявлення в нормальну форму. Це і зроблено нижче.

Контрольні приклади.

Завдання 6. Нехай дійсне невід'ємне десяткове число a представлено двома векторами in і fr, компоненти яких послідовні десяткові цифри, починаючи від старшої і далі, відповідно цілої і дробової частини а. Скласти програму-функцію перекладу a в систему числення за основою p.

Рішення. Функція dec_pv (in, fr, p, k) вирішує поставлене завдання, здійснюючи переклад десяткового числа a в p-ічную систему числення. Результат обчислень формується у вигляді складеного вектора. Компоненти цього вектора знову вектори, що містять відповідно цифри цілої і дробової частин числа a в p-ічной системі числення. Цифри цілої і дробової частини a повертаються, починаючи зі старших розрядів і далі. У дробової частини присутні не більше ніж k (k = 1,2, ...) цифр. При обчисленнях функція dec_p () звертається до двох рекурсивним функціям dec_p_iv () і dec_p_fv ().

Контрольні приклади.

B. Переклад чисел з p-ічной системи в десяткову систему

Нехай p {2,3, ...} і цифрами p-ічной системи є десяткові числа 0,1, ..., p1. Будемо вважати, що розглядаються невід'ємні p-ічние числа, а їх цифри від старшого розряду і далі задаються послідовними компонентами векторів. Розглянемо 3 конкретні завдання.

Завдання 7. Нехай m = (v 0 v 1... v n 1) p ціле p-ічное невід'ємне число, цифри якого від старшої і далі задані послідовними компонентами вектора v = (v 0, v 1,..., v n 1) T. Скласти програму-функцію перекладу m в десяткову систему числення.

Рішення. Функція p_dec_i (v, p) вирішує поставлене завдання, використовуючи рекурсивний алгоритм послідовного розподілу. Результат формується в природному стані.

Контрольні приклади.

Завдання 8. Нехай y = (. V 0 v 1... v n 1) p правильна неотрицательная десяткова дріб, цифри якої від старшої і далі задані послідовними компонентами вектора v = (v 0, v 1,..., v n 1) T. Скласти програму-функцію перекладу y в десяткову систему числення.

Рішення. Функція p_dec_f (v, p) вирішує поставлене завдання, використовуючи рекурсивний алгоритм послідовного множення. Результат формується в природному стані.

Контрольні приклади.

Завдання 9. Нехай дійсне невід'ємне p-ічное число а представлено двома векторами in і fr, компоненти яких послідовні p-ічние цифри, починаючи від старшої і далі, відповідно цілої і дробової частини а. Скласти програму-функцію перекладу a в десяткову систему числення.

Рішення. Функція p_dec (in, fr, p) вирішує поставлене завдання, здійснюючи переклад p-ічного числа a в десяткову систему числення. Результат обчислень формується в природному стані. При обчисленнях функція p_dec () звертається до двох рекурсивним функціям p_dec_i () і p_dec_f ().

Контрольні приклади.

Зауваження. Переклад чисел з p-ічной системи числення в q-ічную систему (p, q {2,3, ...}) можна здійснювати через проміжну десяткову систему.

13.5 Генератори перестановок

Раніше в розділі 12.9 ми описали один з алгоритмів отримання n! перестановок з елементів безлічі S = {a 0, a 1,..., a n 1}, де a k (k = 0..n1) попарно різні дійсні числа. Вважаючи, що S = {1,2, ..., n}, обговоримо ще кілька варіантів рекурсивних алгоритмів генерування перестановок. Відрізняються один від одного вони різними характеристиками: швидкодією, компактністю записи, кількістю транспозиція при отриманні чергової перестановки і т.д.

A. Метод вертикальної прогонки. При S = ​​{1} маємо одну перестановку 1. Якщо вже є послідовність перестановок з n1 елемента {1,2, ..., n1}, то отримати всі перестановки з n елементів {1,2, ... n} можна способом, який ми будемо іменувати як "метод вертикальної прогонки" елемента n. Суть його в наступному. Розглянемо n ідентичних примірників (груп) послідовностей перестановок з елементів {1,2, ..., n1}. У першому примірнику в кінець кожної перестановки помістимо елемент n. У другому екземплярі цей елемент помістимо на передостанньому місці і т.д. Нарешті, в останньому примірнику помістимо n перед першим елементом. На малюнку 13.4 описана процедура демонструється при переході від n = 3 до n = 4. Неважко зрозуміти, що зазначені дії будь-яку перестановку з n1 елемента переводять в деяку перестановку з n елементів. При цьому загальна кількість отриманих перестановок одно n !. Залишається показати, що серед них немає співпадаючих. Якщо взяти дві згенеровані перестановки всередині однієї групи, то вони будуть відрізнятися один від одного позиціями елементів {1,2, ..., n1} і, отже, не можуть бути однаковими. Якщо ж взяти перестановки з різних груп, то позиції елемента n в них будуть різними і перестановки знову не можуть бути однаковими. Таким чином, всі отримані n! перестановок різні.

Мал. 13.6. Генерування перестановок методом вертикальної прогонки.

Описаний алгоритм вертикальної прогонки реалізується рекурсивної програмою-функцією permut1 (n):

контрольний приклад

B. Метод послідовного заміщення. При S = ​​{1} маємо одну перестановку 1. Якщо вже є послідовність перестановок з n1 елемента {1,2, ..., n1}, то отримати всі перестановки з n елементів {1,2, ... n} можна способом, який ми будемо іменувати як "метод послідовного заміщення" елемента n. Суть його в наступному. Розглянемо n ідентичних примірників (груп) послідовностей перестановок з елементів {1,2, ..., n1}. У першому екземплярі, як і в методі вертикальної прогонки, в кінець кожної перестановки помістимо елемент n. У кожній перестановці другого примірника поміняємо місцями елементи n і 1. У кожній перестановці третього примірника поміняємо місцями елементи n і 2 і т.д. Нарешті, в останньому примірнику поміняємо місцями елементи n і n1. На малюнку 13.5 описана процедура демонструється при переході від n = 3 до n = 4. Неважко зрозуміти, що зазначені дії будь-яку перестановку з n1 елемента переводять в деяку перестановку з n елементів. При цьому загальна кількість отриманих перестановок одно n !. Залишається показати, що серед них немає співпадаючих. Якщо взяти дві згенеровані перестановки всередині однієї групи, то вони обов'язково будуть відрізнятися один від одного розташуванням елементів на позиціях від 1 до n1 і, отже, не можуть бути однаковими. Якщо ж взяти перестановки з різних груп, то на останніх позиціях у них стоять різні елементи і перестановки знову не можуть бути однаковими. Таким чином, всі отримані n! перестановок різні.

Мал. 13.5. Генерування перестановок методом послідовного

заміщення

Описаний алгоритм послідовного заміщення реалізується рекурсивної програмою-функцією permut2 (n):

С. Перестановки в антілексікографіческом порядку. На безлічі P всіх перестановок 0, x 1,..., x n -1> з елементів {1,2, ..., n} визначимо два типи порядку.

Лексикографічний порядок на P вводиться наступним чином. для

(0, a 1,..., a n 1>, 0, b 1,..., b n 1> P) (19)

покладемо

0, a 1,..., a n 1> < 0, b 1,..., b n 1>

(k 0) [(a k b k) & (s s = b s)]], (20)

де символ <використаний в якості знака лексикографічного порівняння перестановок.

Зауважимо, що якщо замість чисел 1,2, ..., n використовувати букви з природним порядком проходження їх в алфавіті, то лексикографічний порядок визначає стандартну послідовність, в якій слова довжини n з'являються в словнику. І це справедливо для алфавітів будь-яких мов.

Аналогічно вводиться і антілексікографіческій порядок на P. Для (19) покладемо

0, a 1,..., a n 1> < " 0, b 1,..., b n 1>

(k n1) [(a k> b k) & (s> k) [(a s = b s)]], (21)

де символ < "використаний в якості знака антілексікографіческого порівняння перестановок.

Побудуємо рекурсивную програму-функцію, яка генерує перестановки елементів {1,2, ... n} в антілексікографіческом порядку.Відповідний алгоритм може базуватися на наступних двох твердженнях, безпосередньо випливають з визначення 21.

Твердження 1. Якщо безліч перестановок P упорядковано антілексікографіческі, то початкова і кінцева перестановки це відповідно <1,2, ..., n> і .

Твердження 2. Упорядкована антілексікографіческі послідовність перестановок за значенням останнього елемента в них може бути розбита на n блоків довжини (n1) !. При цьому q-й блок на останньому місці має елемент рівний (nq + 1), а перші n1 позицій цього блоку визначають послідовність перестановок множини {1,2, ..., n} {q} в антілексікографіческом порядку.

Головний функція permut3 (n) вирішує поставлене завдання. У ній за значенням n для рекурсивної програми-функції permu (p) формується початкова перестановка p. У permu (p) і проводяться всі обчислення. На рис. 13.6 представлений результат виконання permut3 (n) при n = 3 і n = 4. Для n = 4 отримані перестановки розташовані по стовпцях.

Мал. 13.6. Генерування перестановок в антілексікографіческом порядку

D. Перестановки в лексикографічному порядку. У попередньому розділі ми ввели поняття лексикографічного порядку. Алгоритм генерування перестановок в такому порядку і відповідні програми-функції можуть бути побудовані на ідеях, близьких до тих, які використовувалися при генеруванні перестановок в антілексікографіческом порядку. Тому тут ми обмежимося лише приведенням відповідних функцій permut (p) і permut4 (n) і представимо отриманий по ним результат обчислень для n = 3 і n = 4 (див. Рис. 13.7). Для n = 4 отримані перестановки розташовані по стовпцях.

Мал. 13.7. Генерування перестановок в лексикографічному порядку

E. Перестановки c однієї транспозицией сусідніх елементів. У цьому пункті розглядається алгоритм генерування послідовності перестановок U з елементів множини {1,2, ..., n} такий, що будь-яка перестановка U, крім початкової, виходить з попередньої перестановки однієї транспозицией сусідніх елементів. Проілюструємо на прикладі ідею відповідного алгоритму, що приписується Джонсону [] і Троттер []. Припустимо, що для елементів {1,2, ..., n1} вже побудована необхідна послідовність перестановок U. Тоді з елементів {1,2, ..., n} необхідна послідовність може бути побудована переміщеннями елемента n між початковою і кінцевою позиціями кожної перестановки U. при цьому переміщення повинні проводитися по черзі вперед і назад (n1)! раз так, як це показано на рис. 13.8.

Рекурсивна програма-функція permut5 (n) реалізує цей, схематично описаний, алгоритм. На рис. 13.8 наведені отримані по permut5 (n) перестановки для n = 3 і n = 4.

Мал. 13.8. Генерування перестановок c транспозицией сусідніх елементів

На закінчення автор висловлює вдячність професорам. Ваграменко Я.А. і Добровольскому Н.М. за консультації і поради при написанні посібника.

література

1. Кнут Д. Мистецтво програмування для ЕBM. Основні алгоритми: т. 1, M .: Світ, 1976.

2. Кнут Д. Мистецтво програмування для ЕBM. Получісленние алгоритми: т. 2, М .: Мир, 1977.

3. Кнут Д. Мистецтво програмування для ЕBM. Сортування і пошук: т. 3, М .: Мир, 1978.

4. Лекції лауреатів премії Тьюрінга. М .: Мир, 1985.

5. Бауер Ф.Л., Гнац Р., Хілл У. Інформатика. Завдання і рішення. М .: Світ, 1978 г.

6. Бауер Ф.Л., Гооз Г. Інформатика. T. 1, М .: Мир, 1990 г.

7. Бауер Ф.Л., Гооз Г. Інформатика. T. 2, М .: Мир, 1990 г.

8. Ландау Е. Основи аналізу. М .: изд. Іноземної літератури, 1947.

9. http://www-cs-staff.stanford.edu/~knuth/taocp.html#vol4-{volume4}).

c).

Ось один з можливих варіантів визначення функції hanoi ():

Функція повертає матрицю розміру k2, в кожному рядку якої фіксується переміщення одного диска (звідки, куди). Величина k дорівнює загальній кількості переміщень.

Контрольний приклад. При трьох дисках з іменами шпилів 1, 2 і 3 отримуємо наступне рішення:

3.11 Екзотичні середні

Тепер вирішимо завдання, пов'язану з екзотичними середніми. Розглянемо два позитивних числа а 0 і b 0 і складемо їх середнє арифметичне і середнє геометричне. Продовжимо цей процес і, якщо числа a n і b n вже побудовані, то визначимо a n +1 і b n +1 наступним чином:

(3)

Відомо, що послідовності {a n} і {b n} прагнуть до загального межі і, слідуючи Гауса, його називають середнім арифметико-геометричним вихідних чисел а 0 і b 0.

Завдання 12. Скласти рекурсивну програму-функцію, по якій для невід'ємних чисел a і b можна було б наближено обчислювати їх арифметико-геометричне середнє.

Рішення. Параметрами завдання природно вважати вихідні величини a, b і кількість ітерацій n за формулами (3). Рекурсію організуємо по n, a рішенням завдання будемо вважати матрицю (a n, b n). Побудувати відповідну функцію нескладно і виглядати вона може, наприклад, т

Контрольні приклади.

age (100,30,3) = [59.77675556213139 59.77665550389991],

age (100,30,5) = [59.77670553300519 59.77670553300519].

Знову вирушаючи від двох позитивних чисел а 0 і b 0 станемо послідовно складати середні арифметичні і середні гармонічні:

(4)

Відомо, що послідовності {a n} і {b n}, що будуються за рекурентним формулами (4), прагнуть до загального межі. Його називають середнім арифметико-гармонійним вихідних чисел а 0 і b 0. Виявляється, що середнє арифметико-гармонійне двох чисел збігається з їх середнім геометричним.

Завдання 13. Скласти рекурсивну програму-функцію, по якій для невід'ємних чисел a і b можна було б наближено обчислювати їх арифметико-гармонійне середнє, тобто наближене значення

Рішення. Як і в попередньому випадку, параметрами завдання природно вважати вихідні величини a, b і кількість ітерацій n за формулами (4). Рекурсію організуємо по n, a рішенням завдання будемо вважати матрицю (a n, b n). Відповідна функція може виглядати так:

Контрольний приклад.

aga (100,20,7) = [44.7213595499958 44.7213595499958],

3.12 Ітерація функції в точці

Завдання 14. Скласти програму для знаходження n-ой ітерації (n = 0, 1, 2, ...) функції F (x) в точці a.

Рішення. Відповідно до умов завдання програма повинна обчислювати значення виразу виду F (F (F ... F (a) ...)) при n-кратному використанні операції F. Функція iter (F, a, n) вирішує поставлене завдання.

Контрольний приклад.

3.13 Речовий корінь f (x)

Завдання 15. Нехай функція f (x) дійсної змінної x неперервна на відрізку [a, b] і f (a) f (b) 0. Скласти програму знаходження на [a, b] будь-якого речового кореня f (x).

Рішення. По-перше, при перерахованих вище умовах принаймні один корінь f (x) на [a, b] існує. По-друге, домовимося про те, як розуміти слова "знайти корінь"? Будемо вважати, що корінь шукається з точністю> 0, тобто повинен бути знайдений відрізок [,] (- <2), на якому корінь є. Тоді як наближене значення кореня може бути взята точка x 0 = (+) / 2.

Для відшукання вирішення багатьох завдань часто використовується метод дихотомії, званий також методом послідовного розподілу навпіл, бисекции або вилки. У деяких раніше розглянутих задачах ми вже стикалися з цим методом. У нашому випадку, коли шукається корінь рівняння, суть його в наступному. Нехай> 0 задано. Ділимо відрізок [a, b] точкою з = (b + a) / 2 на дві рівні частини і в якості нового відрізка [a, b] беремо ту з його половин, для якої знову f (a) f (b) 0 і т.д. Ясно, що на певному етапі матимемо відрізок [a, b] такий, що b - a <2 і f (a) f (b) 0. Отже, наближене рішення знайдено і воно дорівнює (b + a) / 2.

А як записати запропонований алгоритм з використанням рекурсії? Виявляється все досить просто.

Контрольні приклади.

1. y (x): = x 3 dicho (y, -1, 1, 0.01) = -0.008

2. f (u) = u (u + sin (u) - 3) exp (cos (u))

dicho (f, 1, 3, 0.0001) = 2.18f (2.18) = 0

Завдання 16. Нехай функція f (x) дійсної змінної x неперервна на відрізку [a, b]. Скласти програму знаходження на [a, b] будь-якого дійсного кореня f (x). При відсутності коренів, має бути видано значення (10 307).

Рішення. Відмінність постановки цього завдання від попередньої в тому, що тут апріорі нічого невідомо про знаках функції на кінцях відрізка і, отже, коренів f (x) вже може і не бути. Однак метод дихотомії з успіхом може бути застосований і в даному випадку. Відповідний алгоритм може бути записаний так.

Контрольні приклади.

Розглянемо функції прикладів з попередньої задачі. маємо:

dichot (y, 1,7,0.001) = 10 307, dichot (f, 2.17,3,0.0001) = 2.18.

періодичне продовження

Завдання 17. Скласти програму, яка для функції g (x), визначеної при x [a, b), будує функцію peri (g, a, b, x), що є періодичним продовженням g (x) на всю дійсну вісь c періодом = b - a.

Рішення. Нам, очевидно, потрібно визначити функцію такого вигляду.

Мовою Mathcad це буде виглядати практично так само:

Зауважимо, що при x знаходиться далеко від проміжку [a, b) обчислення значення функції peri () вимагає значної кількості рекурсивних викликів. Відбувається це з тієї причини, що за один такий виклик ми просуваємося в напрямку [a, b) лише на відстань = ba.

Значно ефективніше проводяться обчислення по функції F (g, x, a, b) також є періодичним продовженням g (x) на всю числову вісь.

Контрольні приклади.

1. Нехай y (x) = x 2 sin (x). тоді:

peri (y, 1,0,2) = 0.841 peri (y, 3,0,2) = 0.841

peri (y, 1,0,2) = 0.841 peri (y, 1001,0,2) = 0.841

2. На рис. 3.4 зображено графік функції H (t), що є періодичним продовженням функції y (x) = x 2 sin (x) для x [10, 0). H (t) побудовано за допомогою програми-функції F (), а графік виведений на проміжку [10,20) з кроком h = 0.1.

t: = 10,9.9..20 H (t): = perri (y, t, 10,0)

Мал. 3.4 Періодичне продовження функції y (x) = x 2 sin (x)

для x [-10, 0).

3.14 Функція Аккермана

Завдання 18. Нехай n і m цілі невід'ємні числа. Написати програму, яка обчислює класичну в теорії рекурсії функцію Аккермана:

(5)

Рішення.Обчислити функцію Аккермана, виходячи безпосередньо з визначення (5), вдається лише для деяких малих n і m. Пов'язано це зі складністю і незвичністю рекурсивного визначення. У загальному випадку не тільки ak () обчислюється через ak (), але і другий з аргументів функції також вимагає рекурсивного виклику ak (). Відповідна програма-функція може бути записана так:

Контрольні приклади.

Наступний варіант програми для обчислення функції Аккермана включає в себе лише один рекурсивний виклик:

Зауваження. Для m = 0..4 справедливі співвідношення [5, с. 69]:

Ці формули можуть виявитися корисними при побудові контрольних прикладів для налагодження нових більш ефективних варіантів програм обчислення функції Аккермана.

В роботі [5, c. 256260] наведено нерекурсивний варіант алгоритму обчислення значень функції Аккермана.

3.15 Функція Маккарті

Завдання 19. Функція Маккарті. Показати, що для наведеної нижче рекурсивної програми-функції

при цілочисельних значеннях n справедлива формула:

(6)

Рішення. Щодо параметра n можливі три випадки:

n> 100,90 n 100, -

У першому з них в силу бази рекурсії слід, що makkarti (n) = n10. У другому випадку:

Нарешті, будь-яке початкове n <90 відповідно до декомпозицией через кінцеве число рекурсивних викликів призводить до другого випадку. Звідси знову makkarti (n) = 91. Таким чином (6) справедливо у всіх випадках.

Зауважимо, що з проведених міркувань випливає, що розглянута функція може бути визначена більш просто, наприклад, так:

3.16 Функція Кадью

Завдання 20. Показати, що для наведеної нижче рекурсивної програми-функції

при цілочисельних значеннях x справедлива формула:

(7)

Рішення. При y = 0 і z = 1 маємо z = y !. Далі з характеру декомпозиції функції cadiou () ясно, що z = y! залишається інваріантом в ході рекурсивних викликів. Разом з умовою завершення x = y це і дає z = x! і (7) встановлено.

3.17 Кількість дільників

Завдання 21. Кількість дільників. Скласти програму-функцію підрахунку для натурального числа n кількості всіх його подільників.

Рішення. Перейдемо до більш загальної задачі. Підрахуємо для натурального числа n кількості всіх його подільників, менших або рівних заданим натуральним числом x. Нехай dn (n) і dnx (n, x) відповідно функції для вирішення вихідної і узагальненої завдань. Очевидно, що dn (n) = dnx (n, n).

Рекурсивну функцію dnx (n, x), по якій послідовно піддаються випробуванню на подільники n все числа від 1 до x включно, можна визначити так:

Контрольні приклади.

Далі, якщо n 2 і dn (n) = 2, то число n - просте. Однак перевірка n на простоту цим способом дуже неекономна.

3.18 Прості числа

Завдання 22. Скласти програму-функцію перевіряє, чи є задане натурально число n простим?

Рішення. Нехай рекурсивна функція isprim (n) є рішенням задачі і

Подальші міркування є ілюстрацією використання класичного прийому "вкладення" (Дж. Маккарті, 1962). Перейдемо до розгляду наступної узагальненої задачі. Нехай a, b, n натуральні числа і 2abn. Чи вірно, що заданий n не ділиться ні на одне ціле з відрізка [a, b]? Нехай це завдання вирішує функція

Нижче наведено три рекурсивних варіанти реалізації цієї функції. По першому з них перевірці на дільник n послідовно піддаються числа: a, a + 1, ..., b; по другому ці ж числа в зворотному порядку і, нарешті, по третьому a, b, a + 1, b1, ....

Контрольні приклади.

Далі, натуральне число n2 є простим, якщо воно не має дільників на відрізку, тому характеристична функція isprim (n) через функцію nodiv (n, a, b) може бути виражена так:

Контрольні приклади.

Завдання 23. Скласти програму-функцію pi (x), яка підраховує кількість простих чисел, що не перевершують задане число x.

Рішення. За допомогою функцій nodiv () або isprim () рекурсивний варіант функції pi (x) будується досить просто, виходячи з такого декомпозіціонного затвердження. Кількість простих чисел, що не перевершують x, складається з кількості простих чисел менших або рівних x1 плюс значення функції isprim (x). Тому:

Контрольні приклади.

Завдання 24. Скласти програму pn (n), яка обчислює n-е просте число (n - натуральне).

Рішення. Попередньо напишемо рекурсивну підпрограму-функ-цію minp (m) знаходження найменшого простого числа, більшого або рівного m (m - натуральне число). Зробити це можна, наприклад, так:

Контрольні приклади.

Тоді шукана функція pn (n) може бути визначена так:

Контрольні приклади.

3.19 Схема Горнера

Завдання 25. Скласти програму-функцію обчислення значень многочлена за схемою Горнера.

Рішення. Нехай f (x) багаточлен з речовими або комплексними коефіцієнтами і v - вектор цих коефіцієнтів:

(8)

(9)

Обчислення f (x) в точці x за схемою Горнера проводиться від самих внутрішніх дужок і далі відповідно до подання:

Звідси ясно, як записати рекурсивний і не рекурсивний варіанти алгоритмів обчислення f (x). Нас цікавить тільки перший з них. Параметрами завдання можна вважати вектор v і точку a для обчислення f (a). Тривіальний випадок - многочлен нульової ступеня: f (a) = a 0. Декомпозиція виходить із зазначеної вище розстановки дужок у записі f (x). Відповідна програма-функція виглядає, наприклад, так.

Контрольні приклади.

Зауваження. Параметр n - це константа, рівна ступеня многочлена. За вектору v вона визначається однозначно. Однак в кожному рекурсивном виклик проводиться переобчислення n. Уникнути зайвої обчислювальної роботи в подібних ситуаціях можна двома способами. Або визначати такі константи заздалегідь поза текстом програми-функції або передавати їх значення через додаткові аргументи функції.

3.20 Розподіл многочлена на двочлен

Завдання 26. Скласти програму-функцію, по якій для многочлена (8) з коефіцієнтами, складовими вектор (9) і двочлена xx 0 (x 0 речовий або комплексне число), обчислюється вектор c:

такий, що

і

Рішення. Якщо в співвідношенні, що зв'язує многочлени f (x) і q (x), здійснити приведення до спільного знаменника і прирівнювання коефіцієнтів при однакових ступенях x, то для визначення компонент вектора c отримаємо наступну систему лінійних рівнянь.

Звідси випливає, що c = qu (v, x 0), де рекурсивне визначення функції qu () може виглядати, наприклад, так.

Контрольний приклад.

Іншими словами:

3.21 Твір двох многочленів

Завдання 27. Нехай коефіцієнти многочленів f n (x) і g m (x) задані компонентами векторів v і w:

(10)

(11)

Скласти рекурсивну програму-функцію обчислює коефіцієнти многочлена h n + m (x) = f n (x) g m (x) і повертає їх у вигляді компонентів вектора:

Рішення. оскільки

де

то цілком можна організувати рекурсию по параметру m ступеня другого співмножники. І як рішення може бути запропонована наступна функція:

Ясно, що аналогічно можна було б реалізувати рекурсію і по параметру n ступеня першого співмножники. У будь-якому випадку величини m і n визначають кількість рекурсивних звернень. Тому в даній задачі рекурсию вигідно реалізовувати по параметру зі значенням, рівним min (n, m).

Контрольний приклад.

3.22 Твір биномом

Завдання 28. Скласти програму-функцію повертає коефіцієнти многочлена g (x), який виходить в результаті перемноження биномом (xv k): (k = 0,1, ... n1; n1):

Рішення. Будемо вважати, що вільні члени биномом задані у вигляді компонентів деякого вектора v: а результат обчислень повинен повертатися також у вигляді вектора. оскільки

то нескладно організувати рекурсию за кількістю перемножуєте биномом. Відповідна програма функція могла б виглядати так:

Контрольний приклад.

3.23 Розподіл многочлена на многочлен

Завдання 29. Нехай виконані співвідношення (10) (11), тобто многочлени f n (x) і g m (x) ступенів n і m (n, m0) відповідно задані своїми коефіцієнтами у вигляді компонентів векторів v і w. Нехай, далі, при m = 0, тобто якщо g m (x) є константа, g m (x) 0. Скласти програму-функцію знаходження приватного q (x) і залишку r (x) при розподілі f n (x) на g m (x):

f n (x) = q (x) g m (x) + r (x), (12)

де ступінь r (x) менше m (при m = 0 r (x) 0).

Рішення. Подання (12) єдино. Надалі нам зручно вважати, що ступінь r (x) дорівнює m1 з можливо нульовими коефіцієнтами при старших ступенях x.

При m = 0 рішення задачі очевидно:

q (x) = f n (x) / w 0, r (x) = 0. (13)

Далі, при n <= m маємо

(14)

Нехай n> m і q 1 (x) і r 1 (x) приватне і залишок від ділення (f n (x) a n -1) / x на g m (x):

З цього співвідношення випливає, що

Разом з (12) це дає:

(15)

Якщо співвідношення (13) (14) розглядати в якості бази рекурсії, то рівності (15) визначають декомпозицію. Вважаємо, що в результаті обчислень повинен бути сформований і повернутий складовою вектор qr = [qr] T, де q і r відповідно вектори коефіцієнтів многочленів q (x) і r (x). Відповідна програма-функція, що реалізує ці ідеї, виглядає так:

Контрольні приклади.

Зауваження. Функція poldiv () повертає складовою вектор [qr] T, в якому другий компонент-вектор r може містити "провідні" нулі. При необхідності ці нулі можна погасити, тобто виділити з r підвектора, що починається з першого з ненульових компонент r. Зробити це можна, наприклад, за допомогою наведеної нижче рекурсивної функції nulera (u). Якщо всі компоненти u дорівнюють нулю, то nulera (u) повертає 0.

3.24 Розбиття цілого на частини

Завдання 30. Скласти програму-функцію підрахунку кількості (m) розбиття натурального числа m, тобто його уявлення у вигляді суми натуральних чисел.

Рішення. Нехай, наприклад, m = 6. Тоді розбивками m є його уявлення у вигляді:

6;

5 + 1;

4 + 2, 4 + 1 + 1;

3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1;

2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1;

1 + 1 + 1 + 1 + 1 + 1;

Таким чином, (m) = 11 і зрозуміло, що простим перебором можливих випадків вже при m> 10 впоратися із завданням досить складно.

Для вирішення вихідної задачі перейдемо до розгляду узагальненої задачі. Скласти програму-функцію підрахунку кількості P (m, n) розбиття натурального числа m з складовими, які не переважаючими n. Ясно, що (m) = P (m, m). Тому, досить навчитися обчислювати значення функції P (m, n). Але для неї неважко виділити рекурсивную базу і вказати правило декомпозиції. Зробити це можна виходячи з таких цілком прозорих властивостей цієї функції.

1. P (m, 1) = 1 існує тільки одне розбиття m, в якому складові не перевищують одиниці, а саме: m = 1 + 1 + ... + 1.

2. P (1, n) = 1 число одиниця має тільки одне подання при будь-якому n.

3. P (m, n) = P (m, m) при n> m складові, великі m в розбитті відсутні.

4. P (m, m) = P (m, m1) +1 існує лише одне розбиття зі складовою рівним m. Всі інші розбиття мають складові не перевищують m1.

5. P (m, n) = P (m, n1) + P (mn, n) (n

Перші дві властивості визначають базу рекурсії, а три наступні задають декомпозицію. Строго відповідно до цими твердженнями і складена рекурсивна програма-функція deco (n, m) для обчислення величини P (m, n).

Контрольні приклади.

3.25 Максимальний і мінімальний елементи

Нехай одновимірний масив заданий вектором Часто виникає завдання пошуку максимального (мінімального) елемента v. Незалежно від того, чи йде мова про знаходження максимального за значенням елемента або його позиції в v, пошук можна реалізувати за один перегляд масиву. Правда в останньому випадку рішення може виявитися неоднозначними і постановка задачі вимагає уточнення. Наприклад, відшукується позиція максимального елемента з найменшим індексом. У будь-якому випадку порівняння характеристик різних алгоритмів пошуку проводять за кількістю тих чи інших виконуваних ними операцій. Найчастіше це операції порівняння.

Рекурсивна функція maxv (v) знаходить максимальний елемент v рівно за n1 операцію порівняння. Декомпозиція реалізується по довжині вектора і спирається на таке твердження. Вирішити вихідну задачу для v це те ж саме, що розв'язати цю проблему для підвектора, одержуваного з v видаленням його першого компонента, порівняти отримане значення з віддаленим елементом і, нарешті, вибрати не менше з них.

Контрольні приклади.

Зауваження. При підрахунку кількості операцій порівняння елементів масиву не враховуються порівняння з керуючими змінними рекурсії або циклу. Це ж саме стосується і інших програм, наведених нижче.

Аналогічно будується і функція minv (v) знаходження за n1 операцію порівняння мінімального за значенням елемента масиву. Неважко написати рекурсивну функцію одночасного пошуку мінімального і максимального значень v за 2n2 операції порівняння. Виглядати вона може, наприклад, так:

Контрольні приклади.

Однак одночасне перебування максимального і мінімального значень v може бути реалізовано набагато ефективніше. Відповідний результат зафіксований в наступної задачі.

Завдання 31. Написати рекурсивну програму-функцію, яка знаходить одночасно максимальний і мінімальний елементи масиву v за операцій порівняння.

Рішення. Якщо довжина вектора v дорівнює одиниці, то рішенням завдання можна вважати вектор При довжині вектора v, що дорівнює двом, рішення знаходиться за одне порівняння. Нехай довжина вектора більше двох. Тоді з двох перших компонентів безпосередньо знайдемо найбільше та найменше (одне порівняння), вирішимо вихідну задачу для підвектора, що виходить з v видаленням цих компонентів і, нарешті, здійснимо правку отриманого рішення для підвектора за рахунок перших двох компонентів (два порівняння). Саме ці ідеї і реалізуються рекурсивної функцією minmax ():

Контрольний приклад.

Підрахуємо тепер S загальна кількість порівнянь:

Тим самим рішення задачі завершено повністю.

У наступному варіанті minmax () функції minmax1 () використовуються три допоміжних параметра: a, b, i. Перші два з них служать для фіксації поточних значень мінімального і максимального елементів масиву, а останній для нумерації рекурсивних звернень. Як і в попередньому випадку, кожен рекурсивний виклик зменшує опрацьований масив на два елементи. Але тут, на відміну від minmax (), вони видаляються з різних його кінців. Використання допоміжної функції mima (v) позбавляє нас від складного звернення до minmax1 ().

Контрольний приклад.

Завдання 32. Написати рекурсивну програму-функцію, яка знаходить одночасно позиції максимального і мінімального елементів масиву v за операцій порівняння.

Рішення. Для вирішення даного завдання можна використовувати той же самий алгоритм, який реалізується функцією minmax1 (), піддаючи запам'ятовування не поточні значення мінімального і максимального елементів масиву, а їх індекси. Відповідні функції posmima () і pmima () можна записати так:

Контрольний приклад.

Зауваження. Рекурсивна функція posmima () дозволяє реалізувати сортування масиву v за таким алгоритмом:

Контрольні приклади.

3.26 Абракадабра

Завдання 33. Послідовність з латинських букв будується наступним чином. На нульовому етапі вона порожня. На кожному наступному кроці послідовність подвоюється, тобто приписується сама до себе, і до неї зліва додається наступна потрібна літера алфавіту (a, b, c, ...). По заданому числу n визначити символ, який стоїть на n-му місці послідовності, отриманої після кроку 26.

Рішення. Це завдання пропонувалася учасникам обласних турів Всеукраїнської олімпіади школярів з інформатики в 1998 році. Наведемо перші кроки формування послідовності: 0 порожня послідовність, 1 a, 2 baa, 3 cbaabaa, 4 dcbaabaacbaabaa, .... Ми маємо явно рекурсивний процес.

Побудуємо більш загальну програму-функцію, ніж це потрібно за умовами задачі. Нехай abra (k, n) n-ая буква в послідовності, отриманої на кроці k (k = 1..26). Тоді ясно, що abra (k, 1) одно k-ой букві латинського алфавіту. Цей факт можна взяти в якості бази рекурсії, а функцію для визначення цієї літери записати так:

Декомпозицію зручно організувати по k, проводячи "розкрутку" послідовності по кроках в зворотному напрямку. Це призводить до наступної функції:

Контрольні приклади.

3.27 Вкладені багатокутники

Завдання 34. Вкладені квадрати. Нехай на площині перший квадрат заданий точками: M 1 (-1, -1), M 2 (-1,1), M 3 (1,1), M 4 (1, -1). Другий квадрат будується так, що вершини першого квадрата є центрами його сторін і т.д. Скласти рекурсивну програму-функцію, яка по заданому натуральному n будує систему з 2n вкладених один в одного описаним чином квадратів, точніше створює масив точок, послідовне з'єднання яких на площині відрізками і формує цю систему (див. Рис. 3.5).

Рішення. Якщо врахувати той факт, що за умовою задачі завжди будується парне число вкладених квадратів, то послідовність точок для побудови перших двох з них можна задати безпосередньо і вважати відповідну матрицю beg базою рекурсії:

Зверніть увагу, що в beg кожен з квадратів задається не чотирма, а п'ятьма точками. При цьому перша і остання з них збігаються. Це допоможе згодом правильної промальовування квадратів.

Далі, декомпозиція визначається таким твердженням. Якщо вже побудована матриця ma точок для 2 (n1) вкладених квадратів, то, поповнивши її точками матриці, отримаємо матрицю точок для 2n таких квадратів. Відповідна рекурсивна функція, що базується на цих фактах, може виглядати так:

Контрольний приклад. Результат обчислень представлений на рис. 3.5 c неоднаковим масштабом по осях.

Мал. 3.5. Вкладені 2n квадратів (n = 4)

Завдання 35. Вкладені багатокутники. Нехай на площині заданий правильний n-кутник, вписаний в одиничну окружність одна з вершин якого має координати (cos (), sin ()), де деякий кут. Другий правильний n-кутник будується так, що його вершини є центрами сторін першого багатокутника і т.д. Скласти рекурсивну програму-функцію, яка по заданому натуральному n будує систему з n вкладених один в одного описаним чином багатокутників, точніше створює масив точок, послідовне з'єднання яких на площині відрізками і формує цю систему (див. Рис. 3.6).

Рішення. Це завдання в якомусь сенсі є узагальненням попередньої. Тут виводяться правильні вписані n-косинці, кількість їх не обов'язково парне і перша з вершин початкового n-кутника може лежати в будь-якій точці одиничному колі. Правда, тут багатокутники не «описуються" один навколо іншого, а "вписуються" один в одного. Але суті справи це не змінює.

Перш за все, складемо програму, яка формує масив вершин правильного n-кутника, вписаного в коло радіуса r і містить вершину (rcos () rsin ()). Зробити це можна, наприклад, так:

Тоді масив polyone (n, 1,) може служити базою рекурсії. Більш того, ця функція при правильному виборі r і дозволяє отримати масив вершин будь-якого з наступних вписаних n-кутників, що допомагає організувати і декомпозицію. Якщо вже побудована матриця ma точок для (n1) -го вписаного правильного n-кутника, то, поповнивши її точками матриці:

отримаємо матрицю точок для 2n таких багатокутників. Відповідна рекурсивна функція, що реалізує ці ідеї, може виглядати так:

Контрольний приклад. Результат обчислень представлений на рис. 3.6 c неоднаковим масштабом по осях.

Мал. 3.6. k вкладених правильних n-кутників (k = 20, n = 6)

Кілька слів перед формулюванням нового завдання.В основах аналізу [8, с. +1738] операції додавання і множення над натуральними числами визначаються рекурсивним способом, спираючись на аксіоми Пеано "про існування наступного числа" і "індукції". Перша з названих аксіом звучить так: "для кожного натурального x є до того ж лише одне натуральне число, зване його наступним і позначається число x". Постараємося промоделювати зазначені вище і деякі інші операції.

Моделювання арифметичних операцій

Завдання 36. Для цілих невід'ємних чисел n, m дозволені операції:

знаходження наступного числа (n + 1) і попереднього числа n1 (n> 0). Промоделювати за допомогою рекурсивних функцій операції знаходження суми (n + m), різниці (nm (nm)), множення (nm), зведення в ступінь n m (n> 0), приватного і залишку при діленні n на m (n / m ).

Рішення.

A. Сума: a + b. очевидне співвідношення

задає одночасно і базу рекурсії і правило декомпозиції. По ньому і побудована наступна рекурсивна програма-функція:

Контрольний приклад:

B. Різниця: ab (ab). В даному випадку база рекурсії і декомпозиція можуть бути вилучені зі співвідношення:

Відповідна рекурсивна програма-функція виглядає так.

Контрольний приклад:

C. Множення: ab. Будемо вважати, що операція додавання вже визначена. Тоді співвідношення, з якого легко витягуються база і декомпозиція для даного випадку виглядає наступним чином:

Відповідна рекурсивна програма-функція може бути записана, наприклад, так:

Контрольний приклад:

D. Піднесення до степеня: a b (a0). Будемо вважати, що операція множення вже визначена. тоді:

і рекурсивна програма-функція зведення в ступінь може бути задана так:

Контрольний приклад:

E. Приватне і залишок: a / b (b> 0). У цьому завданню йдеться про відшукання величин q і r з вистави: a = qb + r (0r T. якщо a a, то a / b = 1 + (ab) / b, що дозволяє організувати декомпозицію. Все сказане враховано в рекурсивної функції divi (q, a, b). У ній перший аргумент q є допоміжним параметром. При зверненнях до divi () він повинен визначати базове значення приватного, тобто дорівнювати нулю. Однак простіше вирішувати завдання за допомогою допоміжної функції div (a, b), покладаючи на неї вирішення питання про правильне значенні допоміжного параметра виклики divi (). Це досить типовий випадок при узагальненнях вихідної задачі за рахунок введення додаткових параметрів.

Контрольний приклад.

Зауваження. Моделювання різних операцій можливо не тільки для цілих невід'ємних чисел. Їх можна було б визначити і для безлічі всіх цілих чисел і навіть для безлічі дійсних чисел. Обмежимося розглядом одного прикладу. Напишемо рекурсивну програму-функцію знаходження дробової частини дійсного числа, якщо дозволені лише операції x + 1 і x1. Ось один з можливих досить ясних варіантів її визначення:

Контрольний приклад.

Синтаксичні мовні конструкції

Завдання 37. Скласти програму-функцію перевіряє, чи є дана послідовність символів ідентифікатором мови Фортран.

Рішення. Будемо вважати, що мова йде про версії Фортрана, де ідентифікатор визначався як послідовність з шести великих латинських букв і (або) цифр, що починається з букви і для символів була прийнята ASCII кодування. Перетворити послідовність символів в вектор відповідних їм ASCII-кодів можна за допомогою вбудованої функції str2vec (). наприклад:

Додаткове обмеження на перший символ ідентифікатора (буква, але не цифра) ускладнює загальну перевірку (або буква, або цифра). Щоб дії були стандартними для всіх символів, перевірку першого з них будемо здійснювати на допустимість окремо в головний програмою. Природно там же розташовувати і перевірку довжини слова, яка повинна знаходитися в межах від 1 до 6. Тоді в підпрограмі залишиться вирішити цілком рекурсивную підзадачу: "якщо перший символ вихідного слова не буква і не цифра, то формуємо відповідь« не ідентифікатор ". В іншому випадку, якщо довжина слова дорівнює одиниці, то повертаємо відповідь "ідентифікатор", а інакше укорочуємо слово на перший символ і знову вирішуємо цю ж підзадачу. Все сказане і реалізується головний програмою identity (word) і рекурсивної підпрограмою iden (v):

Контрольні приклади.

Зауваження. У будь-якій мові програмування все базові мовні конструкції (ідентифікатори, константи, змінні, вирази, мітки, типи і т.п.) визначаються рекурсивно. Особливо наочно це видно, коли вони представлені за допомогою синтаксичних діаграм [7, c. 685703] або у формі Бекуса-Наура. Подібні визначення в рамках конкретного мови програмування можуть служити наборами тренувальних завдань з написання рекурсивних програм і навіть найпростіших рекурсивних трансляторів.

Наведемо приклад. Ідентифікатор в Паскалі визначається, як і в Фортране, але без обмежень на довжину послідовності символів. За допомогою синтаксичної діаграми це виглядає так, як це вказано на рис.3.7., А в формі Бекуса-Наура наступним чином (значок ":: =" читається як "є за визначенням"):

ідентифікатор :: = буква

ідентифікатор :: = ідентіфікаторбуква

ідентифікатор :: = ідентіфікаторціфра

Мал. 3.7. Синтаксична діаграма ідентифікатора (Паскаль)

І в тому і в іншому випадках ідентифікатор визначається сам через себе.

3.28 Проблемна ситуація

Завдання 38. При будь-якому чи натуральному n чи рекурсивна функція

дорівнює 1?

Рішення. Хоча дана рядок і розпочато зі слова "рішення", відповіді на поставлене запитання ми не знаємо і, мабуть, на сьогоднішній день його не знає ніхто. Більш того, невідомо, для будь-якого чи n problem (n) обчислюється за кінцеве число кроків. Розглянуту задачу називають 3n + 1 проблемою. Ми включили її в список завдань для того, щоб звернути увагу читача на наступний факт. Досить прості на вигляд рекурсивні визначення функцій можуть таїти в собі глибокі проблеми, вирішення яких лежать зовсім не на поверхні. Проте, конкретні обчислення problem (n) при різних n призводять до одного і того ж значення, рівному 1. Нижче наведена рекурсивна програма для перевірки істинності твердження "problem (n) = 1" при значеннях n з діапазону k1..k2.

Контрольні приклади.

6. Завдання Йосипа Флавія

З ім'ям відомого історика першого століття Йосипа Флавія пов'язують таку задачу-легенду. В ході іудейської війни він у складі загону з 41 воїна був загнаний римлянами в печеру. Аби не допустити здаватися, обложені воїни вирішили покінчити життя самогубством і розробили для цього наступну процедуру. Вони вишикувалися в коло і, починаючи відлік з конкретної позиції, кожен третій мав вбивати себе, поки не залишиться жодної людини. Математично обдарований Йосип вважав подібний кінець безглуздим і тому поставив себе і свого друга на такі позиції, що після серії з 39 самогубств вони залишилися вдвох, ніж та врятували собі життя. Що це були за позиції?

Дамо цьому завданні-легендою точнішу і узагальнене формулювання, звільнившись від суїциду. При цьому будемо шукати рекурсивні рішення двох нижче наведених завдань, що розрізняються завершенням відповідної процедури. Детальніше рекурсія як метод вирішення практичних завдань обговорюється в наступному параграфі.

Завдання 1. По колу в напрямку руху годинникової стрілки розташовані n послідовних натуральних чисел від 1 до n. При переміщенні по числам 1, 2, ... кожне k-е число (k> 1) викреслюється (видаляється). Цей процес триває до тих пір, поки чисел не стане менше k. Визначити залишилися числа.

Завдання 2. По колу в напрямку руху годинникової стрілки розташовані n послідовних натуральних чисел від 1 до n. При переміщенні по числам 1, 2, ... кожне k-е число (k> 1) викреслюється (видаляється). Цей процес триває до тих пір, поки не залишиться одне число. Визначити його.

A. Рішення першого завдання Флавія при k = 2.

Нижче розглянуті три варіанти A1A3 рішення задачі 1 при k = 2, що спираються на різні ідеї.

A1. Якщо n = 2s, то після першого проходу по колу залишаться числа: 1, 3, ... 2s1 і наступний прохід почнеться з викреслювання числа 3. Це все одно, як якщо б ми починали з s послідовних натуральних чисел від 1 до s, але кожне врятоване число подвоювали і результат зменшували на 1. звідси, якщо fla1 (n) функція, яка вирішує поставлену задачу, то fla1 (1) = 1 і

fla1 (2s) = 2fla1 (s) 1 (s1). (16)

Аналогічні міркування показують, що

fla1 (2s + 1) = 2fla1 (s) + 1 (s1). (17)

Величини fla1 (n) назвемо числами Флавія. Співвідношення (16) і (17) відразу ж дозволяють написати наступну рекурсивну програму-функцію обчислення значень fla1 (n).

A2. Дослідження зворотних співвідношень (16) (17) показує, що

fla1 (2 s + q) = 2q + 1 (s0, 0q <2s) (18)

Звідси отримуємо ще один рекурсивний алгоритм для обчислення чисел Флавія (див. Нижче). При цьому допоміжна рекурсивна функція power (n, 0) обчислює значення s, яке задовольняє співвідношенню (18), тобто зменшене на 1 кількість цифр двійкового розкладу n, а функція fla2 (n) безпосередньо обчислює число Флавія для заданого n.

A3. Ще один спосіб знаходження чисел Флавія дається програмою-функцією flavec (v), де v = (1 2 3 ... n) T вектор. Подавати такий вектор в якості аргументу необов'язково. Простіше звертатися до flavec (v) c допомогою функції fla3 (n), де по заданому n генерується відповідний вектор v. Відзначимо, що в flavec (v) використовується рекурсивний алгоритм безпосереднього викреслювання кожного другого числа. При цьому вектор v перебудовується при кожному новому русі по колу.

Контрольні приклади.

1. fla1 (6) = 5fla2 (6) = 5fla3 (6) = 5

2. fla1 (11) = 7 fla2 (11) = 7 fla3 (11) = 7

3. fla1 (1000) = 997fla2 (1000) = 997fla3 (1000) = 997

B. Рішення першого завдання Флавія в загальному випадку.

Нижче розглянуті два варіанти B1B2 рішення задачі 1 в загальному випадку. Перший з них являє пряме узагальнення алгоритму з пункту A3 і реалізує рекурсію по кожному викреслити елементу. У другому варіанті рекурсія організована за окремими проходами по колу.

B1. Спосіб A3 рішення задачі 1 при k = 2 хоч і дещо громіздкий, але він досить просто переноситься на загальний випадок. При цьому природно вважати k аргументом функції.Тоді рішення задачі дає рекурсивна програма-функція flave (v, k), де v = (1 2 3 ... n) T вектор. Однак простіше використовувати для цих цілей функцію fla4 (n, k), яка формує по заданому цілому n необхідний вектор v, а потім вже обертається k flave (v, k).

B2. Наведений нижче спосіб вирішення першого завдання Флавія відрізняється від попереднього лише способом організації рекурсії. Тут вона реалізована не по кожному викреслити елементу, а по окремим проходах по колу. Рішення завдання дається програмою-функцією flavmek (v, k), де v = (1 2 3 ... n) T вектор. Однак простіше використовувати для цих цілей функцію fla5 (n, k), яка формує по заданому цілому n необхідний вектор v, а потім вже обертається до flavmek (v, k). Зверніть увагу на використовуваний в fla5 (n, k) метод формування вектора v.

Контрольні приклади.

1. fla4 (6,2) = 5 fla5 (6) = 5

2. fla4 (41,3) T = [16 31] fla5 (11) T = [16 31]

3. fla4 (1000,5) T = [563 763 802 73] fla5 (1000) T = [563 763 802 73]

С. Вирішення другого завдання Флавія в загальному випадку.

Нехай функція flav (v, k), де v = (1 2 ... n) T вирішує поставлене завдання і нехай w вектор, отриманий з v викреслюванням одного k-го компонента. Після кожної такої операції будемо організовувати рекурсивний виклик flav (w, k), припиняючи обчислення тоді, коли довжина вектора стане дорівнює одиниці. Нехай le - довжина вектора v і s = mod (k, le). Неважко бачити, що після одного викреслювання отримаємо:

w = (1 2 ... le1) T при s = 0,

w = (2 3 ... le) T при s = 1,

w = (s + 1, s + 2, ..., le, 1,2, ..., s1) при s> = 2.

Тому функцію flav (v, k) і обертається до неї функцію fla6 (n, k) можна визначити наступним чином:

Контрольні приклади.

fla6 (10,5) = 3 fla6 (5,10) = 4 fla6 (1000,7) = 404.

13.4 Системи числення

A. Переклад чисел з десяткової системи в p-ічную систему

Без обмеження спільності мову можна вести про невід'ємних чіслах.Пусть p {2,3, ...} і цифри p-ічной системи це послідовні десяткові числа: 0, 1, ... p1. Розглянемо 6 конкретних завдань. У трьох перших з них мова йде про переведення природним чином заданих десяткових чисел в p-ічную систему числення. У наступних трьох завданнях йдеться про переведення десяткових чисел, цифри яких задані у вигляді послідовних компонентів векторів, в p-ічную систему числення. У всіх випадках результат формується у вигляді вектора, компоненти якого p-ічние цифри вихідного числа.

Завдання 1. Скласти програму-функцію перекладу цілих невід'ємних десяткових чисел m в систему числення за основою p.

Рішення. Функція dec_p_i (m, p) вирішує поставлене завдання, використовуючи рекурсивний алгоритм послідовного розподілу. Результат формується у вигляді вектора, компоненти якого p-ічние цифри m.

Контрольні приклади.

.

Зауваження.

1. Якщо розряди p-ічного числа необхідно формувати не з старшого розряду, а від молодшого і далі, то в програмі dec_p_i () перший і другий аргументи функції stack () необхідно поміняти місцями.

2. При перекладі невід'ємних десяткових чисел в конкретну систему числення, в функції dec_p_i () досить мати один аргумент. Наприклад, переклад в двійкову систему можна здійснювати наступною програмою-функцією dec_b_i (m).

Контрольні приклади.

Як ми вже відзначали при реалізації функцій dec_p_i (m, p) і dec_b_i (m) використаний рекурсивний варіант алгоритму послідовного розподілу виділення цифр p-ічной системи для цілих чисел. Пояснень потребують лише фрагменти виду identity (1) x. Справа в тому, що функція stack () в якості своїх аргументів використовує вектори або матриці. І сенс записи identity (1) x полягає в перетворенні скаляра х в матрицю розміру 11 з елементом x.

Завдання 2. Скласти програму-функцію перекладу правильної неотрицательной десяткового дробу y в систему числення за основою p.

Рішення. Функція dec_p_f (y, p, k) вирішує поставлене завдання, використовуючи рекурсивний алгоритм послідовного множення. Результат формується у вигляді вектора з не більше ніж k (k = 1,2, ...) компонентами, які суть p-ічние цифри числа y, почавши з найстарших та розрядів і далі.

Контрольні приклади.

Завдання 3. Скласти програму-функцію перекладу невід'ємного дійсного десяткового числа a в систему числення за основою p (p = 2, 3, ...).