15.11.2021-21.11.2021 Алгоритми з числовими даними та їх властивостями

 

15.11.2021-21.11.2021

 

Тема: Алгоритми з числовими даними та їх властивостями

 

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

 

Створення математичної моделі до алгоритму з числовими даними

 Зразки задач комбінаторики

Задача 1. З Києва до Чернігова можна дістатися пароплавом, поїздом, автобусом, літаком; з Чернігова до Новгород-Сіверська – пароплавом і автобусом. Cкількома способами можна здійснити подорож за маршрутом Київ – Чернігів – Новгород-Сіверськ?

Розв’язання. Очевидно, число різних шляхів з Києва до Новгород-Сіверська дорівнює 4∙2 = 8, бо, обравши один з чотирьох можливих способів подорожі від Києва до Чернігова, маємо два можливих способи подорожування від Чернігова до Новгород-Сіверська.

Такі міркування, які були проведені при розв'язуванні задачі 1, доводять справедливість такого простого тверджен­ня, яке будемо називати основним правилом комбінаторики.

 

Якщо деякий вибір А можна здійснити m різними спосо­бами, а для кожного з цих способів деякий другий вибір В можна здійснити n способами, то вибір А і В (у вказаному порядку) можна здійснити m∙n способами.

 

Інакше кажучи, якщо певну дію (наприклад, вибір шля­ху від Києва до Чернігова) можна здійснити m різними спо­собами, після чого другу дію (вибір шляху від Чернігова до Новгород-Сіверська) можна здійснити n способами, то дві дії разом (вибір шляху від Києва до Чернігова, вибір шляху від Чернігова до Новгород-Сіверська) можна здійснити m∙n способами.

 

Задача 2. У розиграші першості країни з футбола бере участь 16 команд. Скількома способами можуть бути розподілені золота і срібна медалі?

Розв’язання. Золоту медаль може одержати одна з 16 команд. Після того, як визначено володаря золотої медалі, срібну медаль може мати одна з 15 команд. Отже, загальне число способів, якими може бути розподілена золота і срібна медалі, до­рівнює 16∙15 = 240.

 

Сформулюємо тепер основне правило комбінаторики (правило множення) в загальному вигляді.

Нехай треба виконати одну за одною k дій. Якщо першу дію можна виконати n₁ способами, другу дію – n₂ способами, третю дію – n₃ способами і так до k-ї дії, яку можна вико­нати n_k способами, то всі k дії разом можуть бути виконані n_1∙ n_2∙ n₃∙…∙ n_k-1 n_k способами.

 

Задача 3. Скільки чотиризначних чисел можна склас­ти з цифр 0, 1,2, 3,4, 5, якщо:

а)         жодна цифра не повторюється більше одного разу;

б)        цифри можуть повторюватись;

в)         числа повинні бути непарними?
Розв'язання.  а) Першою цифрою числа може бути одна з 5 цифр 1, 2, 3, 4, 5 (0 не може бути, бо тоді число не чотиризначне); якщо перша цифра обрана, то друга може бути обрана 5 способами, третя – 4, четверта – 3. Згідно з правилом множення загальне число способів дорівнює 5∙5∙4∙3 = 300.

б)        Першою цифрою може бути одна з цифр 1, 2, 3, 4, 5 (5 можливостей), для кожної з наступних цифр маємо 6 мож­ливостей (0, 1,2,3, 4, 5). Отже, число шуканих чисел дорів­нює 5∙6∙6∙6=5∙ 6³ = 1080.

в)         Першою цифрою може бути одна з цифр 1, 2, 3, 4, 5, а останньою – одна з цифр 1,3,5, (числа повинні бути не­парними). Отже, загальна кількість чисел дорівнює 5∙6∙6∙3 = 540.

 

Для того щоб добре засвоїти основне правило комбінато­рики, обов'язково треба розв'язати подані нижче вправи.

 

Вправи

4. Скільки існує п’ятицифрових чисел, для запису яких використовуються тільки цифри: а) 1, 2, 3, 4  б) 0, 1, 2, 3?( Кожна цифра може бути використана декілька разів). Відповідь: а)4⁵ , б) 3∙4⁴.

 

5.На вершину гори веде 7 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються різними шляхами. Відповідь: 49 способи, 42 способи.

 

6.В наряд можна послати трьох чоловік, одного із п’яти офіцерів, одного із семи сержантів і одного із 20 солдат. Скількома способами можна скласти наряд?

Відповідь: 20∙7∙5.

 

7. а)Скільки тризначних чисел можна утворити з цифр 1, 2, 3, 4, 5? Відповідь: 3⁵.

В наряд можна послати двох чоловік, одного із трьох сержантів і одного із 6 солдат. б)Скількома способами можна скласти наряд? Відповідь: 3∙6 =18.

 

8.Скільки різних дільників має число 3⁵∙5⁴? Відповідь: (5+1)∙(4+1) = 30. Скласти таблицю всіх дільників.

 

9. Скільки тризначних чисел можна утворити з цифр 1, 2, 3, 4, 5, якщо кожну з цих цифр можна використовувати не більше одного разу? Відповідь: 5∙4∙3.

 

10. Скількома способами 7 осіб можуть розташуватись в чергу до каси? Відповідь: 7∙6∙8∙5∙4∙3∙2∙1.

 

11. В класі вивчають 14 предметів. В понеділок 7 уроків, причому всі уроки різні. Скількома способами можна скласти розклад на понеділок?

 

12. Скільки є п'ятизначних чисел, які діляться на 5?

 

13. П'ять хлопчиків і 5 дівчаток сідають в ряд на 10 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити? Відповідь: (5!)∙(5!)

 

14. Скільки різних слів можна утворити переставлянням букв у слові «математика»? Відповідь: 10!/(3!∙2!∙2!)

 

15.Автомобільні номери складаються з однієї, двох або трьох букв і чотирьох цифр. Знайти число таких номерів, використовуючи 33 букви алфавіту.

 

16. В селищі мешкає 1500 жителів. Довести, що принаймні два з них мають однакові  ініціали.

 

17. Скільки різних дільників має число 6⁶∙7⁴?

 

18. Скільки тризначних чисел можна утворити з цифр 1, 2, 3, 4, 5, якщо кожну з цих цифр можна використовувати не більше одного разу? Відповідь: 5∙4∙3.

Скількома способами 7 осіб можуть розташуватись в чергу до каси? Відповідь: 7∙6∙8∙5∙4∙3∙2∙1.

 

19. В класі вивчають 10 предметів. В понеділок 6 уроків, причому всі
уроки різні. Скількома способами можна скласти розклад на понеділок?

Скільки є п'ятизначних чисел, які діляться на 5? Відповідь: 10∙9∙8∙7∙6∙5= 151200

 

20. П'ять хлопчиків і 5 дівчаток сідають в ряд не 10 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити? Відповідь: (5!)∙(5!)

 

21. Скільки різних слів можна утворити переставлянням букв у слові «арифметика»?

 

22. Автомобільні номери складаються з однієї, двох або трьох букв і чотирьох цифр. Знайти число таких номерів, використовуючи 30 букви алфавіту.

 

 

23. Скільки різних дільників має число 8³∙9⁴? Скласти таблицю всіх дільників цього числа.

 

24. Від А до В 999 км. Вздовж дороги стоять стовпи, на яких вказано відстані до А і до В | 0.999 | ; | 1.998| ; | 2.997] ; . . . ; | 999.0 |. Скільки серед них таких, на яких є тільки дві різні цифри? Відповідь: 40.

 

25. Пасажир залишив речі в автоматичній камері схову, а коли при­йшов одержувати речі, то виявилось, що він забув номер. Він лише па­м'ятає, що в номері були цифри 23 і 37. Щоб відкрити камеру, треба пра­вильно набрати п'ятизначний номер. Яку найбільшу кількість номерів треба перебрати, щоб відкрити камеру?

 

25. В прямокутній таблиці з m рядків і n стовпців записані числа +1 і -1 так, що добуток чисел в кожному рядку і кожному стовпці дорівнює 1. Скількома способами це можна зробити?

Відповідь: Всі таблиці, які мають вказану в умові задачі властивість, можна скласти так. Всюди, крім останнього рядка і останнього стовпця, до­вільно виписуємо +1 і –1. Це можна зробити 2^(n-1)(m-1) способами. Нехай р – добуток всіх виписаних чисел. Тепер в кожному з перших m -1  рядів на перетині з n-м стовпцем виписуємо +1 або –1 так, щоб добуток чисел в усьому рядку дорівнював 1. Позначимо добуток чисел, які будуть виписані в n-му рядку, через x. Тепер в кожному з перших n-1 стовпців на перетині з m-м рядком випишемо теж +1 або –1 тaк, щоб добуток в стовпці дорівнював 1. Добуток чисел, які будуть виписані в m-му рядку, позначимо через у. Зауважимо, що х і у мають однаковий знак. Справді, рх = 1, ру = 1. і тому р²ху = 1, і, значить, ху > 0. Випишемо на перетині т-го рядка і л-го стовпця 1 з тим знаком, який мають х і у. Тоді добуток чисел в n-му стовпці і m-му рядку також до­рівнюватиме 1. Склали таблицю, яка має вказану властивість. Число всіх  таких   таблиць   дорівнює  2^(n-1)(m-1).

26. На залізниці є десять семафорів, кожний з яких може передати три сигнали: червоний, жовтий, зелений. Скільки різних сигналів можна передати за допомогою усіх семафорів. Відповідь: 3^10.

 

27. Існує десять ліхтариків, кожен з яких може бути або включений, або виключений.Скільки різних сигналів можна передати за допомогою усіх ліхтарів? Відповідь: 2¹⁰.

 

28. Проста шашка знаходиться в крайньому нижньому лівому полі шахової дошки. Скількома різними способами вона може  пройти в дамки? Способи вважаються різними, якщо вони відміняються один від одного хоча б одним ходом.

Відповідь: На другу горизонталь шашка може перейти одним способом, на третю – двома, на четверту – трьома, на п’яту – шістьма, на шосту – дев’ятьма, на сьому горизонталь – двадцятьма способами, а пройти в дамки шашка може 35 способами.

 

29. У квадраті 3х3 клітинки верхня ліва точка позначена літерою А. Скільки можна побудувати трикутників, одною з вершин яких є точка А, а дві інші вершини – будь-які вершини квадратиків 1х1 даного квадрата? Відповідь: 25 трикутників.

 

 

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

 

Завдання 1. Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження кількості натуральних чисел, які не діляться на n, на m, на p на проміжку (q, h)') в залежності від введених натуральних чисел  k, m, n, p, h, q.

Реалізація.

import random

print('Алгоритм пошуку кількості натуральних чисел, які не діляться на n, на m, на p на проміжку (q, h)')

h=random.randint(2,500); print(' Нижня межа для проміжку чисел h=',h)

q=random.randint(500,1000); print('Верхня межа для проміжку чисел q=',q)

n=random.randint(2,9); print(' Перший дільник n=',n)

m=random.randint(10,19); print('Другий дільник m=',m)

p=random.randint(20,30); print(' Третій дільник p=',p)

w=0

for k in range(h,q):

    if not((k%n==0)or(k%m==0)or(k%p==0)):

        w+=1

print('Кількість чисел із ',q-h,' натуральних чисел на проміжку (',h,'; ', q,')')

print('які не діляться або на ',n,' або на ',m, ' або на ',p,' дорівнює', w)

v=0

for k in range(h,q):

    if (k%n==0)or(k%m==0)or(k%p==0):

        v+=1

print('Кількість чисел із ',q-h,' натуральних чисел на проміжку (',h,'; ', q,')')

print('які  діляться або на ',n,' або на ',m, ' або на ',p,' дорівнює', v)

a=[s for s in range(h,q) if ((s%n==0)or(s%m==0)or(s%p==0))]

print('Перелік натуральних чисел, які  діляться або на ',n,' або на ',m, ' або на ',p,' дорівнює',a)

 

Завдання 2. Якщо б школяр купив  k зошитів, то в нього залишилось  р гривень.  Якщо б школяр купив  k+4 зошитів, то в нього  не вистачило   q гривень.  Скільки грошей було у школяра?  Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження кількості грошей у школяра, в залежності від введених натуральних чисел  k, p, q.

Математична модель завдання 7:

X= 0,25*k*(p+q)+ p  гривень  у школяра

Реалізація.

import random

k=random.randint(1,999)

p=random.randint(1,25)

q=random.randint(1,50)

print('Кількість куплених зошитів k=',k, ' тоді залишок гривень', p)

print('Кількість куплених зошитів k+4=',k+4,'тоді недостаток гривень', q)

X=0.25*k*(p+q)+p

print('Вартість одного зошита ', (X-p)/k, 'гривень')

print('Кількість наявних гривень у хлопчика:', X)

 

Завдання 3.  Два рябих поросят та три полосатих  просят разом важать m  кг. А різниця у вазі між такою  ж кількістю поросят   k кг. Скільки важить окремо  рябе поросятко та окремо полосате порося, якщо два рябих поросят мають однакову вагу, і троє полосатих поросят мають однакову вагу?  Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження ваги чорного та білого поросят, в залежності від введених натуральних чисел  k, m.

Математична модель завдання 8:   

X= 0,25*(m-k) кг – вага рябого  порося

У= 0,5*(m+k) /3 кг – вага  полосатого порося

Реалізація.

import random

k=random.randint(35,48)

m=random.randint(2,6)

print('Разом вага 2х +3у  для 5-ти  поросят ', k)

print('Різниця |2х -3у | у вазі поросят ', m)

print('X= 0,5*(k-m) кг – вага рябого порося =', 0.25*(k-m))

print('У= 0,5*(m+k) кг – вага полосатого порося=', 0.5*(m+k)//3 )

 

Завдання 4. За один і той самий час велосипедист долає 1/m частину шляху, а другий велосипедист долає  1/k  частину того самого шляху.  Різниця між пройденими відстанями дорівює n км.  Який шлях повинен проїхати  велосипедист?  Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження довжини  усього шляху, в залежності від введених натуральних чисел  k, m, n.

Математична модель завдання 9:   

S= n*m*k/(m-k) км – весь шлях велосипедиста

Реалізація.

import random

k=random.randint(4,7)

m=random.randint(7,9)

n=random.randint(3,5)

print('Частина шляху 1-ого велосипедиста =', k)

print('Частина шляху 2-ого велосипедиста = ', m)

print('Різниця пройденого шляху між 1-им та 2-им велосипедистами = ', n)

print('S= n*m*k/(m-k) км – весь шлях велосипедиста =', n*m*k//abs(m-k))

print('Швидкість 1-го велосипедиста =', (n*m*k//abs(m-k))/k)

print('Швидкість 2-го велосипедиста =', (n*m*k//abs(m-k))/m)

 

Завдання 5. За 4 смартфони бізнесмен заплатив  електронною карткою. Усі чотири смартфони без першого  коштують m тис. гривень.  Усі чотири смартфони без другого  коштують  n тис. гривень.

Усі чотири смартфони без третього  коштують  k тис. гривень.  Усі чотири смартфони без четвертого  коштують  р тис. гривень.  Скільки коштували всі чотири смартфони. Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження вартості усіх чотирьох смартфонів разом, в залежності від введених натуральних чисел  k, m, n, p.

Математична модель завдання 10:    

S=(m+n+k+p)/3  тис. грн вартість усіх чотирьох смартфонів разом

Реалізація.

import random

k=random.randint(36,57)

m=random.randint(37,58)

n=random.randint(39,59)

p=random.randint(34,54)

print('S=(m+n+k+p)/3  тис. грн вартість усіх чотирьох смартфонів разом=', (m+n+k+p)//3,'тис. грн ' )

print('Вартість 1-го смартфона =', ((m+n+k+p)//3)-k,'тис. грн ' )

print('Вартість 2-го смартфона =', ((m+n+k+p)//3)-m,'тис. грн ' )

print('Вартість 3-го смартфона =', ((m+n+k+p)//3)-n,'тис. грн ' )

print('Вартість 4-го смартфона =', ((m+n+k+p)//3)-p,'тис. грн ' )

 

Завдання 6. У шаховому турнірі приймають участь k осіб. Кожний з кожним зіграв по  n партії. Скільки усіх зіграних шахових партій на турнірі? Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження кількості усіх зігранних шахових партій, в залежності від введених натуральних чисел  k.

 

Математична модель завдання 11:

M=0,5*n*k(k-1)  шахових партій,

Реалізація.

import random

k=random.randint(10,15)

n=random.randint(1,3)

print('Кількість шахматистів =',  k,'осіб' )

print('Кількість партій між двома шахматистами =',  n,'партій  гри в шахи' )

print('Кількість усіх шахових партій, зіграних усіма учасниками в турнірі=', n*k*(k-1)//2 ,'шахових партій' )

print('Кількість усіх шахових партій, зіграних одним учасником в турнірі=', n*(k-1) ,'шахових партій' )

 

Завдання 7.  Разом вага чотирьох заповнених контейнерів складає  m тон.  Вантаж для чотирьох контейнерів розподіляються у відношенні  p:g:k:n. Яка вага  кожного  заповненого контейнера? Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження ваги кожного контейнера, в залежності від введених натуральних чисел  p, g, k, n, m.

Математична модель завдання 12:

1)p*m/(p+g+n+k) тонн вага 1-ого контейнера

2)g*m/(p+g+n+k) тонн вага 2-oго контейнера

3)m*k/(p+g+n+k) тонн вага 3-ого контейнера

4)m*n/(p+g+n+k) тонн вага  4-oго контейнера

Реалізація.

Маючи математичну модель  створити алгоритм самостійно.

 

Завдання 8.   У Вінницю приїхало  m туристів. З них  k туристів не знають жодної іноземної мови,окрім англійської.  Розмовляють німецькою мовою n туристів. Розмовляють французькою мовою p туристів. Скільки серед туристів осіб, що знають дві мови: німецьку та французьку? Створити, реалізувати, протестувати алгоритм мовою програмування Python3 в середовищі програмування Thonny  для знаходження кількості двомовних туристів, в залежності від введених натуральних чисел  p, k, n, m.

Математична модель завдання 13:

Х=n+p-m+k.

Реалізація.

Маючи математичну модель  створити алгоритм самостійно.

 

Результат виконаної практичної роботи надіслати вашому учителю на електронну скриньку:  vinnser@gmail.com (Сергій Петрович)

*****

Додаткові завдання на розвиток кмітливості