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=xn натурального показника, використовуючи тільки операції множення та ділення навпіл.
Розв`язок. Розглянемо функцію y=zxk. При z=1 і k=n вона дaє шукану величинy y=xn. При k=0 функція y=zxk обчислюється тривіально : 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)
ка.
Обмежувальну функцію побудувати самостійно.
Немає коментарів:
Дописати коментар