Задача 5. Алгоритмы и исполнители
На картинках изображены блок-схемы различных алгоритмов. На какой изображен линейный алгоритм?
Пояснение:
Линейный алгоритм – это алгоритм, в котором все действия выполняются строго последовательно, одно за другим, без каких-либо условий, ветвлений или повторений (циклов).
Рассмотрим каждую блок-схему:
Блок-схема 1 (слева):
- Начало: "Начало"
- Действие: "Возьмите чашку"
- Условие: "Чашка пуста?" (ромб) – это ветвление.
- Если "нет", то действие "Вылейте воду", затем возврат к условию "Чашка пуста?". Это цикл.
- Если "да", то "Конец".
- Эта блок-схема содержит ветвление и цикл, поэтому она не является линейной.
Блок-схема 2 (в центре):
- Начало: "Начало"
- Действие: "Возьмите чашку"
- Условие: "Чашка пуста?" (ромб) – это ветвление.
- Если "да", то действие "Налейте воды", затем "Конец".
- Если "нет", то действие "Вылейте воду", затем "Конец".
- Эта блок-схема содержит ветвление, поэтому она не является линейной.
Блок-схема 3 (справа):
- Начало: "Начало"
- Действие: "Возьмите чашку"
- Действие: "Налейте воды"
- Действие: "Выпейте воду"
- Конец: "Конец"
- Все действия выполняются строго последовательно, без условий, ветвлений или циклов.
- Эта блок-схема является линейным алгоритмом.
Ответ: Линейный алгоритм изображен на третьей (правой) блок-схеме.
***Задача 6. Средняя
Цепочка символов (3)
Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала записывается исходная цепочка символов, после неё записывается буква, которая стоит в исходной цепочке на первом месте, затем дописывается исходная цепочка ещё раз. Получившаяся цепочка является результатом работы алгоритма.
Например, если исходная цепочка символов была ЛЕС, то результатом работы алгоритма будет цепочка ЛЕСЛЛЕС.
Дана цепочка символов УЖ. Какая цепочка символов получится, если к данной цепочке применить алгоритм дважды (то есть к данной цепочке применить алгоритм, а затем к результату его работы применить алгоритм ещё раз)?
Решение:
Опишем алгоритм:
Пусть исходная цепочка \(S\).
Первая буква исходной цепочки: \(S_1\).
Новая цепочка \(S_{новая} = S + S_1 + S\).
Дана исходная цепочка: УЖ
Применение алгоритма в первый раз:
Исходная цепочка \(S = \text{УЖ}\).
Первая буква \(S_1 = \text{У}\).
Применяем алгоритм:
\(S_{новая1} = \text{УЖ} + \text{У} + \text{УЖ} = \text{УЖУУЖ}\)
Результат первого применения: УЖУУЖ
Применение алгоритма во второй раз:
Теперь исходной цепочкой для второго применения является результат первого применения: \(S = \text{УЖУУЖ}\).
Первая буква этой новой исходной цепочки: \(S_1 = \text{У}\).
Применяем алгоритм:
\(S_{новая2} = \text{УЖУУЖ} + \text{У} + \text{УЖУУЖ} = \text{УЖУУЖУУЖУУЖ}\)
Ответ: УЖУУЖУУЖУУЖ
***Задача 7. Средняя
Блок-схема алгоритма
Что напечатает алгоритм для \(a = -11, b = 9\)?
Дана блок-схема. Проследим за изменением значений переменных \(a\) и \(b\).
Начало.
Ввод \(a, b\):
\(a = -11\)
\(b = 9\)
Шаг 1: Проверка условия \(a > b\)?
\(-11 > 9\) – это нет.
Шаг 2: Выполняем действия по ветке "Нет":
\(a := a + b \Rightarrow a = -11 + 9 = -2\)
Шаг 3: Возвращаемся к проверке условия \(a > b\).
Теперь \(a = -2\), \(b = 9\).
\(-2 > 9\) – это нет.
Шаг 4: Выполняем действия по ветке "Нет":
\(a := a + b \Rightarrow a = -2 + 9 = 7\)
Шаг 5: Возвращаемся к проверке условия \(a > b\).
Теперь \(a = 7\), \(b = 9\).
\(7 > 9\) – это нет.
Шаг 6: Выполняем действия по ветке "Нет":
\(a := a + b \Rightarrow a = 7 + 9 = 16\)
Шаг 7: Возвращаемся к проверке условия \(a > b\).
Теперь \(a = 16\), \(b = 9\).
\(16 > 9\) – это да.
Шаг 8: Выполняем действия по ветке "Да":
Вывод \(a\).
Алгоритм напечатает текущее значение \(a\), которое равно 16.
Конец.
Ответ: 16
***Задача 8. Сложная
Купцы и разбойники
К реке одновременно подошли три купца и три разбойника. Всем необходимо переправиться на противоположный берег. У берега стояла лодка, которая могла вместить только двух человек. Купцы боязливо поглядывали на разбойников: если во время переправы на берегу число разбойников превысит число купцов хотя бы на одного человека, то разбойники убьют купцов. Перед купцами стояла сложная задача, но она была ими решена – все перебрались на тот берег, и жертв не было.
Какое наименьшее количество рейсов лодки могло быть? За рейс следует считать движение лодки в одном направлении.
Напиши в ответ число.
Решение (Задача о купцах и разбойниках):
Обозначим купцов как К, разбойников как Р. Начальное состояние: 3К, 3Р на левом берегу (ЛБ). 0К, 0Р на правом берегу (ПБ). Лодка на ЛБ.
Правило: на любом берегу число разбойников не должно превышать число купцов, если купцы присутствуют. Если купцов нет, то разбойники могут быть в любом количестве.
Давайте проследим за перемещениями:
Состояние: (Купцы на ЛБ, Разбойники на ЛБ) | (Купцы на ПБ, Разбойники на ПБ) | Лодка
Начало: (3К, 3Р) | (0К, 0Р) | ЛБ
Рейс 1 (ЛБ -> ПБ): Отправляем 1К, 1Р. (Если отправить 2Р, то на ЛБ останется 3К, 1Р - безопасно. На ПБ 0К, 2Р - безопасно. Но как вернуть лодку? Если 1Р вернется, на ЛБ 3К, 1Р. Если 2Р останутся, то на ПБ 0К, 2Р. Если 1К вернется, на ЛБ 2К, 2Р. На ПБ 1К, 1Р. Это сложнее. Проще начать с 1К, 1Р).
1. 1К, 1Р переправляются на ПБ.
Состояние: (2К, 2Р) | (1К, 1Р) | ПБ. (Оба берега безопасны)
Рейс 2 (ПБ -> ЛБ): Возвращаем 1К.
2. 1К возвращается на ЛБ.
Состояние: (3К, 2Р) | (0К, 1Р) | ЛБ. (Оба берега безопасны)
Рейс 3 (ЛБ -> ПБ): Отправляем 2Р.
3. 2Р переправляются на ПБ.
Состояние: (3К, 0Р) | (0К, 3Р) | ПБ. (Оба берега безопасны: на ЛБ только купцы, на ПБ только разбойники)
Рейс 4 (ПБ -> ЛБ): Возвращаем 1Р.
4. 1Р возвращается на ЛБ.
Состояние: (3К, 1Р) | (0К, 2Р) | ЛБ. (Оба берега безопасны)
Рейс 5 (ЛБ -> ПБ): Отправляем 2К.
5. 2К переправляются на ПБ.
Состояние: (1К, 1Р) | (2К, 2Р) | ПБ. (Оба берега безопасны)
Рейс 6 (ПБ -> ЛБ): Возвращаем 1К, 1Р.
6. 1К, 1Р возвращаются на ЛБ.
Состояние: (2К, 2Р) | (1К, 1Р) | ЛБ. (Оба берега безопасны)
Рейс 7 (ЛБ -> ПБ): Отправляем 2К.
7. 2К переправляются на ПБ.
Состояние: (0К, 2Р) | (3К, 1Р) | ПБ. (Оба берега безопасны)
Рейс 8 (ПБ -> ЛБ): Возвращаем 1Р.
8. 1Р возвращается на ЛБ.
Состояние: (0К, 3Р) | (3К, 0Р) | ЛБ. (Оба берега безопасны)
Рейс 9 (ЛБ -> ПБ): Отправляем 2Р.
9. 2Р переправляются на ПБ.
Состояние: (0К, 1Р) | (3К, 2Р) | ПБ. (Оба берега безопасны)
Рейс 10 (ПБ -> ЛБ): Возвращаем 1Р.
10. 1Р возвращается на ЛБ.
Состояние: (0К, 2Р) | (3К, 1Р) | ЛБ. (Оба берега безопасны)
Рейс 11 (ЛБ -> ПБ): Отправляем 2Р.
11. 2Р переправляются на ПБ.
Состояние: (0К, 0Р) | (3К, 3Р) | ПБ. (Все переправились)
Это один из возможных вариантов решения. Существуют и другие, но 11 рейсов является минимальным количеством.
Ответ: 11