.

Подільність (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
1 2111
Скачать документ

Реферат на тему:

Подільність

Нехай x – дійсне число. Через ?x??будемо позначати найбільше ціле
число, яке не перевищує x.

Теорема. Нехай a та b – цілі числа, при чому b > 0. Тоді існують такі
числа q та r, які визначаються однозначно, що a = b * q + r, при чому 0
? r < q. Число q називається неповною часткою, а r – залишком від ділення a на b., то це і доводить теорему.b (a ділиться на b).-4, тому що 20 = (-4) * 5.Властивості подільності. Нехай a, b та c – цілі числа. Тоді1. a | a.2. Якщо a | b та b | a, то a = ±b.3. Якщо a | b та b | c, то a | c.4. Якщо a | b та a | c, то a | (bx + cy) для всіх x, y ? Z.Алгоритм ЕвклідаОбчислення найбільшого спільного дільника (НСД) двох чисел a та b базується на наступному факті: якщо a та b – додатні цілі числа, a > b,
тоді НСД(a, b) = НСД(b, a mod b). У випадку, коли a < b маємо: НСД(a, b) = НСД(b, a mod b) = НСД(b, a).ВХІД: два невід’ємних числа a та b.ВИХІД: НСД(a, b)int nsd(int a, int b){int temp;while (b != 0){temp = a % b;a = b;b = temp;}return a;}Приклад. Обчислення НСД(4864, 3458).4864 = 1* 3458 + 14063458 = 2 * 1406 + 6461406 = 2 * 646 + 76114 = 1 * 76 + 3876 = 2 * 38 + 0Алгоритм Евкліда можна розширити для знаходження таких цілих чисел x та y, що a * x + b * y = d.ВХІД: два невід’ємних числа a та b, a і b.ВИХІД: d = НСД(a, b) та такі цілі числа x та y, що a * x + b * y = d.void nsdrozsh(int a, int b, int *x, int *y, int *k){int p, q, r, s, m, n;m = a; n = b; p = 1; q = 0; r = 0; s = 1;while (m!=0 && n!=0){if (m >= n)

{ m = m – n; p = p – r; q = q – s; }

else

{ n = n – m; r = r – p; s = s – q; }

}

if (m == 0)

{ *k = n; *x = r; *y = s; }

else

{ *k = m; *x = p; *y = q; }

}

Приклад. Розширений алгоритм Евкліда. Обчислення НСД(4864, 3458).

Q r x y a b x2 x1 y2 y1

4864 3458 1 0 0 1

1 1406 1 1 3458 1406 0 1 1 1

2 646 2 3 1406 646 1 2 1 3

2 114 5 7 646 114 2 5 3 7

5 76 27 38 114 76 5 27 7 38

1 38 32 45 76 38 27 32 38 45

2 0 91 128 38 0 32 91 45 128

Результат: НСД(4864, 3458) = 38, при цьому 4864 * 32 + 3458 * (-45) =
38.

Для обчислення найменшого спільного кратного (НСК) можна використати
формулу:

a * b = НСД(a, b) * НСК(a, b).

Приклад. Знайти НСК(12, 18). Скориставшись наведеним алгоритмом,
знайдемо, що НСД(12, 18) = 6. Отже 12 * 18 = 6 * НСК(12, 18). Звідки
НСК(12, 18) = (12 * 18) / 6 = 36.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат
UkrReferat.com. Всі права захищені. 2000-2019