[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 369
Вы упускаете торговые возможности:
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Регистрация
Вход
Вы принимаете политику сайта и условия использования
Если у вас нет учетной записи, зарегистрируйтесь
Конечно, можно - если противник тоже владеет оптимальной стратегией. И от того, кто ходит первым, тоже зависит, похоже.
Да-да, два ряда тут ключевой момент. Но не просто два ряда, а с уточнениями:
- если ты оставил ему 1,1, то проиграл ты
- если ты оставил ему равные n,n (n>1), то проиграл он
- если ты оставил ему любые два неравных числа, то выиграл он.
Проблема в том, как сделать оптимальные ходы до этих двух рядов.
Ухххх, Парни, ТАКУЮ штуку сегодня поймал - закачаетесь :)))))))))
Сомневаюсь, что этот мужик в подпитии преобразовывал числа в двоичные... Ну для маленьких чисел это легко. А если уже пива на грудь литра три принял?
Бородатая игра. Называется "Ним". Стратегия заключается в том, что количество спичек на каждом "этаже" преобразуется в двоичное число, а потом считается четность-нечетность для отдельных колонок нулей и единиц.
Решение есть?
На википедии https://ru.wikipedia.org/wiki/Ним_(игра) есть описание выигрышной стратегии. Честоно говоря, я так и не понял, в чём суть. Как-то мутно написано.
Все там предельно ясно написано. Преобразуем количество спичек в двоичные числа, потом проводим побитовые операции над числами через логическое сложение по модулю 2 - что является полным аналогом вычисления четности-нечетности. Получаем стратегию, т.е. число которое нужно обнулить. Берем "этаж" в которой число спичек больше или равно числу стратегии. Если равно, то забираем все спички с этажа.
Если не равно, тогда число спичек на этаже складываем с числом-стратегией с помощью двоичного сложения по модулю 2. Получаем результат, т.е. сколько спичек должно остаться на "этаже", чтобы ход следующего игрока стал заведомо проигрышным. Забираем с "этажа" лишние спички.
Сомневаюсь, что этот мужик в подпитии преобразовывал числа в двоичные... Ну для маленьких чисел это легко. А если уже пива на грудь литра три принял?
Все гораздо проще. Для такого количества спичек все выигрышные комбинации можно запросто запомнить и вспомнить даже в подпитии. Будучи студентом я именно так и делал и обыгрывал своих сокурсников. Поэтому и говорю, что игра бородатая.
Попробуем разобрать пример, который приведён на википедии.
Складываем числа:
0010+1000+1101 = 0111 если не учитывать перенос единиц в старший разряд. Согласен. Как только ним-сумма была вичислена, автор утверждает, что нужно взять три предмета из третьей кучки. Вот этого-то я и не понял. С чего он взял что брать нужно только три предмета и почему именно из третьей кучки? Ведь для того, чтоб ним-сумма стала равна 0 нужно из числа 0111 вычесть 0111, то есть, вычесть семь.
Попробуем разобрать пример, который приведён на википедии.
Складываем числа:
0010+1000+1101 = 0111 если не учитывать перенос единиц в старший разряд. Согласен. Как только ним-сумма была вичислена, автор утверждает, что нужно взять три предмета из третьей кучки. Вот этого-то я и не понял. С чего он взял что брать нужно только три предмета и почему именно из третьей кучки? Ведь для того, чтоб ним-сумма стала равна 0 нужно из числа 0111 вычесть 0111, то есть, вычесть семь.
0010
1000
1101
-----
0111 - результат, т.е. в первой колонке четное количество спичек, в остальных нечетное.
Третий этаж 1101 = 13
Складываем количество кучек третьего этажа с результатом:
1101
0111
----
1010 = 10
13 - 10 = 3, т.е. с третьего этажа нужно забрать 3 спички, тогда там останется 10 спичек, что в двоичной системе = 1010
Проверяем, то что осталось:
0010
1000
1010
-----
0000 - выигрышная стратегия