Функції на просторі послідовностей

Ще одним типовим випадком, в якому загальна схема ітерації значно спрощується, є задача обчислення індуктивних функцій. Такі функції визначені на послідовностях Х* елементів з деякого алфавіту X. Нагадаємо найважливіші з визначень.

Алфавіт X - довільна не порожня множина.
Символом алфавіту X називають будь-який його елемент, а ланцюжком над алфавітом - довільну послідовність символів ω.

Ланцюжки часто називають також словами, фразами і реченнями. Порожній ланцюжок позначається спеціальним символом , а множину всіх ланцюжків над алфавітом X прийнято позначати Х*.

Довжиною |ω| ланцюжка називається кількість вхідних у неї символів. Множину усіх ланцюжків довжини не менш k позначають через . Справедлива наступна послідовність включень:

 

Операція конкатенації (або зчеплення) двох ланцюжків визначена наступним чином. Нехай , , тоді .
Тепер можна дати визначення індуктивної функції.

 

Визначення 9.9. Функція називається індуктивною, якщо можна обчислити, знаючи і x, тобто якщо таке, що .

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

Для обчислення значення індуктивної функції f на ланцюжку застосовується наступна cхема.

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

На рисунку 9.4 наведена графічна ілюстрація схеми обчислення індуктивної функції.

Рис. 9.4. Схема обчислення індуктивної функції

 

 

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

Схема обчислення індуктивної функції дозволяє легко побудувати програму типу "S0; while (e) S;", яка одержує на кожній наступній ітерації циклу черговий елемент ланцюжка (послідовності) , яка знаходить значення . Інваріантом даного циклу є , умовою продовження , S0 має обчислювати , а S - бути програмної реалізацією функції G.

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

ЗАВДАННЯ 9.27. Напишіть програму, що визначає значення в цілій точці t, багаточлена, заданого послідовністю його цілих коефіцієнтів (у порядку убування ступенів).

 

Зауважимо, що , де . Тому функція , визначена, як , задовольняє співвідношенню

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

Текст програми.
public class Pol {
public static void main (String [] args) throws Exception {
int t = Xterm.inputInt ("t ->");
int y = 0;
try {
while (true) {
int x = Xterm.inputInt ("x ->");
y = t * y + x;
}
} Catch (Exception e) {
Xterm.println ("\ ny =" + y);
}
}
}
Цей ефективний метод обчислення значення багаточлена в точці носить ім'я схеми Горнера.

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

 

Завдання для самостійного вирішення

Вирішуючи завдання на рекурсію необхідно обгрунтовувати як закінчення роботи програми, так і вірність отриманого результату при її завершені.

За використання схеми обчислення інваріантної функції необхідно вказати множини X, Yі , функцію F і перетворення T (див. визначення інваріантної функції) та пояснити програмну реалізацію перетворення T.

ЗАВДАННЯ 9.28. Напишіть рекурсивну програму, яка друкує значення похідної багаточлена ступеня у заданій точці . Коефіцієнти багаточлена зберігаються в масиві а в порядку убування ступенів і є цілими числами, так само як і значення . Величини n, і елементи масиву змінювати в програмі не можна.

ВКАЗІВКА. Нехай . Продиференціюємо по x рівність та підставимо потім . Ми отримаємо наступні співвідношення:

Скориставшись ними і формулами

,

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

ЗАВДАННЯ 9.29. Напишіть програму, яка підносить ціле число в цілу невід ' ємну ступінь. Точні перед- і постумови цієї програми такі: . При написанні програми величини і змінювати не дозволяється, слід використовувати інваріант і обмежуючу функцію h = у.

ЗАВДАННЯ 9.30. Напишіть програму, що знаходить найбільший спільний дільник двох цілих невід'ємних чисел та не рівних одночасно нулю. Скористайтеся наступною властивістю найбільшого загального дільника (доведіть її!):

Тут операція дозволяє знайти залишок від ділення на .

ЗАВДАННЯ 9.31. Напишіть програму, що зводить ціле число в цілу невід’ємну ступінь. Точні перед- і постумови цієїї програми такі: , . При написанні програми величини i змінювати не дозволяється. Скористайтеся тим, що функція , інваріантної щодо перетворення , що задається формулою

 

ЗАВДАННЯ 9.32. Напишіть програму, що знаходить найбільший спільний дільник двох цілих невід'ємних чисел і , не рівних одночасно нулю. Програма повинна мати тимчасову складність порядку і не використовувати операцій ділення і знаходження залишку від ділення (допустимо поділ навпіл, реалізоване з допомогою операції зсуву). Скористайтеся наступними властивостями найбільшого загального дільника (доведіть їх!):

.

ВКАЗІВКИ. Скористайтеся інваріантністю функції щодо наступного перетворення T:

 

 

Не забудьте довести Т інваріантність функції F

 

Лекція 10.