Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
谁能帮解释一下下面这段话? 怎么找到the nim-value that each position of every Impartial Game hasIn Reply To:是不是根据已知的图推出一个公式,然后把初始位置带进去得到答案,那个公式就是SG? Posted by:alpc04 at 2006-07-02 14:20:37 Nim-Value Every position of every Impartial Game has a nim-value, making it equivalent to a Nim-Heap. To find the nim-value (also called the Sprague-Grundy Number), take the Mex of the nim-values of the possible moves. The nim-value can also be found by writing the number of counters in each heap in binary, adding without carrying, and replacing the digits with their values mod 2. If the nim-value is 0, the position is Safe; otherwise, it is Unsafe. With two heaps, safe positions are where . With three heaps, (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6), (2, 5, 7), and (3, 4, 7). Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator