[ЗМІСТ] [Далі] [Назад]

4. НАЙПРОСТІШІ ВЛАСТИВОСТІ ПРОГРАМ

4.1. Дослідити цикл на скінченність

поки x>0 повт x ¬ x-1 кц .

Розв`язок. Необхідна умова скінченності циклу очевидно виконується. Розглянемо функцію В(х)=[x]+1. Оскільки [x]³0 при x>0, то x>0 тягне B(x)>0. Оскільки [x-1]=[x]-1, то В(х)=[x]+1>[x]=[x-1]+1=B(x-1). Отже B(x) - обмежувальна функція і цикл скінченний.

4.2. Встановити умови скінченності циклів:

а) поки x<>0 повт x ¬ x-1 кц;

б) поки x>0 повт x ¬ x+1 кц;

в) поки x<=b повт x ¬ x+a кц;

г) поки x<>b повт x ¬ x+a кц;

д) поки x<y повт z ¬ x; x ¬ y; y ¬ z+2 кц.

4.3. Довести скінченність циклу в алгоритмі

Алг Circle_1 це

змін n: ціл;

поч

взяти(n);

поки n>1 повт

якщо n mod 2 =0 то n ¬ n div 2

інакше n ¬ n+1

кр

кц;

показати(n)

ка.

4.4. Довести нескінченність циклу в алгоритмі

Алг Circle_2 це

змін n: ціл;

поч

взяти(n);

поки n>1 повт

якщо n mod 2 =0 то n ¬ n div 2+1

інакше n ¬ n+1

кр

кц;

показати(n)

ка.

4.5. Встановити умови скінченності циклу у наступному фрагменті алгоритму

s¬ 0;

поки n<>m повт

n ¬ n+1; s ¬ s+1

кц

4.6. Скласти алгоритм ділення натуральних чисел n i m націло з остачею:

n=q*m+r, 0<=r<m.

Розв`язок. Виберемо початкові значення q=0, r=n. В цьому випадку умова

J=(n=m*q+r)&(r>=0)

очевидно істинна. Побудуємо цикл таким чином, щоб умова J була його інваріантом, а умову повторення циклу виберемо так, щоб його заперечення разом з інваріантом Øa & J давало б умову задачі. Очевидно, a=Ø (r<m) = (r>=m).

Будемо шукати дії, що зберігають умову J при умові a. Значення змінної q в результаті виконання цієї дії, очевидно, повинне збільшуватися. Розглянемо збільшення q на 1. Тоді r потрібно зменшити на величину (q+1)*m-q*m=m, щоб забезпечити збереження J .Таким чином, пара присвоєнь q ¬ q+1; r ¬ r-m зберігає умову J при r>=m. Оскільки задача має зміст при натуральних m і невід`ємних цілих n, то передбачимо в ній захищене введення. Отримаємо алгоритм:

алгоритм Div це

змін m,n,q,r :ціл;

поч

повт

взяти (m,n)

до (m>0)&(n>=0) ;

q¬ 0; r¬ n;

поки r>=m повт

q¬ q+1; r¬ r-m

кц;

показати(q,r)

ка.

Спадною цілочисловою величиною, очевидно, є значення змінної r, оскільки m>0 , а обмежувальною функцією - функція B(r,m)=r-m.

4.7. Скласти алгоритм обчислення найбільшого спільного дільника двох натуральних чисел m, n .

Розв`язок 1. Задача полягає в обчисленні функції, позначимо її НСД, двох натуральних аргументів: НСД(m,n). При m=n обчислення НСД тривіальне, так як НСД(m,m)=m.

В силу адитивності функції НСД вона інваріантна відносно перетворень

m ¬ m - n якщо m>n

n ¬ n - m якщо n>m

а також дій n ¬ n+m; m ¬ m+n.

Вибір потрібної дії серед перелічених више необхідно здійснити одночасно з пошуком обмежувальної функції. Якщо за таку функцію взяти B(m,n)=m+n , а за умову повторення циклу умову m<>n , то функція B(m,n) буде спадати під дією першої сукупності перетворень. Щоб привести цю функцію у відповідність з умовою скінченності, перейдемо до pізниці B1(m,n) = B(m,n) - 2НСД(m,n). Отримаємо алгоритм

алгоритм НСД це

змін m,n :нат;

поч

повт

взяти (m,n)

до m>0 & n>0;

поки m<>n повт

якщо m>n то m ¬ m-- n

інакше n ¬ n - m

кр

кц;

показати (m)

ка.

Показати, що функція B1(m,n) дійсно є обмежувальною функцією отриманого циклу.

Розв`язок 2. Другий спосіб полягає у розгляді іншої умови тривіальності обчислення НСД, наприклад НСД(m,0)=m. Функція НСД інваріантна відносно перетворень m ¬ n; n ¬ m mod n. Якщо за обмежувальну функцію взяти B(n)=n, а за умову повторення циклу умову n<>0, то функція B(n) буде спадати під дією вказаних перетворень. Отримаємо алгоритм

алгоритм НСД це

змін m,n :нат:

поч

повт

взяти (m,n)

до m>0 & n>0 ;

поки n<>0 повт

l¬ m; m¬ n; n¬ l mod n

кц;

показати (m)

ка.

4.8. Скласти алгоритм обчислення добутку двох натуральних чисел, користуючись операціями додавання та ділення навпіл.

4.9. Скласти алгоритм обчислення степеня y=xⁿ натурального показника, використовуючи тільки операції множення та ділення навпіл.

Розв`язок. Розглянемо функцію y=zx^k. При z=1 і k=n вона дaє шукану величинy y=xⁿ. При k=0 функція y=zx^k обчислюється тривіально : y=z. Ця функція є інваріантною відносно перетворень

x¬ x¬ x, k¬ k/2;

z¬ z¬ x, k¬ k-1.

Першу пару дій можна застосовувати при парному k, другу доречно застосовувати при непарному k. Умова закінчення k=0. Отримаємо алгоритм

алг степінь це

змін n,k: нат; x,z : дійсн;

поч

взяти(n,x);

z¬ 1; k¬ n;

поки k <> 0 повт

якщо k mod 2=0 то

x¬ x*x; k¬ k div 2

інакше

z¬ z* k; k¬ k-1;

кр

кц;

показати(z)

ка.

Обмежувальну функцію побудувати самостійно.

[ЗМІСТ] [Далі] [Назад]