1 of 22

Розв’язування задач перебору за допомогою вкладених циклів

Нова українська школа

Урок 43

Інформатика 6

teach-inf.com.ua

за підручником

Бондаренко О.О. та ін.

2 of 22

Розв’язування задач перебору�за допомогою вкладених циклів

Вкладення циклів широко використовують під час

складання алгоритмів розв’язування арифметичних задач методом перебору можливих значень.

Розділ 6

§ 37

3 of 22

Метод перебору варіантів

На уроках математики корінь рівняння 3x + 4 = 15 знаходять у такий спосіб: x = (15 – 4)/3.

У програмуванні інший спосіб пошуку невідомої величини — метод перебору значень.

Розділ 6

§ 37

4 of 22

Метод перебору варіантів

Розглянемо, як застосовується метод перебору значень.

При цьому перебираються можливі цілі значення х із обмеженого діапазону і підставляються в рівняння. Відповіддю є таке значення х, за якого рівняння перетворюється на рівність.

Розділ 6

§ 37

5 of 22

Метод перебору варіантів

Розгляньте приклад 1

Складемо програму для знаходження сторін прямокутника:

Позначимо сторони прямокутника змінними а і b. Тоді b = а+4, а периметр дорівнює 2*(а+b) = 2*(2а+4).

периметр прямокутника становить

20

одна зі сторін

більша від іншої

на 4 см

Розділ 6

§ 37

6 of 22

Метод перебору варіантів

(Продовження…) Розгляньте приклад 1

Зрозуміло, що значення а може бути більше за 0, але менше від 10 (половини периметра).

а = 3 b = 7

for а in range(10):

if 2*(2*а+4) == 20:

print('а =', а, 'b =', а+4)

У циклі переберемо значення а зі вказаного діапазону. Відповіддю буде таке значення а, за якого 2*(2а+4) = 20

Розділ 6

§ 37

7 of 22

Метод перебору варіантів

Розгляньте приклад 2

Складемо програму для розв’язування задачі.

Визначимо, скільки в клітці фазанів і кролів, якщо всього в ній 35 голів і 94 ноги.

Розділ 6

§ 37

8 of 22

Метод перебору варіантів

Нехай,

кількість фазанів

х

кількість кролів

у

Тоді х + у = 35. Відомо, що,

у фазанів

у кролів

2 ноги

4 ноги

Тому 2x + 4y = 94. Зверніть увагу на те, що ці дві умови мають виконуватись одночасно, тобто утворюють складену умову.

Фазанів може бути

від 0 до 35

Кролів теж може бути

від 0 до 35

Розділ 6

§ 37

9 of 22

Метод перебору варіантів

(Продовження…) Розгляньте приклад 2

Організуємо перебір варіантів:

x = 23

y = 12

for x in range(0, 36):

for y in range(0, 36):

if (2*x+4*y == 94) and (x+y == 35):

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

Програмний код

Отримуємо єдину відповідь:

Розділ 6

§ 37

10 of 22

Метод перебору варіантів

Розгляньте приклад 3

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

Розділ 6

§ 37

11 of 22

Метод перебору варіантів

Для розв’язування задачі можна перебрати всі можливі сполучення цифр, з яких утворюється десятковий запис трицифрового числа, і перевіряти для кожного сполучення умову задачі.

123

132

213

231

312

321

k = 6

k = 0

for a in range(1, 10): # Першою може бути цифра від 1 до 9

for b in range(10): # На другому й третьому місцях

for c in range(10): # можуть стояти цифри від 0 до 9

if a+b+c == a*b*c:

k = k+1

print(100*a+10*b+c)

print('k =', k)

Розділ 6

§ 37

12 of 22

Метод перебору варіантів

У цьому коді цикл із параметром с є тілом

k = 0

for a in range(1, 10):

for b in range(10):

for c in range(10):

if a+b+c == a*b*c:

k = k+1

print(100*a+10*b+c)

print('k =', k)

циклу з параметром b, а той, у свою чергу, є тілом

циклу з параметром а

Розділ 6

§ 37

13 of 22

Пошук простих чисел у заданому діапазоні

Розгляньте приклад 4

Знайдемо прості числа в діапазоні від 2 до 30. (Простими є числа, крім 1, які діляться без остачі тільки на 1 і на самого себе.)

2 просте число

3 просте число

5 просте число

7 просте число

11 просте число

13 просте число

17 просте число

19 просте число

23 просте число

29 просте число

Щасти Вам!

for i in range(2, 30):

j = 2

prap = 0

while(j <= (i/2)):

if i%j == 0: prap = 1

j = j+1

if prap == 0: print(i, 'просте число')

print('Щасти Вам!')

Розділ 6

§ 37

14 of 22

Пошук простих чисел у заданому діапазоні

Проаналізуємо програмний код.

for i in range(2, 30):

j = 2

prap = 0

while(j <= (i/2)):

if i%j == 0: prap = 1

j = j+1

if prap == 0: print(i, 'просте число')

print('Щасти Вам!')

У зовнішньому циклі параметр і послідовно набуває значень від 2 до 30.

Розділ 6

§ 37

15 of 22

Пошук простих чисел у заданому діапазоні

for i in range(2, 30):

j = 2

prap = 0

while(j <= (i/2)):

if i%j == 0: prap = 1

j = j+1

if prap == 0: print(i, 'просте число')

print('Щасти Вам!')

Прапорцева змінна prap отримує значення 0 перед початком опрацювання чергового числа і із заданого діапазону.

Розділ 6

§ 37

16 of 22

Пошук простих чисел у заданому діапазоні

for i in range(2, 30):

j = 2

prap = 0

while(j <= (i/2)):

if i%j == 0: prap = 1

j = j+1

if prap == 0: print(i, 'просте число')

print('Щасти Вам!')

У тілі внутрішнього циклу змінна j послідовно набуває значень від 2 до і//2 і перевіряється, чи є число j дільником числа і.

Розділ 6

§ 37

17 of 22

Пошук простих чисел у заданому діапазоні

for i in range(2, 30):

j = 2

prap = 0

while(j <= (i/2)):

if i%j == 0: prap = 1

j = j+1

if prap == 0: print(i, 'просте число')

print('Щасти Вам!')

Якщо хоча б раз виконалась умова i%j == 0, тобто знайшовся хоча б один дільник числа і, змінна ргар набуває значення 1.

Розділ 6

§ 37

18 of 22

Пошук простих чисел у заданому діапазоні

for i in range(2, 30):

j = 2

prap = 0

while(j <= (i/2)):

if i%j == 0: prap = 1

j = j+1

if prap == 0: print(i, 'просте число')

print('Щасти Вам!')

Якщо після закінчення роботи внутрішнього циклу ргар = 0, це означає, що жодного дільника для числа і не виявилося.

Розділ 6

§ 37

19 of 22

Питання для самоперевірки

Що буде виведено на екран під час виконання програмного коду?

Складіть програму для розв’язування задачі. Знайдіть усі двоцифрові числа, що діляться на добуток їхніх цифр.

Складіть програму для розв’язування задачі. Діти зібрали 174 кг яблук. Кожен хлопець зібрав по 21 кг, а кожна дівчина по 15 кг. Скільки хлопців і дівчат збирали яблука?

for i in range(1, 10):

for j in range(1, 10):

print(i, '*', j, ' = ', i*j)

Розділ 6

§ 37

20 of 22

Домашнє завдання

Проаналізувати

с. 235-240

Розділ 6

§ 37

21 of 22

Працюємо за комп’ютером

Сторінка

239-240

Розділ 6

§ 37

22 of 22

Дякую за увагу!

Нова українська школа

Урок 43

Інформатика 6

teach-inf.com.ua

за підручником

Бондаренко О.О. та ін.