ニム和表の作成方法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/23 08:10 UTC 版)
方法１ ビットごとの排他的論理和を用いる。整数を２進数表現に変換し、ビットごとの排他的論理和を計算する。 例 ニム和(6,12)の場合、十進数6は0110で、十進数12は1100で、これらのビットごとの排他的論理和は1010で、十進数10となる。 方法２ 未使用最小整数を用いる。0以上の整数m,nに対し以下の関数Gを計算し、ニム和(m,n)=G(m,n)とする。すなわちゲームの局面の値は、次のケームの局面の値として未使用の０以上の最小の整数であるというグランディ値の定義を利用する。 G(0,0)=0。 正のmについて、G(m,0)はG(m -1,0),...,G(0,0)に値として使われていない最小の0以上の整数。 正のnについて、G(0,n)はG(0,n -1),...,G(0,0)に値として使われていない最小の0以上の整数。 正のm,nについて、G(m,n)はG(m,n -1),...,G(m,0),G(m -1,n),...,G(0,n)に値として使われていない最小の0以上の整数。 例 G(1,0)はG(0,0)=0に値として使われていない最小の0以上の整数なので1。同様にG(0,1)は1。G(1,1)はG(1,0)=1 と G(0,1)=1に値として使われていない最小の0以上の整数なので0。 方法３ 以下のニム和表の再帰的構成法を用いる。サイズ 2 k {\displaystyle 2^{k}} の表は0以上 2 k − 1 {\displaystyle 2^{k}-1} 以下の整数m,nに対するニム和(m,n)表の値部分のことである。サイズ１の表４枚でサイズ２の表が、サイズ２の表４枚でサイズ４の表が、サイズ４の表４枚でサイズ８の表ができる。 サイズ１の表は 値0 である。 サイズ 2 k + 1 {\displaystyle 2^{k+1}} の表は４枚のサイズ 2 k {\displaystyle 2^{k}} の表を次のように配置する。 (左上)サイズ 2 k {\displaystyle 2^{k}} の表の値+0 (右上)サイズ 2 k {\displaystyle 2^{k}} の表の値+ 2 k {\displaystyle 2^{k}} (左下)サイズ 2 k {\displaystyle 2^{k}} の表の値+ 2 k {\displaystyle 2^{k}} (右下)サイズ 2 k {\displaystyle 2^{k}} の表の値+0
※この「ニム和表の作成方法」の解説は、「ニム和」の解説の一部です。
「ニム和表の作成方法」を含む「ニム和」の記事については、「ニム和」の概要を参照ください。
- ニム和表の作成方法のページへのリンク
