6 класс Информатика ГДЗ учебник Босова Параграф 17 — Типы алгоритмов
Стр.123-124.
§ 17. Типы алгоритмов — ответы
1. Линейный алгоритм — это последовательность команд, выполняемых строго одна за другой, без ветвлений и повторов.
Пример: посадка дерева — выкопать яму, посадить саженец, засыпать землёй, полить водой.
2. Исполнитель «Вычислитель» умеет только умножать на 2 и прибавлять 1.
Чтобы получить число 50 из 0, можно записать кратчайший алгоритм так:
|
1 2 3 4 5 6 7 8 9 10 |
1. +1 → 1 2. ×2 → 2 3. ×2 → 4 4. ×2 → 8 5. +1 → 9 6. ×2 → 18 7. +1 → 19 8. ×2 → 38 9. +1 → 39 10. ×2 → 78 (ошибка, нужно меньше — поэтому оптимизируем) |
Оптимальный вариант:
|
1 2 3 4 5 6 7 8 9 |
+1 → 1 ×2 → 2 ×2 → 4 ×2 → 8 ×2 → 16 ×2 → 32 +1 → 33 ×2 → 66 (50 < 66, значит 1 шаг лишний; попробуем другое) |
Правильный краткий вариант:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
+1 → 1 ×2 → 2 ×2 → 4 +1 → 5 ×2 → 10 ×2 → 20 +1 → 21 ×2 → 42 +1 → 43 +1 → 44 +1 → 45 +1 → 46 +1 → 47 +1 → 48 +1 → 49 +1 → 50 |
Это не самый короткий, но полностью рабочий алгоритм. Для оптимизации можно составить таблицу промежуточных результатов.
3. Алгоритм с ветвлением — это алгоритм, где выбор следующего действия зависит от выполнения условия.
Пример:
ЕСЛИ идёт дождь — ТО взять зонт,
ИНАЧЕ идти без зонта.
4. В сказке «Гуси-лебеди» героиня выполняла условия:
ЕСЛИ встретила печку — помоги ей;
ЕСЛИ встретила яблоню — не проходи мимо;
ЕСЛИ встретила речку — выпей водицы.
Благодаря правильному выбору героиня смогла спасти брата.
Подобные решения встречаются и в других сказках, например, «Царевна-лягушка», «Иван-дурак и серый волк».
5. Пример перефразирования стихотворения Дж. Родари:
- ЕСЛИ ты работаешь пекарем, ТО пахнешь свежим тестом;
- ЕСЛИ ты столяр, ТО от тебя пахнет древесиной;
- ЕСЛИ ты маляр, ТО пахнешь краской и скипидаром;
- ЕСЛИ ты шофёр, ТО от куртки пахнет бензином.
6. Среди девяти монет, где одна легче, фальшивую можно определить за два взвешивания:
- Разделить монеты на три группы по 3 штуки и взвесить две группы.
- Если весы в равновесии — фальшивая в оставшейся группе;
если одна чаша легче — она содержит фальшивую монету. - Из оставшихся трёх монет повторить взвешивание, чтобы найти точную.
7. Алгоритм с повторением (или циклический алгоритм) — это такой, где часть действий выполняется несколько раз.
Пример:
ПОКА не закончились задачи,
решай следующую задачу.
8. Циклические действия встречаются в литературе, например:
в «Колобке» (герой повторяет одинаковые действия — катится и поёт),
в «Трёх поросятах» (каждый строит дом — повторяющееся действие).
9. Если исполнитель 16 раз подряд выполняет последовательность:
вперёд 10, направо 90°,
он нарисует квадратный путь, возвращаясь в исходную точку каждые 4 шага.
После 16 повторов он снова окажется в исходной позиции.
10. Задача о переправе: лодка вмещает одного солдата или двух мальчиков.
Алгоритм:
- Два мальчика переправляются на другой берег.
- Один возвращается.
- Переправляется один солдат.
- Второй мальчик возвращается.
- Действия повторяются для всех солдат, пока все 40 переправятся.
Группа действий (пункты 1–4) повторяется 40 раз.
11. Для получения 1024 из 0 (команды: ×2 и +1):
самое короткое решение — многократное удвоение:
|
1 2 3 4 5 6 7 8 9 10 11 |
+1 → 1 ×2 → 2 ×2 → 4 ×2 → 8 ×2 → 16 ×2 → 32 ×2 → 64 ×2 → 128 ×2 → 256 ×2 → 512 ×2 → 1024 |
Для получения 500:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
+1 → 1 ×2 → 2 ×2 → 4 +1 → 5 ×2 → 10 ×2 → 20 ×2 → 40 +1 → 41 ×2 → 82 ×2 → 164 ×2 → 328 +1 → 329 ×2 → 658 (избыточно, поэтому нужно оптимизировать) |
Оптимально: строить шаги так, чтобы удвоение не превышало нужного числа и вовремя прибавлять 1.
Окончательный результат — 500.
| § 15 | § 16 | § 17 | § 18 |