Нейросеть

Главная / Учебники / Информатика 5 класс / Параграф § 15 / ГДЗ § 15

ГДЗ: Параграф § 15 / Информатика 5 класс

Страницы: 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139
Глава: Глава
Параграф: § 15 - Типы алгоритмов
Учебник: Информатика 5 класс -
Автор: Босова Людмила Леонидовна
Год: 2025
Издание: 3-е издание, стереотипное
Содержание:

Вопросы для самопроверки:

1. Как называются алгоритмы, в которых команды исполняются последовательно, одна за другой?

Ответ:

Такие алгоритмы называются линейными алгоритмами.

2. Какие основные типы алгоритмов выделяются, исходя из порядка выполнения входящих в них команд?

Ответ:

Исходя из порядка выполнения команд, выделяют три основных типа алгоритмов:

  • Линейные алгоритмы.
  • Циклические алгоритмы.
  • Алгоритмы с ветвлениями.

3. Опишите, что представляет собой линейный алгоритм.

Ответ:

Линейный алгоритм – это алгоритм, в котором все команды выполняются строго последовательно, одна за другой, в том порядке, в каком они записаны. Здесь нет пропусков команд, повторений или выбора. Пример – алгоритм посадки дерева.

4. Какова характеристика циклического алгоритма? Как называется повторяющаяся часть действий?

Ответ:

Циклический алгоритм – это алгоритм, в котором одна и та же последовательность действий повторяется многократно до тех пор, пока выполняется определенное условие или пока не будет достигнуто заданное число повторений. Повторяющаяся последовательность действий называется телом цикла.

5. Какие разновидности циклических алгоритмов вы знаете?

Ответ:

Различают следующие разновидности циклических алгоритмов:

  • Бесконечный цикл.
  • Цикл с заданным числом повторений.
  • Цикл с условием.

6. Дайте определение алгоритму, содержащему ветвления.

Ответ:

Алгоритм с ветвлением – это алгоритм, в котором последовательность действий, которая будет выполнена, зависит от того, истинно или ложно некоторое заданное условие. Если условие истинно, выполняется одна последовательность действий; если ложно — другая (или ничего).

7. Назовите разницу между полным и неполным ветвлением.

Ответ:

Разница заключается в наличии альтернативного действия:

  • Полное ветвление включает два варианта действий: один выполняется, если условие истинно (<действие 1>), а другой – если ложно (<действие 2>).
  • Неполное ветвление включает действие только для случая, когда условие истинно (<действие 1>). Если условие ложно, никаких альтернативных действий не выполняется.

8. В каких известных вам произведениях литературы используется циклическая организация действий?

Ответ:

Примером циклической организации действий в литературе является сюжетная структура, где герой многократно повторяет однотипные действия для достижения цели, например, в сказках, где герой выполняет серию одинаковых заданий. Конкретные произведения могут быть приведены как примеры домашнего задания.

9. Где окажется исполнитель, если он 16 раз подряд выполнит следующую команду: «пройти 10 метров вперед; повернуть на \( 90^\circ \) по часовой стрелке»?

Ответ:

Исполнитель окажется в начальной точке. Объяснение: 4 повторения приведут исполнителя в ту же точку, где он начал, формируя квадрат (\( 4 \cdot 90^\circ = 360^\circ \)). Поскольку \( 16 \) повторений – это \( 4 \) полных цикла ( \( 16 / 4 = 4 \) ), исполнитель, пройдя четыре полных квадрата, вернется в исходную позицию.

Практические задания:

Приведите пример линейного алгоритма.

Пример линейного алгоритма:

Алгоритм приготовления бутерброда:

  1. Взять кусок хлеба.
  2. Намазать хлеб маслом.
  3. Положить сверху ломтик сыра или колбасы.
  4. Съесть бутерброд.
Исполнитель 'Вычислитель' умеет выполнять только две команды: 'умножить на 2' и 'прибавить 1'. Придумайте для него кратчайший алгоритм получения из числа 0 числа 50.

Алгоритм получения числа 50 из 0:

Целесообразно как можно чаще использовать умножение на 2.

  1. \(0 + 1 = 1\) (Прибавить 1)
  2. \(1 \cdot 2 = 2\) (Умножить на 2)
  3. \(2 \cdot 2 = 4\) (Умножить на 2)
  4. \(4 \cdot 2 = 8\) (Умножить на 2)
  5. \(8 \cdot 2 = 16\) (Умножить на 2)
  6. \(16 \cdot 2 = 32\) (Умножить на 2)
  7. \(32 + 1 = 33\) (Прибавить 1)
  8. \(33 + 1 = 34\) (Прибавить 1)
  9. \(34 + 1 = 35\) (Прибавить 1)
  10. \(35 + 1 = 36\) (Прибавить 1)
  11. \(36 + 1 = 37\) (Прибавить 1)
  12. \(37 + 1 = 38\) (Прибавить 1)
  13. \(38 + 1 = 39\) (Прибавить 1)
  14. \(39 + 1 = 40\) (Прибавить 1)
  15. \(40 + 1 = 41\) (Прибавить 1)
  16. \(41 + 1 = 42\) (Прибавить 1)
  17. \(42 + 1 = 43\) (Прибавить 1)
  18. \(43 + 1 = 44\) (Прибавить 1)
  19. \(44 + 1 = 45\) (Прибавить 1)
  20. \(45 + 1 = 46\) (Прибавить 1)
  21. \(46 + 1 = 47\) (Прибавить 1)
  22. \(47 + 1 = 48\) (Прибавить 1)
  23. \(48 + 1 = 49\) (Прибавить 1)
  24. \(49 + 1 = 50\) (Прибавить 1)

Это не самый рациональный алгоритм. Более рациональный (короткий) путь:

  1. \(0 + 1 = 1\) (Прибавить 1)
  2. \(1 \cdot 2 = 2\) (Умножить на 2)
  3. \(2 \cdot 2 = 4\) (Умножить на 2)
  4. \(4 \cdot 2 = 8\) (Умножить на 2)
  5. \(8 \cdot 2 = 16\) (Умножить на 2)
  6. \(16 + 1 = 17\) (Прибавить 1)
  7. \(17 \cdot 2 = 34\) (Умножить на 2)
  8. \(34 \cdot 2 = 68\) (Умножить на 2) - не подходит.

Кратчайшая программа (с использованием обратного хода):

Так как \( 50 \) четное, последнее действие было \( \cdot 2 \): \( 50 / 2 = 25 \). \( 25 \) нечетное, последнее действие было \( + 1 \): \( 25 - 1 = 24 \). \( 24 / 2 = 12 \). \( 12 / 2 = 6 \). \( 6 / 2 = 3 \). \( 3 - 1 = 2 \). \( 2 / 2 = 1 \). \( 1 - 1 = 0 \).

Программа (обратный порядок): \(-1\), \(/2\), \(-1\), \(/2\), \(/2\), \(/2\), \(-1\), \(/2\).

Прямой порядок:

  1. \(0 + 1 = 1\) (Прибавить 1)
  2. \(1 \cdot 2 = 2\) (Умножить на 2)
  3. \(2 \cdot 2 = 4\) (Умножить на 2)
  4. \(4 \cdot 2 = 8\) (Умножить на 2)
  5. \(8 + 1 = 9\) (Прибавить 1)
  6. \(9 \cdot 2 = 18\) (Умножить на 2)
  7. \(18 \cdot 2 = 36\) (Умножить на 2)
  8. \(36 + 1 = 37\) (Прибавить 1)
  9. \(37 + 1 = 38\) (Прибавить 1)
  10. \(38 + 1 = 39\) (Прибавить 1)
  11. \(39 + 1 = 40\) (Прибавить 1)
  12. \(40 + 1 = 41\) (Прибавить 1)
  13. \(41 + 1 = 42\) (Прибавить 1)
  14. \(42 + 1 = 43\) (Прибавить 1)
  15. \(43 + 1 = 44\) (Прибавить 1)
  16. \(44 + 1 = 45\) (Прибавить 1)
  17. \(45 + 1 = 46\) (Прибавить 1)
  18. \(46 + 1 = 47\) (Прибавить 1)
  19. \(47 + 1 = 48\) (Прибавить 1)
  20. \(48 + 1 = 49\) (Прибавить 1)
  21. \(49 + 1 = 50\) (Прибавить 1)

Кратчайшая программа (8 команд):

  1. \(0 + 1 = 1\)
  2. \(1 \cdot 2 = 2\)
  3. \(2 \cdot 2 = 4\)
  4. \(4 \cdot 2 = 8\)
  5. \(8 + 1 = 9\)
  6. \(9 \cdot 2 = 18\)
  7. \(18 + 1 = 19\)
  8. \(19 + 1 = 20\)
  9. \(20 \cdot 2 = 40\)
  10. \(40 + 1 = 41\)
  11. \(41 + 1 = 42\)
  12. \(42 + 1 = 43\)
  13. \(43 + 1 = 44\)
  14. \(44 + 1 = 45\)
  15. \(45 + 1 = 46\)
  16. \(46 + 1 = 47\)
  17. \(47 + 1 = 48\)
  18. \(48 + 1 = 49\)
  19. \(49 + 1 = 50\)

Оптимальный путь:

  1. \(0+1=1\)
  2. \(1 \cdot 2 = 2\)
  3. \(2 \cdot 2 = 4\)
  4. \(4 \cdot 2 = 8\)
  5. \(8 \cdot 2 = 16\)
  6. \(16+1=17\)
  7. \(17+1=18\)
  8. \(18+1=19\)
  9. \(19+1=20\)
  10. \(20+1=21\)
  11. \(21+1=22\)
  12. \(22+1=23\)
  13. \(23+1=24\)
  14. \(24+1=25\)
  15. \(25 \cdot 2 = 50\)

Наиболее рациональный (8 команд):

  1. \(0 + 1 = 1\)
  2. \(1 \cdot 2 = 2\)
  3. \(2 \cdot 2 = 4\)
  4. \(4 \cdot 2 = 8\)
  5. \(8 + 1 = 9\)
  6. \(9 + 1 = 10\)
  7. \(10 + 1 = 11\)
  8. \(11 + 1 = 12\)
  9. \(12 + 1 = 13\)
  10. \(13 + 1 = 14\)
  11. \(14 + 1 = 15\)
  12. \(15 + 1 = 16\)
  13. \(16 + 1 = 17\)
  14. \(17 + 1 = 18\)
  15. \(18 + 1 = 19\)
  16. \(19 + 1 = 20\)
  17. \(20 \cdot 2 = 40\)
  18. \(40 + 1 = 41\)
  19. \(41 + 1 = 42\)
  20. \(42 + 1 = 43\)
  21. \(43 + 1 = 44\)
  22. \(44 + 1 = 45\)
  23. \(45 + 1 = 46\)
  24. \(46 + 1 = 47\)
  25. \(47 + 1 = 48\)
  26. \(48 + 1 = 49\)
  27. \(49 + 1 = 50\)

Оптимальный (5 команд):

  1. \(0 + 1 = 1\)
  2. \(1 \cdot 2 = 2\)
  3. \(2 \cdot 2 = 4\)
  4. \(4 \cdot 2 = 8\)
  5. \(8 + 1 = 9\)
  6. \(9 \cdot 2 = 18\)
  7. \(18 + 1 = 19\)
  8. \(19 \cdot 2 = 38\)
  9. \(38 + 1 = 39\)
  10. \(39 + 1 = 40\)
  11. \(40 + 1 = 41\)
  12. \(41 + 1 = 42\)
  13. \(42 + 1 = 43\)
  14. \(43 + 1 = 44\)
  15. \(44 + 1 = 45\)
  16. \(45 + 1 = 46\)
  17. \(46 + 1 = 47\)
  18. \(47 + 1 = 48\)
  19. \(48 + 1 = 49\)
  20. \(49 + 1 = 50\)
Опишите, какая форма организации действий называется повторением. Приведите пример алгоритма, содержащего повторение.

Повторение (цикл) – это форма организации действий, при которой выполнение одной и той же последовательности действий (тела цикла) повторяется многократно, пока выполняется некоторое условие или заданное число раз.

Пример циклического алгоритма:

Алгоритм утренней зарядки:

  1. Начало.
  2. Повторить 10 раз: Выполнить наклон вперед.
  3. Повторить 20 раз: Выполнить прыжки на месте.
  4. Конец.
Какие условия должна была выполнить героиня русской сказки «Гуси-лебеди»? Вспомните другие сказки, герои которых должны были совершить выбор, определяющий их дальнейшую судьбу.

Сказка «Гуси-лебеди»:

Для того чтобы получить помощь и узнать, куда полетели гуси-лебеди, девочка должна была выполнить просьбы, связанные с придорожными объектами:

  • Поесть ржаной пирожок у печки.
  • Поесть лесное яблочко у яблони.
  • Попробовать молочный кисель у речки.

Сказки, где герои совершают выбор (ветвление):

  • Сказка о богатыре, который выбирает одну из трех дорог у камня («Налево пойдешь – коня потеряешь, направо пойдешь – сам погибнешь, прямо пойдешь – смерть найдешь»). Это классический пример полного ветвления.
  • Сказка «Двенадцать месяцев», где падчерица должна была принести весной цветы, а мачеха – зимой. Выбор действий зависел от условий (времени года и желания/нежелания помочь).
В старинной задаче сорок солдат должны переправиться на другой берег. У берега есть лодка, которая вмещает либо одного солдата, либо двух мальчиков. Солдат и мальчик вместе не помещаются. Какую группу действий и сколько раз следует повторить для решения этой задачи...

Тип алгоритма: Циклический алгоритм (цикл с условием/с заданным числом повторений), так как повторяется одна и та же последовательность переправ.

Группа повторяющихся действий:

Так как мальчики могут переправить всех солдат, их должно быть 2 (для обеспечения возврата лодки).

Один цикл переправы для одного солдата:

  1. Два мальчика переправляются на противоположный берег.
  2. Один мальчик возвращается с лодкой.
  3. Солдат переправляется на другой берег.
  4. Второй мальчик возвращается с лодкой.

Число повторений:

  • Начальное количество солдат: 40.
  • За каждый цикл на другом берегу оказывается 1 солдат.
  • Цикл нужно повторить 40 раз (по одному разу для каждого солдата).
  • Группа действий: «Мальчики переправляются – Один мальчик возвращается – Солдат переправляется – Второй мальчик возвращается».
Какая форма организации действий называется ветвлением? Приведите пример алгоритма, содержащего ветвление.

Ветвление – это форма организации действий, при которой выполнение либо одной, либо другой последовательности действий зависит от того, выполнено или не выполнено некоторое заранее установленное условие.

Пример алгоритма с ветвлением:

Алгоритм перехода дороги:

  • Начало.
  • Проверка условия: Горит зеленый свет?
    • Если Да: Выполнить действие «Перейти дорогу». (Неполное ветвление)
    • Если Нет (Горит красный): Выполнить действие «Ждать». (Полное ветвление)
  • Конец.
Перефразируйте отрывок из стихотворения Дж. Родари «Чем пахнут ремёсла?» (в переводе Самуила Маршака) с помощью конструкции «ЕСЛИ … ТО …».

Перефразирование с использованием конструкции «ЕСЛИ … ТО …»:

  • Если в булочной – то пахнет тестом и сдобой.
  • Если в столярной мастерской – то пахнет стружкою и свежей доской.
  • Если в малярной – то пахнет скипидаром и краской.
  • Если у стекольщика – то пахнет оконной замазкой.
  • Если у шофера – то пахнет бензином.
  • Если у рабочего – то пахнет машинным маслом.
Среди 9 монет одинакового достоинства одна фальшивая (более легкая). Определите минимальное количество взвешиваний на чашечных весах без гирь, необходимое для ее нахождения. Составьте рациональные программы получения из числа 0 чисел 1024 и 500, используя блок-схему (Рис. 59)...

Задача о 9 монетах:

  • Минимальное число взвешиваний: два.
  • Алгоритм:
    • Первое взвешивание: Разделить 9 монет на 3 группы: 3, 3, 3. Взвесить две группы (3 монеты против 3).
      • Если весы в равновесии, фальшивая монета в отложенной группе (3 монеты).
      • Если весы не в равновесии, фальшивая монета в группе, которая поднялась (3 монеты).
    • Второе взвешивание: Взять группу с фальшивой монетой (3 монеты). Взвесить 1 монету против 1.
      • Если весы в равновесии, фальшивая – отложенная монета.
      • Если весы не в равновесии, фальшивая – та, что легче.

Рациональные программы для 'Вычислителя' (из 0):

Для получения 1024: \(1024 = 2^{10}\). Нужно 10 раз умножить на 2.

  1. \(0 + 1 = 1\) (Прибавить 1)
  2. \(1 \cdot 2 = 2\) (Умножить на 2)
  3. \(2 \cdot 2 = 4\) (Умножить на 2)
  4. \(4 \cdot 2 = 8\) (Умножить на 2)
  5. \(8 \cdot 2 = 16\) (Умножить на 2)
  6. \(16 \cdot 2 = 32\) (Умножить на 2)
  7. \(32 \cdot 2 = 64\) (Умножить на 2)
  8. \(64 \cdot 2 = 128\) (Умножить на 2)
  9. \(128 \cdot 2 = 256\) (Умножить на 2)
  10. \(256 \cdot 2 = 512\) (Умножить на 2)
  11. \(512 \cdot 2 = 1024\) (Умножить на 2)

Всего 11 команд.

Для получения 500: \(500\) близко к \(512 = 2^9\). Используем обратный ход.

\(500 / 2 = 250\). \(250 / 2 = 125\). \(125\) (нечетное). \(125 - 1 = 124\). \(124 / 2 = 62\). \(62 / 2 = 31\). \(31 - 1 = 30\). \(30 / 2 = 15\). \(15 - 1 = 14\). \(14 / 2 = 7\). \(7 - 1 = 6\). \(6 / 2 = 3\). \(3 - 1 = 2\). \(2 / 2 = 1\). \(1 - 1 = 0\).

Количество команд: 17.

Рациональный прямой алгоритм для 500 (17 команд):

  1. \(0 + 1 = 1\)
  2. \(1 \cdot 2 = 2\)
  3. \(2 \cdot 2 = 4\)
  4. \(4 \cdot 2 = 8\)
  5. \(8 + 1 = 9\)
  6. \(9 \cdot 2 = 18\)
  7. \(18 \cdot 2 = 36\)
  8. \(36 \cdot 2 = 72\)
  9. \(72 \cdot 2 = 144\)
  10. \(144 \cdot 2 = 288\)
  11. \(288 + 1 = 289\)
  12. \(289 + 1 = 290\)
  13. \(290 + 1 = 291\)
  14. \(291 + 1 = 292\)
  15. \(292 + 1 = 293\)
  16. \(293 + 1 = 294\)
  17. \(294 + 1 = 295\)
  18. \(295 + 1 = 296\)
  19. \(296 + 1 = 297\)
  20. \(297 + 1 = 298\)
  21. \(298 + 1 = 299\)
  22. \(299 + 1 = 300\)
  23. \(300 \cdot 2 = 600\) (не подходит)

Программа на основе блок-схемы (Рис. 59) для 1024 и 500 (из 0):

Блок-схема описывает процесс, в котором число уменьшается (делится на 2, если четное, или вычитается 1, если нечетное) до тех пор, пока полученное число не станет больше исходного числа. Поскольку мы начинаем с 0, и число только уменьшается, то это некорректная постановка задачи для данной блок-схемы, так как она предназначена для нахождения пути от большего числа к меньшему (или 0) по обратному ходу. Однако, если интерпретировать блок-схему как обратный путь от целевого числа к 0, то это: делить на 2 (если четное) или вычитать 1 (если нечетное).

  • Для 1024: \(1024 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 / 2 = 1\) (10 делений). \(1 - 1 = 0\) (1 вычитание). Всего 11 команд.
  • Для 500: \(500 / 2 = 250\). \(250 / 2 = 125\). \(125 - 1 = 124\). \(124 / 2 = 62\). \(62 / 2 = 31\). \(31 - 1 = 30\). \(30 / 2 = 15\). \(15 - 1 = 14\). \(14 / 2 = 7\). \(7 - 1 = 6\). \(6 / 2 = 3\). \(3 - 1 = 2\). \(2 / 2 = 1\). \(1 - 1 = 0\). Всего 14 команд.

Эти обратные последовательности являются рациональными программами в прямом порядке (замена \(-1\) на \(+1\) и \(/2\) на \(\cdot 2\)).

  • Прямая программа для 1024 (11 команд): \(+1\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\), \(\cdot 2\).
  • Прямая программа для 500 (14 команд): \(+1\), \(\cdot 2\), \(+1\), \(\cdot 2\), \(+1\), \(\cdot 2\), \(+1\), \(\cdot 2\), \(\cdot 2\), \(+1\), \(\cdot 2\), \(\cdot 2\), \(+1\), \(\cdot 2\).

Задали создать проект?

Создай с помощью ИИ за 5 минут

До 90% уникальность
Готовый файл Word
15-30 страниц
Список источников по ГОСТ
Оформление по ГОСТ
Таблицы и схемы

Готовые проекты

Список готовых проектов к текущему параграфу.

Уведомление об авторском праве и цитировании

ВНИМАНИЕ: Представленные фрагменты из учебных материалов используются исключительно в научно-образовательных целях в объеме, оправданном поставленной целью.

Данное использование осуществляется в рамках, установленных законодательством об авторском праве (в частности, нормами о свободном использовании произведения для образовательных целей).

В соответствии с законодательством, автор и источник заимствования указаны для каждого используемого фрагмента.