NIM(3)， python
false_table = dict()true_table = dict()
def possible_next_moves(m,n):
for i in range(0,m):
yield(i,n)
for i in range(0,n):
if m<i:
yield(m,i)
else:
yield(i,m)
for i in range(0,m):
yield(i,n-m+i)
def can_reach(m,n,m1,n1):
if m==m1 and n==n1:
return False
if m==m1 or n==n1 or m-m1 == n-n1:
return True
else:
return False;
def quick_check(m,n,name):
for k,v in false_table.items():
if can_reach(m,n,v,v):
true_table = (True,v)
return (True,v)
return None
def nim(m,n):
if m>n:
m,n = n,m
name = str(m) + '+' +str(n)
if name in false_table:
return false_table
if name in true_table:
return true_table
#Used for Optimization, but optional
check = quick_check(m,n,name)
if check:
return check
for possible in possible_next_moves(m,n):
r=nim(possible,possible)
if r == False:
true_table = (True,possible)
return (True, possible)
# elif can_reach(m, n, r, r):
# true_table = (True,r)
# return (True,r)
false_table = (False,(m,n))
return (False,(m,n))
def assert_false(m,n):
size = 0
for possible in possible_next_moves(m,n):
size = size +1
r = nim (possible,possible)
if r != True:
print('error!',m,n,'should be false but it has false sub move', possible)
return
print('all',size,'possible moves are checked!')
if __name__ == '__main__':
assert_false(6,8)
false_table
{'3+5': (False, (3, 5)), '1+2': (False, (1, 2)), '0+0': (False, (0, 0)),
'4+7': (False, (4, 7))}
true_table
{'2+4': (True, (1, 2)), '2+5': (True, (1, 2)), '2+7': (True, (1, 2)),
'0+5': (True, (0, 0)), '4+8': (True, (4, 7)), '0+2': (True, (0, 0)),
'0+3': (True, (0, 0)), '2+6': (True, (1, 2)), '0+1': (True, (0, 0)),
'0+6': (True, (0, 0)), '0+7': (True, (0, 0)), '0+4': (True, (0, 0)),
'2+3': (True, (1, 2)), '0+8': (True, (0, 0)), '2+8': (True, (1, 2)),
'4+6': (True, (3, 5)), '4+4': (True, (0, 0)), '1+8': (True, (1, 2)),
'1+3': (True, (1, 2)), '1+1': (True, (0, 0)), '1+7': (True, (1, 2)),
'1+6': (True, (1, 2)), '1+5': (True, (1, 2)), '1+4': (True, (1, 2)),
'3+4': (True, (1, 2)), '3+7': (True, (3, 5)), '3+6': (True, (3, 5)),
'3+3': (True, (0, 0)), '5+8': (True, (4, 7)), '5+6': (True, (1, 2)),
'3+8': (True, (3, 5)), '6+6': (True, (0, 0)), '6+7': (True, (1, 2)),
'4+5': (True, (3, 5))}
页:
[1]