7 клас. Інформатика. Дистанційне навчання: 29.11.2021 - 05.12.2021 Алгоритми пошуку НСД та НСК, розгалуження та повторення

29.11.2021 - 05.12.2021

Тема: Алгоритми пошуку НСД та НСК, розгалуження та повторення

Теоретична частина

Множина цілих чисел складається з множини натуральних чисел 1, 2, 3,..., нуля і множини від'ємних.цілих чисел -1, -2, -3.

Сума двох цілих чисел т і п є цілим числом.

Якщо т, п будь-які цілі числа, то існує єдине ціле число х, яке задовольняє рівняння т+х=п. х — різниця чисел т і п.

Добуток двох цілих чисел є цілим числом х=аb.

Множина цілих чисел є кільцем, тобто у множині цілих чисел виконуються три дії: додавання, віднімання та множення.

Найбільшим спільним дільником НСД(а, b) =с називається найбільше натуральне число с, на яке діляться два дані числа а і b без остачі.

Приклади: НСД(6, 3)=3; НСД(8, 4)=4; НСД(22, 11)=11; НСД(12, 18)=6; НСД (1320, 408)=24.

Взаємно прості числа

Два числа називаються взаємно простими, якщо вони не мають жодних спільних дільників, крім 1 і -1.

Приклади. 7 та 2 - це взаєсно прості два числа, бо у них тільки два спільні дільника -1 та 1.

Можна довести, що числа 2m-1 і 2m+1 взаємно прості.

Довести, що якщо число n ділиться на кожне з двох взаємно простих чисел а і b, то воно ділиться на їх добуток аb.

Найбільший спільний дільник записуємо так: НСД (а, b)=с,

і він має властивості:

Якщо а:b ділиться націло , де a та b натуральні числа, то НСД(а, b)=b

Якщо а=bg+r, то НСД(а, b)= НСД(b, r).

Якщо m довільне натуральне число, то НСД(аm, bm)= m*НСД(а, b).

Якщо НСД(а, b)=с, то НСД( a/c, b/c)=1.

НСК[а, b] ділиться на НСД(а, b).

Якщо m ділиться на кожне з двох чисел а і b, то m ділиться і на їх найменше спільне кратне НСК[а, b].

Чому може дорівнювати найменше спільне кратне трьох чисел n-1, n, n+1 (де n — натуральне число)?

Довести, що частки від ділення найменшого спільного кратного на дані числа є взаємно прості.

Найбільший дільник для взаємно простих чисел дорівнює 1.

Якщо НСД(а,b)=1, то НСД(ас, b)= НСД(b, с).

Якщо НСД(а, b)=1 і ас/b, то с/b.

Якщо НСД(а,b)=1, с/а i с/b, то с=аb.

Алгоритм НСД(а,b) мовою програмування Python3

print('Алгоритм пошуку НСД та НСК)

m=int(input('Введіть з клавіатури '))

print('Пошук найбільшого спільного ділка для двох чисел ',a,' i ',b)

while a*b>0:

if a>b:

a=(a%b); print('остача a%b=',a,'%',b,'=', a);

else:

b=(b%a); print('остача b%a= ',b,'%',a,'=', b);

d=a+b;

print('Найбільший спільний дільник = НСД(',n,';',m,')=d=',a,'+',b,'=d=', d);

print('Найменше спільне кратне= НСK(',n,';',m,')=n*m//d=k=',a,'*',b,'=', n*m//d);

Завдання для написання алгоритмів мовою програмування Python3

1) Використовуючи цифри 1, 2, 3, 4 і 6, записати множину тризначних парних чисел (без повторення цифр), які діляться на 9.

2) За допомогою цифр 1, 2, 3, 4 і 6 записати множину тризначних чисел (без повторення цифр), які діляться на 14.

3) За допомогою цифр 1, 2, 3, 4, 5 і 6 записати множину тризначних чисел (без повторення цифр), які діляться на 22.

4) За допомогою цифр 1, 2, 3, 4, 5 і 6 записати множину тризначних чисел (без повторення цифр), які діляться на 26.

5) За допомогою цифр 1, 2, 3 і 6 записати множину двозначних чисел (без повторення цифр), які діляться на 18.

6) Записати множину кількох багатоцифрових чисел, з яких кожне ділилося б на 36.

7) У чотирицифровому числі, кратному 9, на місці тисяч стоїть цифра 3 і на місці сотень цифра 6. Знайти множину чисел.

8) Написати множину кількох трицифрових чисел (без повторення цифр), які при діленні на 9 давали б остачу 2, 5, 7.

9) За допомогою цифр 3, 4, 5, 6 записати множини чисел, які діляться на 24, 36, 21, 33.

10) Яке найменше число треба відняти від 839756, щоб остача поділилася на 90?

11) Яке найменше число треба відняти від 368457, щоб остача поділилася на 7?

Теорема про остачі: Якщо остача від ділення числа а на b дорівнює с, то остача від ділення числа аⁿ на b дорівнює остачі від ділення числа сⁿ на b.

Приклад 1. 13 : 5 = 2 (ост. 3), тоді 13ⁿ :5 дає таку саму остачу, як і 3ⁿ: 5.

Розв'язання

1) n = 2, 13²:5 = 169:5 = 33 (ост. 4) і 3²:5 = 9:5 = 1 (ост. 4);

2) n = 3, 13³:5 = 2197:5 = 439 (ост. 2) і 3³:5 = 27:5 = 5 (ост. 2);

3) n = 4, 13⁴:5 = 28 561:5 = 5712 (ост. 1) і 3⁴:5 = 81:5 = 16(ост. 1);

4) n = 5, 13⁵:5 = 371 293:5 = 74 258 (ост. 3) і 3⁵:5 = 243:5 = 48 (ост. 3).

Приклад 2. Знайти остачу від ділення числа 2222ⁿ на 7.

Розв'язання

1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).

2) Остача від ділення 2222⁴ на 7 така сама, як остача від ділення 3⁴ на 7, тобто 4, бо

3⁴:7 = 81:7 = 11 (ост. 4).

Відповідь. 4.

II. Розв'язування вправ.

Задача 1. Знайти остачу від ділення числа 2222⁵⁵⁵⁵на 7.

Розв'язання

1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).

Остача від ділення 2222⁵⁵⁵⁵ на 7 така сама, як остача від ділення 3⁵⁵⁵⁵ на 7.

Знайдемо остачі від ділення 3ⁿ на 7 для різних значень n:

n=1, З':7 = 3:7 = 0 (ост. 3);

n = 2, 3²:7 = 9:7 = 1 (ост. 2);

n = 3, 3³:7 = 27:7 = 3 (ост. 6);

n = 4, 3⁴:7 = 81:7 = 11 (ост. 4);

n = 5, 3⁵:7 = 243:7 = 34 (ост. 5);

n = 6, 3⁶:7 = 729:7 = 104 (ост. 1);

n = 7, 3⁷:7 = 2187:7 = 312 (ост. 3).

Цикл дорівнює 6.

4) Знайдемо кількість повних циклів у числі 5555.

5555 : 6 = 925 (ост. 5).

925 повних циклів відкидаємо.

Отже, остача відділення 3⁵⁵⁵⁵ на 7 така сама, як від ділення 3⁵ на 7, тобто 5.

Отже, і остача від ділення 2222⁵⁵⁵⁵ на 7 дорівнює 5.

Відповідь. 5.

Задача 2. Знайти остачу від ділення числа 5555²²²²на 7.

Розв'язання

1) Знайдемо остачу від ділення 5555 на 7:

5555 : 7 = 793 (ост. 4).

Остача від ділення 5555²²²² на 7 така сама, як остача від ділення 4²²²² на 7.

Знайдемо остачі від ділення 4" на 7 для різних значень л:

n = 1, 4':7 = 4:7 = 0 (ост. 4);

n = 2, 4²:7 = 16:7 = 2 (ост. 2);

n = 3, 4³:7 = 64:7 = 9 (ост.1);

n = 4, 4⁴:7 = 256:7 = 36 (ост. 4).

Цикл дорівнює 3.

4) Знайдемо кількість повних циклів у числі 2222.

2222 : 3 = 740 (ост. 2).

740 повних циклів відкидаємо.

Отже, остача від ділення 4²²²² на 7 така сама, як і від ділення 4² на 7, тобто 2.

Отже, і остача відділення 5555²²²² на 7 дорівнює 2.

Відповідь. 2.

Задача 3. Довести, що (2222⁵⁵⁵⁵+5555²²²²) ділиться на 7 без остачі.

Доведення.

Оскільки 22225555 при діленні на 7 дає остачу 5, а 55552222 при діленні на 7 дає остачу 2, а сума цих остач 5+2 = 7 ділиться на 7, то (22225555 +55552222) ділиться на 7 без остачі, що і треба було довести.

Задача 4. Знайти остачу від ділення числа 7 2003 на 10.

Розв'язання

1) Знайдемо остачу від ділення 7 на 10: 7: 10 = 0 (ост. 7).

2) Знайдемо остачі від ділення 7 ⁿ на 10 для різних значень п:

n = 1, 7':10 = 7:10 = 0 (ост. 7);

n = 2, 7²:10 = 49:10 = 4 (ост. 9);

n = 3, 7³:10 = 343:10 = 34 (ост. 3);

n = 4, 7⁴:10 = 2401:10 = 240'(ост. 1);

n = 5, 7⁵ : 10 = 16 807:10 = 1680 (ост. 7).

Цикл дорівнює 4.

3) Знайдемо кількість повних циклів у числі 2003.

2003 : 4 = 500 (ост. 3).

4) 500 повних циклів відкидаємо. Отже, остача від ділення 7²⁰⁰³ на 10 така сама, як остача
від ділення 7³ на 10 , тобто 3.

Відповідь. 3.

5. Якою цифрою закінчується число 7²⁰⁰³ ?

Розв'язання.

Остача відділення числа 7^200З на 10 є останньою цифрою цього числа. Тобто число 7²⁰⁰³ закінчується цифрою 3.

Знаходження НСК(m, n) та НСД(а, b).

Розподілити 20 тверджень на три групи:

· перша група тверджень, які завжди правильні на множині натуральних чисел;

· друга група тверджень, які завжди неправильні на множині натуральних чисел;

· третя група тверджень, які не входять до першої та до другої групи.

1. Усі натуральні числа, які діляться на 30 можна подати у вигляді 2∙15n або 2∙3∙5n, де n − натуральне число.

2. Найменше натуральне число т, яке ділиться на кожне з чисел а і b без остачі, тобто найменше спільне кратне цих чисел (НСК(а, b)), завжди можна знайти таким чином: розкласти кожне число на прості множники, потім, взявши розклад одного із них, помножити його на відсутні прості множники, які зустрічаються в розкладі другого числа.

3. Найбільше натуральне число т, на яке ділиться на кожне з чисел а і b без остачі, тобто найбільший спільний дільник цих чисел (НСД(а, b)), завжди можна знайти таким чином: розкласти кожне число на прості множники, потім, виписати з двох розкладів спільні множники, до речі, кожний зі спільних простих множників треба взяти з найменшим показником, який зустрічається в обох розкладах, і помножити.

4. Добуток чисел а і b дорівнює добуткові їх найбільшого спільного дільника на найменше спільне кратне аb= НСК(а, b)∙НСД(а, b)

5. Найменше спільне кратне двох чисел дорівнює 3024, а їх найбільший спільний дільник 4. Друге число має лише три дільники, якщо перше дорівнює 28.

6. Найменше спільне кратне трьох чисел дорівнює 5544. Існує декілька третіх чисел, якщо перші два дорівнюють 72 і 168.

7. Два перші числа дорівнюють 165 і 156. Множину третіх чисел складають тільки непарні числа, якщо найменше спільне кратне всіх трьох чисел дорівнює 25740.

8. Найменше натуральне число т, яке ділиться на кожне з чисел а і b, тобто НСК(а, b) ділиться на їхній найбільший спільний дільник, тобто ділиться на НСД(а, b).

9. Якщо т ділиться на кожне з двох чисел а і b, то т ділиться і на їх найменше спільне кратне, тобто НСК(а, b).

10. Найменше спільне кратне трьох чисел n-1, n, n+1 (де n — натуральне число) це добуток цих чисел.

11. Частки від ділення найменшого спільного кратного на дані числа є взаємно прості.

12. Якщо число 3х+2у ділиться на 19, де х і у натуральні числа, то 8х-у не ділиться на 19.

13. Найменше спільне кратне двох чисел 5040, а їх найбільший спільний дільник 48. Множину таких пар чисел складають лише парні числа.

14. Найменше спільне кратне двох чисел 462, а їх найбільший спільний дільник 21. Множину таких пар чисел складають лише непарні числа.

15. Всього існує дві пари чисел, для яких добуток дорівнює 840, а їх найбільший спільний дільник дорівнює 2.

16. Сума двох чисел 168, а їх найбільший спільний дільник 24. Множину таких пар чисел складають лише числа різної парності, тобто одне з них парне число, а друге – непарне число.

17. Сума двох чисел 667, а їх найбільший спільний дільник 29. Множину таких пар чисел складають лише числа різної парності, тобто одне з них парне число, а друге – непарне число.

18. З космодрому одночасно запустили три супутники Землі. Перший має період обертання 1 год. 20 хв., другий — 1 год. 45 хв., а третій — 2 год. 20 хв. Тоді через 28 год − це найближчий час, коли вони знову будуть всі три разом над космодромом?

19. Три автобуси відправляються з автостанції о 7 год. ранку в трьох напрямах і повертаються: перший через 2 год. 15 хв. і знову відправляється через 15 хв.; другий — через 1 год. 45 хв. і знову відправляється через 15 хв.; третій — через 1 год. 30 хв. і знову відправляється через 10 хв. Тоді 12.00 − це найближчий час, коли вони знову одночасно виїдуть з автостанції?

Теорема про остачі може використовуватися під час розв'язування задач двох вище розглянутих типів.

Завдання для самостійного програмування

1.Знайти остачу від ділення числа 2003²⁰⁰⁴на 3, створити алгоритм для загального випадку: N^mна 3.

2.Якою цифрою закінчується 19²⁰⁰⁴? и алгоритм для загального випадку: 19^m

Практична частина

Алгоритми пошуку НСД та НСК, розгалуження та повторення

Завдання 1. Створити, реалізувати, протестувати алгоритм знаходження пошуку найбільшого числа та найменшого числа за відомою піврізницею та півсуммою двох випадкових чисел.

Реалізація.

print('Алгоритм 1 пошуку найбільшого числа та найменшого числа за піврізницею та за півсумою двох чисел ')

m=int(input('Введіть півсуму з клавіатури'))

n=int(input('Введіть піврізницю з клавіатури'))

x=m+n; y= m-n

print('Відповідь: 1-e число x=', x )

print('Відповідь: 2-e число', y)

if x>y:

print('max=', x , 'min=', y)

elif y>x:

print('max=',y, 'min=', x)

Протестувати алгоритм для таких чисел: 1)піврізниця: -2, півсума: 22;

2) піврізниця: -3, півсума:-8; 3) піврізниця: 0, півсума:-8; 4) піврізниця: 9, півсума: 9

Завдання 2. Створити, реалізувати, протестувати алгоритм знаходження пошуку найбільшого числа та найменшого числа за відомою піврізницею та півсуммою двох випадкових чисел.

Реалізація.

print('Алгоритм 2 пошуку найбільшого числа та найменшого числа за півДОБУТКОМ та за півЧАСТКОЮ двох ДОДАТНИХ чисел ')

m=float(input('Введіть півДОБУТok з клавіатури'))

n=float(input('Введіть півЧАСТКy з клавіатури'))

x=2*(m*n)**0.5; y= (m/n)**0.5

print('Відповідь: 1-e ДОДАТНЕ число x=', x )

print('Відповідь: 2-e ДОДАТНЕ число', y)

if x>y:

print('max=', x , 'min=', y)

elif y>x:

print('max=',y, 'min=', x)

Протестувати алгоритм для таких четвірок чисел: 1) півдобуток: 2, півчастка: 22;

2) півдобуток:36, півчастка:8; 3) півдобуток: 0, півчастка6 8; 4) півдобуток:1, півчастка: 1.

Завдання 3. Одинокий шаховий король знаходиться на шаховій дошці розміром NxN. Як і всі шахові королі він може перейти за один хід на сусідню клітинку. Скільки можливих варіантів ходу є короля? Програма читає з пристрою стандартного введення 3 натуральних числа N, X,Y. Кожне з чисел не більше 50, числа розділені пропусками (N ≥X,Y) N- розмір сторони дошки, X,Y – номер стрічки та стовпця клітинки з королем. Програма виводить єдине число – шукану величину.

Реалізація.

print('Алгоритм 3пошуку кількості ходів короля на шахівниці розміром nxn ')

n=int(input('Введіть 1-е додатне число з клавіатури n='))

x=int(input('Введіть 2-е додатне число з клавіатури x='))

y=int(input('Введіть 3-е додатне число з клавіатури y='))

if (((x==1) and (y==1)) or ((x==n) and (y==1)) or ((x==1) and (y==n)) or ((x==n) and (y==n))):

print(' Кількість ходів фігури король на шахівниці r:=',3)

elif ((x==1) or (x==n) or (y==n) or (y==1)):

print(' Кількість ходів фігури король на шахівниці r:=',5)

else:

print(' Кількість ходів фігури король на шахівниці r:=',8)

if n==1:

print(' Кількість ходів фігури король на шахівниці r:=',0)

Завдання 4. Створити, реалізувати, протестувати алгоритм знаходження пошуку півтретини різниці та півчверті суми найбільшого числа та найменшого числа із чотирьох введених з клавіатури цілих чисел.

Реалізація.

print('Алгоритм 4 пошуку піврізниці найбільшого числа та найменшого числа із чотирьох цілих чисел ')

v1=int(input('Введіть 1-е число з клавіатури')); v2=int(input('Введіть 2-е число з клавіатури'))

v3=int(input('Введіть 3-е число з клавіатури')); v4=int(input('Введіть 4-е число з клавіатури'))

print('Відповідь: найбільше число')

if ((v1>v2) and (v1>v3) and (v1>v4)):

print('max=', v1)

elif ((v2>v3) and (v2>v4)):

print('max=',v2)

elif v3>v4:

print('max=',v3)

else:

print('max=', v4)

print('Відповідь: найменше число')

if ((v1<v2) and (v1<v3) and (v1<v4)):

print('min=', v1)

elif ((v2<v3) and (v2<v4)):

print('min=',v2)

elif v3<v4:

print('min=',v3)

else:

print('min=', v4)

m=max(v1,v2,v3,v4); n=min(v1,v2,v3,v4);

print('Відповідь: піврізниця найбільшого та найменшого чисел с= (max-min)/6=', (m-n)/6)

print('Відповідь: півcума найбільшого та найменшого чисел с= (max+min)/8=', (m+n)/8)

Протестувати алгоритм для таких четвірок чисел: 1) 2, 2, 2, 2 2) -3,8, -1, 9 3)-9, -8, 7, 7 4) -3, -5, -8, -1.

Завдання 5. В цукерню «Солодка мрія» завезли m цукерок і n тістечок. Продавці бажають продати всі свої товари без залишку. Прийшов оптовий покупець, який закуповує подарунки для дітей на свято. Але, щоб нікому з дітей не було образливо, подарунки мають бути однаковими, тобто в кожному подарунку має бути однакова кількість цукерок і однакова кількість тістечок. Скільки цукерок і скільки тістечок повинен покласти продавець в кожен подарунок, щоб кількість подарунків була максимальною? Програма читає з пристрою стандартного введення числа m та n кожне з яких не перевищує 50000. Програма виводить через пропуск кількість цукерок і тістечок в кожному подарунку.

Реалізація.

print('Алгоритм 5 пошуку кількості цукерок і тістечок у кожному подарунку')

m=int(input('Введіть з клавіатури число цукерок '))

n=int(input('Введіть з клавіатури число тістечок'))

a=n; b=m;

print('Пошук найбільшого спільного дільника для двох чисел ',a,' i ',b)

while a*b>0:

if a>b:

a=(a%b); print('остача a%b=',a,'%',b,'=', a);

else:

b=(b%a); print('остача b%a= ',b,'%',a,'=', b);

d=a+b;

print('Найбільший спільний дільник = НСД(',n,';',m,')=d=',a,'+',b,'=d=', d);

print('Найменше спільне кратне= НСK(',n,';',m,')=n*m//d=k=',a,'*',b,'=', n*m//d);

print('Пошук двох часток від ділення даних чисел n i m на їхнє НСД' )

kn=(n//d); km=(m//d)

print('Кількість цукерок у одному подарунку kn=',n,'//',d,'=',kn)

print('Кількість тістечок у одному подарунку: km=',m,'//',d,'=',km)

Протестувати алгоритм для таких четвірок чисел: 1) цукерок: 2, тістечок: 22;

2)цукерок:36, тістечок: 8; 3) цукерок: 0, тістечок 8; 4) цукерок:1, тістечок: 1.

Завдання 6. Дано піфагорове рівняння x²+ y²= z², де х,y,z - невідомі цілі змінні. Створити та реалізувати алгоритм мовою програмування Python в середовищі програмування Thonny для знаходження розв’язків для цього рівняння на множині цілих чисел.