15.07.2010, 05:53 | |
Ответы с готовыми решениями:
1272
Элементарные программы, для лучшего понимания языка... Задачи для тренировки и лучшего понимания языка Литература для лучшего понимания сути программирования Набор задачь для тренировки и улучшения понимания программирования |
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
09.01.2011, 17:45 | 1001 |
valeriikozlov, ааа, всё, теперь понял. Надо постоянно отслеживать, можно ли ещё добраться до угла, двигаясь только вниз и влево, и если нет, откатываться назад (при одном варианте решение, возможно, есть алгоритм без отката).
Добавлено через 4 минуты А такой алгоритм: Проверяем не достигнем ли мы за один ход по диагонали угла. Если да - победа за первым. Если нет, и при максимальном движении по диагонали попадаем на нижнюю границу доски - побеждает второй (первый двигает по диагонали до этой границы, а второй - вдоль неё и до угла), а если на левую границу - побеждает первый (первый двигает по диагонали на, по сути, любое количество клеток, ограниченное одним рядом клеток по левой границе, второй двигает до максимума вниз, а первый вдоль нижней границы до угла). Добавлено через 3 минуты Не, что-то левое, под ваши примеры не подходит... Добавлено через 3 минуты Похоже это я тупой... Но суть задания не доходит. Как будто не хватает каких-то ограничений. Потому что так, как я сейчас понял задание, выиграть всегда может как первый, так и второй игрок... Балин, я чего-то не понимаю... Добавлено через 3 минуты Во, я не понимаю, что есть "правильная игра"? Я знаю такой тип задачек, где оговорены условия, но чего-то делать нельзя, и определить надо, кто при правильной игре выиграет. Здесь вроде всё то же самое, только вот не пойму я, чего делать-то нельзя?
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
09.01.2011, 18:08 | 1002 |
Правильная игра, это когда каждый игрок своим ходом старается выиграть (и выигрывает, если ситуация не проигрышная). Ход мыслей у Вас в правильном направлении.... Еще чуть-чуть и додумаетесь.
По своему опыту: лучше взять листок в клетку и начиная с клетки (1, 1) подумать кто выигрывает с какой клетки (для достижения истины не так уж много клеток нужно рассмотреть).
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
09.01.2011, 18:24 | 1003 |
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
09.01.2011, 18:55 | 1004 |
Ну по-моему это одно и тоже. Один игрок делая ход и ставя этим ходом другого игрока в пригрышную позицию, тем самым обеспечивает себе победу (т.е. такой ход и называется правильным ходом).
0
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
10.01.2011, 02:22 [ТС] | 1005 |
Функция Шпрага-Гранди
Разве не та же тема?
0
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
10.01.2011, 04:19 | 1006 | |||||
1
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 07:58 | 1007 |
Mr.X, Ваш код прошел все тесты.
ForEveR, Та же самая получается тема. Теперь у меня вопрос: раз есть правильное решение, разбор этой задачи нужно делать?
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
10.01.2011, 07:59 | 1008 |
valeriikozlov, можно, вряд ли вы предполагали такое решение))) (честно говоря, мне лень было думать))) Если бы подумал - решил бы, а так - посмотрю ваш вариант)
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 08:35 | 1009 |
silent_1991, Алгоритм решения у меня такой (я привожу доску не бесконечную а 8*8, но все будет понятно):
Клетки обозначенные 0 - это клетки неизвестные (неизвестно, кто победит если с них начать). Клетка с координатами 0 0 - это клетка нижняя левая. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Т.к. всегда начинает 1 игрок, то логично предположить: 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Т.е. все клетки обозначенные 1 - это клетки из которых если начать, то выигрывает 1 игрок. Теперь обращаем внимание на клетки с координатами (3,2) и (2,3) - Если первый игрок начинает ходить с этих клеток, то он сможет пойти только на те клетки где выигрывает "первый начинающий ходить" игрок. В данном случае после его хода, "первым начинающим ходить" будет второй. Т.е. клетки (3,2) и (2,3) - это клетки выигрышные для второго игрока. Получаем: 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 2 1 0 0 0 0 0 1 1 2 0 0 0 0 0 1 1 1 1 1 1 1 1 (Еще раз повторюсь, что начинает всегда ходить 1 игрок. А 1 на поле означает что из этой клетки если начинается игра выиграет 1 игрок. А 2 на поле означает, что из этой клетки если начинается игра выиграет 2 игрок) Теперь рассмотрим клетки (пока неизвестные) вертикальные, горизонтальные и по диагонали к полученным 2-кам. Если игра начинается из них, то выигает всегда 1 игрок. При правильной игре 1 игрок всегда сделает ход в клетку с 2-кой (тем самым обрекает противника на поражение). Значит имеем: 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 Следующие на рассмотрении клетки (6,4) (4,6) (пока неизвестные) Если первый игрок начинает ходить из этих клеток, то из них он может попасть только в клетки, в которых выигрывает только "первый начинающий ходить". В данном случае это будет игрок 2. Значит получаем: 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 2 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 2 0 0 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 Затем снова заполняем (пока неизвестные) вертикальные, горизонтальные и по диагонали к полученным 2-кам, единицами (выше сказано почему): 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 Следующие на рассмотрении точки с координатами (8,5) и (5,8) - там значения равны 2. и т.д. Значения: (1 <= M, N <= 250) не такие уж и большие. Все заполнение матрицы пройдет быстро.
3
|
10.01.2011, 10:38 | 1010 |
valeriikozlov, именно это я и имел в виду, что задача математическая (аналитическая), ибо решается на бумажке. Т.е. будь ты хоть 100 раз программист, но если ты на бумажке её не решил, то программу не напишешь. Наверное я неправильным термином пользуюсь, но под "математической" задачей подразумеваю именно такие
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 12:57 | 1011 |
с этим согласен полностью. Сначало должен родится алгоритм решения такой задачи. А потом его реализация кодом.
Насчет терминов: может быть и правильный термин. По моему мнению аналитика и математика очень сильно связаны.
1
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
10.01.2011, 13:18 | 1012 |
Так и есть, в частности, аналитическое решение - решение, полученное с использованием логических заключений и математических выкладок, т.е. решение, которое, по сути, описывается формулой (или группой формул), и, что самое важное, даёт точный ответ (в отличие от численного решения, в котором главное не формула, а итерации, и отвёт даётся только с некоторой точностью).
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 13:39 | 1013 |
Как говорится "раз пошла такая пьянка ..." , то выкладываю еще одну задачу, на мой взгляд интересную:
INPUT.TXT 5 3 POLTE RWYMS OAIPT BDANR LEMES OLYMPIAD PROBLEM TEST OUTPUT.TXT AENRSW Следующий пример: INPUT.TXT 3 2 ISQ ABC IQW I IS OUTPUT.TXT ABCQQW
1
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
|
10.01.2011, 16:36 | 1014 |
Задача слишком легкая
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 16:37 | 1015 |
Хохол, точно.
1
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
10.01.2011, 18:54 | 1016 | |||||
2
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 19:02 | 1017 |
Mr.X, Как говорится в точку. Ваш код прошел все тесты.
2
|
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
|
||||||
10.01.2011, 19:13 | 1018 | |||||
1
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
10.01.2011, 22:15 | 1019 |
Хохол, И Вы в точку (кстати я решал так же как и Вы). Ваш код тоже прошел все тесты.
Добавлено через 11 минут Раз задача решена, осталось провести только ее разбор: Во-первых сразу сообщаю, что эту задачу не сам придумал, она действительно олимпиадная. Если кто не верит могу дать ссылку на нее. Я бы сказал, что эта задача в первую очередь на внимательность. Ключевая фраза в условии: Добавлено через 2 часа 43 минуты Ну и еще одна задачка: INPUT.TXT 7 3 OUTPUT.TXT 83
1
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
11.01.2011, 05:23 | 1020 | |||||
4
|
11.01.2011, 05:23 | |
Помогаю со студенческими работами здесь
1020
Проверить на правильность и закомментировать весь код для лучшего понимания Нужны задачи для тренировки Нужны задачи для тренировки Нужны задачи для тренировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |