ГДЗ по информатике, 11 класс, Босова, номер 5.4: Основные сведения об алгоритмах

План решения.

Нам нужно отмерить ровно 7 минут с помощью песочных часов на 3 и 8 минут. Логика задачи строится на разнице во времени: если мы запустим часы одновременно, то в момент, когда закончатся меньшие часы (через 3 минуты), большие часы будут показывать остаток 5 минут (8-3=5). Если мы перевернем большие часы в этот момент, они начнут отсчитывать эти оставшиеся 5 минут заново. Но нам нужно 7. Попробуем другой путь: сумма 3+3+... или разница 8-.... Давайте проанализируем возможные комбинации: 1) 8-3=5 минут. 2) 3+3=6 минут. 3) 8-(3+3)? Нет, так не получится напрямую. 4) А что если использовать переливание? Запустим оба часа. Когда закончатся 3-минутные, перевернем их снова. Когда закончатся 8-минутные, сколько прошло времени? Ровно 8 минут. В этот момент 3-минутные часы были перевернуты один раз (в момент t=3) и сейчас идут второй цикл. Сколько осталось до конца второго цикла 3-минутных часов? Второй цикл начался в t=3, значит к t=8 он шел 8-3=5 минут. До конца ему осталось 3-5... стоп, это невозможно, так как 5 больше 3. Значит, к моменту t=8 трехминутные часы уже дважды переворачивались? Пересмотрим стратегию. Нам нужно получить 7. Заметим, что 7=8-1. Как получить 1 минуту? Или 7=3+4. Как получить 4 минуты? Или 7=10-3. Как получить 10 минут? 8+(10-8)... Попробуем алгоритм «отсечки»: 1. Запускаем часы на 3 и 8 минут одновременно. 2. Ждем, пока закончатся часы на 3 минуты (прошло t=3). Перевергиваем их сразу же. 3. Ждем, пока закончатся часы на 8 минут (прошло t=8). В этот момент часы на 3 минуты шли второй раз с момента t=3, то есть они отработали 8-3=5 минут из своих 3? Нет, они бы закончились раньше. Значит, к моменту t=8 трехминутные часы успели закончиться еще раз в t=6 и были перевернуты в третий раз (если мы следим за ними постоянно). Давайте будем внимательнее. Исполнитель Колдун может только переворачивать часы и ждать сигнала об окончании. Попробуем такой вариант: 1. Запускаем часы на 3 и 8 мин. 2. Через 3 мин (кончилось 3-х) переворачиваем 3-х. 3. Через 6 мин (кончилось 3-х во второй раз) переворачиваем 3-х. 4. Через 8 мин (кончилось 8-ми). В этот момент 3-х часы идут третий раз и прошли 8-6=2 минуты. Значит, в них осталось сыпаться 3-2=1 минута. 5. Переворачиваем 8-ми часы (они пустые, начинаем новый цикл на 8 мин). 6. Ждем, пока кончатся 3-х часы (пройдет еще 1 минута, всего с начала 9 мин). В этот момент в 8-ми часах прошло 1 минута, осталось 7. 7. Это сложно для эликсира, который варится непрерывно. Есть более простое решение через сумму: 7=3+3+1? Нет. 7=8-1. Как отмерить 1 минуту? Запустить 3 и 8. Когда кончатся 3 (t=3), перевернуть 3. Когда кончатся 8 (t=8), в 3-х часах прошло 8-3=5 минут? Нет, они бы закончились в t=6. Значит, в t=8 они идут третий раз и прошло 8-6=2 минуты. Осталось 1 минута до конца. Если в момент t=8 (когда кончились 8-минутные) мы перевернем 3-минутные часы, то они пойдут обратно. В них было 2 минуты снизу, 1 сверху. После переворота сверху станет 2 минуты, снизу 1. Они будут идти 2 минуты. Это не дает 7. А вот классический способ для 7 минут: 1. Запускаем часы на 3 и 8 минут одновременно. 2. Ждем окончания 3-минутных часов (t=3). Перевергиваем их. 3. Ждем окончания 3-минутных часов (t=6). Перевергиваем их. 4. Ждем окончания 8-минутных часов (t=8). В этот момент 3-минутные часы идут третий раз и отработали 8-6=2 минуты. Значит, в верхней части осталось 1 минута песка. 5. Важный шаг: В момент t=8 перевергиваем 8-минутные часы (запускаем новый цикл на 8 мин) И НЕ трогаем 3-минутные. 6. Ждем окончания 3-минутных часов. Пройдет 1 минута (до t=9). В этот момент в 8-минутных часах прошло 1 минута, осталось 7. 7. Теперь перевергиваем 8-минутные часы. Песок, который был внизу (1 минута), оказывается вверху. Часы начинают отсчитывать эту 1 минуту вниз? Нет, если перевернуть часы, где прошло 1 минута из 8, то в нижней части будет 1 минута песка, в верхней 7. При перевороте верхняя часть (7 мин) окажется внизу, а нижняя (1 мин) вверху. Часы будут идти 7 минут, пока весь песок из верхней части (которая теперь внизу?) нет, давайте физически. Часы на 8 мин. Прошло 1 мин. Снизу 1 мин песка, сверху 7 мин. Перевернули. Теперь сверху 1 мин, снизу 7 мин. Они будут идти 1 минуту, пока весь песок не упадет вниз. Это не 7 минут. Нужен другой подход. 7=3+4. Как получить 4? 4=8/2? Нет. 4=3+1. Попробуем систему команд: Команды исполнителя: `START_3`, `START_8`, `FLIP_3`, `FLIP_8`, `WAIT_END_3`, `WAIT_END_8`. Решение: 1. Запускаем часы на 3 и 8 минут (`START_3`, `START_8`). 2. Ждем окончания 3-минутных часов (`WAIT_END_3`). Время t=3. Перевергиваем их (`FLIP_3`). 3. Ждем окончания 3-минутных часов (`WAIT_END_3`). Время t=6. Перевергиваем их (`FLIP_3`). 4. Ждем окончания 8-минутных часов (`WAIT_END_8`). Время t=8. В этот момент 3-минутные часы идут третий раз и прошли 8-6=2 минуты. Значит, до их окончания осталось 1 минута. 5. Перевергиваем 8-минутные часы (`FLIP_8`). Они начинают новый цикл на 8 минут. 6. Ждем окончания 3-минутных часов (`WAIT_END_3`). Время t=9. Прошла 1 минута после шага 5. В 8-минутных часах прошло 1 минута, осталось 7 минут до полного истечения. 7. Перевергиваем 8-минутные часы (`FLIP_8`). *Физика процесса:* В часах на 8 мин прошло 1 минута. Значит, в нижней колбе 1 минута песка, в верхней 7 минут. При перевороте в верхней колбе оказывается 1 минута, в нижней 7 минут. Часы будут идти, пока весь песок из верхней колбы не пересыплется в нижнюю. То есть они будут идти ровно 1 минуту . Это не то, что нам нужно. Мы хотим сварить эликсир 7 минут. Значит, нам нужно начать варку в какой-то момент и остановить через 7 минут. Вернемся к шагу 6. В момент t=9 у нас есть часы на 8 минут, в которых прошло 1 минута (осталось 7). Если мы просто оставим их идти, они досыпаются через 7 минут (к t=16). Но эликсир должен вариться непрерывно. Мы можем начать варку в момент t=9 и закончить в момент t=16? Да! В момент t=9 мы знаем, что в больших часах осталось ровно 7 минут песка. Если мы поставим котел под огонь в этот момент и снимем его, когда большие часы опустеют, то время варки составит ровно 7 минут. Но нужно ли переворачивать маленькие часы? Нет, они уже закончились. Проверка логики: 1. t=0: Старт 3 и 8. 2. t=3: Конец 3. Флип 3. 3. t=6: Конец 3. Флип 3. 4. t=8: Конец 8. Флип 8 (старт нового цикла). 5. t=9: Конец 3 (так как с t=6 прошло 3 мин? Нет. С t=6 флипнули. К t=8 прошло 2 мин. К t=9 пройдет 3 мин. Да, конец 3). В момент t=9: Большие часы (флипнутые в t=8) идут первый раз. Прошло 9-8=1 минута. Значит, в них осталось 8-1=7 минут. 6. Действие: Ставим эликсир на огонь в момент t=9. Ждем, пока закончатся большие часы. 7. t=16: Конец больших часов. Снимаем эликсир. Время варки: 16-9=7 минут. Это работает! Система команд для исполнителя Колдуна:

• ЗАПУСТИТЬ(часы) — переворачивает часы, чтобы песок начал течь.
• ЖДАТЬ_КОНЦА(часы) — блокирует выполнение до момента, когда песок в указанных часах полностью пересыплется.
• НАЧАТЬ_ВАРКУ() — ставит котел на огонь.
• ЗАКОНЧИТЬ_ВАРКУ() — снимает котел с огня.

1. ЗАПУСТИТЬ(3); ЗАПУСТИТЬ(8).
2. ЖДАТЬ_КОНЦА(3); ЗАПУСТИТЬ(3).
3. ЖДАТЬ_КОНЦА(3); ЗАПУСТИТЬ(3).
4. ЖДАТЬ_КОНЦА(8); ЗАПУСТИТЬ(8).
5. ЖДАТЬ_КОНЦА(3); НАЧАТЬ_ВАРКУ().
6. ЖДАТЬ_КОНЦА(8); ЗАКОНЧИТЬ_ВАРКУ().

• t=0: Запуск обоих часов.
• t=3: Закончились 3-минутные. Перезапуск. 8-минутные продолжают идти (осталось 5).
• t=6: Закончились 3-минутные (второй цикл). Перезапуск. 8-минутные продолжают идти (осталось 2).
• t=8: Закончились 8-минутные. Перезапуск (новый цикл на 8 мин). 3-минутные идут третий цикл, прошло 8-6=2 мин, осталось 1 мин.
• t=9: Закончились 3-минутные. В этот момент 8-минутные часы (перезапущенные в t=8) идут ровно 1 минуту. Значит, в них осталось 8-1=7 минут песка. Начинаем варку.
• t=16: Закончились 8-минутные часы. Варка длилась 16-9=7 минут. Условие выполнено.