Среди множества исполнителей в системе КуМир особое место занимает Кузнечик — простой, но невероятно полезный виртуальный персонаж, который перемещается по числовой прямой, выполняя ваши команды. На первый взгляд кажется, что это слишком примитивно, но не спешите с выводами! Кузнечик обитает в одномерном мире — числовой оси. Его возможности ограничены всего парой действий: он умеет прыгать вправо или влево на заданное количество единиц. Эта простота и делает его идеальным для новичков. Вместо того чтобы разбираться с сотнями функций и методов, вы концентрируетесь на алгоритмической логике — самом фундаменте программирования. Я до сих пор помню свои первые программы для Кузнечика. Казалось бы — чего проще? Заставить его попрыгать туда-сюда по прямой? Но когда задачи усложнились, появились условия и ограничения, пришлось серьезно напрягать мозги. И знаете что? Именно это и помогло мне лучше понимать программирование в будущем.
Большинство задач для Кузнечика формулируются так: "Кузнечик находится в точке X, необходимо переместить его в точку Y, используя определенный набор команд/с ограничениями/оптимальным путем". Их красота в том, что для решения не нужен дорогой компьютер или специальное образование — достаточно листа бумаги, карандаша и немного упорства. Интересно, что через эти простые упражнения вы на интуитивном уровне осваиваете сложные концепции: циклы, условные операторы, вложенные алгоритмы, оптимизацию. Всё это в игровой форме, без страха ошибиться или сломать что-то важное.
В этой статье я собрал задачи разной сложности с подробными решениями. Мы начнем с самых простых примеров, постепено доберемся до настоящих головоломок! Я попытался подобрать задачи, которые не только научат вас программировать Кузнечика, но и разовьют алгоритмическое мышление в целом.
Что такое КуМир и исполнитель Кузнечик
КуМир (Комплект Учебных МИРов) — это образовательная программная среда, разработанная специально для обучения программированию в российских школах. Название говорит само за себя: система создает учебные миры, где начинающие программисты могут экспериментировать без риска что-то сломать в реальном компьютере. КуМир возник не вчера — его история началась еще в 1980-х годах под руководством академика А.П. Ершова, но современная версия существенно переработана и адаптирована под текущие образовательные задачи. КуМир использует понятный русскоязычный синтаксис. Вместо английских команд типа if, for, while здесь применяются их русские аналоги: "если", "нц" (для начала цикла), "кц" (для конца цикла). Это снимает языковой барьер и позволяет сосредоточиться на логике программирования, а не на запоминании иностранных слов. Главное достоинство системы — набор исполнителей, виртуальных персонажей с ограниченным набором команд. Помимо Кузнечика, здесь есть Робот (двигается по клеточному полю), Чертежник (рисует линии на координатной плоскости), Водолей (переливает воду между сосудами) и другие. Каждый из них помогает освоить определенные алгоритмические конструкции.
Теперь конкретно о нашем прыгучем герое. Исполнитель Кузнечик — это, пожалуй, самый простой персонаж в системе КуМир, но именно эта простота делает его идеальным для первых шагов в программировании. Кузнечик живет на числовой прямой и может выполнять два базовых действия:- прыгать вправо на определенное число единиц.
- прыгать влево на определенное число единиц.
Попробуем представить: вот бескрайняя прямая с отметками ...-3, -2, -1, 0, 1, 2, 3... и маленький зеленый кузнечик, сидящий в какой-то точке. По вашей команде он может перепрыгнуть на несколько делений вперед или назад. Никаких диагональных прыжков, полетов или кувырков — только прямая линия.
Изначально система КуМир настроена так, что Кузнечик умеет прыгать только на 1 или 2 единицы в любом направлении. То есть его базовый набор команд — это:
| Code | 1
2
3
4
| ВПРАВО 1
ВПРАВО 2
ВЛЕВО 1
ВЛЕВО 2 |
|
Работа с Кузнечиком в системе КуМир строится через написание алгоритмов — последовательностей команд. Для решения более сложных задач используются вспомогательные алгоритмы (аналог функций или процедур в "взрослых" языках программирования), условные конструкции и циклы. Интерфейс КуМир при работе с Кузнечиком предельно прост: слева — поле для ввода программы, справа — числовая прямая, на которой отображается текущее положение Кузнечика. При запуске программы можно наблюдать, как наш герой скачет по прямой, выполняя заданные команды. Если где-то допущена ошибка, система сразу же укажет на нее и объяснит, в чем проблема. За этой простотой скрывается глубокий педагогический смысл — ученик получает визуальную обратную связь, видит результат работы своего алгоритма и может наглядно отследить ошибки. Это намного эффективнее, чем просто писать код и получать сухое сообщение "ошибка в строке N".
Исполнитель КУЗНЕЧИК живёт на числовой оси
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 5 – Кузнечик прыгает вперёд... Исполнитель КУЗНЕЧИК живёт на числовой оси
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 7 – Кузнечик прыгает вперёд... Задача Гиа: какая фигура появится на экране при выполнении Исполнителем Черепашка данного алгоритма?
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и... [КуМир] Нарисовать график функции y = tg(x+1)^2, исполнитель Рисователь
Ребят, простите дурака, но я не знаю где найти нужный форум по КУМИРУ, но так как он мне безумно напоминает Паскаь, пишу суда.
Нужно...
Основные команды Кузнечика
Теперь, когда мы познакомились с самим Кузнечиком и средой КуМир, пора разобраться с его командным репертуаром. Несмотря на кажущуюся простоту, наш виртуальный попрыгунчик обладает достаточным набором инструментов для решения весьма нетривиальных задач. Базовый набор команд Кузнечика очень лаконичен:
где n — это величина прыжка, выраженная целым положительным числом. В стандартной конфигурации n может принимать значения 1 или 2, но в некоторых задачах диапазон допустимых значений может быть расширен.
Команда ВПРАВО n заставляет Кузнечика прыгнуть на n единиц в положительном направлении числовой оси. Если Кузнечик находился в точке x, то после выполнения этой команды он окажется в точке x + n. Аналогично, команда ВЛЕВО n перемещает Кузнечика на n единиц в отрицательном направлении оси. Из точки x он прыгнет в точку x - n. Программа для Кузнечика — это последовательность таких команд. Вот пример простейшей программы:
| Code | 1
2
3
4
| ВПРАВО 2
ВПРАВО 1
ВЛЕВО 1
ВПРАВО 2 |
|
1. Вспомогательные алгоритмы — аналог процедур или функций в традиционных языках программирования. Они позволяют выделить часто повторяющуюся последовательность действий и оформить её отдельно.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг Шаг3()
нач
ВПРАВО 2
ВПРАВО 1
кон
алг Основной
нач
Шаг3()
ВЛЕВО 1
Шаг3()
кон |
|
Шаг3(), который перемещает Кузнечика на 3 единицы вправо (через два прыжка). Затем используем его дважды в основной программе.
2. Условные конструкции — позволяют выполнять команды в зависимости от текущей позиции Кузнечика или других условий.
| Code | 1
2
3
4
5
6
7
8
| алг УсловныйШаг(цел x)
нач
если x < 10 то
ВПРАВО 2
иначе
ВЛЕВО 1
все
кон |
|
3. Циклы — незаменимы, когда нужно многократно повторить одни и те же действия.
| Code | 1
2
3
4
5
6
7
| алг Пила(цел n)
нач
нц для i от 1 до n
ВПРАВО 2
ВЛЕВО 1
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| алг Фибоначчи(цел n)
нач
если n <= 0 то
вывод "Введите положительное число"
стоп
все
если n = 1 или n = 2 то
ВПРАВО 1
стоп
все
цел a := 1
цел b := 1
цел c
нц для i от 3 до n
c := a + b
a := b
b := c
кц
нц для i от 1 до b
ВПРАВО 1
кц
кон |
|
Важно понимать, что хотя базовые команды Кузнечика предельно просты, их комбинирование с алгоритмическими конструкциями позволяет решать задачи практически любой сложности. Это отличная иллюстрация принципа, что суть программирования не в знании множества команд, а в умении составлять из простых элементов сложные алгоритмы. Опытные программисты знают, что ограничения часто рождают креативность. В случае с Кузнечиком это особенно заметно — имея всего две базовые команды, мы вынуждены искать нестандартные решения. Например, как быстрее всего переместить Кузнечика из точки 0 в точку 9, если он умеет прыгать только на 1 или 2 единицы? Интуитивно кажется, что нужно максимально использовать прыжки по 2, но всегда ли это оптимально?
Для более наглядного представления часто используют графы переходов — схемы, показывающие возможные перемещения Кузнечика. Например, если Кузнечик может прыгать на 1 или 2 единицы, то из каждой точки числовой оси есть два возможных перехода вправо и два влево. Поиск оптимального маршрута в таком графе — классическая алгоритмическая задача.
Отдельно стоит упомянуть о процедуре тестирования программ для Кузнечика. КуМир предоставляет удобные инструменты отладки: пошаговое выполнение, точки остановки, просмотр значений переменных. Это позволяет легко отследить ошибки в алгоритме и исправить их.
Обратите внимание, что хотя мы говорим о визуальном представлении Кузнечика на числовой прямой, в реальности КуМир оперирует абстрактной моделью. Точнее, положение Кузнечика — это просто число, которое увеличивается или уменьшается при выполнении команд. Эта абстракция и делает Кузнечика таким универсальным инструментом — на его примере можно моделировать множество реальных процессов, от движения лифта между этажами до изменения значений счетчиков в программе.
Особенности формальной записи команд Кузнечика
Формальная запись алгоритмов для Кузнечика имеет свои особенности, которые важно понимать для успешного решения задач. КуМир использует русскоязычный псевдокод с чёткой структурой, позволяющий сосредоточиться на логике программы, а не на синтаксических нюансах. Любая программа для Кузнечика начинается с объявления алгоритма:
| Code | 1
2
3
4
| алг Название_алгоритма([параметры])
нач
// тело алгоритма
кон |
|
- цел — целые числа.
- вещ — вещественные (дробные) числа.
- лит — символы и строки.
- лог — логические значения (Да/Нет).
Вот как выглядит объявление алгоритма с параметрами:
| Code | 1
2
3
4
| алг ДойтиДо(цел x)
нач
// тело алгоритма
кон |
|
| Code | 1
2
3
4
5
| если <условие> то
// команды при истинном условии
иначе
// команды при ложном условии
все |
|
| Code | 1
2
3
| если <условие> то
// команды при истинном условии
все |
|
| Code | 1
2
3
| нц для i от <начало> до <конец> [шаг <шаг>]
// тело цикла
кц |
|
| Code | 1
2
3
| нц пока <условие>
// тело цикла
кц |
|
| Code | 1
2
3
| нц
// тело цикла
кц_при <условие> |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| алг ДостичьТочки(цел цель)
нач
цел позиция := 0 // начальная позиция Кузнечика
нц пока позиция < цель
если цель - позиция >= 2 то
ВПРАВО 2
позиция := позиция + 2
иначе
ВПРАВО 1
позиция := позиция + 1
все
кц
нц пока позиция > цель
если позиция - цель >= 2 то
ВЛЕВО 2
позиция := позиция - 2
иначе
ВЛЕВО 1
позиция := позиция - 1
все
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг ПрыжокВправоНа3()
нач
ВПРАВО 2
ВПРАВО 1
кон
алг Основной
нач
ПрыжокВправоНа3()
ВЛЕВО 1
ПрыжокВправоНа3()
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ОтладкаПозиции(цел n)
нач
цел позиция := 0
нц для i от 1 до n
ВПРАВО 2
позиция := позиция + 2
вывод "Текущая позиция: ", позиция
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг ДвиженияКузнечика(цел n)
нач
// Сначала делаем n прыжков вправо
нц для i от 1 до n
ВПРАВО 1
кц
// Теперь возвращаемся в исходную точку
нц для i от 1 до n
ВЛЕВО 1
кц
кон |
|
| Code | 1
2
3
4
5
6
| алг ИспользованиеПозиции
нач
цел начальная_позиция := поз
ВПРАВО 5
вывод "Кузнечик переместился на ", поз - начальная_позиция, " единиц"
кон |
|
| Code | 1
2
3
4
5
6
7
8
| алг БезопасныйПрыжок(цел n)
нач
если свободно справа n то
ВПРАВО n
иначе
вывод "Прыжок невозможен!"
все
кон |
|
Визуальное представление перемещений Кузнечика
Визуализация — мощный инструмент для понимания алгоритмов. В случае с Кузнечиком графическое представление его перемещений помогает не только отслеживать ход выполнения программы, но и лучше осмысливать логику решаемых задач. В КуМире движения Кузнечика отображаются на числовой прямой, где каждая позиция представлена делением с соответствующим числом. Сам Кузнечик обычно изображается как маленький зеленый значок, перепрыгивающий с одного деления на другое. Такой интерфейс интуитивно понятен даже младшим школьникам. Но что если вы хотите более детально проанализировать маршрут Кузнечика или поделиться своим решением с другими? Существует несколько способов визуального представления перемещений, которые я часто использую при обучении программированию.
Самый простой способ — линейная диаграмма перемещений. Представьте числовую ось, на которой отмечены все позиции Кузнечика в порядке их посещения:
| Code | 1
2
3
4
| 0 1 2 3 4 5 6
│ │ │ │ │ │ │
▼ │ ▼ │ ▼ │ ▼
(1)───┘ (3)───┘ (5)───┘ (7) |
|
| Code | 1
2
3
4
5
| Начальная позиция: 0
ВПРАВО 2 → Позиция: 2
ВПРАВО 1 → Позиция: 3
ВЛЕВО 2 → Позиция: 1
ВПРАВО 2 → Позиция: 3 |
|
| Code | 1
2
3
4
5
6
7
| 0 1 2 3 4 5
│ │ │ │ │ │
●─────●─────●─────●─────●─────●
↓ │ ↑ ↓ │ ↑
Start→●→→→→●←←←←←●→→→→→●←←←←←●→→→→→●←Finish
│ ↑ │ ↑ │ │
●─────●─────●─────●─────●─────● |
|
| Code | 1
2
3
4
5
6
7
8
9
10
| (0)
/ \
/ \
+1 +2
/ \
(1) (2)
/ \ / \
+1 +2 +1 +2
/ \ / \
(2) (3) (3) (4) |
|
| Code | 1
2
3
4
5
6
| | Начальная позиция | Целевая позиция | Оптимальный маршрут | Количество прыжков |
|-------------------|-----------------|---------------------|-------------------|
| 0 | 5 | +2, +2, +1 | 3 |
| 0 | 6 | +2, +2, +2 | 3 |
| 5 | 0 | -2, -2, -1 | 3 |
| 5 | 2 | -2, -1 | 2 | |
|
Для наглядности также хорошо работает временная диаграмма, где по горизонтали откладывается шаг алгоритма, а по вертикали — позиция Кузнечика:
| Code | 1
2
3
4
5
6
7
8
9
10
| Позиция
6 │ x
5 │ x
4 │ x
3 │ x
2 │ x
1 │ x
0 │ x
└───────────────────> Шаг
1 2 3 4 5 6 7 8 |
|
- Зелёный цвет — прыжки вправо.
- Красный цвет — прыжки влево.
- Синий цвет — специальные прыжки (например, через препятствия).
Для интерактивного обучения можно создать физическую модель числовой прямой с фишкой-"кузнечиком". Это отлично работает при демонстрации алгоритмов в классе или на открытых уроках.
В КуМире также есть возможность включить режим трассировки, при котором система автоматически визуализирует каждый шаг выполнения программы. Это незаменимо при отладке и изучении алгоритмов. При работе со сложными задачами полезно строить дерево решений — структуру, показывающую все возможные последовательности прыжков и их результаты. Это помогает находить не только правильные, но и оптимальные решения.
В конце концов, визуализация перемещений Кузнечика — не просто способ сделать обучение наглядным. Это мощный инструмент для развития алгоритмического мышления, помогающий перейти от конкретных действий к абстрактным понятиям программирования.
Базовые задачи: перемещение на заданное расстояние
Начнём наше практическое путешествие с самых простых, но важных задач для Кузнечика — перемещения на заданное расстояние. Эти задачи формируют фундамент для более сложных алгоритмов и помогают освоиться с базовыми принципами программирования.
Задача 1: Переместить Кузнечика на 5 единиц вправо
Самая базовая задача для начинающих: переместить Кузнечика из начальной точки (допустим, это 0) на 5 единиц вправо. Помните, что у нашего исполнителя есть только команды ВПРАВО 1 и ВПРАВО 2. Рассмотрим несколько способов решения:
Решение 1: Использование только команды ВПРАВО 1
| Code | 1
2
3
4
5
6
7
8
| алг Вправо5_способ1
нач
ВПРАВО 1
ВПРАВО 1
ВПРАВО 1
ВПРАВО 1
ВПРАВО 1
кон |
|
Решение 2: Комбинация команд ВПРАВО 1 и ВПРАВО 2
| Code | 1
2
3
4
5
6
| алг Вправо5_способ2
нач
ВПРАВО 2
ВПРАВО 2
ВПРАВО 1
кон |
|
ВПРАВО 2 и одну ВПРАВО 1, что дало нам суммарно 5 единиц перемещения (2 + 2 + 1 = 5). Это уже лучше!
Решение 3: Использование цикла
| Code | 1
2
3
4
5
6
| алг Вправо5_способ3
нач
нц для i от 1 до 5
ВПРАВО 1
кц
кон |
|
ВПРАВО 1 выполняется 5 раз. Это более элегантное решение, особенно если нужно перемещаться на большие расстояния.
Решение 4: Оптимизация с использованием цикла
| Code | 1
2
3
4
5
6
7
| алг Вправо5_способ4
нач
нц для i от 1 до 2
ВПРАВО 2
кц
ВПРАВО 1
кон |
|
Задача 2: Переместить Кузнечика на произвольное расстояние N
Теперь усложним задачу — нужно написать алгоритм, который переместит Кузнечика на произвольное расстояние N вправо. Этот алгоритм должен работать для любого положительного целого значения N.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| алг ВправоНаN(цел N)
нач
цел остаток
// Делаем максимальное количество прыжков по 2
нц пока N >= 2
ВПРАВО 2
N := N - 2
кц
// Если остался нечетный остаток, делаем еще один прыжок на 1
если N = 1 то
ВПРАВО 1
все
кон |
|
Задача 3: Переместить Кузнечика на отрицательное расстояние
А что если нам нужно переместить Кузнечика влево, а не вправо? Напишем алгоритм для перемещения на N единиц влево:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| алг ВлевоНаN(цел N)
нач
цел остаток
// Делаем максимальное количество прыжков по 2
нц пока N >= 2
ВЛЕВО 2
N := N - 2
кц
// Если остался нечетный остаток, делаем еще один прыжок на 1
если N = 1 то
ВЛЕВО 1
все
кон |
|
ВЛЕВО вместо ВПРАВО.
Задача 4: Универсальное перемещение на расстояние N
Объединим предыдущие два алгоритма в один, который сможет перемещать Кузнечика на произвольное расстояние N (как положительное, так и отрицательное):
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| алг ПеремещениеНаN(цел N)
нач
// Определяем направление движения
если N > 0 то
// Движение вправо
нц пока N >= 2
ВПРАВО 2
N := N - 2
кц
если N = 1 то
ВПРАВО 1
все
иначе
// Движение влево (меняем знак N для удобства)
N := -N
нц пока N >= 2
ВЛЕВО 2
N := N - 2
кц
если N = 1 то
ВЛЕВО 1
все
все
кон |
|
Задача 5: Перемещение с подсчётом шагов
Иногда важно не только достичь цели, но и сделать это за минимальное количество шагов. Напишем алгоритм, который не только перемещает Кузнечика на расстояние N, но и подсчитывает количество сделанных шагов:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| алг ПеремещениеСПодсчетом(цел N)
нач
цел шагов := 0
если N > 0 то
// Движение вправо
нц пока N >= 2
ВПРАВО 2
N := N - 2
шагов := шагов + 1
кц
если N = 1 то
ВПРАВО 1
шагов := шагов + 1
все
иначе
// Движение влево
N := -N
нц пока N >= 2
ВЛЕВО 2
N := N - 2
шагов := шагов + 1
кц
если N = 1 то
ВЛЕВО 1
шагов := шагов + 1
все
все
вывод "Количество шагов: ", шагов
кон |
|
шагов, которая увеличивается на 1 при каждом прыжке Кузнечика. В конце алгоритма мы выводим общее количество шагов. Важно понимать, что для перемещения на расстояние N оптимальное количество шагов будет равно⌈N/2⌉ (округление вверх от N/2). Например, для N = 5 оптимальное количество шагов равно 3 (два прыжка по 2 и один прыжок по 1).
Базовые задачи: достижение конкретной точки
Переместиться на заданное расстояние — это хорошо, но в реальных задачах чаще требуется достичь конкретной точки на числовой прямой. В этом разделе мы рассмотрим задачи, где Кузнечик должен попасть в определённую позицию, независимо от того, где он находился изначально.
Задача 6: Достичь точки с известной текущей позицией
Допустим, Кузнечик находится в точке X, и нам нужно переместить его в точку Y. Обе точки известны заранее.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| алг ДостичьТочки(цел X, цел Y)
нач
цел расстояние := Y - X
если расстояние > 0 то
// Движение вправо
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
иначе
// Движение влево
расстояние := -расстояние
нц пока расстояние >= 2
ВЛЕВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВЛЕВО 1
все
все
кон |
|
Задача 7: Достичь точки с неизвестной текущей позицией
А что если текущая позиция Кузнечика неизвестна? В КуМире есть функция поз, которая возвращает текущую позицию исполнителя:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| алг ДостичьТочкиНезависимо(цел Y)
нач
цел X := поз
цел расстояние := Y - X
если расстояние > 0 то
// Движение вправо
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
иначе
// Движение влево
расстояние := -расстояние
нц пока расстояние >= 2
ВЛЕВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВЛЕВО 1
все
все
кон |
|
Задача 8: Достичь ближайшей чётной точки
Попробуем что-то поинтереснее: переместить Кузнечика в ближайшую чётную точку на числовой прямой. Если Кузнечик уже находится в чётной точке, он остаётся на месте.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| алг ДостичьЧетнойТочки
нач
цел текущая_позиция := поз
если текущая_позиция mod 2 = 0 то
// Уже в четной точке, ничего делать не нужно
иначе
// Находимся в нечетной точке, нужно переместиться
// Выбираем ближайшую четную точку
если текущая_позиция > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кон |
|
mod 2 = 0). Если нет, то он перемещается на 1 единицу в направлении, которое зависит от текущей позиции. Стоп, но тут есть ошибка! Если Кузнечик находится в положительной нечётной точке, то ближайшая чётная точка может быть как справа (+1), так и слева (-1). Аналогично для отрицательной нечётной точки. Давайте исправим:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| алг ДостичьЧетнойТочки
нач
цел текущая_позиция := поз
если текущая_позиция mod 2 = 0 то
// Уже в четной точке, ничего делать не нужно
иначе
// Решаем, куда двигаться
// Если конечная часть числа равна 1 (например, 1, -3, 5), то ближайшая четная точка справа
// Если конечная часть числа равна -1 (например, -1, 3, -5), то ближайшая четная точка слева
если текущая_позиция mod 2 = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| алг ДостичьЧетнойТочки
нач
цел текущая_позиция := поз
если текущая_позиция mod 2 = 0 то
// Уже в четной точке, ничего делать не нужно
иначе
// Для нечетных чисел
если текущая_позиция > 0 то
// Для положительных нечетных минимальное расстояние до четного - это +1
ВПРАВО 1
иначе
// Для отрицательных нечетных минимальное расстояние до четного - это +1
ВПРАВО 1
все
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг ДостичьЧетнойТочки
нач
цел текущая_позиция := поз
если текущая_позиция mod 2 = 0 то
// Уже в четной точке, ничего делать не нужно
иначе
// Для любого нечетного числа ближайшее четное в +1
ВПРАВО 1
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| алг ДостичьЧетнойТочки
нач
цел текущая_позиция := поз
если текущая_позиция mod 2 = 0 то
// Уже в четной точке, ничего делать не нужно
иначе
// Для нечетных чисел
если текущая_позиция > 0 то
// Положительные нечетные: ближайшее четное справа (+1) или слева (-1)
ВПРАВО 1 // Выбираем движение вправо
иначе
// Отрицательные нечетные: ближайшее четное справа (+1) или слева (-1)
ВЛЕВО 1 // Выбираем движение влево
все
все
кон |
|
Задача 9: Достичь ближайшей точки, кратной 3
Усложним предыдущую задачу — теперь нужно переместить Кузнечика в ближайшую точку, кратную 3.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| алг ДостичьТочкиКратной3
нач
цел текущая_позиция := поз
цел остаток := текущая_позиция mod 3
если остаток = 0 то
// Уже в точке, кратной 3
иначе если остаток = 1 то
// Нужно сдвинуться на 1 влево или на 2 вправо
ВЛЕВО 1 // Выбираем меньшее перемещение
иначе // остаток = 2
// Нужно сдвинуться на 2 влево или на 1 вправо
ВПРАВО 1 // Выбираем меньшее перемещение
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| алг ДостичьТочкиКратной3
нач
цел текущая_позиция := поз
цел остаток := abs(текущая_позиция) mod 3
если остаток = 0 то
// Уже в точке, кратной 3
иначе
если текущая_позиция > 0 то
// Положительное число
если остаток = 1 то
ВЛЕВО 1
иначе // остаток = 2
ВПРАВО 1
все
иначе
// Отрицательное число
если остаток = 1 то
ВПРАВО 1
иначе // остаток = 2
ВЛЕВО 1
все
все
все
кон |
|
Задача 10: Достичь заданной точки за минимальное количество шагов
Вернёмся к задаче достижения произвольной точки, но теперь с акцентом на минимальное количество шагов:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| алг ДостичьТочкиОптимально(цел цель)
нач
цел текущая_позиция := поз
цел расстояние := abs(цель - текущая_позиция)
цел направление := знак(цель - текущая_позиция)
// Максимально используем прыжки по 2
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
// Если остался нечетный остаток
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кон |
|
Базовые задачи: минимальное количество шагов
Оптимизация алгоритмов — важный навык для любого программиста. Когда мы говорим о Кузнечике, минимизация количества шагов становится интересной математической задачей. Вспомните, что наш Кузнечик может прыгать только на 1 или 2 единицы в любом направлении. Как же достичь нужной точки за минимальное количество прыжков?
Задача 11: Определение минимального количества шагов
Прежде чем писать программу, давайте разберёмся с математической частью. Если нам нужно переместиться из точки A в точку B, то расстояние между ними равно |B - A|. Как определить минимальное число шагов для преодоления этого расстояния? Поскольку максимальная длина прыжка Кузнечика — 2 единицы, оптимальная стратегия — использовать как можно больше таких прыжков. Для расстояния N формула минимального числа шагов будет:- Если N чётное, то минимальное число шагов = N / 2.
- Если N нечётное, то минимальное число шагов = (N - 1) / 2 + 1 = (N + 1) / 2.
Напишем алгоритм, который вычисляет минимальное количество шагов между двумя точками:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
| алг МинимальноеКоличествоШагов(цел A, цел B)
нач
цел расстояние := abs(B - A)
цел минимум_шагов
если расстояние mod 2 = 0 то
минимум_шагов := расстояние div 2
иначе
минимум_шагов := (расстояние + 1) div 2
все
вывод "Минимальное количество шагов: ", минимум_шагов
кон |
|
Задача 12: Перемещение с подсчётом минимального количества шагов
Теперь напишем алгоритм, который не только вычисляет минимальное количество шагов, но и фактически перемещает Кузнечика оптимальным путём:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| алг ПеремещениеЗаМинимумШагов(цел цель)
нач
цел старт := поз
цел расстояние := abs(цель - старт)
цел шагов := 0
цел направление
если цель > старт то
направление := 1 // движение вправо
иначе
направление := -1 // движение влево
все
// Максимально используем прыжки по 2
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
шагов := шагов + 1
кц
// Если остался нечётный остаток
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
шагов := шагов + 1
все
вывод "Кузнечик переместился из ", старт, " в ", цель, " за ", шагов, " шагов"
кон |
|
Задача 13: Сравнение разных стратегий перемещения
Интересно сравнить различные стратегии перемещения и убедиться, что наш подход действительно оптимален. Напишем алгоритм, который сравнивает три стратегии:
1. Только прыжки на 1.
2. Только прыжки на 2 (там, где возможно) + один прыжок на 1 для нечётного расстояния.
3. Смешанная стратегия (например, чередование прыжков).
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| алг СравнениеСтратегий(цел цель)
нач
цел старт := поз
цел расстояние := abs(цель - старт)
// Стратегия 1: только прыжки на 1
цел шагов1 := расстояние
// Стратегия 2: максимум прыжков на 2
цел шагов2
если расстояние mod 2 = 0 то
шагов2 := расстояние div 2
иначе
шагов2 := (расстояние div 2) + 1
все
// Стратегия 3: чередование прыжков (1-2-1-2...)
цел шагов3 := 0
цел оставшееся := расстояние
лог прыжок_на_1 := истина // начинаем с прыжка на 1
нц пока оставшееся > 0
если прыжок_на_1 то
оставшееся := оставшееся - 1
иначе
если оставшееся >= 2 то
оставшееся := оставшееся - 2
иначе
оставшееся := оставшееся - 1
все
все
шагов3 := шагов3 + 1
прыжок_на_1 := не прыжок_на_1 // меняем тип прыжка
кц
вывод "Для перемещения на ", расстояние, " единиц:"
вывод "Стратегия 1 (только по 1): ", шагов1, " шагов"
вывод "Стратегия 2 (максимум по 2): ", шагов2, " шагов"
вывод "Стратегия 3 (чередование): ", шагов3, " шагов"
// Определяем победителя
если шагов1 <= шагов2 и шагов1 <= шагов3 то
вывод "Оптимальная стратегия: только прыжки на 1"
иначе если шагов2 <= шагов1 и шагов2 <= шагов3 то
вывод "Оптимальная стратегия: максимум прыжков на 2"
иначе
вывод "Оптимальная стратегия: чередование прыжков"
все
кон |
|
Задача 14: Достижение точки на заданном интервале за минимальное количество шагов
Теперь усложним задачу: нам нужно переместить Кузнечика в любую точку на интервале [A, B] за минимальное количество шагов. Это может пригодиться, когда нам нужно, чтобы Кузнечик попал в определённую зону, а не в конкретную точку.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| алг ДостичьИнтервала(цел A, цел B)
нач
цел текущая_позиция := поз
// Если уже в интервале, ничего делать не нужно
если текущая_позиция >= A и текущая_позиция <= B то
вывод "Кузнечик уже находится в заданном интервале"
стоп
все
цел расстояние_до_A := abs(A - текущая_позиция)
цел расстояние_до_B := abs(B - текущая_позиция)
цел цель
// Выбираем ближайшую точку интервала
если расстояние_до_A <= расстояние_до_B то
цель := A
иначе
цель := B
все
// Перемещаемся к выбранной точке оптимальным путём
ПеремещениеЗаМинимумШагов(цель)
кон |
|
Задача 15: Двусторонняя оптимизация
До сих пор мы оптимизировали только количество шагов. А что если нам нужно минимизировать и количество шагов, и суммарное расстояние, пройденное Кузнечиком? Такая задача становится двукритериальной. Представим, что каждый прыжок на 2 стоит дороже, чем два прыжка на 1. В этом случае оптимальной может оказаться другая стратегия:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| алг ДвойнаяОптимизация(цел цель, вещ вес_прыжка_1, вещ вес_прыжка_2)
нач
цел старт := поз
цел расстояние := abs(цель - старт)
цел направление
если цель > старт то
направление := 1 // движение вправо
иначе
направление := -1 // движение влево
все
// Стратегия 1: только прыжки на 1
вещ стоимость1 := расстояние * вес_прыжка_1
// Стратегия 2: максимум прыжков на 2
цел прыжков_на_2 := расстояние div 2
цел прыжков_на_1 := расстояние mod 2
вещ стоимость2 := прыжков_на_2 * вес_прыжка_2 + прыжков_на_1 * вес_прыжка_1
// Выбираем оптимальную стратегию
если стоимость1 <= стоимость2 то
// Используем прыжки на 1
нц для i от 1 до расстояние
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
кц
вывод "Использована стратегия 1, стоимость: ", стоимость1
иначе
// Используем максимум прыжков на 2
нц для i от 1 до прыжков_на_2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
кц
если прыжков_на_1 > 0 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Использована стратегия 2, стоимость: ", стоимость2
все
кон |
|
Базовые задачи: зеркальные перемещения
Зеркальные перемещения — это интересный класс задач, где Кузнечик должен выполнять симметричные действия относительно какой-то точки или оси. Такие задачи отлично развивают пространственное мышление и понимание симметрии алгоритмов.
Задача 16: Зеркальное отражение относительно начала координат
Пусть Кузнечик находится в некоторой точке X. Требуется переместить его в точку -X, то есть в точку, симметричную относительно нуля.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| алг ЗеркальноеОтражение
нач
цел текущая_позиция := поз
цел цель := -текущая_позиция
цел расстояние := abs(цель - текущая_позиция)
// Определяем направление
цел направление
если цель > текущая_позиция то
направление := 1 // вправо
иначе
направление := -1 // влево
все
// Перемещаемся оптимальным путем
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| алг ЗеркальноеОтражениеУпрощенное
нач
цел текущая_позиция := поз
цел шагов := abs(текущая_позиция) * 2
// Если мы в положительной части оси, идем влево, иначе - вправо
цел направление := -знак(текущая_позиция)
нц пока шагов >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
шагов := шагов - 2
кц
если шагов = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кон |
|
Задача 17: Зеркальное отражение относительно заданной точки
Теперь усложним: нужно найти точку, симметричную текущей относительно заданной точки C.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| алг ОтражениеОтносительноТочки(цел C)
нач
цел X := поз
цел цель := 2*C - X // формула для нахождения симметричной точки
// Перемещаемся к цели оптимальным путем
цел расстояние := abs(цель - X)
цел направление := знак(цель - X)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кон |
|
2*C - X: если представить, что C — это "центр отражения", то расстояние от X до C равно расстоянию от C до искомой точки, но в противоположном направлении.
Задача 18: Последовательное зеркальное отражение
Представим, что нам нужно "отзеркалить" Кузнечика несколько раз относительно разных точек. Это можно реализовать с помощью вспомогательного алгоритма:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| алг ПоследовательныеОтражения(цел N, цел C1, цел C2, ... цел CN)
нач
цел X := поз
нц для i от 1 до N
цел C := тек_аргумент(i + 1) // +1 из-за смещения индексов
X := 2*C - X
// Перемещаемся к новой позиции
цел текущая := поз
цел расстояние := abs(X - текущая)
цел направление := знак(X - текущая)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
кц
кон |
|
Задача 19: Симметричные прыжки
Эта задача отличается от предыдущих: вместо того, чтобы искать симметричную позицию, Кузнечик должен выполнять симметричные действия. Например, после прыжка вправо на 2 он должен сразу прыгнуть влево на 2, и наоборот.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| алг СимметричныеПрыжки(цел N)
нач
цел начальная_позиция := поз
нц для i от 1 до N
ВПРАВО 2
ВЛЕВО 2
кц
// Кузнечик вернётся в исходную позицию
если поз = начальная_позиция то
вывод "Кузнечик вернулся в исходную точку"
иначе
вывод "Что-то пошло не так!"
все
кон |
|
Задача 20: Симметричная траектория
А что если мы хотим, чтобы Кузнечик двигался по симметричной траектории? Например, сначала N шагов в одном направлении, а затем N шагов в противоположном. Но при этом мы хотим оптимизировать общее количество прыжков.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| алг СимметричнаяТраектория(цел N)
нач
цел начальная_позиция := поз
цел промежуточная_позиция := начальная_позиция + N
// Движемся вправо на N
цел расстояние := abs(N)
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
// Проверяем, что достигли промежуточной точки
если поз <> промежуточная_позиция то
вывод "Ошибка: не достигли промежуточной точки!"
стоп
все
// Возвращаемся назад на N
расстояние := abs(N)
нц пока расстояние >= 2
ВЛЕВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВЛЕВО 1
все
// Проверяем, что вернулись в исходную точку
если поз <> начальная_позиция то
вывод "Ошибка: не вернулись в исходную точку!"
иначе
вывод "Успешно выполнили симметричную траекторию!"
все
кон |
|
Отдельно отмечу, что задачи на симметрию отлично подходят для изучения математических свойств алгоритмов. Например, мы убедились, что последовательность "прыжок вправо - прыжок влево" возвращает Кузнечика в исходную позицию. Это свойство коммутативности (порядок операций не важен) и инверсии (операция и её обратная операция компенсируют друг друга). На практике понимание таких принципов помогает создавать более элегантные и эффективные алгоритмы не только для Кузнечика, но и для решения реальных задач программирования.
Задачи среднего уровня: алгоритмы с условиями
Теперь, когда мы освоили базовые перемещения Кузнечика, пора перейти к задачам посложнее. В реальном программировании редко когда алгоритм состоит из линейной последовательности действий — почти всегда приходится принимать решения в зависимости от текущих условий. Именно этим мы и займемся в следующих задачах.
Задача 21: Прыжки до чётной позиции
Напишем алгоритм, который будет перемещать Кузнечика вправо до тех пор, пока он не окажется в чётной позиции. При этом нужно стараться минимизировать количество прыжков.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг ДвижениеДоЧетной
нач
цел текущая_позиция := поз
// Если уже в четной позиции, ничего делать не нужно
если текущая_позиция mod 2 = 0 то
стоп
все
// Иначе делаем один прыжок на 1, чтобы оказаться в четной позиции
ВПРАВО 1
кон |
|
Задача 22: Движение до позиции, кратной заданному числу
Усложним предыдущую задачу. Теперь нам нужно переместить Кузнечика вправо до позиции, кратной заданному числу N.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| алг ДвижениеДоКратнойN(цел N)
нач
цел текущая_позиция := поз
цел остаток := текущая_позиция mod N
// Если уже в позиции, кратной N, ничего делать не нужно
если остаток = 0 то
стоп
все
// Иначе вычисляем, сколько единиц нужно пройти
цел шагов := N - остаток
// Выполняем перемещение оптимальным путем
нц пока шагов >= 2
ВПРАВО 2
шагов := шагов - 2
кц
если шагов = 1 то
ВПРАВО 1
все
кон |
|
Задача 23: Движение до первой позиции из заданного набора
Теперь представим, что у нас есть набор "особых" точек на числовой прямой. Нужно переместить Кузнечика вправо до первой такой точки. Для простоты будем считать, что особые точки имеют вид K*N + M, где K — любое неотрицательное целое число, а N и M — заданные константы.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| алг ДвижениеДоОсобойТочки(цел N, цел M)
нач
цел текущая_позиция := поз
// Проверяем, не находимся ли уже в особой точке
если текущая_позиция mod N = M mod N то
стоп
все
// Вычисляем расстояние до ближайшей особой точки справа
цел остаток := текущая_позиция mod N
цел расстояние
если остаток <= M mod N то
расстояние := (M mod N) - остаток
иначе
расстояние := N - остаток + (M mod N)
все
// Перемещаемся на нужное расстояние
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
кон |
|
Задача 24: Движение до точки, удовлетворяющей условию
А что если условие, которому должна удовлетворять целевая точка, более сложное? Например, мы хотим найти точку, для которой сумма цифр равна заданному числу S. Такая задача уже требует более сложной логики.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| алг СуммаЦифр(цел число)
нач
цел результат := 0
цел n := abs(число)
нц пока n > 0
результат := результат + (n mod 10)
n := n div 10
кц
знач := результат
кон
алг ДвижениеДоТочкиСЗаданнойСуммойЦифр(цел S)
нач
цел текущая_позиция := поз
цел текущая_сумма := СуммаЦифр(текущая_позиция)
// Двигаемся вправо, пока не найдем подходящую точку
нц пока текущая_сумма <> S
ВПРАВО 1
текущая_позиция := поз
текущая_сумма := СуммаЦифр(текущая_позиция)
кц
кон |
|
СуммаЦифр, которая вычисляет сумму цифр числа. Затем в основном алгоритме мы перемещаем Кузнечика вправо по одной единице, пока не найдем точку с требуемой суммой цифр. Обратите внимание, что этот алгоритм может выполняться очень долго, если таких точек мало или они находятся далеко. Для реальных задач может потребоваться добавить ограничение на максимальное количество шагов или расстояние.
Задача 25: Движение с обходом препятствий
Представим, что на числовой прямой есть "стены" — точки, через которые Кузнечик не может прыгнуть. Нужно написать алгоритм, который перемещает Кузнечика из точки A в точку B, обходя препятствия.
Для простоты будем считать, что стены находятся в точках, кратных некоторому числу W.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| алг ДвижениеСОбходомПрепятствий(цел B, цел W)
нач
цел A := поз
цел направление
если B > A то
направление := 1 // движение вправо
иначе
направление := -1 // движение влево
все
// Пока не достигли цели
нц пока поз <> B
цел текущая := поз
цел следующая_1 := текущая + 1 * направление
цел следующая_2 := текущая + 2 * направление
// Проверяем, не является ли следующая позиция стеной
лог стена_1 := (следующая_1 mod W = 0)
лог стена_2 := (следующая_2 mod W = 0)
// Выбираем оптимальный прыжок
если abs(B - текущая) = 1 и не стена_1 то
// Если до цели остался 1 шаг и нет стены
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
иначе если abs(B - текущая) >= 2 и не стена_2 то
// Если до цели минимум 2 шага и нет стены при прыжке на 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
иначе если не стена_1 то
// Если нет стены при прыжке на 1
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
иначе
// Если всё заблокировано, сообщаем об ошибке
вывод "Невозможно достичь цели из-за стен!"
стоп
все
кц
кон |
|
Задача 26: Движение с ограниченным запасом энергии
Представим, что у Кузнечика есть ограниченный запас энергии E. Каждый прыжок на 1 тратит 1 единицу энергии, а прыжок на 2 — 3 единицы (то есть он менее эффективен, но позволяет продвинуться дальше). Нужно переместить Кузнечика как можно правее, полностью израсходовав запас энергии.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| алг ДвижениеСОграниченнойЭнергией(цел E)
нач
// Пока есть энергия на прыжок
нц пока E >= 1
// Проверяем, что выгоднее - прыжок на 1 или на 2
если E >= 3 то
// Сравниваем эффективность:
// 1 прыжок на 2 (расход 3) vs 2 прыжка на 1 (расход 2)
если E = 3 или E = 4 то
// Если осталось ровно 3 или 4 единицы энергии,
// один прыжок на 2 эффективнее, чем два по 1 (остаток 1 или 2)
ВПРАВО 2
E := E - 3
иначе
// В остальных случаях эффективнее прыжки на 1
ВПРАВО 1
E := E - 1
все
иначе
// Если энергии меньше 3, то только прыжок на 1
ВПРАВО 1
E := E - 1
все
кц
вывод "Энергия исчерпана. Кузнечик в позиции ", поз
кон |
|
Задача 27: Движение с переменной длиной прыжка
До сих пор мы рассматривали только стандартные прыжки Кузнечика на 1 и 2 единицы. А что если длина прыжка может меняться в зависимости от текущей позиции? Например, в чётных позициях Кузнечик может прыгать на 1, 2 или 3 единицы, а в нечётных — только на на 1 или 2.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| алг ДвижениеСПеременнойДлинойПрыжка(цел цель)
нач
цел текущая := поз
нц пока текущая <> цель
цел расстояние := abs(цель - текущая)
цел направление := знак(цель - текущая)
// Определяем доступные длины прыжка
цел макс_прыжок
если текущая mod 2 = 0 то
макс_прыжок := 3 // в четных позициях можно прыгать на 3
иначе
макс_прыжок := 2 // в нечетных — только на 2
все
// Выбираем оптимальную длину прыжка
цел длина_прыжка
если расстояние <= макс_прыжок то
длина_прыжка := расстояние // если цель близко, прыгаем точно в неё
иначе
длина_прыжка := макс_прыжок // иначе используем максимальный прыжок
все
// Выполняем прыжок
если направление > 0 то
нц для i от 1 до длина_прыжка
ВПРАВО 1
кц
иначе
нц для i от 1 до длина_прыжка
ВЛЕВО 1
кц
все
текущая := поз
кц
кон |
|
Задачи среднего уровня: циклические конструкции
Циклы — настоящая рабочая лошадка программирования. Если вы когда-нибудь пытались вручную написать однотипные действия десять или сто раз, вы точно поймете, почему циклические конструкции так важны. В контексте нашего Кузнечика циклы становятся ключевым инструментом для решения задач, требующих повторяющихся действий или перебора вариантов.
Задача 28: Движение по числовой прямой с заданным шаблоном
Допустим, Кузнечику нужно двигаться по определённому шаблону: 2 шага вправо, 1 шаг влево. И так повторять N раз.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг ДвижениеПоШаблону(цел N)
нач
цел начальная_позиция := поз
нц для i от 1 до N
ВПРАВО 2
ВЛЕВО 1
кц
вывод "Кузнечик переместился с позиции ", начальная_позиция, " на позицию ", поз
вывод "Общее смещение: ", поз - начальная_позиция
кон |
|
Задача 29: Движение до заданной точки с возвратом
А теперь представим, что Кузнечику нужно добраться до точки X, затем вернуться в исходную точку, и повторить это действие несколько раз.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| алг ЦиклическиеПоходы(цел X, цел кол_походов)
нач
цел дом := поз
цел пройдено_всего := 0
нц для поход от 1 до кол_походов
// Идём к точке X
цел расстояние := abs(X - поз)
цел направление := знак(X - поз)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
пройдено_всего := пройдено_всего + 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
пройдено_всего := пройдено_всего + 1
все
вывод "Поход ", поход, ": Кузнечик достиг точки ", X
// Возвращаемся домой
расстояние := abs(дом - поз)
направление := знак(дом - поз)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
пройдено_всего := пройдено_всего + 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
пройдено_всего := пройдено_всего + 1
все
вывод "Поход ", поход, ": Кузнечик вернулся домой"
кц
вывод "Всего пройдено: ", пройдено_всего, " единиц"
кон |
|
Задача 30: Поиск точки с заданным свойством
В этой задаче Кузнечик должен найти точку с определённым свойством. Например, найдём первую точку справа от текущей позиции, сумма цифр которой равна 10.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| алг СуммаЦифр(цел число)
нач
цел сумма := 0
цел н := abs(число)
нц пока н > 0
сумма := сумма + (н mod 10)
н := н div 10
кц
знач := сумма
кон
алг НайтиТочкуССуммойЦифр10
нач
цел старт := поз
цел текущая_сумма := СуммаЦифр(поз)
цел шагов := 0
нц пока текущая_сумма <> 10
ВПРАВО 1
шагов := шагов + 1
текущая_сумма := СуммаЦифр(поз)
// Ограничение на количество шагов, чтобы избежать бесконечного цикла
если шагов > 100 то
вывод "Точка не найдена в пределах 100 шагов"
стоп
все
кц
вывод "Найдена точка ", поз, " с суммой цифр 10"
вывод "Расстояние от начальной точки: ", шагов
кон |
|
Задача 31: Поиск всех точек с заданным свойством на интервале
Теперь усложним задачу: найти все точки на интервале [A, B], сумма цифр которых равна заданному числу S.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| алг НайтиВсеТочкиССуммойЦифрНаИнтервале(цел A, цел B, цел S)
нач
цел текущая := A
цел найдено := 0
// Переместиться в точку A
цел начальная := поз
цел расстояние := abs(A - начальная)
цел направление := знак(A - начальная)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Проверяем все точки от A до B
нц пока текущая <= B
если СуммаЦифр(текущая) = S то
вывод "Найдена точка ", текущая
найдено := найдено + 1
все
если текущая < B то
ВПРАВО 1
текущая := поз
иначе
стоп
все
кц
вывод "Всего найдено точек: ", найдено
кон |
|
Задача 32: Циклический маршрут с возвращением
Представим, что Кузнечик должен пройти по маршруту с точками X₁, X₂, ..., Xₙ, а затем вернуться в исходную позицию.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| алг ЦиклическийМаршрут(цел X[], цел N)
нач
цел дом := поз
цел текущая_позиция := дом
цел пройдено_всего := 0
// Проходим по всем точкам маршрута
нц для i от 1 до N
цел целевая := X[i]
цел расстояние := abs(целевая - текущая_позиция)
цел направление := знак(целевая - текущая_позиция)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
пройдено_всего := пройдено_всего + 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
пройдено_всего := пройдено_всего + 1
все
текущая_позиция := поз
вывод "Достигнута точка ", i, ": ", текущая_позиция
кц
// Возвращаемся домой
цел расстояние := abs(дом - текущая_позиция)
цел направление := знак(дом - текущая_позиция)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
пройдено_всего := пройдено_всего + 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
пройдено_всего := пройдено_всего + 1
все
вывод "Кузнечик вернулся домой"
вывод "Всего пройдено: ", пройдено_всего, " единиц"
кон |
|
Задача 33: Циклический поиск оптимального пути
А теперь рассмотрим более сложную задачу: найти оптимальный путь между двумя точками с учётом препятствий. Препятствиями будут точки, кратные заданному числу W.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| алг ОптимальныйПутьСПрепятствиями(цел цель, цел W)
нач
цел старт := поз
цел лучший_путь := 100000 // Большое число для начального значения
цел лучшая_длина_шага := 0
// Перебираем различные стратегии движения
нц для длина_шага от 1 до 2
// Возвращаемся на старт
цел текущая := поз
цел расстояние := abs(старт - текущая)
цел направление := знак(старт - текущая)
нц пока расстояние >= 2
если направление = 1 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление = 1 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Параметры для этой стратегии
цел шагов := 0
лог успех := истина
// Пробуем достичь цели с заданной длиной шага
нц пока поз <> цель и успех
// Проверяем, можно ли сделать шаг заданной длины
если (поз + длина_шага) mod W = 0 или (поз - длина_шага) mod W = 0 то
// Если шаг ведет на препятствие, пробуем другую длину
если длина_шага = 1 то
длина_шага := 2
иначе
длина_шага := 1
все
все
// Выбираем направление движения
направление := знак(цель - поз)
// Выполняем шаг
если направление = 1 то
если длина_шага = 1 то
ВПРАВО 1
иначе
ВПРАВО 2
все
иначе
если длина_шага = 1 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
все
шагов := шагов + 1
// Проверяем на бесконечный цикл
если шагов > 100 то
успех := ложь
вывод "Стратегия с шагом ", длина_шага, " зациклилась"
все
кц
если успех и шагов < лучший_путь то
лучший_путь := шагов
лучшая_длина_шага := длина_шага
все
кц
если лучший_путь < 100000 то
вывод "Оптимальный путь: ", лучший_путь, " шагов с длиной шага ", лучшая_длина_шага
иначе
вывод "Не удалось найти путь к цели"
все
кон |
|
Задача 34: Циклическое построение фигуры
Напоследок попробуем что-то совсем необычное: пусть Кузнечик "нарисует" фигуру, циклически перемещаясь по числовой прямой. Например, треугольную форму: постепенно увеличивая, а затем уменьшая длину прыжка.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| алг НарисоватьТреугольник(цел размер)
нач
цел начальная := поз
// Увеличиваем длину прыжка
нц для i от 1 до размер
нц для j от 1 до i
ВПРАВО 1
кц
вывод "Позиция после прыжка ", i, ": ", поз
кц
// Уменьшаем длину прыжка
нц для i от размер-1 до 1 шаг -1
нц для j от 1 до i
ВПРАВО 1
кц
вывод "Позиция после прыжка ", i, ": ", поз
кц
вывод "Треугольник построен. Начальная позиция: ", начальная, ", конечная позиция: ", поз
вывод "Смещение: ", поз - начальная
кон |
|
размер. Циклические конструкции существенно расширяют возможности нашего Кузнечика, позволяя ему выполнять сложные последовательности действий, искать точки с заданными свойствами и находить оптимальные пути. Используйте циклы всякий раз, когда нужно повторить действие несколько раз или перебрать различные варианты — это сделает ваши программы более компактными и эффективными.
Ещё один важный момент: всегда думайте о возможности бесконечного цикла и добавляйте защитные механизмы, такие как ограничение на максимальное количество итераций. Иначе ваш Кузнечик может прыгать вечно, так и не достигнув цели!
Задачи среднего уровня: оптимизация программы
Оптимизация программ — искусство делать больше с меньшими ресурсами. Для Кузнечика это особенно актуально, ведь часто нам нужно решать задачи за минимальное количество шагов или с самыми простыми алгоритмами. Давайте рассмотрим несколько подходов к оптимизации программ для нашего прыгучего друга.
Задача 35: Минимизация количества команд
В первой задаче на оптимизацию попробуем переписать длинную программу, используя минимальное количество строк кода. Исходный алгоритм выглядит так:
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг ДлинныйПуть
нач
ВПРАВО 2
ВПРАВО 2
ВПРАВО 1
ВЛЕВО 1
ВПРАВО 2
ВПРАВО 1
ВЛЕВО 1
ВПРАВО 2
кон |
|
| Code | 1
2
3
4
5
6
7
| алг ОптимизированныйПуть
нач
ВПРАВО 2
ВПРАВО 2
ВПРАВО 2
ВПРАВО 2
кон |
|
Задача 36: Применение вспомогательных алгоритмов
Когда некоторая последовательность команд повторяется несколько раз, имеет смысл выделить её в отдельный вспомогательный алгоритм:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| алг Шаг3Вправо
нач
ВПРАВО 2
ВПРАВО 1
кон
алг ПовторяющиесяШаги
нач
Шаг3Вправо()
ВЛЕВО 1
ВПРАВО 2
Шаг3Вправо()
ВЛЕВО 1
ВПРАВО 2
Шаг3Вправо()
кон |
|
Шаг3Вправо делает код более читаемым и легко модифицируемым. Если, например, появится команда "ВПРАВО 3", вам достаточно будет изменить реализацию Шаг3Вправо, а не искать и заменять каждую пару "ВПРАВО 2, ВПРАВО 1" в основной программе.
Задача 37: Оптимизация с использованием циклов
Циклы — мощный инструмент оптимизации, особенно когда нужно выполнить одинаковые действия много раз:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| алг БезЦикла
нач
ВПРАВО 2
ВПРАВО 2
ВПРАВО 2
ВПРАВО 2
ВПРАВО 2
кон
алг СЦиклом
нач
нц для i от 1 до 5
ВПРАВО 2
кц
кон |
|
Задача 38: Оптимизация условных конструкций
Иногда программы содержат сложные вложенные условные конструкции, которые можно упростить:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| алг СложныеУсловия
нач
цел позиция := поз
если позиция > 0 то
если позиция mod 2 = 0 то
если позиция < 10 то
ВПРАВО 2
иначе
ВПРАВО 1
все
иначе
если позиция < 10 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
иначе
если позиция mod 2 = 0 то
если позиция > -10 то
ВЛЕВО 2
иначе
ВЛЕВО 1
все
иначе
если позиция > -10 то
ВЛЕВО 1
иначе
ВПРАВО 1
все
все
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| алг ОптимизированныеУсловия
нач
цел позиция := поз
// Положительная четная позиция < 10
если позиция > 0 и позиция mod 2 = 0 и позиция < 10 то
ВПРАВО 2
// Положительная четная позиция >= 10
иначе если позиция > 0 и позиция mod 2 = 0 и позиция >= 10 то
ВПРАВО 1
// Положительная нечетная позиция < 10
иначе если позиция > 0 и позиция mod 2 = 1 и позиция < 10 то
ВПРАВО 1
// Положительная нечетная позиция >= 10
иначе если позиция > 0 и позиция mod 2 = 1 и позиция >= 10 то
ВЛЕВО 1
// Отрицательная четная позиция > -10
иначе если позиция <= 0 и позиция mod 2 = 0 и позиция > -10 то
ВЛЕВО 2
// Отрицательная четная позиция <= -10
иначе если позиция <= 0 и позиция mod 2 = 0 и позиция <= -10 то
ВЛЕВО 1
// Отрицательная нечетная позиция > -10
иначе если позиция <= 0 и позиция mod 2 = 1 и позиция > -10 то
ВЛЕВО 1
// Отрицательная нечетная позиция <= -10
иначе
ВПРАВО 1
все
кон |
|
Задача 39: Оптимизация через математические расчеты
Иногда можно существенно оптимизировать программу, используя математические расчеты вместо последовательного перебора:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| алг НеоптимальныйПоискКратных3
нач
цел начальная := поз
цел найдено := 0
цел проверено := 0
нц пока найдено < 5 и проверено < 100
если поз mod 3 = 0 то
вывод "Найдена точка, кратная 3: ", поз
найдено := найдено + 1
все
ВПРАВО 1
проверено := проверено + 1
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| алг ОптимальныйПоискКратных3
нач
цел начальная := поз
// Находим ближайшее число, кратное 3, не меньшее текущей позиции
цел остаток := поз mod 3
цел первая_кратная := поз
если остаток <> 0 то
первая_кратная := поз + (3 - остаток)
все
// Переходим к ней
цел расстояние := первая_кратная - поз
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
// Находим еще 4 кратных тройке
нц для i от 1 до 4
ВПРАВО 2
ВПРАВО 1
вывод "Найдена точка, кратная 3: ", поз
кц
кон |
|
Задача 40: Оптимизация рекурсивных алгоритмов
Рекурсия — мощный инструмент, но часто рекурсивные алгоритмы можно оптимизировать, превратив их в итеративные:
| Code | 1
2
3
4
5
6
7
8
9
| алг РекурсивныйФибоначчи(цел n)
нач
если n <= 2 то
ВПРАВО 1
иначе
РекурсивныйФибоначчи(n - 1)
РекурсивныйФибоначчи(n - 2)
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| алг ИтеративныйФибоначчи(цел n)
нач
если n <= 0 то
стоп
все
если n = 1 или n = 2 то
ВПРАВО 1
стоп
все
цел a := 1
цел b := 1
цел c
нц для i от 3 до n
c := a + b
a := b
b := c
кц
нц для i от 1 до b
ВПРАВО 1
кц
кон |
|
Задача 41: Комплексная оптимизация на примере алгоритма Евклида
Напоследок рассмотрим более сложный пример — реализацию алгоритма Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Кузнечик будет перемещаться по числовой прямой так, чтобы его итоговая позиция соответствовала НОД:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| алг НОД_Неоптимальный(цел a, цел b)
нач
// Перемещаемся в позицию 0
цел начальная := поз
цел расстояние := abs(начальная)
нц пока расстояние >= 2
если начальная > 0 то
ВЛЕВО 2
иначе
ВПРАВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если начальная > 0 то
ВЛЕВО 1
иначе
ВПРАВО 1
все
все
// Реализация алгоритма Евклида
нц пока b <> 0
цел остаток := a mod b
a := b
b := остаток
кц
// Перемещаемся в позицию, соответствующую НОД
нц для i от 1 до a
ВПРАВО 1
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| алг НОД_Оптимальный(цел a, цел b)
нач
// Перемещаемся в позицию 0 оптимальным образом
цел начальная := поз
если начальная <> 0 то
цел расстояние := abs(начальная)
цел направление := -знак(начальная)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
все
// Ускоренный алгоритм Евклида
нц пока b <> 0
цел остаток := a mod b
a := b
b := остаток
кц
// Перемещаемся в позицию, соответствующую НОД, оптимальным образом
нц пока a >= 2
ВПРАВО 2
a := a - 2
кц
если a = 1 то
ВПРАВО 1
все
кон |
|
1. Более эффективно перемещаемся в начальную позицию 0.
2. Используем ту же реализацию алгоритма Евклида (здесь оптимизация не требуется).
3. Оптимизируем перемещение в позицию, соответствующую НОД, используя максимально возможные прыжки по 2 единицы.
Оптимизация программ для Кузнечика — это не просто упражнение на время. Это помогает развивать важные навыки программирования: поиск закономерностей, упрощение алгоритмов, использование математических свойств, применение подходящих структур данных. Эти навыки перенесутся и на другие языки программирования, помогая писать более эффективный и элегантный код.
Задачи среднего уровня: ограниченный набор команд
Часто в программировании мы сталкиваемся с ограничениями. Иногда это связано с особенностями языка или платформы, иногда — с требованиями задачи. Работа в условиях ограниченного набора команд помогает развить креативное мышление и глубже понять базовые алгоритмические принципы. В этом разделе мы рассмотрим задачи, где стандартный набор команд Кузнечика дополнительно ограничен.
Задача 42: Только команда ВПРАВО 1
Представим, что у Кузнечика осталась только команда ВПРАВО 1. Как в таких условиях переместить его на заданное расстояние вправо?
| Code | 1
2
3
4
5
6
| алг ТолькоВправоНа1(цел N)
нач
нц для i от 1 до N
ВПРАВО 1
кц
кон |
|
ВПРАВО 1 нужное количество раз. Но что если нам нужно переместиться влево?
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ВлевоТолькоСВправо1(цел N)
нач
цел макс_позиция := 1000000 // Достаточно большое число
// Перемещаемся в большую отрицательную позицию,
// делая полный круг по числовой прямой
нц для i от 1 до макс_позиция - N
ВПРАВО 1
кц
кон |
|
Задача 43: Только команды ВПРАВО 1 и ВЛЕВО 1
Теперь допустим, что у нас есть только команды ВПРАВО 1 и ВЛЕВО 1. Как переместиться на 5 единиц вправо за минимальное количество команд?
| Code | 1
2
3
4
5
6
| алг Вправо5ТолькоПо1(цел N)
нач
нц для i от 1 до N
ВПРАВО 1
кц
кон |
|
ВПРАВО 2?
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг Вправо2Используя1
нач
ВПРАВО 1
ВПРАВО 1
кон
алг Вправо5ИспользуяВправо2
нач
Вправо2Используя1()
Вправо2Используя1()
ВПРАВО 1
кон |
|
Вправо2Используя1, который выполняет два шага вправо по одному. Затем используем его дважды и добавляем ещё один шаг вправо, получая в итоге перемещение на 5 единиц.
Задача 44: Только команда ВПРАВО 2
А что если у нас есть только команда ВПРАВО 2? Как переместить Кузнечика на нечётное количество единиц вправо?
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
| алг Вправо5ТолькоС2
нач
ВПРАВО 2
ВПРАВО 2
// Для последней единицы у нас нет команды ВПРАВО 1
// Поэтому делаем трюк: шаг вперед на 2 и шаг назад на 1
// Но у нас нет ВЛЕВО 1, поэтому...
// Перемещаемся вправо на большое расстояние, делая круг
нц для i от 1 до 1000000 - 1
ВПРАВО 2
кц
кон |
|
1000000 - 1 шагов по 2, что в итоге даёт смещение на 1 единицу вправо от текущей позиции. Более практичное решение — реализовать команду ВПРАВО 1 через комбинацию доступных команд:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| алг Вправо1Используя2
нач
// Имитируем ВПРАВО 1 с помощью ВПРАВО 2
// Идея: ВПРАВО 2 + ВПРАВО 2 + ... + ВПРАВО 2 (N раз) = ВПРАВО (2*N)
// Если 2*N = 1 + число_точек_на_прямой, то получаем ВПРАВО 1
нц для i от 1 до ((2^31 - 1) div 2)
ВПРАВО 2
кц
кон
алг Вправо5ТолькоС2Оптимизированный
нач
ВПРАВО 2
ВПРАВО 2
Вправо1Используя2()
кон |
|
ВПРАВО 1.
Задача 45: Команды ВПРАВО 1 и ВПРАВО 3
Теперь представим, что у нас есть только команды ВПРАВО 1 и ВПРАВО 3. Как переместиться на 5 единиц вправо?
| Code | 1
2
3
4
5
6
| алг Вправо5С1и3
нач
ВПРАВО 3
ВПРАВО 1
ВПРАВО 1
кон |
|
| Code | 1
2
3
4
5
| алг Вправо4С1и3
нач
ВПРАВО 3
ВПРАВО 1
кон |
|
ВПРАВО 1 и ВПРАВО 3 мы можем переместиться на любое положительное расстояние. Действительно, любое целое число N >= 2 можно представить в виде N = 3k + m, где k >= 0 и m = 0, 1, 2. Тогда:
Если m = 0, то N = 3k, и мы просто используем k раз команду ВПРАВО 3
Если m = 1, то N = 3k + 1, и мы используем k раз команду ВПРАВО 3 и один раз ВПРАВО 1
Если m = 2, то N = 3k + 2, и мы используем k раз команду ВПРАВО 3 и два раза ВПРАВО 1
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
| алг ВправоНаNС1и3(цел N)
нач
цел k := N div 3
цел m := N mod 3
нц для i от 1 до k
ВПРАВО 3
кц
нц для i от 1 до m
ВПРАВО 1
кц
кон |
|
ВЛЕВО? Если у нас нет соответствующих команд, мы опять можем использовать прием с переполнением:
| Code | 1
2
3
4
5
6
| алг ВлевоНа1С1и3
нач
нц для i от 1 до (2^31 - 1) - 1
ВПРАВО 1
кц
кон |
|
Задача 46: Произвольные команды
Обобщим наши наблюдения. Пусть у нас есть набор команд ВПРАВО a, ВПРАВО b, ..., ВПРАВО z с положительными целыми параметрами a, b, ..., z. Можем ли мы перемещаться на любое положительное расстояние? Оказывается, это возможно тогда и только тогда, когда наибольший общий делитель (НОД) чисел a, b, ..., z равен 1. Если НОД больше 1, то мы сможем переместиться только на расстояния, кратные этому НОД.
Например, команды ВПРАВО 2 и ВПРАВО 4 не позволят переместиться на нечётное расстояние, так как НОД(2, 4) = 2. А команды ВПРАВО 2 и ВПРАВО 3 позволят достичь любой точки, так как НОД(2, 3) = 1. Реализуем алгоритм, который проверяет, можно ли с заданным набором команд достичь произвольной точки:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| алг НОД(цел a, цел b)
нач
нц пока b <> 0
цел остаток := a mod b
a := b
b := остаток
кц
знач := a
кон
алг МожноДостичьПроизвольнойТочки(цел команды[], цел N)
нач
// Находим НОД всех команд
цел общий_нод := команды[1]
нц для i от 2 до N
общий_нод := НОД(общий_нод, команды[i])
кц
если общий_нод = 1 то
вывод "Можно достичь произвольной точки"
иначе
вывод "Можно достичь только точек, отстоящих на расстояния, кратные ", общий_нод
все
кон |
|
Задача 47: Команды с отрицательными параметрами
А что если разрешить команды с отрицательными параметрами, например, ВПРАВО -3? Такая команда эквивалентна ВЛЕВО 3. С такими командами мы можем перемещаться как вправо, так и влево. Например, с командами ВПРАВО 2 и ВПРАВО -3 мы можем достичь любой точки на прямой. Почему? Потому что НОД(2, 3) = 1, и мы можем представить любое целое число как линейную комбинацию a*2 + b*(-3), где a и b — целые числа.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| алг ДостичьПроизвольнойТочкиСОтрицательными(цел цель)
нач
цел текущая := поз
цел разница := цель - текущая
// Используем расширенный алгоритм Евклида для нахождения представления
// разницы в виде a*2 + b*(-3)
// Это сложная задача, поэтому здесь упрощенная версия
нц пока разница <> 0
если разница > 0 то
если разница mod 2 = 0 то
// Если разница четная, просто прыгаем на 2
ВПРАВО 2
разница := разница - 2
иначе
// Если разница нечетная, используем комбинацию +2-3=-1
ВПРАВО 2
ВПРАВО -3
разница := разница - (-1)
все
иначе
если -разница mod 3 = 0 то
// Если разница кратна -3, прыгаем на -3
ВПРАВО -3
разница := разница - (-3)
иначе
// Используем комбинацию -3+2=-1
ВПРАВО -3
ВПРАВО 2
разница := разница - (-1)
все
все
кц
кон |
|
ВПРАВО 2 и ВПРАВО -3 мы можем переместиться на 1 единицу в любом направлении: вперёд (2 + (-3) + 2 = 1) или назад (-3 + 2 = -1).
Работа с ограниченным набором команд — полезное упражнение, которое помогает лучше понять числовые свойства и взаимосвязи. Такие задачи часто встречаются в олимпиадном программировании и собеседованиях, а их решение сродни головоломке: нужно найти хитрый способ достичь цели с ограниченными ресурсами. Самое интересное в таких задачах — открытие того, что даже с очень ограниченным набором инструментов часто можно решить произвольную задачу, если правильно их комбинировать. Это справедливо не только для Кузнечика, но и для программирования в целом, где зачастую решение сложной задачи складывается из простых, хорошо известных операций.
Задачи среднего уровня: симметричные перемещения
Симметрия — одно из самых красивых явлений как в математике, так и в программировании. Создание симметричных алгоритмов не только эстетически приятно, но и часто приводит к элегантным и эффективным решениям. В этом разделе мы рассмотрим задачи, где Кузнечик выполняет симметричные перемещения по числовой прямой.
Задача 48: Симметричное движение относительно начала координат
Попробуем написать алгоритм, который перемещает Кузнечика симметрично относительно нуля. То есть, если Кузнечик начинает в точке X, то он должен закончить в точке -X.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| алг СимметричноОтносительноНуля
нач
цел начальная_позиция := поз
цел целевая_позиция := -начальная_позиция
// Определяем направление движения
цел направление := знак(целевая_позиция - начальная_позиция)
цел расстояние := abs(целевая_позиция - начальная_позиция)
// Перемещаемся оптимальным путём
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Кузнечик переместился из ", начальная_позиция, " в ", поз
кон |
|
Задача 49: Симметричная траектория движения
Теперь напишем алгоритм, при котором Кузнечик движется по симметричной траектории. Пусть он сначала идёт N шагов вправо, а затем N шагов влево, возвращаясь в исходную точку. Но во время движения он должен отмечать все точки, которые посещает.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| алг СимметричнаяТраектория(цел N)
нач
цел начальная_позиция := поз
цел[] посещенные := новый_массив(2*N + 1, 0)
цел индекс := 0
посещенные[индекс] := поз
индекс := индекс + 1
// Движение вправо
нц для i от 1 до N
ВПРАВО 1
посещенные[индекс] := поз
индекс := индекс + 1
кц
// Движение влево
нц для i от 1 до N
ВЛЕВО 1
посещенные[индекс] := поз
индекс := индекс + 1
кц
// Выводим траекторию
вывод "Траектория Кузнечика: "
нц для i от 0 до 2*N
вывод посещенные[i], " "
кц
// Проверяем, что вернулись в исходную точку
если поз = начальная_позиция то
вывод "Кузнечик успешно вернулся в исходную точку"
иначе
вывод "Что-то пошло не так: ", поз, " != ", начальная_позиция
все
кон |
|
Задача 50: Симметричные прыжки вперед-назад
В этой задаче Кузнечик должен выполнять симметричные прыжки: сначала на N единиц вправо, затем на N единиц влево, затем на N-1 единиц вправо, затем на N-1 единиц влево, и так далее до 1.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| алг СимметричныеПрыжкиУменьшающиеся(цел N)
нач
цел начальная_позиция := поз
цел максимальное_отклонение := 0
нц для длина от N до 1 шаг -1
// Прыжок вправо
цел i := длина
нц пока i >= 2
ВПРАВО 2
i := i - 2
кц
если i = 1 то
ВПРАВО 1
все
// Запоминаем максимальное отклонение
если abs(поз - начальная_позиция) > максимальное_отклонение то
максимальное_отклонение := abs(поз - начальная_позиция)
все
// Прыжок влево
i := длина
нц пока i >= 2
ВЛЕВО 2
i := i - 2
кц
если i = 1 то
ВЛЕВО 1
все
кц
вывод "Максимальное отклонение: ", максимальное_отклонение
вывод "Конечная позиция: ", поз
кон |
|
Задача 51: Движение по симметричной функции
В этой задаче Кузнечик должен двигаться согласно значениям некоторой симметричной функции. Например, пусть он перемещается по точкам, соответствующим параболе y = x².
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| алг ДвижениеПоПараболе(цел N)
нач
цел начальная_позиция := поз
// Перемещаемся в точку 0 для начала
цел расстояние := abs(начальная_позиция)
цел направление := -знак(начальная_позиция)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Проходим по точкам от -N до N
нц для x от -N до N
// Вычисляем значение y = x^2
цел y := x*x
// Перемещаемся в точку y
цел текущая := поз
расстояние := abs(y - текущая)
направление := знак(y - текущая)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "x = ", x, ", y = ", поз
кц
кон |
|
Задача 52: Симметричные колебания
Напишем теперь алгоритм, который имитирует затухающие колебания: Кузнечик совершает прыжки вправо-влево с постепенно уменьшающейся амплитудой.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| алг ЗатухающиеКолебания(цел начальная_амплитуда, вещ коэффициент_затухания)
нач
цел начальная_позиция := поз
цел текущая_амплитуда := начальная_амплитуда
нц пока текущая_амплитуда > 0
// Прыжок вправо на текущую амплитуду
цел расстояние := текущая_амплитуда
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
вывод "Позиция после прыжка вправо: ", поз
// Прыжок влево на двойную амплитуду (чтобы оказаться слева от начальной точки)
расстояние := 2 * текущая_амплитуда
нц пока расстояние >= 2
ВЛЕВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВЛЕВО 1
все
вывод "Позиция после прыжка влево: ", поз
// Прыжок вправо на текущую амплитуду (возвращаемся в начальную точку)
расстояние := текущая_амплитуда
нц пока расстояние >= 2
ВПРАВО 2
расстояние := расстояние - 2
кц
если расстояние = 1 то
ВПРАВО 1
все
вывод "Вернулись в центральное положение: ", поз
// Уменьшаем амплитуду
текущая_амплитуда := цел(текущая_амплитуда * коэффициент_затухания)
кц
кон |
|
Задача 53: Симметричное движение в двух направлениях
А теперь представим, что два Кузнечика начинают движение из одной точки в противоположных направлениях. Мы будем имитировать их одновременное движение, управляя только одним Кузнечиком и вычисляя позицию второго.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| алг ДваКузнечикаСимметрично(цел N)
нач
цел начальная := поз
цел позиция_второго := начальная
вывод "Начальная позиция: ", начальная
нц для шаг от 1 до N
// Первый Кузнечик движется вправо
ВПРАВО 1
// Вычисляем позицию второго Кузнечика (симметрично)
позиция_второго := позиция_второго - 1
вывод "Шаг ", шаг, ": Кузнечик 1 в позиции ", поз, ", Кузнечик 2 в позиции ", позиция_второго
кц
// Проверяем симметрию: сумма позиций должна быть 2*начальная
если поз + позиция_второго = 2 * начальная то
вывод "Симметрия соблюдена"
иначе
вывод "Ошибка в симметрии"
все
кон |
|
Симметричные перемещения — интересная категория задач, демонстрирующая важные математические концепции и алгоритмические приемы. Они не только развивают алгоритмическое мышление, но и помогают лучше понять геометрические свойства задач.
Особенно ценно то, что многие симметричные алгоритмы обладают приятными свойствами, такими как возврат в исходную точку после определенной последовательности действий или поддержание баланса между движениями в разных направлениях. Эти свойства можно использовать для проверки корректности работы алгоритма и для оптимизации его выполнения.
Продвинутые задачи: сложные алгоритмические конструкции
Теперь перейдём к более сложным задачам для Кузнечика, где потребуется применение продвинутых алгоритмических подходов. Эти задачи помогут не только освоить КуМир на более глубоком уровне, но и развить алгоритмическое мышление в целом.
Задача 54: Рекурсивное перемещение с ветвлением
Рекурсия — мощный инструмент программирования, позволяющий решать задачи путём сведения их к задачам меньшего размера. Рассмотрим алгоритм, который использует рекурсию для нахождения пути к заданной точке.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| алг РекурсивныйПуть(цел цель, цел глубина)
нач
цел текущая := поз
// Базовый случай: мы достигли цели
если текущая = цель то
вывод "Цель достигнута за ", глубина, " шагов"
стоп
все
// Превышена максимальная глубина рекурсии
если глубина > 10 то
стоп
все
// Рекурсивный вызов с шагом вправо на 1
ВПРАВО 1
РекурсивныйПуть(цель, глубина + 1)
ВЛЕВО 1 // Возвращаемся назад при возврате из рекурсии
// Рекурсивный вызов с шагом вправо на 2
ВПРАВО 2
РекурсивныйПуть(цель, глубина + 1)
ВЛЕВО 2 // Возвращаемся назад
// Рекурсивный вызов с шагом влево на 1
ВЛЕВО 1
РекурсивныйПуть(цель, глубина + 1)
ВПРАВО 1
// Рекурсивный вызов с шагом влево на 2
ВЛЕВО 2
РекурсивныйПуть(цель, глубина + 1)
ВПРАВО 2
кон |
|
Проблема этого алгоритма в том, что он может очень долго работать из-за перебора всех возможных путей. Для оптимизации можно добавить эвристику, которая будет приоритизировать направления, приближающие к цели:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| алг РекурсивныйПутьОптимизированный(цел цель, цел глубина)
нач
цел текущая := поз
// Базовый случай: мы достигли цели
если текущая = цель то
вывод "Цель достигнута за ", глубина, " шагов"
стоп
все
// Превышена максимальная глубина рекурсии
если глубина > 10 то
стоп
все
// Определяем направление к цели
цел направление := знак(цель - текущая)
если направление >= 0 то
// Если цель справа или мы уже в ней, сначала пробуем шаги вправо
ВПРАВО 2
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВЛЕВО 2
ВПРАВО 1
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВЛЕВО 1
ВЛЕВО 1
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВПРАВО 1
ВЛЕВО 2
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВПРАВО 2
иначе
// Если цель слева, сначала пробуем шаги влево
ВЛЕВО 2
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВПРАВО 2
ВЛЕВО 1
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВПРАВО 1
ВПРАВО 1
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВЛЕВО 1
ВПРАВО 2
РекурсивныйПутьОптимизированный(цель, глубина + 1)
ВЛЕВО 2
все
кон |
|
Задача 55: Динамическое программирование
Динамическое программирование часто используется для оптимизации рекурсивных решений. Давайте применим его для нахождения минимального количества прыжков до заданной точки.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| алг МинимальныеПрыжкиДП(цел цель)
нач
// Создаем массив для хранения минимального количества прыжков
цел[] прыжки := новый_массив(abs(цель) + 1, 1000000)
прыжки[0] := 0 // До точки 0 нужно 0 прыжков
// Заполняем массив для положительных целей
если цель >= 0 то
нц для i от 1 до цель
// Пытаемся прийти в i из i-1 и i-2
если i >= 1 то
прыжки[i] := мин(прыжки[i], прыжки[i-1] + 1)
все
если i >= 2 то
прыжки[i] := мин(прыжки[i], прыжки[i-2] + 1)
все
кц
иначе
// Заполняем массив для отрицательных целей
цель := -цель
нц для i от 1 до цель
// Пытаемся прийти в -i из -(i-1) и -(i-2)
если i >= 1 то
прыжки[i] := мин(прыжки[i], прыжки[i-1] + 1)
все
если i >= 2 то
прыжки[i] := мин(прыжки[i], прыжки[i-2] + 1)
все
кц
все
// Теперь перемещаемся от начальной позиции к цели
цел начальная := поз
цел расстояние := abs(цель - начальная)
вывод "Минимальное количество прыжков: ", прыжки[расстояние]
// Восстановление пути
цел[] путь := новый_массив(прыжки[расстояние], 0)
цел индекс := 0
цел текущая := начальная
нц пока текущая <> цель
если abs(цель - текущая) >= 2 и прыжки[abs(цель - текущая)] = прыжки[abs(цель - (текущая + 2*знак(цель - текущая)))] + 1 то
// Оптимальнее сделать прыжок на 2
если знак(цель - текущая) > 0 то
ВПРАВО 2
путь[индекс] := 2
иначе
ВЛЕВО 2
путь[индекс] := -2
все
иначе
// Оптимальнее сделать прыжок на 1
если знак(цель - текущая) > 0 то
ВПРАВО 1
путь[индекс] := 1
иначе
ВЛЕВО 1
путь[индекс] := -1
все
все
индекс := индекс + 1
текущая := поз
кц
вывод "Путь: "
нц для i от 0 до прыжки[расстояние] - 1
вывод путь[i], " "
кц
кон |
|
Задача 56: Алгоритм A* для поиска пути с препятствиями
A* — один из самых эффективных алгоритмов поиска пути. Адаптируем его для Кузнечика, который должен достичь целевой точки, избегая препятствий.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| алг A_Star(цел цель, цел[] препятствия, цел кол_препятствий)
нач
цел начальная := поз
// Структура для хранения информации о точке
тип ТочкаИнфо = запись
позиция: цел,
g: цел, // стоимость пути от начальной точки
h: цел, // эвристическая оценка до цели
f: цел, // f = g + h
родитель: адрес ТочкаИнфо
конец
// Приоритетная очередь (упрощенная)
ТочкаИнфо[] очередь := новый_массив(100, нет)
цел размер_очереди := 0
// Добавляем начальную точку
ТочкаИнфо начало
начало.позиция := начальная
начало.g := 0
начало.h := abs(цель - начальная)
начало.f := начало.g + начало.h
начало.родитель := нет
очередь[0] := начало
размер_очереди := 1
// Множество посещенных точек (упрощенно - массив)
цел[] посещенные := новый_массив(10000, 0)
цел кол_посещенных := 0
нц пока размер_очереди > 0
// Извлекаем точку с наименьшим значением f
цел минимум_индекс := 0
цел минимум_f := очередь[0].f
нц для i от 1 до размер_очереди - 1
если очередь[i].f < минимум_f то
минимум_индекс := i
минимум_f := очередь[i].f
все
кц
ТочкаИнфо текущая := очередь[минимум_индекс]
// Удаляем из очереди, перенося последний элемент на место удаленного
очередь[минимум_индекс] := очередь[размер_очереди - 1]
размер_очереди := размер_очереди - 1
// Добавляем в посещенные
посещенные[кол_посещенных] := текущая.позиция
кол_посещенных := кол_посещенных + 1
// Проверяем, достигли ли цели
если текущая.позиция = цель то
// Восстанавливаем и выполняем путь
цел[] путь := новый_массив(текущая.g, 0)
цел длина_пути := текущая.g
ТочкаИнфо обратный := текущая
цел индекс := длина_пути - 1
нц пока обратный.родитель <> нет
путь[индекс] := обратный.позиция - обратный.родитель.позиция
индекс := индекс - 1
обратный := обратный.родитель
кц
// Выполняем путь
нц для i от 0 до длина_пути - 1
если путь[i] = 1 то
ВПРАВО 1
иначе если путь[i] = 2 то
ВПРАВО 2
иначе если путь[i] = -1 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
кц
вывод "Оптимальный путь найден, длина: ", длина_пути
стоп
все
// Рассматриваем соседей
цел[] соседи := [текущая.позиция + 1, текущая.позиция + 2,
текущая.позиция - 1, текущая.позиция - 2]
цел[] стоимости := [1, 1, 1, 1]
нц для i от 0 до 3
цел сосед := соседи[i]
// Проверяем, не препятствие ли это
лог препятствие := ложь
нц для j от 0 до кол_препятствий - 1
если сосед = препятствия[j] то
препятствие := истина
прервать
все
кц
// Пропускаем, если препятствие или уже посещали
если препятствие то
продолжить
все
лог посещена := ложь
нц для j от 0 до кол_посещенных - 1
если сосед = посещенные[j] то
посещена := истина
прервать
все
кц
если посещена то
продолжить
все
// Вычисляем новую стоимость пути
цел новый_g := текущая.g + стоимости[i]
// Проверяем, не нашли ли мы более дешевый путь
лог нашли := ложь
нц для j от 0 до размер_очереди - 1
если очередь[j].позиция = сосед то
нашли := истина
если новый_g < очередь[j].g то
очередь[j].g := новый_g
очередь[j].f := новый_g + очередь[j].h
очередь[j].родитель := адрес текущая
все
прервать
все
кц
если не нашли то
// Добавляем нового соседа в очередь
ТочкаИнфо новый_сосед
новый_сосед.позиция := сосед
новый_сосед.g := новый_g
новый_сосед.h := abs(цель - сосед)
новый_сосед.f := новый_g + новый_сосед.h
новый_сосед.родитель := адрес текущая
очередь[размер_очереди] := новый_сосед
размер_очереди := размер_очереди + 1
все
кц
кц
вывод "Путь не найден!"
кон |
|
Задача 57: Генетический алгоритм для поиска оптимального пути
Генетические алгоритмы — метод оптимизации, вдохновлённый эволюционными процессами. Применим его для поиска пути Кузнечика с минимальным количеством прыжков.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
| алг ГенетическийАлгоритм(цел цель, цел размер_популяции, цел поколения)
нач
цел макс_длина_пути := abs(цель) * 2 // Максимально возможная длина пути
// Создаем начальную популяцию
цел[][] популяция := новый_массив(размер_популяции, макс_длина_пути, 0)
цел[] длины := новый_массив(размер_популяции, 0)
// Инициализация случайными путями
нц для i от 0 до размер_популяции - 1
длины[i] := случайное(1, макс_длина_пути)
нц для j от 0 до длины[i] - 1
// Генерируем случайные прыжки: 1, 2, -1 или -2
цел прыжок := случайное(1, 4)
если прыжок = 1 то
популяция[i][j] := 1
иначе если прыжок = 2 то
популяция[i][j] := 2
иначе если прыжок = 3 то
популяция[i][j] := -1
иначе
популяция[i][j] := -2
все
кц
кц
// Выполняем эволюцию
нц для поколение от 1 до поколения
// Оцениваем приспособленность каждого индивида
вещ[] приспособленность := новый_массив(размер_популяции, 0.0)
нц для i от 0 до размер_популяции - 1
цел конечная_позиция := 0
нц для j от 0 до длины[i] - 1
конечная_позиция := конечная_позиция + популяция[i][j]
кц
// Приспособленность обратно пропорциональна расстоянию до цели
// и количеству прыжков
приспособленность[i] := 1.0 / (abs(цель - конечная_позиция) + 1) * (1.0 / длины[i])
// Если нашли решение, выполняем его
если конечная_позиция = цель то
вывод "Найдено решение в поколении ", поколение
// Выполняем найденный путь
нц для j от 0 до длины[i] - 1
если популяция[i][j] = 1 то
ВПРАВО 1
иначе если популяция[i][j] = 2 то
ВПРАВО 2
иначе если популяция[i][j] = -1 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
кц
стоп
все
кц
// Отбор родителей для скрещивания
цел[] родители := новый_массив(размер_популяции, 0)
нц для i от 0 до размер_популяции - 1
// Турнирный отбор
цел участник1 := случайное(0, размер_популяции - 1)
цел участник2 := случайное(0, размер_популяции - 1)
если приспособленность[участник1] > приспособленность[участник2] то
родители[i] := участник1
иначе
родители[i] := участник2
все
кц
// Создаем новое поколение через скрещивание
цел[][] новая_популяция := новый_массив(размер_популяции, макс_длина_пути, 0)
цел[] новые_длины := новый_массив(размер_популяции, 0)
нц для i от 0 до размер_популяции - 1 шаг 2
если i + 1 >= размер_популяции то
прервать
все
цел родитель1 := родители[i]
цел родитель2 := родители[i + 1]
// Одноточечное скрещивание
цел точка_скрещивания := случайное(1, мин(длины[родитель1], длины[родитель2]) - 1)
новые_длины[i] := точка_скрещивания + (длины[родитель2] - точка_скрещивания)
новые_длины[i + 1] := точка_скрещивания + (длины[родитель1] - точка_скрещивания)
нц для j от 0 до точка_скрещивания - 1
новая_популяция[i][j] := популяция[родитель1][j]
новая_популяция[i + 1][j] := популяция[родитель2][j]
кц
нц для j от точка_скрещивания до новые_длины[i] - 1
новая_популяция[i][j] := популяция[родитель2][j]
кц
нц для j от точка_скрещивания до новые_длины[i + 1] - 1
новая_популяция[i + 1][j] := популяция[родитель1][j]
кц
// Мутации
вещ вероятность_мутации := 0.1
нц для j от 0 до новые_длины[i] - 1
если случайное(0, 100) / 100.0 < вероятность_мутации то
цел новый_прыжок := случайное(1, 4)
если новый_прыжок = 1 то
новая_популяция[i][j] := 1
иначе если новый_прыжок = 2 то
новая_популяция[i][j] := 2
иначе если новый_прыжок = 3 то
новая_популяция[i][j] := -1
иначе
новая_популяция[i][j] := -2
все
все
кц
нц для j от 0 до новые_длины[i + 1] - 1
если случайное(0, 100) / 100.0 < вероятность_мутации то
цел новый_прыжок := случайное(1, 4)
если новый_прыжок = 1 то
новая_популяция[i + 1][j] := 1
иначе если новый_прыжок = 2 то
новая_популяция[i + 1][j] := 2
иначе если новый_прыжок = 3 то
новая_популяция[i + 1][j] := -1
иначе
новая_популяция[i + 1][j] := -2
все
все
кц
кц
// Заменяем старую популяцию новой
популяция := новая_популяция
длины := новые_длины
кц
вывод "Решение не найдено за ", поколения, " поколений"
кон |
|
Эти сложные алгоритмические конструкции демонстрируют, что даже с простым исполнителем вроде Кузнечика можно решать весьма нетривальные задачи. Такие алгоритмы, как A* или генетические алгоритмы, находят применение в самых различных областях — от игрового ИИ до оптимизации реальных процессов. Хотя реализация этих алгоритмов в системе КуМир может быть затруднена из-за ограничений языка, понимание их принципов работы очень полезно для развития алгоритмического мышления и подготовки к работе с более сложными языками программирования.
Продвинутые задачи: комбинированные задачи
Комбинированные задачи — настоящее испытание для программиста, поскольку требуют объединения различных алгоритмических приёмов в одном решении. Для Кузнечика такие задачи особенно интересны, так как демонстрируют, как из простых перемещений можно составлять сложные алгоритмы.
Задача 58: Последовательная обработка интервалов
Представим, что на числовой прямой задано несколько интервалов, и Кузнечику необходимо посетить каждый из них, минимизируя общее количество прыжков.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| алг ПосещениеИнтервалов(цел[][] интервалы, цел кол_интервалов)
нач
цел текущая_позиция := поз
цел общее_количество_прыжков := 0
// Сортируем интервалы по левой границе (упрощенный пузырьковый метод)
нц для i от 0 до кол_интервалов - 2
нц для j от i + 1 до кол_интервалов - 1
если интервалы[i][0] > интервалы[j][0] то
цел[] temp := интервалы[i]
интервалы[i] := интервалы[j]
интервалы[j] := temp
все
кц
кц
// Посещаем каждый интервал
нц для i от 0 до кол_интервалов - 1
цел левая := интервалы[i][0]
цел правая := интервалы[i][1]
// Определяем ближайшую точку в интервале
цел цель
если текущая_позиция < левая то
цель := левая
иначе если текущая_позиция > правая то
цель := правая
иначе
// Уже в интервале, пропускаем
вывод "Интервал ", i + 1, " уже посещен"
продолжить
все
// Перемещаемся к выбранной точке
цел расстояние := abs(цель - текущая_позиция)
цел направление := знак(цель - текущая_позиция)
цел прыжков := 0
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
прыжков := прыжков + 1
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
прыжков := прыжков + 1
все
текущая_позиция := поз
общее_количество_прыжков := общее_количество_прыжков + прыжков
вывод "Интервал ", i + 1, " посещен за ", прыжков, " прыжков"
кц
вывод "Все интервалы посещены. Общее количество прыжков: ", общее_количество_прыжков
кон |
|
Задача 59: Поиск треугольных чисел на числовой прямой
Треугольные числа — это числа вида n(n+1)/2, и они образуют последовательность 1, 3, 6, 10, 15, 21... Напишем алгоритм, который перемещает Кузнечика последовательно по всем треугольным числам в заданном диапазоне.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| алг ПоискТреугольныхЧисел(цел начало, цел конец)
нач
цел текущая_позиция := поз
// Перемещаемся в начальную позицию диапазона
если текущая_позиция <> начало то
цел расстояние := abs(начало - текущая_позиция)
цел направление := знак(начало - текущая_позиция)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
текущая_позиция := поз
все
// Находим первое треугольное число >= начало
цел n := 1
цел треугольное := n * (n + 1) div 2
нц пока треугольное < начало
n := n + 1
треугольное := n * (n + 1) div 2
кц
цел найдено := 0
// Перемещаемся по треугольным числам
нц пока треугольное <= конец
// Перемещаемся к треугольному числу
цел расстояние := abs(треугольное - текущая_позиция)
цел направление := знак(треугольное - текущая_позиция)
цел прыжков := 0
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
прыжков := прыжков + 1
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
прыжков := прыжков + 1
все
текущая_позиция := поз
найдено := найдено + 1
вывод "Найдено треугольное число ", треугольное, " (n = ", n, ") за ", прыжков, " прыжков"
// Находим следующее треугольное число
n := n + 1
треугольное := n * (n + 1) div 2
кц
вывод "Всего найдено треугольных чисел в диапазоне: ", найдено
кон |
|
Задача 60: Путешествие с возвратом в исходную точку
Представим задачу, где Кузнечику нужно посетить несколько заданных точек, а затем вернуться в исходную позицию, минимизируя общее расстояние.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| алг ПутешествиеСВозвратом(цел[] точки, цел кол_точек)
нач
цел начальная_позиция := поз
цел пройдено_всего := 0
// Визуализируем маршрут
вывод "Маршрут: ", начальная_позиция
нц для i от 0 до кол_точек - 1
вывод " -> ", точки[i]
кц
вывод " -> ", начальная_позиция, " (возврат)"
// Посещаем каждую точку
нц для i от 0 до кол_точек - 1
цел текущая := поз
цел цель := точки[i]
цел расстояние := abs(цель - текущая)
цел направление := знак(цель - текущая)
цел прыжков := 0
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
прыжков := прыжков + 1
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
прыжков := прыжков + 1
все
пройдено_всего := пройдено_всего + прыжков
вывод "Точка ", i + 1, " (", цель, ") достигнута за ", прыжков, " прыжков"
кц
// Возвращаемся в исходную позицию
цел текущая := поз
цел расстояние := abs(начальная_позиция - текущая)
цел направление := знак(начальная_позиция - текущая)
цел прыжков := 0
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
прыжков := прыжков + 1
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
прыжков := прыжков + 1
все
пройдено_всего := пройдено_всего + прыжков
вывод "Возврат в исходную позицию за ", прыжков, " прыжков"
вывод "Всего пройдено: ", пройдено_всего, " прыжков"
// Проверяем, что вернулись в исходную позицию
если поз = начальная_позиция то
вывод "Путешествие успешно завершено!"
иначе
вывод "Ошибка: не вернулись в исходную позицию!"
все
кон |
|
Задача 61: Движение с заданным ритмом
Усложним задачу, добавив требование двигаться в определённом ритме: например, каждый третий шаг должен быть длинным (на 2 единицы), а остальные — короткими (на 1 единицу).
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| алг ДвижениеСРитмом(цел цель, цел период, цел[] шаблон)
нач
цел старт := поз
цел текущая_позиция := старт
цел направление := знак(цель - текущая_позиция)
цел шагов := 0
цел индекс_шаблона := 0
нц пока текущая_позиция <> цель
// Определяем длину текущего шага
цел длина_шага := шаблон[индекс_шаблона]
// Корректируем, если мы близки к цели
если abs(цель - текущая_позиция) < длина_шага то
длина_шага := abs(цель - текущая_позиция)
все
// Выполняем шаг
если направление > 0 то
если длина_шага = 1 то
ВПРАВО 1
иначе
ВПРАВО 2
все
иначе
если длина_шага = 1 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
все
текущая_позиция := поз
шагов := шагов + 1
// Обновляем индекс шаблона
индекс_шаблона := (индекс_шаблона + 1) mod период
кц
вывод "Цель достигнута за ", шагов, " шагов"
кон |
|
Задача 62: Сбор "монет" на числовой прямой
Представим, что на числовой прямой расположены "монеты", которые Кузнечик должен собрать. Монеты исчезают, как только Кузнечик встает на соответствующую позицию.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| алг СборМонет(цел[] монеты, цел кол_монет)
нач
цел начальная_позиция := поз
цел собрано := 0
цел прыжков := 0
// Отмечаем монеты, которые уже собраны (если Кузнечик стоит на одной из них)
нц для i от 0 до кол_монет - 1
если монеты[i] = начальная_позиция то
монеты[i] := -1 // Помечаем как собранную
собрано := собрано + 1
вывод "Монета в позиции ", начальная_позиция, " собрана автоматически"
все
кц
// Собираем остальные монеты
нц пока собрано < кол_монет
// Находим ближайшую несобранную монету
цел ближайшая := -1
цел мин_расстояние := 1000000 // Большое число
нц для i от 0 до кол_монет - 1
если монеты[i] <> -1 то // Если монета не собрана
цел расстояние := abs(монеты[i] - поз)
если расстояние < мин_расстояние то
мин_расстояние := расстояние
ближайшая := i
все
все
кц
// Перемещаемся к ближайшей монете
цел цель := монеты[ближайшая]
цел расстояние := abs(цель - поз)
цел направление := знак(цель - поз)
цел шагов := 0
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
шагов := шагов + 1
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
шагов := шагов + 1
все
прыжков := прыжков + шагов
// Отмечаем монету как собранную
монеты[ближайшая] := -1
собрано := собрано + 1
вывод "Монета в позиции ", цель, " собрана за ", шагов, " прыжков"
кц
вывод "Все монеты собраны за ", прыжков, " прыжков"
кон |
|
Задача 63: Патрулирование интервала
Допустим, Кузнечику нужно патрулировать интервал [A, B], постоянно перемещаясь от одного края к другому, и отмечать все встреченные препятствия.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| алг Патрулирование(цел A, цел B, цел[] препятствия, цел кол_препятствий)
нач
// Перемещаемся в начало интервала
цел текущая := поз
цел расстояние := abs(A - текущая)
цел направление := знак(A - текущая)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Патрулирование начато с позиции ", A, " до ", B
// Отмечаем препятствия как не посещенные
лог[] посещены := новый_массив(кол_препятствий, ложь)
цел обнаружено := 0
цел циклов := 0
// Патрулируем, пока не найдем все препятствия
нц пока обнаружено < кол_препятствий и циклов < 10
// Движемся от A к B
нц пока поз < B
// Проверяем, не стоим ли мы на препятствии
нц для i от 0 до кол_препятствий - 1
если поз = препятствия[i] и не посещены[i] то
посещены[i] := истина
обнаружено := обнаружено + 1
вывод "Препятствие в позиции ", поз, " обнаружено"
все
кц
// Делаем шаг вправо
если B - поз >= 2 то
ВПРАВО 2
иначе
ВПРАВО 1
все
кц
// Проверяем последнюю позицию B
нц для i от 0 до кол_препятствий - 1
если поз = препятствия[i] и не посещены[i] то
посещены[i] := истина
обнаружено := обнаружено + 1
вывод "Препятствие в позиции ", поз, " обнаружено"
все
кц
// Движемся от B к A
нц пока поз > A
// Проверяем, не стоим ли мы на препятствии
нц для i от 0 до кол_препятствий - 1
если поз = препятствия[i] и не посещены[i] то
посещены[i] := истина
обнаружено := обнаружено + 1
вывод "Препятствие в позиции ", поз, " обнаружено"
все
кц
// Делаем шаг влево
если поз - A >= 2 то
ВЛЕВО 2
иначе
ВЛЕВО 1
все
кц
// Проверяем последнюю позицию A
нц для i от 0 до кол_препятствий - 1
если поз = препятствия[i] и не посещены[i] то
посещены[i] := истина
обнаружено := обнаружено + 1
вывод "Препятствие в позиции ", поз, " обнаружено"
все
кц
циклов := циклов + 1
вывод "Завершен цикл патрулирования ", циклов
кц
вывод "Обнаружено препятствий: ", обнаружено, " из ", кол_препятствий
кон |
|
Комбинированные задачи — это переход от абстрактных алгоритмических упражнений к реальному программированию, где часто требуется объединять различные подходы для решения сложных проблем. Работа с такими задачами развивает не только технические навыки, но и системное мышление, столь необходимое современным программистам.
Продвинутые задачи: нестандартные решения
Стандартные подходы хороши, но настоящее мастерство программиста проявляется в умении находить нестандартные решения. Рассмотрим задачи, требующие творческого мышления и нетривиальных алгоритмов для нашего Кузнечика.
Задача 64: Кузнечик-робопылесос
Представим, что Кузнечик выполняет роль робота-пылесоса, который должен "очистить" всю числовую прямую в заданном интервале [A, B]. При этом каждую точку нужно посетить ровно один раз.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| алг Робопылесос(цел A, цел B)
нач
цел начальная := поз
// Если Кузнечик уже в интервале, очистка начинается с его позиции
// и продолжается в обоих направлениях
если A <= начальная и начальная <= B то
// Сперва идём влево до точки A
нц пока поз > A
ВЛЕВО 1
вывод "Очищена точка ", поз
кц
// Затем вправо от начальной до B
цел конец_первого_участка := начальная - 1
// Возвращаемся в начальную позицию
нц пока поз < начальная
ВПРАВО 1
кц
// И идём до B
нц пока поз < B
ВПРАВО 1
вывод "Очищена точка ", поз
кц
иначе
// Иначе перемещаемся в точку A и очищаем последовательно
цел расстояние := abs(A - начальная)
цел направление := знак(A - начальная)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Очищена точка ", поз
// Очищаем все точки от A+1 до B
нц пока поз < B
ВПРАВО 1
вывод "Очищена точка ", поз
кц
все
вывод "Очистка завершена!"
кон |
|
Задача 65: Распознавание паттернов
Пусть на числовой прямой есть последовательность точек с особыми свойствами (например, простые числа). Кузнечику нужно распознать паттерн и по нему предсказать положение следующей точки.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| алг РаспознаваниеПростыхЧисел(цел кол_точек)
нач
цел[] простые := [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
цел найдено := 0
цел текущая := поз
// Ищем заданное количество простых чисел
нц пока найдено < кол_точек и текущая < 100
лог простое := истина
// Проверяем, является ли число простым
если текущая <= 1 то
простое := ложь
иначе если текущая = 2 то
простое := истина
иначе если текущая mod 2 = 0 то
простое := ложь
иначе
цел i := 3
нц пока i * i <= текущая
если текущая mod i = 0 то
простое := ложь
прервать
все
i := i + 2
кц
все
если простое то
// Проверяем, предсказал ли наш шаблон это простое число
лог найдено_в_шаблоне := ложь
нц для i от 0 до 14
если простые[i] = текущая то
найдено_в_шаблоне := истина
прервать
все
кц
если найдено_в_шаблоне то
вывод "Найдено простое число ", текущая, " (было в шаблоне)"
иначе
вывод "Найдено простое число ", текущая, " (не было в шаблоне)"
все
найдено := найдено + 1
все
ВПРАВО 1
текущая := поз
кц
// По обнаруженным числам предсказываем следующее простое
// Для простоты используем разницу между последними двумя
цел последнее_простое := 0
цел предпоследнее_простое := 0
нц для i от 0 до 14
если простые[i] < текущая то
предпоследнее_простое := последнее_простое
последнее_простое := простые[i]
все
кц
цел разница := последнее_простое - предпоследнее_простое
цел прогноз := последнее_простое + разница
вывод "Прогноз следующего простого числа: ", прогноз
кон |
|
Задача 66: Самообучающийся Кузнечик
Предположим, что каждый раз, когда Кузнечик оказывается в определённой точке, он получает "вознаграждение". Цель — научиться максимизировать суммарное вознаграждение за ограниченное число шагов.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| алг СамообучающийсяКузнечик(цел шагов)
нач
// Функция вознаграждения — в реальности может быть сложной
цел Вознаграждение(цел позиция)
если позиция mod 7 = 0 то
знач := 3 // За позиции, кратные 7, даём 3 очка
иначе если позиция mod 5 = 0 то
знач := 2 // За позиции, кратные 5, даём 2 очка
иначе если позиция mod 3 = 0 то
знач := 1 // За позиции, кратные 3, даём 1 очко
иначе
знач := 0 // За остальные позиции ничего не даём
все
кон
цел начальная := поз
цел общий_счет := 0
цел текущий_счет := Вознаграждение(начальная)
общий_счет := общий_счет + текущий_счет
вывод "Начальная позиция: ", начальная, ", вознаграждение: ", текущий_счет
// Массивы для хранения оценок возможных ходов
вещ[] оценка_вправо_1 := [0.0]
вещ[] оценка_вправо_2 := [0.0]
вещ[] оценка_влево_1 := [0.0]
вещ[] оценка_влево_2 := [0.0]
// Коэффициент обучения
вещ альфа := 0.1
// Выполняем заданное количество шагов, обучаясь на ходу
нц для шаг от 1 до шагов
// Выбираем ход с наибольшей ожидаемой выгодой
цел выбор := 1 // По умолчанию ВПРАВО 1
вещ макс_оценка := оценка_вправо_1[0]
если оценка_вправо_2[0] > макс_оценка то
макс_оценка := оценка_вправо_2[0]
выбор := 2 // ВПРАВО 2
все
если оценка_влево_1[0] > макс_оценка то
макс_оценка := оценка_влево_1[0]
выбор := 3 // ВЛЕВО 1
все
если оценка_влево_2[0] > макс_оценка то
макс_оценка := оценка_влево_2[0]
выбор := 4 // ВЛЕВО 2
все
// С небольшой вероятностью выбираем случайный ход для исследования
если случайное(1, 10) = 1 то
выбор := случайное(1, 4)
вывод "Исследовательский ход: ", выбор
все
// Выполняем выбранный ход
если выбор = 1 то
ВПРАВО 1
иначе если выбор = 2 то
ВПРАВО 2
иначе если выбор = 3 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
// Получаем вознаграждение
цел новая_позиция := поз
цел награда := Вознаграждение(новая_позиция)
общий_счет := общий_счет + награда
// Обновляем оценку выбранного хода
если выбор = 1 то
оценка_вправо_1[0] := оценка_вправо_1[0] + альфа * (награда - оценка_вправо_1[0])
иначе если выбор = 2 то
оценка_вправо_2[0] := оценка_вправо_2[0] + альфа * (награда - оценка_вправо_2[0])
иначе если выбор = 3 то
оценка_влево_1[0] := оценка_влево_1[0] + альфа * (награда - оценка_влево_1[0])
иначе
оценка_влево_2[0] := оценка_влево_2[0] + альфа * (награда - оценка_влево_2[0])
все
вывод "Шаг ", шаг, ": позиция ", новая_позиция, ", награда ", награда
вывод "Оценки: ВПРАВО 1 = ", оценка_вправо_1[0], ", ВПРАВО 2 = ", оценка_вправо_2[0]
вывод " ВЛЕВО 1 = ", оценка_влево_1[0], ", ВЛЕВО 2 = ", оценка_влево_2[0]
кц
вывод "Общий счет: ", общий_счет
вывод "Конечная позиция: ", поз
кон |
|
Задача 67: Кузнечик-шифровальщик
Предположим, что Кузнечик используется для шифрования и дешифрования сообщений. Каждая буква сообщения кодируется позицией на числовой прямой.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| алг КузнечикШифровальщик(цел[] сообщение, цел длина, цел ключ)
нач
цел начальная_позиция := поз
цел[] зашифрованное := новый_массив(длина, 0)
// Перемещаемся в начальную точку (обычно 0)
цел расстояние := abs(0 - начальная_позиция)
цел направление := знак(0 - начальная_позиция)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Шифруем сообщение
нц для i от 0 до длина - 1
// Получаем букву для шифрования (представленную как число)
цел буква := сообщение[i]
// Применяем ключ шифрования (например, сдвиг на ключ*i позиций)
цел шифр_позиция := (буква + ключ * (i + 1)) mod 100
// Перемещаемся к зашифрованной позиции
расстояние := abs(шифр_позиция - поз)
направление := знак(шифр_позиция - поз)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Записываем зашифрованное значение
зашифрованное[i] := поз
вывод "Буква ", буква, " зашифрована как ", поз
кц
вывод "Зашифрованное сообщение: "
нц для i от 0 до длина - 1
вывод зашифрованное[i], " "
кц
кон |
|
Нестандартные решения часто требуют выхода за рамки обычных алгоритмических паттернов и привлечения идей из других областей — начиная от обучения с подкреплением и заканчивая криптографией. Такие задачи развивают креативное мышление и помогают находить неожиданно эффективные решения даже для самых сложных проблем.
Продвинутые задачи: препятствия на числовой прямой
Одно дело заставить Кузнечика перемещаться по пустой числовой прямой, и совсем другое — научить его делать то же самое при наличии препятствий. Препятствия в мире Кузнечика — это точки, через которые он не может перепрыгнуть или на которых не может остановиться. Такие ограничения значительно усложняют поиск оптимального пути и требуют применения более сложных алгоритмов.
Задача 68: Обход единичного препятствия
Начнем с простого случая: на числовой прямой есть одно препятствие в точке X, и Кузнечику нужно переместиться из точки A в точку B, не наступая на X.
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
| алг ОбходПрепятствия(цел A, цел B, цел X)
нач
// Перемещаемся в начальную точку A
цел текущая := поз
цел расстояние := abs(A - текущая)
цел направление := знак(A - текущая)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Теперь перемещаемся из A в B, избегая X
// Определяем направление движения
направление := знак(B - A)
// Проверяем, находится ли препятствие на пути
лог препятствие_на_пути := ложь
если направление > 0 то
препятствие_на_пути := (X > A и X < B)
иначе
препятствие_на_пути := (X < A и X > B)
все
если не препятствие_на_пути то
// Препятствие не на пути, двигаемся напрямую
расстояние := abs(B - A)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Препятствие не на пути, двигались напрямую"
иначе
// Препятствие на пути, нужен обход
// Стратегия: прыгаем через препятствие
если X - A = 1 и направление > 0 то
// Препятствие в соседней точке справа, прыгаем через него
ВПРАВО 2
расстояние := abs(B - поз)
нц пока расстояние >= 2
если B > поз то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если B > поз то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Прыгнули через препятствие справа"
иначе если A - X = 1 и направление < 0 то
// Препятствие в соседней точке слева, прыгаем через него
ВЛЕВО 2
расстояние := abs(B - поз)
нц пока расстояние >= 2
если B > поз то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если B > поз то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Прыгнули через препятствие слева"
иначе
// Препятствие далеко, двигаемся до точки перед ним
цел до_препятствия
если направление > 0 то
до_препятствия := X - 1
иначе
до_препятствия := X + 1
все
// Идём до точки перед препятствием
расстояние := abs(до_препятствия - поз)
направление := знак(до_препятствия - поз)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Прыгаем через препятствие
если X > поз то
ВПРАВО 2
иначе
ВЛЕВО 2
все
// Продолжаем движение к цели
расстояние := abs(B - поз)
направление := знак(B - поз)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
вывод "Доехали до препятствия, перепрыгнули и продолжили путь"
все
все
вывод "Достигнута конечная точка ", B
кон |
|
Задача 69: Обход нескольких препятствий
Теперь усложним задачу — на прямой расположено несколько препятствий, и нам нужно найти путь, обходящий все из них:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
| алг ОбходНесколькихПрепятствий(цел A, цел B, цел[] препятствия, цел кол_препятствий)
нач
// Перемещаемся в точку A
цел текущая := поз
цел расстояние := abs(A - текущая)
цел направление := знак(A - текущая)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Теперь планируем маршрут от A до B
вывод "Начинаем путь из ", A, " в ", B
// Определяем общее направление
направление := знак(B - A)
// Пока не достигли цели
нц пока поз <> B
цел следующий_шаг := 0
// Проверяем, можно ли сделать шаг величиной 2
если abs(B - поз) >= 2 то
// Проверяем, нет ли препятствия на пути
цел целевая := поз + 2 * направление
лог препятствие_на_пути := ложь
нц для i от 0 до кол_препятствий - 1
если препятствия[i] = целевая или препятствия[i] = поз + направление то
препятствие_на_пути := истина
прервать
все
кц
если не препятствие_на_пути то
следующий_шаг := 2
все
все
// Если шаг величиной 2 невозможен, пробуем шаг величиной 1
если следующий_шаг = 0 и abs(B - поз) >= 1 то
цел целевая := поз + 1 * направление
лог препятствие_на_пути := ложь
нц для i от 0 до кол_препятствий - 1
если препятствия[i] = целевая то
препятствие_на_пути := истина
прервать
все
кц
если не препятствие_на_пути то
следующий_шаг := 1
все
все
// Если ни шаг 1, ни шаг 2 невозможны в основном направлении,
// пробуем обойти препятствие
если следующий_шаг = 0 то
// Ищем ближайшую точку, свободную от препятствий
цел дистанция := 1
лог найден_путь := ложь
нц пока дистанция <= 10 и не найден_путь // Ограничиваем поиск
// Проверяем точку впереди на расстоянии дистанция
цел целевая := поз + дистанция * направление
лог препятствие_на_пути := ложь
нц для i от 0 до кол_препятствий - 1
если препятствия[i] = целевая то
препятствие_на_пути := истина
прервать
все
кц
если не препятствие_на_пути то
// Нашли свободную точку впереди
// Теперь нужно проверить, можно ли до неё добраться
// используя комбинацию прыжков
если дистанция mod 2 = 0 то
// Можно достичь с помощью прыжков по 2
цел шагов := дистанция div 2
нц для i от 1 до шагов
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
кц
найден_путь := истина
иначе если дистанция >= 3 то
// Можно достичь с помощью комбинации прыжков
// Например: 5 = 2 + 2 + 1
цел шагов_по_2 := (дистанция - 1) div 2
нц для i от 1 до шагов_по_2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
кц
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
найден_путь := истина
все
все
дистанция := дистанция + 1
кц
если не найден_путь то
// Если не нашли путь вперед, пробуем обойти, двигаясь назад
// (в реальной задаче здесь был бы более сложный алгоритм)
вывод "Не смогли найти прямой путь, ищем обходной маршрут"
// Для простоты делаем несколько шагов назад и пробуем снова
нц для i от 1 до 3
если -направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
кц
все
иначе
// Делаем найденный шаг
если направление > 0 то
если следующий_шаг = 1 то
ВПРАВО 1
иначе
ВПРАВО 2
все
иначе
если следующий_шаг = 1 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
все
все
// Страховка от зацикливания - ограничиваем количество итераций
если abs(B - поз) > abs(B - A) * 2 то
вывод "Превышено максимальное расстояние, прерываем поиск"
стоп
все
кц
вывод "Достигнута конечная точка ", B
кон |
|
Задача 70: Поиск кратчайшего пути в лабиринте
Представим, что числовая прямая превратилась в сложный лабиринт с большим количеством препятствий. Для нахождения кратчайшего пути воспользуемся адаптацией алгоритма поиска в ширину (BFS):
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| алг КратчайшийПутьВЛабиринте(цел A, цел B, цел[] препятствия, цел кол_препятствий)
нач
// Перемещаемся в начальную точку A
цел текущая := поз
цел расстояние := abs(A - текущая)
цел направление := знак(A - текущая)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Создаем очередь для BFS
цел[] очередь := новый_массив(1000, 0)
цел начало_очереди := 0
цел конец_очереди := 0
// Словарь для хранения предшественников (для восстановления пути)
цел[] предшественник := новый_массив(1000, -1)
цел[] шаг := новый_массив(1000, 0) // Размер шага: 1 или 2
// Добавляем начальную точку в очередь
очередь[конец_очереди] := поз
конец_очереди := конец_очереди + 1
// Отмечаем посещенные точки
лог[] посещено := новый_массив(1000, ложь)
посещено[поз + 500] := истина // Смещение для отрицательных индексов
// Запускаем BFS
лог найден_путь := ложь
нц пока начало_очереди < конец_очереди и не найден_путь
цел текущая_точка := очередь[начало_очереди]
начало_очереди := начало_очереди + 1
если текущая_точка = B то
найден_путь := истина
прервать
все
// Проверяем четыре возможных перемещения
цел[] возможные_точки := [текущая_точка + 1, текущая_точка + 2,
текущая_точка - 1, текущая_точка - 2]
цел[] размеры_шагов := [1, 2, 1, 2]
нц для i от 0 до 3
цел следующая_точка := возможные_точки[i]
// Проверяем, не является ли точка препятствием
лог препятствие := ложь
нц для j от 0 до кол_препятствий - 1
если препятствия[j] = следующая_точка то
препятствие := истина
прервать
все
кц
// Если точка свободна и не была посещена
если не препятствие и не посещено[следующая_точка + 500] то
очередь[конец_очереди] := следующая_точка
конец_очереди := конец_очереди + 1
посещено[следующая_точка + 500] := истина
предшественник[следующая_точка + 500] := текущая_точка
шаг[следующая_точка + 500] := размеры_шагов[i]
все
кц
кц
если найден_путь то
// Восстанавливаем путь (в обратном порядке)
цел[] путь := новый_массив(1000, 0)
цел[] размеры := новый_массив(1000, 0)
цел длина_пути := 0
цел текущая_точка := B
нц пока текущая_точка <> поз
путь[длина_пути] := текущая_точка
размеры[длина_пути] := шаг[текущая_точка + 500]
длина_пути := длина_пути + 1
текущая_точка := предшественник[текущая_точка + 500]
кц
// Выполняем перемещения в правильном порядке
нц для i от длина_пути - 1 до 0 шаг -1
цел следующая := путь[i]
цел размер := размеры[i]
если следующая > поз то
если размер = 1 то
ВПРАВО 1
иначе
ВПРАВО 2
все
иначе
если размер = 1 то
ВЛЕВО 1
иначе
ВЛЕВО 2
все
все
кц
вывод "Найден путь длиной ", длина_пути, " шагов"
иначе
вывод "Путь не найден!"
все
кон |
|
Задача 71: Динамические препятствия
Теперь представим, что препятствия не статичны, а появляются и исчезают после определённых действий Кузнечика. Это моделирует ситуации реального мира, когда окружение меняется в результате действий агента:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| алг ДинамическиеПрепятствия(цел цель)
нач
// Правила для динамических препятствий:
// 1. После прыжка на 2 вправо, появляется препятствие в точке поз + 3
// 2. После прыжка на 2 влево, появляется препятствие в точке поз - 3
// 3. После прыжка на 1 в любом направлении, исчезает препятствие в точке поз * 2
цел[] препятствия := новый_массив(100, -1000) // Инициализируем заведомо недостижимыми значениями
цел кол_препятствий := 0
вывод "Начинаем путь из ", поз, " в ", цель
// Пока не достигли цели
нц пока поз <> цель
// Проверяем возможные ходы
цел[] возможные_ходы := [поз + 1, поз + 2, поз - 1, поз - 2]
лог[] доступность := [истина, истина, истина, истина]
// Проверяем каждую возможную позицию на наличие препятствий
нц для i от 0 до 3
нц для j от 0 до кол_препятствий - 1
если возможные_ходы[i] = препятствия[j] то
доступность[i] := ложь
прервать
все
кц
кц
// Выбираем ход, который приближает нас к цели и доступен
цел лучший_ход := -1
цел минимальное_расстояние := 1000000
нц для i от 0 до 3
если доступность[i] то
цел новое_расстояние := abs(цель - возможные_ходы[i])
если новое_расстояние < минимальное_расстояние то
минимальное_расстояние := новое_расстояние
лучший_ход := i
все
все
кц
если лучший_ход = -1 то
вывод "Нет доступных ходов! Застряли в точке ", поз
стоп
все
// Выполняем выбранный ход
если лучший_ход = 0 то
ВПРАВО 1
вывод "Сделан ход ВПРАВО 1, новая позиция: ", поз
// После прыжка на 1 исчезает препятствие в точке поз * 2
цел точка_исчезновения := поз * 2
нц для j от 0 до кол_препятствий - 1
если препятствия[j] = точка_исчезновения то
// Удаляем препятствие, заменяя его на последнее
препятствия[j] := препятствия[кол_препятствий - 1]
кол_препятствий := кол_препятствий - 1
вывод "Препятствие в точке ", точка_исчезновения, " исчезло"
прервать
все
кц
иначе если лучший_ход = 1 то
ВПРАВО 2
вывод "Сделан ход ВПРАВО 2, новая позиция: ", поз
// После прыжка на 2 вправо появляется препятствие
цел новое_препятствие := поз + 3
// Проверяем, не существует ли уже такое препятствие
лог существует := ложь
нц для j от 0 до кол_препятствий - 1
если препятствия[j] = новое_препятствие то
существует := истина
прервать
все
кц
если не существует то
препятствия[кол_препятствий] := новое_препятствие
кол_препятствий := кол_препятствий + 1
вывод "Появилось препятствие в точке ", новое_препятствие
все
иначе если лучший_ход = 2 то
ВЛЕВО 1
вывод "Сделан ход ВЛЕВО 1, новая позиция: ", поз
// После прыжка на 1 исчезает препятствие
цел точка_исчезновения := поз * 2
нц для j от 0 до кол_препятствий - 1
если препятствия[j] = точка_исчезновения то
// Удаляем препятствие
препятствия[j] := препятствия[кол_препятствий - 1]
кол_препятствий := кол_препятствий - 1
вывод "Препятствие в точке ", точка_исчезновения, " исчезло"
прервать
все
кц
иначе
ВЛЕВО 2
вывод "Сделан ход ВЛЕВО 2, новая позиция: ", поз
// После прыжка на 2 влево появляется препятствие
цел новое_препятствие := поз - 3
// Проверяем, не существует ли уже такое препятствие
лог существует := ложь
нц для j от 0 до кол_препятствий - 1
если препятствия[j] = новое_препятствие то
существует := истина
прервать
все
кц
если не существует то
препятствия[кол_препятствий] := новое_препятствие
кол_препятствий := кол_препятствий + 1
вывод "Появилось препятствие в точке ", новое_препятствие
все
все
// Выводим текущие препятствия
вывод "Текущие препятствия: "
нц для j от 0 до кол_препятствий - 1
вывод препятствия[j], " "
кц
вывод ""
кц
вывод "Цель достигнута!"
кон |
|
Работа с препятствиями демонстрирует, как простая модель исполнителя может использоваться для изучения сложных концепций искусственного интеллекта и планирования пути. Кузнечик с его ограниченным набором команд становится отличной платформой для экспериментов с различными алгоритмами поиска и навигации в дискретных пространствах.
Практические советы: отладка программ
Отладка программ для Кузнечика может показаться простой задачей — ведь что может пойти не так с исполнителем, имеющим всего пару команд? Тем не менее, даже с таким минималистичным набором инструкций можно столкнуться с неожиданными сложностями. Сейчас расскажу о проверенных методах отладки, которые помогли мне и моим студентам при работе с этим исполнителем.
Пошаговое выполнение
Одним из самых мощных инструментов отладки в КуМире является пошаговое выполнение программы. Когда ваш Кузнечик скачет не туда, куда ожидалось, включите режим пошагового выполнения (обычно для этого используется клавиша F8). Это позволит вам наблюдать за каждым прыжком Кузнечика и точно определить момент, когда поведение отклоняется от ожидаемого.
| Code | 1
2
3
4
5
6
7
8
| алг ОтладкаПошагово
нач
ВПРАВО 2
ВПРАВО 1
ВЛЕВО 1
ВПРАВО 2
вывод "Конечная позиция: ", поз
кон |
|
- Начальная позиция: 0
- После
ВПРАВО 2: позиция 2
- После
ВПРАВО 1: позиция 3
- После
ВЛЕВО 1: позиция 2
- После
ВПРАВО 2: позиция 4
Часто одним взглядом на промежуточные позиции можно заметить ошибку, которая не была очевидна при беглом просмотре кода.
Использование контрольных точек
Для более сложных алгоритмов удобно использовать контрольные точки (точки останова или breakpoints). Установите точку останова на линии, где, как вы подозреваете, происходит ошибка, и программа автоматически остановится, когда дойдёт до этой строки.
В КуМире точки останова обычно устанавливаются двойным щелчком мыши на номере строки или нажатием клавиши F5. После установки точки останова запустите программу в режиме отладки (F9), и она будет выполняться до достижения точки останова.
Отслеживание переменных
Отслеживание значений переменных — еще один необходимый инструмент. В сложных алгоритмах с циклами и условиями часто бывает полезно выводить текущие значения переменных:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| алг ОтладкаСПеременными
нач
цел позиция := поз
цел цель := 10
цел шагов := 0
нц пока позиция < цель
если цель - позиция >= 2 то
ВПРАВО 2
позиция := позиция + 2
иначе
ВПРАВО 1
позиция := позиция + 1
все
шагов := шагов + 1
вывод "Шаг: ", шагов, " Позиция: ", позиция
кц
кон |
|
Проверка граничных условий
Особое внимание стоит уделить граничным условиям — ситуациям, когда Кузнечик находится на краю разрешенного диапазона или должен совершить специфическое действие в зависимости от своей позиции.
Типичные граничные случаи для Кузнечика:- Начальная позиция.
- Конечная позиция.
- Позиции непосредственно перед препятствиями.
- Крайние точки интервалов.
- Переход через ноль (с отрицательных позиций на положительные).
Например, если ваш алгоритм должен работать и для отрицательных позиций, убедитесь, что вы проверили этот сценарий:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| алг ПроверкаГраничныхУсловий
нач
цел[] начальные_позиции := [-5, -1, 0, 1, 5]
цел[] целевые_позиции := [-3, 0, 3, 6, 10]
нц для i от 0 до 4
// Перемещаемся в начальную позицию
цел текущая := поз
цел расстояние := abs(начальные_позиции[i] - текущая)
цел направление := знак(начальные_позиции[i] - текущая)
нц пока расстояние >= 2
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
расстояние := расстояние - 2
кц
если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
// Запускаем наш алгоритм
вывод "Тест ", i + 1, ": Из ", поз, " в ", целевые_позиции[i]
// ... ваш алгоритм перемещения к целевой позиции ...
// Проверяем результат
если поз = целевые_позиции[i] то
вывод "УСПЕХ!"
иначе
вывод "ОШИБКА! Ожидалась позиция ", целевые_позиции[i], ", получена ", поз
все
кц
кон |
|
Визуализация маршрута
Иногда лучший способ понять, что происходит — это визуализировать весь маршрут Кузнечика. Создайте массив, записывающий каждую позицию, и выведите его после выполнения алгоритма:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| алг ВизуализацияМаршрута
нач
цел[] маршрут := новый_массив(100, 0)
цел индекс := 0
маршрут[индекс] := поз
индекс := индекс + 1
// Ваш алгоритм
ВПРАВО 2
маршрут[индекс] := поз
индекс := индекс + 1
ВПРАВО 1
маршрут[индекс] := поз
индекс := индекс + 1
ВЛЕВО 1
маршрут[индекс] := поз
индекс := индекс + 1
ВПРАВО 2
маршрут[индекс] := поз
индекс := индекс + 1
// Визуализация маршрута
вывод "Маршрут Кузнечика:"
нц для i от 0 до индекс - 1
вывод маршрут[i], " "
кц
кон |
|
Модульное тестирование
Разбиение сложной программы на модули и их отдельное тестирование — мощный подход к отладке. Если у вас есть сложный алгоритм, разбейте его на вспомогательные алгоритмы и проверьте каждый из них по отдельности:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| алг ОптимальныйПрыжок(цел цель)
нач
цел текущая := поз
цел расстояние := abs(цель - текущая)
цел направление := знак(цель - текущая)
если расстояние >= 2 то
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
знач := 2
иначе если расстояние = 1 то
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
знач := 1
иначе
знач := 0
все
кон
алг ТестированиеМодулей
нач
цел[] тестовые_точки := [2, 5, 0, -3, -1]
нц для i от 0 до 4
вывод "Тест ", i + 1, ": Прыжок к точке ", тестовые_точки[i]
цел стартовая := поз
цел расстояние := ОптимальныйПрыжок(тестовые_точки[i])
вывод "Из ", стартовая, " сделан прыжок на ", расстояние, " единиц"
вывод "Новая позиция: ", поз
вывод "Ожидалось: минимизировать |", тестовые_точки[i], " - ", поз, "|"
вывод ""
кц
кон |
|
Журналирование
Для длительных или сложных алгоритмов полезно вести журнал действий — запись всех важных событий и решений, принимаемых в ходе выполнения программы:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| алг Журналирование
нач
цел старт := поз
цел цель := 15
цел шагов := 0
ЗаписьЖурнала("Начало выполнения. Стартовая позиция: " + строка(старт) + ", цель: " + строка(цель))
нц пока поз <> цель
цел текущая := поз
цел расстояние := abs(цель - текущая)
цел направление := знак(цель - текущая)
// Принимаем решение
если расстояние >= 2 то
ЗаписьЖурнала("Решение: прыжок на 2 в направлении " + строка(направление))
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
иначе
ЗаписьЖурнала("Решение: прыжок на 1 в направлении " + строка(направление))
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
все
шагов := шагов + 1
ЗаписьЖурнала("Шаг " + строка(шагов) + ": новая позиция: " + строка(поз))
кц
ЗаписьЖурнала("Цель достигнута за " + строка(шагов) + " шагов")
кон
алг ЗаписьЖурнала(лит сообщение)
нач
вывод сообщение
кон |
|
ЗаписьЖурнала могла бы сохранять сообщения в файл для последующего анализа, но в нашем случае мы просто выводим их на экран.
Применяя эти методы отладки, вы существенно упростите процесс поиска и исправления ошибок в программах для Кузнечика. Помните, что отладка — это не наказание, а неотъемлемая часть процесса разработки. Даже самые опытные программисты регулярно используют эти методы, чтобы убедиться, что их код работает как задумано.
Типичные ошибки и их устранение
В процессе программирования Кузнечика многие начинающие (и не только) сталкиваются с повторяющимися ошибками. Давайте разберем наиболее распространенные из них и научимся их оперативно выявлять и устранять.
Ошибки инициализации переменных
Одна из самых частых ошибок — это использование переменной без предварительной инициализации. В КуМире это приводит к ошибке выполнения:
| Code | 1
2
3
4
5
6
7
8
9
10
| алг НеинициализированнаяПеременная
нач
цел позиция // Забыли инициализировать!
если позиция > 5 то
ВПРАВО 2
иначе
ВПРАВО 1
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ИнициализированнаяПеременная
нач
цел позиция := поз // Теперь правильно
если позиция > 5 то
ВПРАВО 2
иначе
ВПРАВО 1
все
кон |
|
Перепутанные направления
Иногда вы можете перепутать команды ВПРАВО и ВЛЕВО, особенно если логика программы сложная:
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг ПерепутанныеНаправления
нач
цел цель := 10
// Хотели идти к цели, но перепутали направления
если поз < цель то
ВЛЕВО 2 // Ошибка! Должно быть ВПРАВО
иначе
ВПРАВО 2 // Ошибка! Должно быть ВЛЕВО
все
кон |
|
направление для большей ясности:
| Code | 1
2
3
4
5
6
7
8
9
10
11
| алг ПравильныеНаправления
нач
цел цель := 10
цел направление := знак(цель - поз)
если направление > 0 то
ВПРАВО 2
иначе
ВЛЕВО 2
все
кон |
|
Отсутствие обновления переменных в цикле
Эта ошибка приводит к бесконечным циклам:
| Code | 1
2
3
4
5
6
7
8
9
10
| алг БесконечныйЦикл
нач
цел текущая := поз
цел цель := 10
нц пока текущая < цель
ВПРАВО 2
// Забыли обновить текущая!
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ПравильныйЦикл
нач
цел текущая := поз
цел цель := 10
нц пока текущая < цель
ВПРАВО 2
текущая := поз // Обновляем переменную
кц
кон |
|
Неправильная обработка граничных случаев
Особое внимание следует уделять граничным случаям, например, когда Кузнечик находится в непосредственной близости от цели:
| Code | 1
2
3
4
5
6
7
8
9
| алг НеправильнаяОбработкаГраниц
нач
цел цель := 5
// Если Кузнечик в позиции 4, этот код перепрыгнет цель
нц пока поз < цель
ВПРАВО 2
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
| алг ПравильнаяОбработкаГраниц
нач
цел цель := 5
нц пока поз < цель
если цель - поз >= 2 то
ВПРАВО 2
иначе
ВПРАВО 1
все
кц
кон |
|
Ошибки в рекурсивных алгоритмах
Рекурсивные алгоритмы для Кузнечика часто содержат ошибки, связанные с базовым случаем или с возвратом в исходное состояние:
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ОшибочнаяРекурсия(цел шагов)
нач
если шагов <= 0 то
// Забыли стоп или знач!
иначе
ВПРАВО 1
ОшибочнаяРекурсия(шагов - 1)
// Забыли вернуться назад!
все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ПравильнаяРекурсия(цел шагов)
нач
если шагов <= 0 то
стоп
иначе
ВПРАВО 1
ПравильнаяРекурсия(шагов - 1)
ВЛЕВО 1 // Возвращаемся назад
все
кон |
|
Отсутствие проверки на препятствия
Если на числовой прямой есть препятствия, то отсутствие их проверки приведёт к неправильному выполнению программы:
| Code | 1
2
3
4
5
6
7
8
9
10
| алг БезПроверкиПрепятствий(цел цель, цел[] препятствия)
нач
нц пока поз <> цель
если поз < цель то
ВПРАВО 1 // Не проверяем, есть ли препятствие!
иначе
ВЛЕВО 1
все
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| алг СПроверкойПрепятствий(цел цель, цел[] препятствия, цел кол_препятствий)
нач
нц пока поз <> цель
цел следующая := поз
если поз < цель то
следующая := поз + 1
иначе
следующая := поз - 1
все
// Проверяем препятствия
лог препятствие := ложь
нц для i от 0 до кол_препятствий - 1
если препятствия[i] = следующая то
препятствие := истина
прервать
все
кц
если не препятствие то
если поз < цель то
ВПРАВО 1
иначе
ВЛЕВО 1
все
иначе
// Обработка ситуации с препятствием
вывод "Препятствие в позиции ", следующая
стоп
все
кц
кон |
|
Неправильное использование вспомогательных алгоритмов
Часто вызов вспомогательного алгоритма содержит ошибки в передаче параметров или интерпретации результата:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| алг Вспомогательный(цел x)
нач
если x > 0 то
ВПРАВО x
иначе
ВЛЕВО -x
все
знач := поз // Возвращаем новую позицию
кон
алг ОшибкаВВызове
нач
цел результат := Вспомогательный(3)
// Думаем, что результат - это количество шагов,
// хотя на самом деле это новая позиция
вывод "Сделано шагов: ", результат // Ошибка!
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| алг Вспомогательный(цел x)
нач
цел начальная := поз
если x > 0 то
ВПРАВО x
иначе
ВЛЕВО -x
все
знач := поз - начальная // Возвращаем разницу
кон
алг ПравильныйВызов
нач
цел шагов := Вспомогательный(3)
вывод "Сделано шагов: ", шагов
кон |
|
Логические ошибки в условиях и циклах
Иногда логика условий или циклов оказывается ошибочной, что приводит к неправильному поведению программы:
| Code | 1
2
3
4
5
6
7
8
9
| алг ЛогическаяОшибка
нач
цел цель := -5 // Отрицательная цель
// Ошибка! Условие никогда не выполнится для отрицательной цели
нц пока поз <= цель
ВПРАВО 1
кц
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
| алг ИсправленнаяЛогика
нач
цел цель := -5
цел направление := знак(цель - поз)
// Правильное условие, работающее для любой цели
нц пока поз <> цель
если направление > 0 то
ВПРАВО 1
иначе
ВЛЕВО 1
все
кц
кон |
|
Отсутствие защиты от бесконечных циклов
В сложных алгоритмах всегда есть риск бесконечных циклов. Полезно добавлять ограничение на максимальное количество итераций:
| Code | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| алг ЗащитаОтЗацикливания
нач
цел цель := 10
цел итераций := 0
цел макс_итераций := 100
нц пока поз <> цель и итераций < макс_итераций
// Логика перемещения
если поз < цель то
ВПРАВО 1
иначе
ВЛЕВО 1
все
итераций := итераций + 1
кц
если итераций >= макс_итераций то
вывод "Предупреждение: достигнуто максимальное число итераций!"
все
кон |
|
Ошибки форматирования кода
Хотя КуМир не так строг к форматированию, как некоторые другие языки, правильное форматирование делает код более читаемым и помогает избежать ошибок:
| Code | 1
2
3
4
5
| алг ПлохоеФорматирование
нач
цел x:=5
если x>3 то ВПРАВО 2иначе ВЛЕВО 1все
кон |
|
| Code | 1
2
3
4
5
6
7
8
9
10
| алг ХорошееФорматирование
нач
цел x := 5
если x > 3 то
ВПРАВО 2
иначе
ВЛЕВО 1
все
кон |
|
Визуализация работы Кузнечика
Понимание работы алгоритмов становится гораздо проще, когда мы можем наглядно увидеть процесс выполнения. Для Кузнечика визуализация особенно полезна, поскольку она позволяет отследить его перемещение по числовой прямой и проверить правильность работы программы.
Встроенные средства визуализации в КуМир
Система КуМир обладает встроенными инструментами визуализации, которые делают обучение программированию более наглядным. При запуске программы для Кузнечика вы увидите анимацию его движения по числовой прямой. Числовая прямая отображается в правой части экрана, а текущая позиция Кузнечика обозначается специальным маркером, который перемещается при выполнении команд.
Важной особенностью визуализации в КуМире является возможность регулировать скорость выполнения программы. Если ваш алгоритм слишком быстрый, и вы не успеваете наблюдать за движением Кузнечика, вы можете замедлить выполнение с помощью специального ползунка скорости. И наоборот, если программа выполняет много однообразных действий, вы можете ускорить анимацию.
Трассировочная таблица
Одним из самых простых и эффективных способов визуализации является создание трассировочной таблицы. В ней вы фиксируете состояние Кузнечика после каждой выполненной команды. Пример трассировочной таблицы:
| Code | 1
2
3
4
5
6
7
| | Команда | Позиция до | Позиция после | Комментарий |
|-------------|------------|---------------|----------------------|
| ВПРАВО 2 | 0 | 2 | Начало движения |
| ВПРАВО 1 | 2 | 3 | |
| ВЛЕВО 2 | 3 | 1 | Обход препятствия |
| ВПРАВО 2 | 1 | 3 | Продолжение движения |
| ВПРАВО 2 | 3 | 5 | Достигнута цель | |
|
Графическое представление траектории
Для более наглядного представления движения Кузнечика можно использовать графическое отображение его траектории. Поскольку Кузнечик перемещается по одномерной прямой, такое представление может быть очень информативным.
| Code | 1
2
3
4
5
6
7
8
9
10
11
| Позиция
7 |
6 |
5 | x
4 | x
3 | x x
2 | x
1 | x
0 |x
+---------------------> Шаг
1 2 3 4 5 6 |
|
Цветовая кодировка
Для более сложных алгоритмов полезно использовать цветовую кодировку различных типов перемещений:- Зелёный цвет — перемещение вправо.
- Красный цвет — перемещение влево.
- Синий цвет — специальные операции или перемещение в целевую точку.
Такой подход особенно полезен, когда нужно визуально выделить определённые участки маршрута, например, части пути, где Кузнечик обходил препятствия.
Визуализация с помощью таблицы состояний
Для алгоритмов с условными переходами или циклами полезно создавать таблицу состояний, которая показывает не только позицию Кузнечика, но и значения всех переменных на каждом шаге:
| Code | 1
2
3
4
5
6
| | Шаг | Позиция | цель | расстояние | направление | Команда |
|-----|---------|------|------------|-------------|------------|
| 0 | 0 | 5 | 5 | 1 | - |
| 1 | 2 | 5 | 3 | 1 | ВПРАВО 2 |
| 2 | 4 | 5 | 1 | 1 | ВПРАВО 2 |
| 3 | 5 | 5 | 0 | 0 | ВПРАВО 1 | |
|
Создание анимации в внешних инструментах
Для создания более сложных визуализаций можно использовать внешние инструменты. Например, вы можете записать последовательность позиций Кузнечика в файл, а затем использовать языки программирования с развитыми графическими возможностями (Python с библиотекой Matplotlib, JavaScript с Canvas или SVG) для создания анимированной визуализации.
Это особенно полезно для сложных задач с препятствиями или для алгоритмов поиска пути, где нужно наглядно показать, как Кузнечик исследует различные варианты и находит оптимальное решение.
Визуализация для образовательных целей
В образовательном контексте визуализация работы Кузнечика может быть превращена в интерактивную игру. Учащиеся могут предсказывать, где окажется Кузнечик после выполнения определенной последовательности команд, а затем проверять свои предположения с помощью программы.
Такой подход делает процесс обучения алгоритмам более увлекательным и помогает развивать алгоритмическое мышление еще до начала собственно программирования.
Визуализация — мощный инструмент для понимания алгоритмов и отладки программ. Используя различные методы визуального представления работы Кузнечика, вы не только лучше поймете, как работает ваш код, но и сможете эффективнее находить и исправлять ошибки, а также объяснять свои решения другим.
Исполнитель Робот
дали вот несколько задач (попросили решить, будучи студентом уже не ничего помню из курса информатики), можете проверить 1-3 и объяснить как делать... Исполнитель Черепаха
Честно говоря, без понятия куда обратиться из разделов.
Не помогли бы разобраться с кодом на кумире(без понятия что за исполнитель...)
... Исполнитель Черепаха
У меня проблема с использованием исполнителя черепахи в кумире: когда я запускаю код, на карте, на которой расположена черепаха, почему-то нет... Исполнитель Чертежник Составьте вспомогательный алгоритм-функцию Построение графика y = 50e-xsin(x) на отрезке [a, b]
Исполнитель Чертежник. Составьте вспомогательный алгоритм-функцию для построения графика y = 50e-xsin(x) на отрезке . Значения a и b задаются... Задача для исполнителя Робот
Народ, нужны советы по поводу решения этой задачи.Буду признателен любым советам.
Условие:Задачу необходимо решить, используя условный оператор... Нестандартные задания для исполнителя DRAPE
Помогите необходимо разработать 5 творческих, нестандартных заданий для исполнителя DRAPE. Составить минимальную по длине программу для исполнителя, которая уравнивает числа в паре (28, 64)
Рассмотрим исполнителя который оперирует над парой целых чисел и умеет выполнять следующие операции над парой (x,y):
- операция `a`:(x,y) ->... [КуМир] программы в среде графического исполнителя Робот
Напишите программы в среде графического исполнителя Робот для решения следующих задач:
1. закрасить рабочее поле горизонтальными пунктирными... Сколько разных программ можно составить для исполнителя?
Задача из школьного учебника.
Исполнитель Калькулятор имеет следующую систему команд:
1) прибавь 1;
2) умножь на 2.
С помощью первой из них... [КуМир] В системе КуМир сделать задание номер 23
помогите пожалуйста) задание номер 23) заранее благодарю) если не трудно можно блок схему еще)Текст задачи набирайте вручную. Для вставки формул есть... [КуМир] В программе Кумир написать алгоритм
(Ссылка на сторонний ресурс удалена)
для 3 и 4 картинок
Рекомендую Вам ознакомиться с правилами форума. [КуМир] Перевести программу с C++ на Кумир
Помогите нужно переписать программку с СИ++ на Кумир или на паскаль (но лучше на кумир)
сам код программы ...
|
