Інформатика 9 клас

inF | 9 клас |4 грудня

Тема:

Складання і виконання алгоритму упорядкування та пошуку значень у масиві.

Repl iT
Вправа
inF-Codes
Презентація 9 клас Урок 44Завантажити
import random
n=9
amax=99
a = []
for j in range(n):
    a.append(random.randint(1,amax))
print(a)
for j in range(n-1):
    for k in range(j+1,n):
        if a[j]>a[k]:
            a[j],a[k]=a[k],a[j]
print('Результат впорядкування цього масиву такий')
print(a)
Code language: Python (python)
Вправа 1. Сортування вибором з «кольоровою діаграмою» масиву
(алгоритм selection sort, різні кольори для всіх елементів)

Інструкція / пояснення
● Алгоритм: на кожному кроці шукається найменший елемент у правій частині масиву й міняється місцями з елементом на поточній позиції i.

Візуалізація:
● Кожен елемент — свій колір, щоб їх легко відрізняти.
● Поточна позиція i виділена зеленим.
● Знайдений мінімальний елемент для цього кроку виділений червоним.

Завдання для учня:
● Змінити розмір масиву n і межу значень amax.
● Прослідкувати, як змінюється масив на кожному кроці.
● Пояснити, скільки разів алгоритм порівнює елементи в гіршому випадку. 
import random

# Кольори ANSI
COLORS = [
    "\033[31m",  # червоний
    "\033[32m",  # зелений
    "\033[33m",  # жовтий
    "\033[34m",  # синій
    "\033[35m",  # пурпурний
    "\033[36m",  # блакитний
]
RESET = "\033[0m"
TITLE = "\033[96m"   # бірюзовий для заголовків
INFO = "\033[90m"    # сірий для службових повідомлень
H_MIN = "\033[91m"   # яскраво-червоний (мінімум на кроці)
H_I = "\033[92m"     # яскраво-зелений (поточна позиція)

n, amax = 10, 50
a = [random.randint(1, amax) for _ in range(n)]

def color_for_index(idx):
    """Повертає колір для елемента з індексом idx (циклічно)."""
    return COLORS[idx % len(COLORS)]

def show_array(arr, i=-1, min_i=-1, title=""):
    """Текстова «діаграма» з різнокольоровими стовпчиками."""
    if title:
        print(TITLE + title + RESET)
    m = max(arr)
    scale = max(1, m // 20)

    print(INFO + "Індекси: " + " ".join(f"{k:3}" for k in range(len(arr))) + RESET)
    print("Значення:", " ".join(f"{v:3}" for v in arr))
    print("Діаграма:")

    for idx, val in enumerate(arr):
        base_color = color_for_index(idx)
        if idx == i:
            color = H_I
        elif idx == min_i:
            color = H_MIN
        else:
            color = base_color
        bar = "█" * (val // scale)
        print(f"{color}{val:3} | {bar}{RESET}")
    print("-" * 40)

print(TITLE + "Сортування вибором (selection sort)" + RESET)
print("Початковий масив:", a)
show_array(a, title="Стартовий стан масиву")

for i in range(len(a) - 1):
    min_i = i
    for j in range(i + 1, len(a)):
        if a[j] < a[min_i]:
            min_i = j
    a[i], a[min_i] = a[min_i], a[i]
    show_array(a, i=i, min_i=min_i, title=f"Крок {i + 1}: мінімум перенесено на позицію {i}")

print(TITLE + "Результат сортування:" + RESET, a)
show_array(a, title="Фінальний вигляд масиву")

Code language: Python (python)
Зображення 1.1 - Сортування вибором з «кольоровою діаграмою» масиву
Вправа 2. Бульбашкове сортування з покроковим переглядом
(алгоритм bubble sort, різні кольори, порівнювані елементи виділяються)

Інструкція / пояснення
Алгоритм: на кожному проході по масиву сусідні елементи порівнюються і, якщо вони «не в порядку», міняються місцями. Найбільший елемент «спливає» в кінець.

Візуалізація:
● Кожен елемент свого кольору (як у Вправі 1).
● Пара порівнюваних елементів виділяється яскравим червоним і зеленим.
● Є запит input(), щоб переходити крок за кроком.

Завдання для учня:
● Відстежити, як змінюється масив протягом проходів.
● З’ясувати, на якому кроці масив стає впорядкованим.
import random

COLORS = [
    "\033[31m", "\033[32m", "\033[33m",
    "\033[34m", "\033[35m", "\033[36m",
]
RESET = "\033[0m"
TITLE = "\033[96m"
INFO = "\033[90m"
C_LEFT = "\033[91m"   # лівий елемент у порівнянні
C_RIGHT = "\033[92m"  # правий елемент у порівнянні

n, amax = 8, 40
a = [random.randint(1, amax) for _ in range(n)]

def color_for_index(idx):
    return COLORS[idx % len(COLORS)]

def show_array_line(arr, i=-1, j=-1, note=""):
    m = max(arr)
    scale = max(1, m // 10)

    if note:
        print(TITLE + note + RESET)

    print(INFO + "Індекси: " + " ".join(f"{k:3}" for k in range(len(arr))) + RESET)
    print("Значення:", " ".join(f"{v:3}" for v in arr))
    print("Стовпчики:")
    for idx, val in enumerate(arr):
        base_color = color_for_index(idx)
        if idx == i:
            color = C_LEFT
        elif idx == j:
            color = C_RIGHT
        else:
            color = base_color
        bar = "█" * (val // scale)
        print(f"{color}{bar:8}{RESET}", end=" ")
    print("\n" + "-" * 60)

print(TITLE + "Бульбашкове сортування (bubble sort)" + RESET)
show_array_line(a, note="Початковий стан масиву")
input(INFO + "Enter → почати сортування..." + RESET)

for i in range(len(a) - 1):
    swapped = False
    print(TITLE + f"Прохід {i + 1}" + RESET)
    for j in range(len(a) - 1 - i):
        show_array_line(a, i=j, j=j+1, note=f"Порівнюємо елементи з індексами {j} і {j+1}")
        if a[j] > a[j + 1]:
            print("\033[91mОбмін елементів\033[0m")
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
            show_array_line(a, i=j, j=j+1, note="Після обміну")
        else:
            print("\033[92mОбмін не потрібен\033[0m")
        input(INFO + "Enter → наступний крок..." + RESET)

    if not swapped:
        print("\033[92mМасив уже впорядкований. Дострокове завершення.\033[0m")
        break

print(TITLE + "Результат сортування:" + RESET, a)
show_array_line(a, note="Фінальний вигляд масиву")

Code language: Python (python)
Зображення 1.2 - Бульбашкове сортування з покроковим переглядом
Вправа 3. Порівняння двох алгоритмів з вибором і напрямом сортування
(короткий код, різні кольори для початкового і відсортованого стану)

Інструкція / пояснення
Алгоритми:
1 — бульбашкове сортування.
2 — сортування вставками (insertion sort).

Користувач обирає:
● Алгоритм.
● Напрям: за зростанням або за спаданням.

Візуалізація:
● Початковий масив — блакитні стовпчики.
● Відсортований масив — зелені стовпчики.
● Значення теж підсвічені, щоб було видно різницю.

Завдання для учня:
● Запустити програму кілька разів з різними параметрами.
● Порівняти час виконання для різних алгоритмів (хоча масив невеликий).
● Пояснити, у чому різниця між підходом bubble sort і insertion sort. 
import random, time

RESET = "\033[0m"
TITLE = "\033[96m"
INFO = "\033[90m"
C_INIT = "\033[36m"   # блакитний (початковий масив)
C_SORT = "\033[32m"   # зелений (відсортований масив)

n, amax = 12, 99
a = [random.randint(1, amax) for _ in range(n)]

def show_bars(arr, color, title):
    m = max(arr)
    scale = max(1, m // 25)
    print(TITLE + title + RESET)
    for v in arr:
        bar = "█" * (v // scale)
        print(f"{color}{v:3} | {bar}{RESET}")
    print("-" * 40)

def bubble(arr, rev=False):
    a = arr[:]
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if (a[j] > a[j+1]) != rev:
                a[j], a[j+1] = a[j+1], a[j]
    return a

def insertion(arr, rev=False):
    a = arr[:]
    for i in range(1, len(a)):
        k = a[i]
        j = i - 1
        while j >= 0 and ((a[j] > k) != rev):
            a[j+1] = a[j]
            j -= 1
        a[j+1] = k
    return a

print(TITLE + "Порівняння алгоритмів сортування" + RESET)
print("Початковий масив:", a)
show_bars(a, C_INIT, "Початковий вигляд масиву")

print("Оберіть алгоритм:")
print("1 – Бульбашкове сортування")
print("2 – Сортування вставками")
alg = input("Ваш вибір (1/2): ").strip()

print("Оберіть напрям:")
print("1 – за зростанням")
print("2 – за спаданням")
rev = (input("Ваш вибір (1/2): ").strip() == "2")

start = time.time()
if alg == "2":
    res = insertion(a, rev)
    name = "Сортування вставками"
else:
    res = bubble(a, rev)
    name = "Бульбашкове сортування"
t = time.time() - start

direction = "спадання" if rev else "зростання"
print(INFO + f"Алгоритм: {name}, напрям: {direction}" + RESET)
show_bars(res, C_SORT, "Відсортований масив")
print(INFO + f"Час виконання: {t:.6f} c" + RESET)
print(INFO + "Перевірка sorted(): " + RESET, sorted(a, reverse=rev))

Code language: Python (python)
Зображення 1.3 - Порівняння двох алгоритмів з вибором і напрямом сортування

Домашня робота
Вивчити з підручника: § 14 ст. ст. 164
та матеріал з презентації

inF | 9 клас |2 грудня

Тема:

Алгоритми впорядкування масиву.

Repl iT
Вправа
inF-Codes
Презентація 9 клас Урок 44Завантажити
import random
n=9
amax=99
a = []
for j in range(n):
    a.append(random.randint(1,amax))
print(a)
for j in range(n-1):
    for k in range(j+1,n):
        if a[j]>a[k]:
            a[j],a[k]=a[k],a[j]
print('Результат впорядкування цього масиву такий')
print(a)
Code language: Python (python)
Вправа 1. Сортування вибором з «кольоровою діаграмою» масиву
(алгоритм selection sort, різні кольори для всіх елементів)

Інструкція / пояснення
● Алгоритм: на кожному кроці шукається найменший елемент у правій частині масиву й міняється місцями з елементом на поточній позиції i.

Візуалізація:
● Кожен елемент — свій колір, щоб їх легко відрізняти.
● Поточна позиція i виділена зеленим.
● Знайдений мінімальний елемент для цього кроку виділений червоним.

Завдання для учня:
● Змінити розмір масиву n і межу значень amax.
● Прослідкувати, як змінюється масив на кожному кроці.
● Пояснити, скільки разів алгоритм порівнює елементи в гіршому випадку. 
import random

# Кольори ANSI
COLORS = [
    "\033[31m",  # червоний
    "\033[32m",  # зелений
    "\033[33m",  # жовтий
    "\033[34m",  # синій
    "\033[35m",  # пурпурний
    "\033[36m",  # блакитний
]
RESET = "\033[0m"
TITLE = "\033[96m"   # бірюзовий для заголовків
INFO = "\033[90m"    # сірий для службових повідомлень
H_MIN = "\033[91m"   # яскраво-червоний (мінімум на кроці)
H_I = "\033[92m"     # яскраво-зелений (поточна позиція)

n, amax = 10, 50
a = [random.randint(1, amax) for _ in range(n)]

def color_for_index(idx):
    """Повертає колір для елемента з індексом idx (циклічно)."""
    return COLORS[idx % len(COLORS)]

def show_array(arr, i=-1, min_i=-1, title=""):
    """Текстова «діаграма» з різнокольоровими стовпчиками."""
    if title:
        print(TITLE + title + RESET)
    m = max(arr)
    scale = max(1, m // 20)

    print(INFO + "Індекси: " + " ".join(f"{k:3}" for k in range(len(arr))) + RESET)
    print("Значення:", " ".join(f"{v:3}" for v in arr))
    print("Діаграма:")

    for idx, val in enumerate(arr):
        base_color = color_for_index(idx)
        if idx == i:
            color = H_I
        elif idx == min_i:
            color = H_MIN
        else:
            color = base_color
        bar = "█" * (val // scale)
        print(f"{color}{val:3} | {bar}{RESET}")
    print("-" * 40)

print(TITLE + "Сортування вибором (selection sort)" + RESET)
print("Початковий масив:", a)
show_array(a, title="Стартовий стан масиву")

for i in range(len(a) - 1):
    min_i = i
    for j in range(i + 1, len(a)):
        if a[j] < a[min_i]:
            min_i = j
    a[i], a[min_i] = a[min_i], a[i]
    show_array(a, i=i, min_i=min_i, title=f"Крок {i + 1}: мінімум перенесено на позицію {i}")

print(TITLE + "Результат сортування:" + RESET, a)
show_array(a, title="Фінальний вигляд масиву")

Code language: Python (python)
Зображення 1.1 - Сортування вибором з «кольоровою діаграмою» масиву
Вправа 2. Бульбашкове сортування з покроковим переглядом
(алгоритм bubble sort, різні кольори, порівнювані елементи виділяються)

Інструкція / пояснення
Алгоритм: на кожному проході по масиву сусідні елементи порівнюються і, якщо вони «не в порядку», міняються місцями. Найбільший елемент «спливає» в кінець.

Візуалізація:
● Кожен елемент свого кольору (як у Вправі 1).
● Пара порівнюваних елементів виділяється яскравим червоним і зеленим.
● Є запит input(), щоб переходити крок за кроком.

Завдання для учня:
● Відстежити, як змінюється масив протягом проходів.
● З’ясувати, на якому кроці масив стає впорядкованим.
import random

COLORS = [
    "\033[31m", "\033[32m", "\033[33m",
    "\033[34m", "\033[35m", "\033[36m",
]
RESET = "\033[0m"
TITLE = "\033[96m"
INFO = "\033[90m"
C_LEFT = "\033[91m"   # лівий елемент у порівнянні
C_RIGHT = "\033[92m"  # правий елемент у порівнянні

n, amax = 8, 40
a = [random.randint(1, amax) for _ in range(n)]

def color_for_index(idx):
    return COLORS[idx % len(COLORS)]

def show_array_line(arr, i=-1, j=-1, note=""):
    m = max(arr)
    scale = max(1, m // 10)

    if note:
        print(TITLE + note + RESET)

    print(INFO + "Індекси: " + " ".join(f"{k:3}" for k in range(len(arr))) + RESET)
    print("Значення:", " ".join(f"{v:3}" for v in arr))
    print("Стовпчики:")
    for idx, val in enumerate(arr):
        base_color = color_for_index(idx)
        if idx == i:
            color = C_LEFT
        elif idx == j:
            color = C_RIGHT
        else:
            color = base_color
        bar = "█" * (val // scale)
        print(f"{color}{bar:8}{RESET}", end=" ")
    print("\n" + "-" * 60)

print(TITLE + "Бульбашкове сортування (bubble sort)" + RESET)
show_array_line(a, note="Початковий стан масиву")
input(INFO + "Enter → почати сортування..." + RESET)

for i in range(len(a) - 1):
    swapped = False
    print(TITLE + f"Прохід {i + 1}" + RESET)
    for j in range(len(a) - 1 - i):
        show_array_line(a, i=j, j=j+1, note=f"Порівнюємо елементи з індексами {j} і {j+1}")
        if a[j] > a[j + 1]:
            print("\033[91mОбмін елементів\033[0m")
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
            show_array_line(a, i=j, j=j+1, note="Після обміну")
        else:
            print("\033[92mОбмін не потрібен\033[0m")
        input(INFO + "Enter → наступний крок..." + RESET)

    if not swapped:
        print("\033[92mМасив уже впорядкований. Дострокове завершення.\033[0m")
        break

print(TITLE + "Результат сортування:" + RESET, a)
show_array_line(a, note="Фінальний вигляд масиву")

Code language: Python (python)
Зображення 1.2 - Бульбашкове сортування з покроковим переглядом
Вправа 3. Порівняння двох алгоритмів з вибором і напрямом сортування
(короткий код, різні кольори для початкового і відсортованого стану)

Інструкція / пояснення
Алгоритми:
1 — бульбашкове сортування.
2 — сортування вставками (insertion sort).

Користувач обирає:
● Алгоритм.
● Напрям: за зростанням або за спаданням.

Візуалізація:
● Початковий масив — блакитні стовпчики.
● Відсортований масив — зелені стовпчики.
● Значення теж підсвічені, щоб було видно різницю.

Завдання для учня:
● Запустити програму кілька разів з різними параметрами.
● Порівняти час виконання для різних алгоритмів (хоча масив невеликий).
● Пояснити, у чому різниця між підходом bubble sort і insertion sort. 
import random, time

RESET = "\033[0m"
TITLE = "\033[96m"
INFO = "\033[90m"
C_INIT = "\033[36m"   # блакитний (початковий масив)
C_SORT = "\033[32m"   # зелений (відсортований масив)

n, amax = 12, 99
a = [random.randint(1, amax) for _ in range(n)]

def show_bars(arr, color, title):
    m = max(arr)
    scale = max(1, m // 25)
    print(TITLE + title + RESET)
    for v in arr:
        bar = "█" * (v // scale)
        print(f"{color}{v:3} | {bar}{RESET}")
    print("-" * 40)

def bubble(arr, rev=False):
    a = arr[:]
    for i in range(len(a) - 1):
        for j in range(len(a) - 1 - i):
            if (a[j] > a[j+1]) != rev:
                a[j], a[j+1] = a[j+1], a[j]
    return a

def insertion(arr, rev=False):
    a = arr[:]
    for i in range(1, len(a)):
        k = a[i]
        j = i - 1
        while j >= 0 and ((a[j] > k) != rev):
            a[j+1] = a[j]
            j -= 1
        a[j+1] = k
    return a

print(TITLE + "Порівняння алгоритмів сортування" + RESET)
print("Початковий масив:", a)
show_bars(a, C_INIT, "Початковий вигляд масиву")

print("Оберіть алгоритм:")
print("1 – Бульбашкове сортування")
print("2 – Сортування вставками")
alg = input("Ваш вибір (1/2): ").strip()

print("Оберіть напрям:")
print("1 – за зростанням")
print("2 – за спаданням")
rev = (input("Ваш вибір (1/2): ").strip() == "2")

start = time.time()
if alg == "2":
    res = insertion(a, rev)
    name = "Сортування вставками"
else:
    res = bubble(a, rev)
    name = "Бульбашкове сортування"
t = time.time() - start

direction = "спадання" if rev else "зростання"
print(INFO + f"Алгоритм: {name}, напрям: {direction}" + RESET)
show_bars(res, C_SORT, "Відсортований масив")
print(INFO + f"Час виконання: {t:.6f} c" + RESET)
print(INFO + "Перевірка sorted(): " + RESET, sorted(a, reverse=rev))

Code language: Python (python)
Зображення 1.3 - Порівняння двох алгоритмів з вибором і напрямом сортування

Домашня робота
Вивчити з підручника: § 14 ст. ст. 159-162
та матеріал з презентації

Pages: 1 2 3 4 5 6 7