прикинуть количество
прикинуть количество лет, требуемых для решения задачи.
Вернемся к исходной задаче. Начнем строить путь Черепашки от пункта В. Каждому углу присвоим вес, равный минимальному времени движения Черепашки от этого угла до пункта В. Как его находить? От углов X, Y очевидно. Для угла Z время движения Черепашки в пункт В через угол X 15 единиц, а через угол Y 11 единиц. Берем минимальный, то есть вес угла будет равен 11. Продолжим вычисления. Их результаты приведены на рисунке. Путь, отмеченный стрелками, является ответом задачи. Оценим количество вычислений. Для каждого угла необходимо выполнить не более двух операций сложения и одной операции сравнения, то есть три операции. При N, равном 300, количество операций - 3*301*301, это меньше 1000000, и компьютеру потребуется меньше одной секунды. Итак, много лет при N=30 и 1 секунда при N=300.
Идея второго способа решения задачи основана на методе динамического программирования. Заслуга его открытия принадлежит американскому математику Ричарду
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
