NIM(三)， python

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[1][0],v[1][1]):            true_table[name] = (True,v[1])            return (True,v[1])            return Nonedef nim(m,n):    if m>n:        m,n = n,m        name = str(m) + '+' +str(n)        if name in false_table:        return false_table[name]    if name in true_table:        return true_table[name]        #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[0],possible[1])        if r[0] == False:            true_table[name] = (True,possible)            return (True, possible)#        elif can_reach(m, n, r[1][0], r[1][1]):#            true_table[name] = (True,r[1])#            return (True,r[1])            false_table[name] = (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[0],possible[1])        if r[0] != 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))}

查看更多 下一篇