Інформатика

Виконати вправу

Прочитайте!

Вкладені цикли

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

Поняття рекурсії

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

Основні елементи рекурсії:

1. Базовий випадок — умова, при виконанні якої рекурсія завершується. Без базового випадку програма зациклиться.
2. Рекурсивний виклик — виклик функції самою собою з іншим (зазвичай меншим) набором параметрів.

Рекурсія часто використовується для обчислення:

• Факторіалів;
• Чисел Фібоначчі;
• Розв’язання задач на обходи дерев і графів.

Рекурентні послідовності — це такі послідовності чисел, де кожен наступний елемент визначається через попередні.

Працюємо за ПК!

Задача 1. Використовуючи Алгоритм Евкліда знайдіть НСД двох чисел.

Як працює алгоритм:

1. Алгоритм Евкліда базується на наступному принципі:
   • НСД двох чисел a і b дорівнює НСД b і залишку від ділення a % b.
2. На кожному кроці ми замінюємо a на b, а b на залишок a % b, поки залишок не стане рівним нулю.
3. Коли залишок дорівнює нулю, значення a є НСД.

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

Оскільки він стоїть прямо поруч зупинок публічного транспорту, то знає, що найближчий автобус приїде через db​ хвилин, дорога на ньому займає tb​ хвилин, а дорога пішки від зупинки приїзду до торгового центру wb​ хвилин.

Петрику також доступне метро, очікування потягу у якому займає dm​ хвилин, поїздка tm​ хвилин, а дорога пішки від станції прибуття до торгового центру wm​ хвилин.

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

Підкажіть, будь ласка, Петрику, який транспорт йому краще використовувати, щоб потрапити у торговий центр як можна скоріше.

Якщо у Петрика є кілька можливих варіантів потрапити у торговий центр як можна скоріше, то він вибере найдешевший варіант. Автобус є дешевшим за метро, а метро є дешевшим за таксі.

Задача 3. Степан збирає речі у відпустку. З собою в літак він може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу – здоровенна валіза.

За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Степан готовий доплатити). Зрозуміло, найбільш цінні речі – ноутбук, фотоапарат, документи і т. д. – Степан хоче покласти в ручну поклажу.

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

Визначте вагу рюкзака і валізи після того, як Степан складе всі речі.

Розв’язання

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

Нехай vr – маса рюкзака і vv – маса валізи. Беремо перший предмет з масою r і перевіряємо, якщо vr+r не перевищує s, то збільшуємо vr на r, інакше vv збільшуємо на r.

Розглянемо алгоритм розв’язування задачі:

• ввести значення s та n, присвоїти значення 0 змінним vr і vv;
• за допомогою циклу та команди розгалуження обчислити vr і vv;
• вивести результат.

 Задача 4. Напишіть програму, яка буде підсумовувати числа, що вводяться з клавіатури до тих пір, доки вони від’ємні.