✅ Обязательные задачи (LMS)#

Эти задачи нужно решить и сдать в LMS.

Задача 1. Ханойские башни#

Условие#

Головоломка «Ханойские башни» состоит из трёх стержней и N дисков разного размера. В начале все диски надеты на первый стержень в порядке убывания: самый большой внизу, самый маленький наверху. Нужно перенести всю пирамиду на третий стержень, соблюдая два правила:

за один ход перекладывается ровно один диск;
больший диск нельзя класть поверх меньшего.

Второй стержень можно использовать как вспомогательный. Определите, за какое наименьшее количество ходов это можно сделать.

Задачу нужно решить рекурсивно: реализуйте функцию int hanoi(int n), которая возвращает минимальное число ходов.

Входные данные#

Одно натуральное число N — количество дисков (1 ≤ N ≤ 30).

Выходные данные#

Одно число — минимальное количество ходов.

Пример#

Ввод:

Вывод:

Совет

Чтобы перенести N дисков, нужно перенести N − 1 дисков на вспомогательный стержень, переложить самый большой диск и снова перенести N − 1 дисков поверх него. Отсюда hanoi(n) = 2 * hanoi(n - 1) + 1, а база — hanoi(1) = 1.

Задача 2. Количество разменов#

Условие#

Даны три номинала монет a, b, c и сумма S. Определите, сколькими способами можно набрать сумму S этими монетами. Каждую монету можно использовать любое количество раз, порядок монет не важен.

Напишите функцию int count_ways(int a, int b, int c, int S), которая возвращает количество способов.

Входные данные#

Четыре натуральных числа a, b, c и S, записанных через пробел.

Выходные данные#

Одно число — количество способов размена.

Пример#

Ввод:

1 2 5 5

Вывод:

Заметка

Способы набрать 5: 5, 1 + 2 + 2, 1 + 1 + 1 + 2, 1 + 1 + 1 + 1 + 1. Перебирайте вложенными циклами количество монет номинала a и b, а остаток проверяйте на делимость на c: (S - i*a - j*b) % c == 0.

Задача 3. Наибольший общий делитель#

Условие#

Напишите рекурсивную функцию int gcd(int a, int b), которая вычисляет НОД двух чисел по алгоритму Евклида. С её помощью найдите НОД трёх чисел.

Входные данные#

Три натуральных числа.

Выходные данные#

Одно число — их наибольший общий делитель.

Пример#

Ввод:

36 48 60

Вывод:

Совет

Алгоритм Евклида: gcd(a, b) = gcd(b, a % b), база — gcd(a, 0) = a. Для трёх чисел используйте вложенный вызов: gcd(gcd(a, b), c).

Задача 4. Синхронизация времени (SNTP)#

Условие#

Клиент отправляет запрос на сервер и запоминает время отправления A. Сервер получает запрос в момент B (по часам сервера) и сразу отправляет клиенту ответ, в котором указано время B. Клиент получает ответ в момент C (по своим часам). Задержки в сети туда и обратно одинаковы.

Определите точное время, которое нужно установить на часах клиента в момент получения ответа.

Входные данные#

Три строки — временные метки A, B и C в формате hh:mm:ss.

Выходные данные#

Точное время в формате hh:mm:ss.

Пример#

Ввод:

15:01:00
18:09:45
15:01:40

Вывод:

18:10:05

Заметка

Запрос шёл туда и обратно C − A = 40 секунд, значит, в одну сторону — 20 секунд. Точное время: B + (C − A) / 2 = 18:09:45 + 20 = 18:10:05.

Совет

Считывайте время с разделителями: cin >> h >> sep >> m >> sep >> s;, где char sep.

Вынесите перевод в секунды в функцию int toSeconds(int h, int m, int s).

Время может перейти через полночь, поэтому используйте (x + 86400) % 86400.

Для ведущих нулей: setfill('0') << setw(2) из <iomanip>.

Задача 5. Бизнес-центр#

Условие#

Бизнес-центр — N-этажное здание. На каждом этаже работает ровно один сотрудник. Утром все сотрудники приезжают на парковку в подвале (на один этаж ниже первого).

Лифт один раз отвозит всех желающих на выбранный этаж X, тратя C секунд на каждый этаж пути. Дальше каждый сотрудник добирается до своего этажа пешком: подъём на один этаж занимает A секунд, спуск — B секунд. Сотрудник может и не пользоваться лифтом, а сразу пойти пешком вверх с парковки.

Найдите минимальное суммарное время: время работы лифта плюс время, которое все сотрудники тратят на дорогу.

Входные данные#

Четыре натуральных числа N, A, B, C.

Выходные данные#

Одно число — минимальное время.

Пример#

Ввод:

3 2 1 1

Вывод:

Заметка

Если лифт едет на 2-й этаж: лифт тратит 2 · 1 = 2 секунды, сотрудник 1-го этажа спускается за 1 секунду, сотрудник 2-го уже на месте, сотрудник 3-го поднимается за 2 секунды. Итого 2 + 1 + 0 + 2 = 5.

Совет

Переберите этаж X от 1 до N. Для каждого сотрудника i выберите лучшее из двух: пешком с парковки (i * A) или от этажа X на лифте. Используйте long long.

Задача 6. Числа Фибоначчи без циклов#

Условие#

Последовательность Фибоначчи задаётся так: a₀ = 0, a₁ = 1, aₖ = aₖ₋₁ + aₖ₋₂ при k > 1.

Найдите N-е число Фибоначчи. В программе запрещается использовать циклы.

Входные данные#

Одно целое неотрицательное число N (N ≤ 30).

Выходные данные#

Одно число — N-е число Фибоначчи.

Пример#

Ввод:

Вывод:

Заметка

Первые числа последовательности: 0, 1, 1, 2, 3, 5, 8, 13, ... Под номером 7 (считая с нуля) стоит 13. У рекурсивной функции две базы: n == 0 и n == 1.