Задачка
Задачка, простенькая, но интересная для тренировки ума.
Итак, условие:
Самолет летит на некой высоте с некоторой скоростью(левый нижний кружок). Ему нужно подняться на определенную высоту и разогнаться до определенной скорости. Одновременно он может делать лишь 1 маневр(ускорение или подъем) и тратит на это указанное у линий количество топлива.
Надо: определить оптимальный по затратам топлива путь и найти затраченное на его выполнение количество топлива.
Нужно из левого нижнего попасть в правый верхний угол?
Тогда 3 - 2 - 3 - 2 - 5 - 6 - 7 - 9
Делаем тупой перебор по клеткам "минимальное <расстояние> до этой" от левого нижнего
Начинаем с края:
18
10
05
03
00 04 10 17 25
теперь край необработанного:
18 23 выбор 24/23
10 14 выбор 15/14
05 08 выбор 08/12
03 08 15 19 26 выбор 24/19 и 27/26
00 04 10 17 25
Итд.
В результате сетка:
18 23 25 28 37
10 14 17 21 30
05 08 10 15 24
03 08 15 19 26
00 04 10 17 25
Итого, если я не ошибся с тупым счётом чиселок, то 37 маршрутом "вверх*2 - вперёд*3 - вверх*2 - вперёд"
Это же типичный граф. Находишь оптимальный путь и всё.
теория графов