Алгоритмизация и программирование

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



Домашние задания

Сообщений 1 страница 2 из 2

1

Эта ветка для:
- постановки задач от тренера,
- самостоятельного их выполнения участниками,
- дальнейшего разбора вариантов решения при личной встрече на тренировке...


То есть в этой ветке именно руководитель ставит задачи исходя из того в какой теме видит резон для дальнейшего развития, а участники команд по Спортивному программированию придумывают свои способы реализации.
В дальнейшем на очных тренировках мы обсуждаем у кого какой вариант и какие сложности при реализации возникли.

Если вы считаете это возможным (не жалко, считаете, что нужно делиться), то можете опубликовать свои находки и решения с небольшими комментариями...
Достаточно будет просто оставить пост, что решил задачу такими-то способами, встретил такие-то трудности при преодолении лимита по времени или по объёму памяти...
После разбора задач со всеми при личных встречах, я буду публиковать и свои варианты решений тоже ;) ...

0

2


Домашнее задание №1 для наработки навыка работы с рекурсивными алгоритмами.

Для тех, кто понимает "динамику".
Задача 0787 - "Игра с пешкой": https://acmp.ru/index.asp?main=task&id_task=787

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a1, a2, …, aN. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

http://s5.uploads.ru/t/SNfAh.gif

Задачу нужно решить тремя способами:
1) Рекурсией - пишется быстрее всего, но в питоне по времени не влазит (((
2) Рекурсией с меморизацией - пишется на две минуты дольше и везде по времени влазит!!!
3) Динамикой чистой - пишется дольше всего и везде влазит )))

0



Рейтинг форумов | Создать форум бесплатно