Зубенко, Омельчук - Програмування. Поглиблений курс
.pdfРозділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
Аналіз.
Вхід: ε R . Вихід: s R .
Залежність:s = |
n |
де |
n |
задовольняє |
умову |
∑ (−1)[lg k ] /k , |
|||||
|
k =1 |
|
|
|
|
1 ≤ k ≤ n |(−1)[lg k ] /k |> ε&|(−1)[lg(n +1)] /(n +1)|≤ ε.
Вимоги: побудувати стандартну програму Prog9.10 для обчислення s . Інші вимоги – ті самі, що й у прикл. 2.29.
Проектування. Початок такий, як і для обчислення сум. Знову ві- зьмемо три послідовності: вхідну послідовність-константу ε , лічиль-
ник k і опорну – із часткових сум s1 ,s2,...,sn ,sn +1,... таку, що sn = s .
Маємо |
s =1 та s |
= s |
−1 |
+ (−1)[lg k ] |
|
|
1 |
k |
k |
|
|
степінь |
(−1)[lg k ] , |
|
розглянемо |
||
a1 = 0,ak = [lgk], |
k >1 |
|
та |
sk = sk −1 + (ak %2 = 0 →1|−1)/k , ak = (k < bk −1 → ak −1|ak −1 +1), bk = (k < bk −1 → bk −1|bk −1 ×10) .
/k ,k >1. Щоб рекурентно подати дві допоміжні послідовності:
b |
=10,b =10(ak +1) |
, |
k >1. |
Тоді |
1 |
k |
|
|
|
Таким чином, маємо потрібну рекурентну систему. Лишилося знайти фільтр Q . Щоб припинити ітерацію, достатньо перевірити на наступно-
му кроці, чи буде модуль нового доданка ( = 1/(k +1)) більшим ніж ε . Як-
що так, то продовжити ітерацію, якщо ні – вийти з неї. Отже, фільтром Q(k,ε) може бути умова 1/(k +1) > ε. Остаточно система (*) має вигляд:
a1 = 0,ak = (k < bk −1 → ak −1|ak −1 +1);b1 =10,bk = (k < bk −1 → bk −1|bk −1 *10);s1 =1,sk = sk −1 + (ak %2 = 0 →1|−1)/k;k1 =1,k = (k −1) +1;
ε − константа.
За побудовою s = μQ* (ε).
Кодування. Змінні програми Prog9.10: a,b,s,k та ε – без дублі- катів. Сама програма Prog9.10 має вигляд:
/*Вх: x R , n N |
Вих: s R */ |
211
ПРОГРАМУВАННЯ
{ ε :=!; 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.31. Швидке піднесення до степеня. Дано n N . Реалі- зувати піднесення до степеня в півгрупі P = (A,o) з кількістю множень
в обчисленні c(n) = О(log2 n) .
Аналіз
Вхід: x A , n N . Вихід: p R .
Залежність: p = xn .
Вимоги: побудувати стандартну програму Prog9.11 для обчислення p із кількістю множень c(n) =О(log2 n) . Базовою Ω -системою є пів-
група P = (A,o) і натуральна арифметика зі стандартними операціями
та предикатами.
Проектування. Якщо вибрати прямий підхід до обчислення степе- ня й покласти p1 = x, pk = pk −1 o x , то отримаємо кількість множень c(n) = n −1.
Щоб підвищити ефективність алгоритму, подамо показник степеня n
у двійковій системі. Нехай |
n = b |
+b 21 |
+b 22 +... +b 2k |
для |
певних |
|||||
bi {0, 1}, де k = [ |
|
0 |
1 |
|
2 |
|
k |
|
|
|
log2 n ]. Тоді з урахуванням асоціативності півгрупо- |
||||||||||
вого множення |
степінь |
xn |
можна |
записати |
як |
добуток |
||||
xb0 × xb1×2 × xb2 ×22 ×...× xbk ×2k , в якому міститься вже тільки k |
множень. |
|||||||||
Розглянемо три послідовності: вхідні послідовності-константи |
x |
та n і |
||||||||
опорну – із часткових добутків p , p ,..., p |
, тобто |
p |
def |
i |
|
j |
||||
= |
∏ xbj 2 |
. Тоді |
||||||||
|
|
0 |
1 |
k |
|
i |
|
j =0 |
|
|
|
|
|
|
|
|
|
|
|
|
212
Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ
p |
= xb0 , |
p = p , p = p |
|
o xbi 2i |
= p |
o(b =1 → x2i |1) , i ≥1 |
. Нам зна- |
|||
0 |
|
k |
i |
i −1 |
|
i −1 |
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
def |
добляться |
ще |
три |
додаткові |
рекурентні послідовності: |
ai = x2i , |
|||||
qi |
= qi −1 /2, bi |
= qi %2 . Дві останні необхідні для відшукання двійко- |
||||||||
вих цифр натурального числа n . При цьому q0 = n , |
b0 = n%2 , a0 = x |
|||||||||
та ai = ai −1 oai −1 . Дійсно, |
якщо розділити ai на ai −1 , |
то отримаємо в |
результаті ai −1 . Залишилось визначитись із фільтром обчислення.
Фільтр із лічильником не зовсім влаштовує, оскільки він потребує до- даткового обчислювання значення k . Менш очевидним, але набагато простішим, є фільтр Q(qi ) = (qi > 0). З ним отримуємо систему (*):
a0 = x,ai = ai −1 oai −1; |
|
|
|
|
|||
p |
0 |
= (n%2 =1 → x |1), p |
= p |
o(b |
=1 → a |
|1); |
|
|
|
i |
i −1 |
i |
i |
|
|
(*5 ) q0 = n,qi = qi /2; |
|
|
|
|
|||
b0 = n%2,bi = qi %2; |
|
|
|
|
|||
x |
− константа; |
|
|
|
|
||
|
− константа. |
|
|
|
|
||
n |
|
|
|
|
|||
|
|
|
|
|
|
|
|
За побудовою p = μ* |
(x,n) . |
|
|
|
|
||
|
|
Q |
|
|
|
|
|
Кодування. Змінні програми Prog9.11 a,b,x,n,p,q – без дубліка- тів. Програма Prog9.11:
/*Вх: x A , n N |
Вих: p R */ |
{x:=!;n:=!;a:=x;q:=n;b:=n%2; p:=(n%2=1 →x|1);
while (q>0) {a:=a oa; q:=q/2;
b:=q%2;
p:=p o(b=1 →a|1);
}
}
Її можна дещо удосконалити, усунувши змінну b. Ця змінна віді- грає роль логічного прапорця, який можна замінити його поточним значенням q%2. Новий варіант програми Prog9.11 може бути таким:
/*Вх: x A , n N . |
Вих: p R */ |
213