Publish your project for free and start receiving offers from freelance contractors in serveral minutes after publication!
150 ₴

Алгоритм на основе динамического программирования

project complete


Задана шахматная доска n на n полей. Будем идентифицировать поле кортежем (x, y), при этом:

(1, 1) поле снизу слева

(n, 1) справа внизу

(n, n) справа наверху.

Другие поля по линиям пронумерованы.

Пусть имеется фигура, которая находится на самом нижнем ряду на поле (x, 1). Задача довести фигуру до верхнего ряда, со следующими ограничениями:

Пускай текущая позиция (х, у), тогда можно двигать фигуру след. образом:

- (х – 1, у + 1)

- (х, у + 1)

- (х + 1, у + 1) при условии, что фигура не выходит за доску.

Дополнительно есть функция v: [n2] x [n2] R+, которая две точки p1 и p2  на шахматной доске на действительное значение v(p1, p2) отображает. Если фигура двигается от p1 к p2  с учетом выше описанных ограничений, получается значение v(p1, p2).

Написать алгоритм или псевдокод, который по принципу динамического программирования за время O(n2) путь от любого поля р1 на нижнем ряду до любого поля pn верхнерго ряда достигнет с максимальным значением суммы v(pi, pi+1). Обосновать время работы алгоритма.

Совет к выполнению:

Пусть w(x, y) максимальная выгода, которой мы можем достичь, если мы от поля (x, y) стартуем. Создайте сначала рекурсивный принцип расчета для  w(x, y). Исходите из того, что v(x, y) за время О(1) может быть рассчитано.

Client's feedback about the contractor Данииле Мунтяне

Quality
Professionalism
Price
Availability
Terms

Очень рекомендую, сделал все досрочно и на очень высоком уровне

Сергей П. Сергей Попов | Safe Safe

Freelancer's feedback about the client Сергее Попове

Payment
Task formulation
Requirements
Availability

Очень толковый, коммуникабельный и надежный заказчик. Объясняет задание быстро, четко ставя задачи. Легко контактировать и решать вопросы. Я остался доволен сотрудничеством. Очень рекомендую.

Даниил М. Даниил Мунтян | Safe Safe



  1. 3 days150 ₴Winning proposal
    Даниил Мунтян
     343   5  1

    Добрый день, я запросто смогу написать реализацию данного алгоритма, так как я призер олимпиад по программированию, близко знаком с темой динамического программирования (одна из моих любимых тем).
    А в чем заключается работа? Написать Вам реализацию на псевдокоде?
    Я смогу сделать это за короткие сроки и качественно, с комментариями и разъяснениями. Можем оговорить цену и нюансы выполнения работы.
    Контакты:
    [email protected]
    Telegram - @daniil_muntyan
    Мой профиль на e-olymp: https://www.e-olymp.com/ru/users/muntyan

    Ukraine Kyiv | 3 July 2018 |