UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваПодільність (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2022
Скачало361
Опис
ЗАКАЧКА
Замовити оригінальну роботу

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

 

Подільність

 

Нехай 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 + 1406

 

3458 = 2 * 1406 + 646

 

1406 = 2 * 646 + 76

 

114 = 1 * 76 + 38

 

76 = 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).

 

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.

 

0

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ