Форум » Теория игр » Задание 20 (№ 4111) » Ответить
Задание 20 (№ 4111)
dim18: Здравствуйте! Подскажите, пож., в чем ошибка. Основанное на таком алгоритме решение задачи 19 дает правильный ответ. [pre2] def f(s, n): if 100 >= s >= 65 and n == 3: return True elif (s < 65 or s > 100) and n == 3: return False elif 100 >= s >= 65 and n == 2: return False else: if n % 2 == 0: return f(s + 1, n + 1) or f(s * 3, n + 1) else: return f(s + 1, n + 1) and f(s * 3, n + 1) for s in range(1, 64 + 1): if f(s, 0): print(s) # (№ 4111) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит # куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может # а) добавить в кучу один камень; # б) увеличить количество камней в куче в три раза. # Игра завершается в тот момент, когда количество камней в куче становится не менее 65. # Если при этом в куче оказалось не более 100 камней, то победителем считается игрок, # сделавший последний ход. В противном случае победителем становится его противник. # В начальный момент в куче было S камней, 1 ≤ S ≤ 64. # Определите, два таких значения S, при которых у Пети есть выигрышная стратегия, # причём одновременно выполняются два условия: # − Петя не может выиграть за один ход; # − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. # Найденные значения запишите в ответе в порядке возрастания. [/pre2]
Ответов - 4
Поляков: Вот решение этой задачи через программу:[pre2] TARGET, FAIL = 65, 100 KADD, KMUL = 1, 3 def gameOver( n1 ): return n1 >= TARGET results = {} def gameResult( x ): if x in results: return results[x] if gameOver(x): return 0 if x <= FAIL else 1 nextCodes = [ gameResult( x+KADD ), gameResult( x*KMUL ) ] negative = [c for c in nextCodes if c <= 0] if negative: res = -max(negative) + 1 else: res = -max(nextCodes) results[x] = res return res from math import ceil ans1 = ceil(TARGET/KMUL/KMUL) ans2 = [] ans3 = [] for S in range(TARGET-1,0,-1): r = gameResult( S ) print( "%d: %d" % (S, r) ) if r == 2: ans2.append(S) if r == -2: ans3.append(S) #------------------------------------------------------- # Ответы на вопросы #------------------------------------------------------- print("--- Ответы на вопросы ---") print("1. ", ans1) print("2. ", sorted(ans2)) print("3. ", sorted(ans3))[/pre2]
dim18: Спасибо!
s11kai: dim18 пишет: # Определите, два таких значения S, при которых у Пети есть выигрышная стратегия, # причём одновременно выполняются два условия: # − Петя не может выиграть за один ход; # − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. # Найденные значения запишите в ответе в порядке возрастания. Конкретно на поставленный вопрос, предложил красивое решение, к сожалению не я, а Алексей Кабанов! [pre2] from functools import * def m(h): return h+1, h*3 @lru_cache(None) def g(h): if 65<=h<=100:return'w' if h>100:return 'p1' if any(g(i)=='w' for i in m(h)):return 'p1' if all(g(i)=='p1' for i in m(h)):return 'v1' if any(g(i)=='v1' for i in m(h)):return 'p2' if all(g(i)=='p1' or g(i)=='p2' for i in m(h)):return 'v2' for i in range(1,64): if g(i)=='p2': print(g(i),i) [/pre2]
s11kai: Кстати, если кому интересно, то полное решение, оказывается, может выглядеть, как вариант, примерно так: [pre2] from math import ceil from functools import * def m(h): return h+1, h*3 @lru_cache(None) def g(h): if 65<=h<=100:return'w' if h>100:return 'p1' if any(g(i)=='w' for i in m(h)):return 'p1' if all(g(i)=='p1' for i in m(h)):return 'v1' if any(g(i)=='v1' for i in m(h)):return 'p2' if all(g(i)=='p1' or g(i)=='p2' for i in m(h)):return 'v2' print('v1',ceil(65/9)) for i in range(1,64): if g(i)=='p2': print(g(i),i) for i in range(1,64): if g(i)=='v2': print(g(i),i) [/pre2]
полная версия страницы