Для реалізації однозв'язного списку (приклад реалізації можна взяти з конспекту) необхідно:
- Написати функцію, яка реалізує реверсування однозв'язного списку, змінюючи посилання між вузлами;
- Розробити алгоритм сортування для однозв'язного списку, наприклад, сортування вставками або злиттям;
- Написати функцію, що об'єднує два відсортовані однозв'язні списки в один відсортований список.
Необхідно написати програму на Python, яка використовує рекурсію для створення фрактала “дерево Піфагора”.
Розробіть алгоритм Дейкстри для знаходження найкоротших шляхів у зваженому графі, використовуючи бінарну купу.
- Виконайте аналіз коду, щоб зрозуміти, як він працює
- Побудуйте функцію, що буде візуалізувати бінарну купу.
Необхідно створити програму на Python, яка візуалізує обходи дерева: у глибину та в ширину.
Код містить два основних методи обходу дерева: DFS (обхід в глибину) та BFS (обхід в ширину). DFS використовує рекурсію, тоді як BFS використовує чергу. DFS викликає функцію для кожного вузла порядку "вглиб", тоді як BFS відвідує всі вузли на одному рівні перед переходом на наступний рівень.
Необхідно написати програму на Python, яка використовує два підходи — жадібний алгоритм та алгоритм динамічного програмування для розв’язання задачі вибору їжі з найбільшою сумарною калорійністю в межах обмеженого бюджету.
Жадібний алгоритм вибирає елементи з найбільшим співвідношенням калорій до вартості на кожному кроці, що може призвести до підбору неоптимального набору страв. Динамічне програмування розв'язує задачу оптимально, обчислюючи найкращий набір страв для максимізації калорійності при заданому бюджеті, враховуючи всі можливі комбінації. Це дозволяє знайти оптимальний результат, але вимагає більше обчислювальних ресурсів. Отже, різниця полягає в тому, що жадібний алгоритм може дати швидкий результат, але не завжди оптимальний, тоді як динамічне програмування гарантує знаходження оптимального рішення за рахунок більш складного обчислення.
Необхідно написати програму на Python, яка імітує велику кількість кидків кубиків, обчислює суми чисел, які випадають на кубиках, і визначає ймовірність кожної можливої суми використовуючи метод Монте-Карло.
Використавуючи алгорит Монте-Карло на симуляціїї кидків кубиків 10000 разів ми бачимо що а умови достатньої кількості симуляцій, результати, отримані методом Монте-Карло, будуть дуже близькими до аналітичних розрахунків. Розбіжності, якщо вони і будуть, мають бути мінімальними і зумовлені лише випадковістю симуляцій. Для перевірки правильності розрахунків можна порівняти отримані ймовірності з аналітично обчисленими. Наприклад, ймовірність отримати суму 7 має бути найвищою і становити (6/36 = 1/6 \approx 0.1667) або 16.67%.