2.5.4. Техніка побудови стандартних програм

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

Проілюструємо дану техніку на прикладах з різних предметних областей.

Приклад 2.28. Для даних , обчислити суму ... .

Аналіз.

Вхід: , .

Вихід: .

Залежність: .

Вимоги: побудувати стандартну програму (Prog9.7) для обчислення . Базовою -системою є дійсна й натуральна арифметики з операціями та предикатами , –, *, /, %, , , до якої долучено функцію sin.

Проектування. Побудувати стандартну програму для обчислення означає побудувати таку програму, параметризований векторний аналог якої буде повертати як результат . Побудуємо 1-рекурентну функцію для обчислення , конструктори якої є похідними операціями базової -системи, і застосуємо до неї теорему 2.1. Ураховуючи, що сума залежить від входів та , долучимо до системи (*) вхідні послідовності-константи та і опорну послідовність . Спробуємо побудувати систему так, щоб . Оскільки , то покладемо , , тобто за члени виберемо часткові суми перших доданків суми . Для рекурентності послідовності необхідно знайти залежність суми від попередньої суми . Ця залежність має вигляд . Оскільки операція додавання й функція є припустимими, то псує дану рекурентну залежність тільки степінь . Уведемо в систему допоміжну рекурентну послідовність , , . Тоді і конструктор праворуч уже є припустимим. Щоб вибрати саме -й член опорної послідовності, долучимо до системи лічильник . Тоді за фільтр можна взяти умову . Дійсно, для та . Таким чином, побудована система (*) має вигляд

За побудовою .

Кодування. Нехай ініціалізація вигляду v:=! означає присвоювання змінній v довільного припустимого значення. Для послідовностей системи виберемо змінні з найменуваннями відповідно a,s,k,n,x. Серед них n, x – вхідні, s – вихідна, а a, k – робочі змінні. Програма Prog9.7:

Лістинг.

/*Вх: x,n Вих: s */

{x:=!; n:=!;s:=sin(x); k:=1; a:=x;

while (i<n) {a:=a*x;

s:=s+sin(a);

k:=k+1;

}

}

Структура програми Prog9.7 вимагає пояснення, оскільки відрізняється від стандартної, застосованої в доведенні теореми 2.1. Як бачимо, член залежить від та ( ) і не залежить від лічильника , а член і лічильник залежать тільки від своїх попередників та і не залежать від інших послідовностей. Вибраний порядок зміни значень змінних забезпечує коректне їхнє оновлення й дозволяє не вводити в програмі Prog9.7 відповідні дублікати-змінні ■

Приклад 2.29. Знайти -те число Фібоначчі, (див. Прикл. 2.27).

Аналіз.

Вхід: .

Вихід: .

Залежність: , де , .

Вимоги: побудувати стандартну програму Prog9.8 для обчислення . Базовою -системою є натуральна арифметика зі стандартними операціями та предикатами: , –, *, /, %, , .

Проектування. Маємо послідовності: опорну та і послідовність-константу . Щоб вибрати саме -й член опорної послідовності, введемо до системи лічильник з початковим значенням 2. Тоді за фільтр можна взяти умову . Таким чином, побудована система (*) має вигляд:

За побудовою .

Кодування. Виберемо змінні програми Prog9.8: f,ff,g,i та n. Серед них: n – вхідна, f – вихідна, а ff, g та i – робочі змінні. Програма Prog9.8 будується стандартно:

/*Вх: Вих: */

{f:=1; g:=1;

i:=2; n:=!;

if (n 2)

while (i<n)

{i:=i+1;

ff:=f+g;

g:=f;

f:=ff;

}

}

У програмі використано змінну-дублікат ff для змінної f. Якщо цього не зробити, то після присвоювання ff:=f+g зникне значення , необхідне для оновлення g ■

Приклад 2.30. Для даних , обчислити суму … , уникнувши вкладених циклів.

Аналіз.

Вхід: , .

Вихід: .

Залежність: .

Вимоги: побудувати стандартну програму Prog9.9 для обчислення . Базовою -системою є дійсна й натуральна арифметики зі стандартними операціями та предикатами. Програма не має містити вкладені цикли, тобто цикли, які є в тілі іншого циклу.

Проектування. Як і у прикл. 9.7, шукана рекурентна система (*) включає три послідовності: вхідні послідовності – константи та – і послідовність часткових сум таку, що . Для останньої маємо співвідношення . Уведемо в систему допоміжну послідовність . Тоді і та , . Дійсно, якщо поділити на , то отримаємо саме . Знову конструктор містить піднесення до степеня та є неприпустимим у базовій алгебрі. Тому необхідно ввести ще одну додаткову послідовність , . Маємо , Як бачимо, остання послідовність рекурентна з конструкторами – похідними операціями базової алгебри. Отже, побудована система (*) має вигляд:

За побудовою .

Кодування. Змінні програми Prog9.9: a,b,s,k,n та x – без дублікатів.

{n:=!; x:=!;k:=1;s:=a:=b:=x;

while (i<n) {B:=B*X*X;

A:=A*B;

S:=S+A;

K:=K+1;

}

} ■

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

Аналіз.

Вхід: .

Вихід: .

Залежність: , де задовольняє умову

Вимоги: побудувати стандартну програму Prog9.10 для обчислення . Інші вимоги – ті самі, що й у задачі 9.9.

Проектування. Початок такий, як і для обчислення сум. Знову візьмемо три послідовності: вхідну послідовність-константу , лічильник і опорну – із часткових сум таку, що . Маємо та , . Щоб рекурентно подати степінь , розглянемо дві допоміжні послідовності: , та . Тоді ,

,

.

Таким чином, маємо потрібну рекурентну систему. Лишилося знайти фільтр . Щоб припинити ітерацію, достатньо перевірити на наступному кроці, чи буде модуль нового доданка ( ) більшим від . Якщо так, то продовжити ітерацію, якщо ні – вийти з неї. Отже, фільтром може бути умова . Остаточно система (*) має вигляд:

За побудовою .

Кодування. Змінні програми Prog9.10: a,b,s,k та – без дублікатів. Сама програма Prog9.10 має вигляд:

/*Вх: , Вих: s */

{ :=!; k:=1;s:=1;a:=0;b:=10;

while (1/(k+1)> ) {k:=k+1;

a:=(k<b a |a+1);

b:=(k<b b | b*10);

s:=s+(a%2=0 1 | -1)/k;

}

}

Тут, як і в усіх попередніх програмах, вдалося уникнути введення дублікатів змінних за рахунок спеціального порядку їхнього оновлення: спочатку змінився лічильник, потім – змінна a (це принципово, тому що її оновлення залежить від поточного, а не нового значення b), а потім, у довільному порядку, – змінні b та s ■

Приклад 2.32. (Швидке піднесення до степеня). Дано . Реалізувати піднесення до степеня в півгрупі з кількістю множень в обчисленні О .

Аналіз

Вхід: , .

Вихід: .

Залежність: .

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

Проектування. Якщо вибрати прямий підхід до обчислення степеня й покласти , то отримаємо кількість множень .

Щоб підвищити ефективність алгоритму, подамо показник степеня у двійковій системі. Нехай для певних {0, 1}, де (див. 7.3). Тоді, з урахуванням асоціативності півгрупового множення, степінь можна записати як добуток , в якому міститься вже тільки множень. Розглянемо три послідовності: вхідні послідовності-константи та і опорну – із часткових добутків , тобто . Тоді , , , . Нам знадобляться ще три додаткові рекурентні послідовності: , , . Дві останні необхідні для знаходження двійкових цифр натурального числа . При цьому , , та . Дійсно, якщо розділити на , то отримаємо в результаті . Залишилось визначитись із фільтром обчислення. Фільтр із лічильником не зовсім підходить, оскільки тоді необхідно ще додатково обчислювати значення . Менш очевидним, але набагато простішим, є фільтр . З ним отримуємо систему (*):

За побудовою .

Кодування. Змінні програми Prog9.11 a,b,x,n,p,q – без дублікатів. Програма Prog9.11:

/*Вх: , Вих: */

{x:=!;n:=!;a:=x;q:=n;b:=n%2;

p:=(n%2=1 x|1);

while (q>0) {a:=a a;

q:=q/2;

b:=q%2;

p:=p (b=1 a|1);

}

}

Її можна дещо удосконалити, усунувши змінну b. Ця змінна відіграє роль логічного прапорця, який можна замінити його поточним значенням q%2. Новий варіант програми Prog9.11 може бути таким:

/*Вх: , . Вих: */

{x:=!;n:=!;a:=x;q:=n;

p:=(n%2=1 x|1);

while (q>0) do {a:=a a;

q:=q/2;

p:=P (q%2=1 a|1);

}

}■

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

Приклад 2.33. Дзеркальне обернення кортежів.

Аналіз.

Вхід: , .

Вихід: .

Залежність: , де – дзеркальне обернення кортежу .

Вимоги: побудувати стандартну програму Prog9.12 для обернення кортежів. Нехай . Базовими операціями є: взяття голови , взяття хвоста та - додавання компоненти в початок кортежа. Базовим предикатом є рівність .

Проектування. Нехай і – опорна послідовність така, що . Обернення кортежів має таку важливу властивість: . Покладемо і введемо допоміжну послідовність , , . Тоді визначимо кортеж рекурентно як . Для справедливо співвідношення . За фільтр можна взяти предикат , де [] – порожній кортеж. Отже, побудована рекурентна система (*) має вигляд:

За побудовою .

Кодування. Змінними в програмі є v,u,f без дублікатів. Програма Prog9.12 будується стандартно за рекурентною системою :

/*Вх: f . Вих: u */

{f:=!;v:=f;u:=head(f);

while (v ) {v:=tail(v);

u:=pre(head(v),u));

}

}

■

Увага! Коректність побудованих у прикл. 9.7–9.12 програм нескладно довести математично. Для цього достатньо перевірити коректість рекурентних функцій, породжених відповідними системами (*) і далі послатися на теорему 2.1. Повернемося, наприклад, до прикл. 9.7. Небхідно довести, що . Для цього достатньо показати, що правильно вибрані конструктори для опорноюї й решти послідовностей, а також фільтр.

Спочатку перевіримо коректність послідовностей , та , . Необхідно показати істинність твердження : ( ). Скористаємося математичною індукцією по .

База індукції: , (за означенням).

Індуктивний перехід. Припустимо, що і для довільного . Тоді за рекурентними співідношеннями: , і, з урахуванням індуктивного припущення, , . Отже індуктивний перехід має місце і з повноти індукції випливає . Щоб довести коректність вибору фільтра , необхідно показати коректність твердження & . Оскільки хибне, то – істинне, а істинність першого коньюнктивного члена випливає з означення лінійного порядку на множині натуральних чисел. Отже, ми довели, що ■

У загальному випадку в подібних доведеннях застосовується метод структурної індукції, який розглядається в підрозд. 10.

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

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

*Література для CР: СБС і алгоритми – [16, 22, 24], pекурентні співідношення й функції – [16, 22], доказове програмування циклічних програм – [Вирт, Дейкст, Грис].

Контрольні запитання та вправи

1. Дати визначення структурних композицій.

2. Що таке ССП?

3. Як інтерпретуються ССП?

4. Що таке структурний алгоритм та абстрактна структурна програма? Яка між ними різниця?

5. Що таке циклічний структурний алгоритм?

6. Що таке рекурентна послідовність?

7. Що таке конструктор рекурентної послідовності ?

8. Дати визначення системи -рекурентних послідовностей.

9. Що таке рекурентна функція?

10. Дати визначення -оператора?

11. Як пов’язані рекурентні функції та циклічні блок-схеми?

12. Провести доведення теореми 2.1 для параметризованих функцій і програм.

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

14. Показати, що композиція мінімізації (див. Вправа 3.12) є частковим випадком -оператора.

Увага! У задачах 15-19 та 21-22 необхідно побудувати стандартні програми над з долученними функціями , та . В задачі 20 мається на увазі стандартний арифметичний базис. Усі числа розглядаються в десятковій системі.

15. Дано

а) З’ясувати, чи містить десяткове подання числа входження цифри 7, і підрахувати кількість таких входжень.

б) Поміняти місцями першу й останню цифри в числі.

в) Приписати одиницю ліворуч і праворуч до числа

16. Дано Знайти найбільший спільний дільник цих чисел. Використати алгоритм Евкліда для знаходження НСД двох натуральних чисел за допомогою віднімання.

17. Дано Обчислити:

а)

б) ;

в)

г) .

18. Дано Обчислити:

а)

б)

б) .

19. Дано Обчислити:

а) ;

б) добуток перших співмножників

20. Дано Обчислити, уникнувши вкладених циклів:

а) ; б) ; в) ( - кількість десяткових цифр у числі ); г) ; д) .

21. Дано Реалізувати швидке множення із кількістю додавань .

22. Довести коректність стандартних програм з Прикладів 21.28-33.

21 Заключні предикати використовуються у детермінованому виборі (див.1.3.3)

23