Алгоритм на основе динамического программирования
150 UAHЗадана шахматная доска 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) может быть рассчитано.
Отзыв заказчика о сотрудничестве с Даниилом Мунтяном
Алгоритм на основе динамического программированияОчень рекомендую, сделал все досрочно и на очень высоком уровне
Отзыв фрилансера о сотрудничестве с заказчиком
Алгоритм на основе динамического программированияОчень толковый, коммуникабельный и надежный заказчик. Объясняет задание быстро, четко ставя задачи. Легко контактировать и решать вопросы. Я остался доволен сотрудничеством. Очень рекомендую.
-
Победившая ставка3 дня150 UAH
177 5 1 Победившая ставка3 дня150 UAH
Добрый день, я запросто смогу написать реализацию данного алгоритма, так как я призер олимпиад по программированию, близко знаком с темой динамического программирования (одна из моих любимых тем).
А в чем заключается работа? Написать Вам реализацию на псевдокоде?
Я смогу сделать это за короткие сроки и качественно, с комментариями и разъяснениями. Можем оговорить цену и нюансы выполнения работы.
Контакты:
[email protected]
Telegram - @daniil_muntyan
Мой профиль на e-olymp: https://www.e-olymp.com/ru/users/muntyan
Актуальные фриланс-проекты в категории Python
Ищем разработчика для создания торгового бота/чат-бота
Ищем разработчика для создания торгового бота / чат-бота. Нужен IT-специалист, который сможет разработать бота для анализа рынка 24/7 и отправки торговых сигналов по золоту, индексам, Bitcoin и Forex-парам. Главное требование - специалист должен разбираться в трейдинге,… Python, Разработка ботов ∙ 1 час 15 минут назад ∙ 14 ставок |
~5 микросервисов на FastAPI + правки и рефакторинг
15 719 UAH
Есть проект состоящий примерно из ~11 микросервисов на FastAPI с интеграциями, который более, чем на половину готов. Задача доделать остальные ~5 микросервисов (более конкретно - subscription/billing и интеграция с Revenuecat, abuse protection для биллинга, Notifications,… Python, Веб-программирование ∙ 6 часов 35 минут назад ∙ 26 ставок |
Power BI
700 UAH
Дашборд работает на гугл сервере, нужно перенести всю логику+код Какие нужны скиллы: развертывание etl процессов на linux сервере + работа с BigQuery и Postgre Есть рабочий код, который работает на google, где есть сама БД, нужно перенести на другой сервер, возможно переписать… Python, Базы данных и SQL ∙ 1 день 12 часов назад ∙ 15 ставок |
Телеграм-бот для найма/поиска работников. Для поиска работы
1100 UAH
1. Общая концепция Создание Telegram-бота для автоматизации подбора персонала и двустороннего поиска работы. Система работает по принципу активного отклика и взаимного подтверждения интереса (Double Opt-In). В системе предусмотрены две роли: Работодатель (Владелец фирмы) и… Python, Разработка ботов ∙ 2 дня 20 часов назад ∙ 93 ставки |
Техническая поддержка веб-платформы (Python/Django)Есть работающий веб-проект, нужно поддерживать и постепенно приводить в порядок, без переписывания с нуля. Стек проекта: Backend: Python, Django, Django Rest Framework Frontend: Next.js База данных: PostgreSQL Инфраструктура: AWS (EC2), Nginx Есть интеграции с внешними API… Python, Веб-программирование ∙ 2 дня 22 часа назад ∙ 73 ставки |