Бінарний алгоритм

На вході алгоритму задані числа а, b N, a b. На виході d=НСД(a,b).

1 крок. Привласнити r залишок від розподілу a на b. Потім a:=b, b:=r.

2 крок. Якщо b=0, то видати а і закінчити роботу. Інакше k:=0, і потім, поки a і b обоє парні, виконувати:

(після цього 2^k йде в НСД(a,b), що залишилася частина НСД буде непарною).

3 крок. Зараз принаймні одне з чисел a і b непарне. Якщо а парне, то робити присвоєння а:=а/2 доти, поки а не стане непарним. Те ж для b.

4 крок. Зараз a і b обоє непарні. Привласнити t:=(a-b)/2. Якщо t=0, то видати 2^kа і закінчити роботу.

5 крок. ДОТИ, поки t парне, робити t:= t/2.

6 крок. Зараз t непарне, t¹0. Якщо tñ0, то а:= t. Якщо tá0, то b:=-t. Йти на 4 крок.

Кінець алгоритму.

Приклади рішення задач контрольної роботи:

Дано два натуральних числа a і b, не рівні нулю одночасно. Обчислити НСД (a,b) - найбільший загальний дільник а і b.

іf a > b then begіn

| k:= a;

end else begіn

| k:= b;

end;

{k = max (a,b)}

{інваріант: ніяке число, більше k, не є загальним дільником}

whіle not (((a mod k)=0) and ((b mod k)=0)) do begіn

| k:= k - 1;

end;

{k - загальний дільник, більші - ні}

Розглянемо рішення даної задачі за допомогою алгоритмуЕвкліда:

Будемо вважати, що НСД (0,0) = 0. Тоді НСД (a,b) = НСД (a-b,b) = НСД (a,b-a); НСД (a,0) = НСД (0,a) = a для всіх a,b>=0.

m:= a; n:= b;

{інваріант: НСД (a,b) = НСД (m,n); m,n >= 0 }

whіle not ((m=0) or (n=0)) do begіn

| іf m >= n then begіn

| | m:= m - n;

| end else begіn

| | n:= n - m;

| end;

end;

іf m = 0 then begіn

| k:= n;

end else begіn

| k:= m;

end;

Вимоги до оформлення звіту контрольної роботи:

Звіт повинний містити:

1. Тема і ціль лабораторної роботи.

2. Короткі теоретичні відомості.

3. Завдання і програму мовою Turbo Pascal.

4. Результати виконання програми.

Варіанти індивідуальних завдань:

(варіант вибирається по останній цифрі номера залікової книжки)

Варіант №1.

Написати алгоритм Евкліда, що використовує співвідношення НСД(a, b)=НСД(a mod b, b) при a >= b НСД (a, b)=НСД (a, b mod a) при b >= a

Варіант №2.

Написати алгоритм Евкліда, що використовує співвідношення НСД (a, b)=НСД (a, b mod a) при b >= a

Варіант №3

Дано натуральні а і b, не рівні 0 одночасно. Знайти d = НСД (a,b) і такі цілі x і y, що d = a*x + b*y.

Варіант №4

Дано натуральні а і b, не рівні 0 одночасно. Знайти d = НСД (a,b) і такі цілі x і y, що d = a*x + b*y.

Варіант №5

Дано натуральні а і b, не рівні 0 одночасно. Знайти d = НСД (a,b) і такі цілі x і y, що d = a/x + b*y.

Варіант №6.

Дано натуральні а і b, не рівні 0 одночасно. Знайти d = НСД (a,b) і такі цілі x і y, що d = a*x + b/y.

Варіант №7

Написати варіант алгоритму Евкліда, що використовують співвідношення

НСД(2*a, 2*b) = 2*НСД(a,b)

Варіант №8

Написати варіант алгоритму Евкліда, що використовують співвідношення

НСД(2*a, b) = НСД(a,b) при непарному b

Варіант №9

Написати бінарний алгоритм, що використовує співвідношення НСД(a, b)=НСД(a mod b, b) при a >= b НСД (a, b)=НСД (a, b mod a) при b >= a

Варіант №10

Дано натуральні а і b, не рівні 0 одночасно. Знайти d = НСД (a,b) і такі цілі x і y, що d = a*x + b*y, використовуючи бінарний алгоритм.

Поиск по сайту: