Может быть зверская тишина лучше всего развеется от решения задачи
Кенгуру не умеет плавать, но должен перебраться на другую сторону пруда.
по поверхности пруда расположены камни - опоры, по которым он мог бы перебраться.
Прыгать он может на произвольное расстояние, но с несколькими условиями
1. кенгуру не механический, он устаёт, поэтому каждый следующий максимальный прыжок может быть не более 4/5 предыдущего
2. кенгуру в курсе своей слабости, потому не решится на прыжок более чем 4/5 предыдущего
3. даже если первый прыжок был очень длинным, а второй маленьким, т.е. не должен бы вызвать усталость, кенгуру всё равно не сможет решиться на прыжок длинее 4/5 предыдущего.
Задача
1. найти путь по камням в пруду для опасливого кенгуру. Понятно, что если камни расположены не слишком густо, нужно экономить длину прыжка, не совершать слишком коротких прыжков, т.к. может не найтись следующий камень на подходящем расстоянии
2. необходимо найти решение с как можно меньшей стартовой длиной прыжка. Понятно, что если ограничений на стартовую длину нет, то можно просто перепрыгнуть пруд, но это неинтересно.
3. при каких условиях возможно решение с использованием только целых чисел
4. какая эвристика возможна для этой задачи?
Камни (неподвижно) и соответственно кенгуру (динамически) расположены в ячейках сетки 25х25, растояние между узлами сетки одинаково и равно 1
соответственно расположение опоры может быть задано или одним числом - позицией в массиве, который описывает пруд
так расстояние по прямой между двумя числами 1 и 2 будет равно единице по горизонтали, между числами 0 25 - единице по вертикали
или двумя числами - X Y
скажем, вот
0,18
1,1
2,6
4,12
5,19
6,3
9,7
10,16
12,3
15,8
15,18
17,13
19,7
21,20
22,4
9,3
13,13
6,8
13,22
23,13
стартовое положение
2 варианта - в более простом - 0,0в более сложном ненамного варианте считается, что вся нулевая полоса Y=0
заставлена камнями и нужно выбрать целое число - координату Х,
которая позволит наименьший прыжок, количество прыжков роли не играет
не ввело кого-то в заблуждение - там показан теоретически лучший вариант