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

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

Визначення 9.8. Нехай X — деяка множина, F: X→ Y — задана на ній функція, а P — предикат такий, що P(x) = (F(x) легко обчислити). Позначимо через ту підмножину множиниX, де P(x) = T. Якщо існує перетворення таке, що , то функція F називається T -інваріантною або просто інваріантною функцією.

Найпростішим прикладом інваріантної функції є добре відома ще з середньої школи функція ,. Вона є T -інваріантною щодо перетворення T: R → R, T(x) = x + 2π,

 

Найбільший спільний дільник двох цілих чисел (greatest common divisor, або просто НОД (x, y)) інваріантний щодо перетворення , що задається формулою

Доказ цього факту, засноване на основній теоремі арифметики про розкладання числа на прості множники, є досить простим і залишається читачеві. Зверніть тільки увагу на те, що функція не визначена в точці (0,0).

Для обчислення значення T-інваріантної функції F в точці застосовується наступна схема.

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

Рисунок 9.3.відображає графічну ілюстрацію цієї схеми.

 

 

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

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

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

 

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

 

 

Рішення. Якщо через позначити множину всіх невід'ємних цілих чисел, які представлені в ЕОМ, то

, .

В якості перетворення →X можна взяти

Таким чином, нам відомі інваріант i умова продовження . Початкові присвоювання S0 в даному випадку не потрібні, тіло циклу S пишеться за визначенням T, a програма S1, що обчислює для , реалізується за допомогою справедливою для цих значень аргументу формули .

Текст програми:

public class Gcd { public static void main(String[] args) throws Exception { int x = Xterm.inputInt("x -> "); int y = Xterm.inputInt("y -> "); Xterm.print("gcd(" + x + "," + y + ") ="); while ((x!= 0) && (y!= 0)) { if (x >= y) x -= y; else y -= x; } Xterm.println(" " + (x+y)); }}

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

Розглянемо ще одну задачу.

 

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

При написанні програми величини а і b змінювати не дозволяється. Скористайтеся тим, що функція

є інваріантної щодо перетворення

,

що задається формулою

T(x, y, z) = (2x, y/2, z), якщо у – парне,

T(x, y, z) = (x, y − 1, z + x), в іншому випадку.

У цьому випадку , , , . Функція F та перетворення T задані в умові завдання.

 

Таким чином, нам відомі інваріант і умова продовження . Початкові присвоювання S0 очевидні ("x = a; y = b; z = 0;"), тіло циклу S пишеться за визначенням T, a програма S1, що обчислює F(x, y, z) для , у цьому випадку вироджується в порожній оператор ";", тому що для цих значень аргументу . У результаті отримуємо вже знайому нам програму.

 

Текст програми:

public class MulInv { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("a -> "); int b = Xterm.inputInt("b -> "); int x = a, y = b, z = 0; while (y > 0) { if ((y&1) == 0) { y >>>= 1; x += x; } else { y -= 1; z += x; } } Xterm.println("a * b = " + z); }}