|
投稿者：山中和義
投稿日：2011年 5月19日(木)10時47分11秒
|
|
|
|
問題
平面上に、n×n個の点が格子状に配置されている。
その中から次の条件を満たすような2n個の点を選ぶことができるだろうか。
条件：2n個の点のうち、どの３点を選んでも同一直線上にはない
参考サイト http://www.maa.org/editorial/mathgames/mathgames_04_11_05.html
具体的に、
対称なものを同一視する場合
N=1
・ なし
N=2
●●
●●
N=3
●●・
●・●
・●●
N=4
●●・・ １
・・●●
●●・・
・・●●
●・●・ ２
・●・●
・●・●
●・●・
●・●・ ３
・・●●
●●・・
・●・●
・●●・ ４
●・・●
●・・●
・●●・
N=5
●●・・・ １
●・・●・
・・・●●
・●●・・
・・●・●
●●・・・ ２
・●・●・
●・・・●
・・●・●
・・●●・
●・●・・ ３
・●・・●
・・・●●
●●・・・
・・●●・
●・●・・ ４
・・●・●
●●・・・
・・・●●
・●・●・
・●●・・ ５
●・・・●
・・・●●
●●・・・
・・●●・
となります。
プログラムでは、
対称なものを同一視しない場合
n= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
0, 1, 2,11,32,50,132,380,368,1135,1120, …
を求めてみました。
２進モードで実行してください。Nが10以上で負荷が大きくなります。
!線上無三問題（No-Three-in-Line問題）
LET t0=TIME
PUBLIC NUMERIC N !N×N個の格子 ※N≧1
LET N=7
PUBLIC NUMERIC s !解の数
LET s=0
PUBLIC NUMERIC C(50),C2(100),C3(100) !列、斜め方向の数（チェック用） ※n個、2n個
MAT C=2*CON
MAT C2=2*CON
MAT C3=2*CON
PUBLIC NUMERIC XX(100),YY(100) !「点」の座標 ※2n個
PUBLIC NUMERIC TBL_GCD(50,50) !GCD(i,j)の値
FOR i=1 TO N-1
FOR j=i TO N-1
LET t=GCD(i,j)
LET TBL_GCD(i,j)=t !上三角
LET TBL_GCD(j,i)=t !下三角 ※対角線は上書きされる
NEXT j
NEXT i
DIM M(N,N) !「点」の配置
MAT M=ZER
CALL try(1,M)
IF s=0 THEN PRINT "解なし"
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB try(p,M(,)) !バックトラック法（深さ優先）で検索する
LET T=2*p !「点」の数
LET YY(T-1)=p !p×nの矩形内の「点」を抽出する
LET YY(T)=p
FOR i=1 TO N-1 !１つの行p（水平線）で２個選ぶ ※COMB(N,2)
IF C(i)>0 AND C2(p+i)>0 AND C3(p-i+N)>0 THEN !１つの列（垂直線）、斜め（±45°）でも２個までとなる
LET FLG=0 !１行目と２行目なら、無条件に追加する
IF p>2 THEN CALL check(p,i,T-4,M, FLG) !３行目以上なら、斜めの直線を考慮する
IF FLG=0 THEN !※T-4： dy=-1では、GCD=1となるので、対象から除外してよい
LET M(p,i)=1 !１つ目の点をとる
LET C(i)=C(i)-1 !列
LET C2(p+i)=C2(p+i)-1 !45°斜め
LET C3(p-i+N)=C3(p-i+N)-1 !-45°斜め
LET XX(T-1)=i !※Tすなわちpによるスタックとなる
FOR j=i+1 TO N !（組合せ）
IF C(j)>0 AND C2(p+j)>0 AND C3(p-j+N)>0 THEN
LET FLG=0
IF p>2 THEN CALL check(p,j,T-4,M, FLG)
IF FLG=0 THEN
LET M(p,j)=1 !２つ目の点をとる
LET C(j)=C(j)-1
LET C2(p+j)=C2(p+j)-1
LET C3(p-j+N)=C3(p-j+N)-1
LET XX(T)=j
IF p=N THEN !全ての行が揃ったら
LET s=s+1 !結果を表示する
PRINT "No."; s
MAT PRINT M;
!!!STOP !※１つのみ ←←←←←
ELSE
CALL try(p+1,M) !次の行へ
END IF
LET M(p,j)=0 !元に戻す
LET C(j)=C(j)+1
LET C2(p+j)=C2(p+j)+1
LET C3(p-j+N)=C3(p-j+N)+1
END IF
END IF
NEXT j
LET M(p,i)=0 !元に戻す
LET C(i)=C(i)+1
LET C2(p+i)=C2(p+i)+1
LET C3(p-i+N)=C3(p-i+N)+1
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB check(Y0,X0,T,M(,), FLG) !斜めの直線に関して
LET FLG=1 !NG
FOR i=1 TO T !追加する点と既存の点を選ぶ
LET dx=XX(i)-X0 !傾き
LET ax=ABS(dx)
IF ax>1 THEN !垂直線（チェック済み）以外 ※またdx=±1では、GCD=1となるので、対象から除外してよい
LET dy=YY(i)-Y0 !※行が異なるため、Y0≠YY(i)からdy≠0（水平線以外）である。
LET ay=ABS(dy)
IF ax<>ay THEN !斜め（±45°）の直線（チェック済み）以外
!線上の格子点の個数
! ２つ端点が(x1,y1)、(x2,y2)なら、この端点を除いて、GCD(|x1-x2|,|y1-y2|)-1 個
LET G=TBL_GCD(ay,ax)
IF G>1 THEN !格子点の数が１以上なら
LET y=Y0 !始端
LET x=X0
FOR j=1 TO G-1
LET y=y+dy/G !線上の格子点
LET x=x+dx/G
IF M(y,x)=1 THEN EXIT SUB !もう１個が見つかったら、ＮＧ！
NEXT j
END IF
END IF
END IF
NEXT i
LET FLG=0 !すべての線分で確認したら、ＯＫ！
END SUB
EXTERNAL FUNCTION GCD(a,b) !最大公約数
DO WHILE b<>0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET GCD=a
END FUNCTION
|
|
|
|
投稿者：山中和義
投稿日：2011年 5月21日(土)19時04分27秒
|
|
|
|
問題
平面上に、n×n個の点が格子状に配置されている。
その中から次の条件を満たすような2n個の点を選ぶことができるだろうか。
条件：2n個の点のうち、どの３点を選んでも同一直線上にはない
答え
n= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
0, 1, 2,11,32,50,132,380,368,1135,1120, …
n= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
0, 1, 1, 4, 5, 11, 22, 57, 51,156,158, …
異なる解の個数を求めるように修正してみました。
LET t0=TIME
PUBLIC NUMERIC N !N×N個の格子 ※N≧1
LET N=6
PUBLIC NUMERIC s(8) !解の数
MAT s=ZER
PUBLIC NUMERIC C(50),C2(100),C3(100) !列、斜め方向の数（チェック用） ※n個、2n個
MAT C=2*CON
MAT C2=2*CON
MAT C3=2*CON
PUBLIC NUMERIC XX(100),YY(100) !「点」の座標 ※2n個
PUBLIC NUMERIC TBL_GCD(50,50) !GCD(i,j)の値
FOR i=1 TO N-1
FOR j=i TO N-1
LET t=GCD(i,j)
LET TBL_GCD(i,j)=t !上三角
LET TBL_GCD(j,i)=t !下三角 ※対角線は上書きされる
NEXT j
NEXT i
DIM M(N,N) !「点」の配置
MAT M=ZER
CALL try(1,M)
IF s(1)=0 THEN PRINT "解なし"
MAT PRINT s;
PRINT "異なる解="; (s(1)+s(2)+s(3)+s(4)+s(5)+s(6)+s(7)+s(8))/8
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB try(p,M(,)) !バックトラック法（深さ優先）で検索する
LET T=2*p !「点」の数
LET YY(T-1)=p !p×nの矩形内の「点」を抽出する
LET YY(T)=p
FOR i=1 TO N-1 !１つの行p（水平線）で２個選ぶ ※COMB(N,2)
IF C(i)>0 AND C2(p+i)>0 AND C3(p-i+N)>0 THEN !１つの列（垂直線）、斜め（±45°）でも２個までとなる
LET FLG=0 !１行目と２行目なら、無条件に追加する
IF p>2 THEN CALL check(p,i,T-4,M, FLG) !３行目以上なら、斜めの直線を考慮する
IF FLG=0 THEN !※T-4： dy=-1では、GCD=1となるので、対象から除外してよい
LET M(p,i)=1 !１つ目の点をとる
LET C(i)=C(i)-1 !列
LET C2(p+i)=C2(p+i)-1 !45°斜め
LET C3(p-i+N)=C3(p-i+N)-1 !-45°斜め
LET XX(T-1)=i !※Tすなわちpによるスタックとなる
FOR j=i+1 TO N !（組合せ）
IF C(j)>0 AND C2(p+j)>0 AND C3(p-j+N)>0 THEN
LET FLG=0
IF p>2 THEN CALL check(p,j,T-4,M, FLG)
IF FLG=0 THEN
LET M(p,j)=1 !２つ目の点をとる
LET C(j)=C(j)-1
LET C2(p+j)=C2(p+j)-1
LET C3(p-j+N)=C3(p-j+N)-1
LET XX(T)=j
IF p=N THEN !全ての行が揃ったら
CALL MtxSymmetry(M) !解の対称性
PRINT "No."; s(1) !結果を表示する
MAT PRINT M;
!!!STOP !※１つのみ ←←←←←
ELSE
CALL try(p+1,M) !次の行へ
END IF
LET M(p,j)=0 !元に戻す
LET C(j)=C(j)+1
LET C2(p+j)=C2(p+j)+1
LET C3(p-j+N)=C3(p-j+N)+1
END IF
END IF
NEXT j
LET M(p,i)=0 !元に戻す
LET C(i)=C(i)+1
LET C2(p+i)=C2(p+i)+1
LET C3(p-i+N)=C3(p-i+N)+1
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB check(Y0,X0,T,M(,), FLG) !斜めの直線に関して
LET FLG=1 !NG
FOR i=1 TO T !追加する点と既存の点を選ぶ
LET dx=XX(i)-X0 !傾き
LET ax=ABS(dx)
IF ax>1 THEN !垂直線（チェック済み）以外 ※またdx=±1では、GCD=1となるので、対象から除外してよい
LET dy=YY(i)-Y0 !※行が異なるため、Y0≠YY(i)からdy≠0（水平線以外）である。
LET ay=ABS(dy)
IF ax<>ay THEN !斜め（±45°）の直線（チェック済み）以外
!線上の格子点の個数
! ２つ端点が(x1,y1)、(x2,y2)なら、この端点を除いて、GCD(|x1-x2|,|y1-y2|)-1 個
LET G=TBL_GCD(ay,ax)
IF G>1 THEN !格子点の数が１以上なら
LET y=Y0 !始端
LET x=X0
FOR j=1 TO G-1
LET y=y+dy/G !線上の格子点
LET x=x+dx/G
IF M(y,x)=1 THEN EXIT SUB !もう１個が見つかったら、ＮＧ！
NEXT j
END IF
END IF
END IF
NEXT i
LET FLG=0 !すべての線分で確認したら、ＯＫ！
END SUB
!バーンサイドの定理（コーシー・フロベニウスの定理）
!集合A={対称なものを同一視しないで求めた解}
!置換群G={σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8}、|G|=8、 ※N次行列の要素の対称性より
! σ1 そのまま（恒等置換）
! σ2 反時計回りに90°回転
! σ3 反時計回りに180°回転
! σ4 反時計回りに270°回転
! σ5 左右裏返し ※裏返す軸は、「水平線（上下）」、「45°斜め線」、「-45°斜め線」でもよい
! σ6 左右裏返し + 反時計回りに90°回転
! σ7 左右裏返し + 反時計回りに180°回転
! σ8 左右裏返し + 反時計回りに270°回転
!S(X) Gの中の置換Xで変わらない、Aの中の不変元の個数
!とすると
! Aの同値類の個数m=Σ[σ∈G]{S(σ)} / |G|
! =( S(σ1)+S(σ2)+S(σ3)+S(σ4)+S(σ5)+S(σ6)+S(σ7)+S(σ8) ) / |G|
!となる。
EXTERNAL SUB MtxSymmetry(M(,)) !解の対称性
DIM B(N,N),B2(N,N)
LET s(1)=s(1)+1 !そのまま
CALL MtxR90(M,B) !90°回転対称な解の数
CALL MtxIsEqual(M,B, FLG)
LET s(2)=s(2)+FLG !FLGは、０または１とする
CALL MtxR90(B,B2) !180°
CALL MtxIsEqual(M,B2, FLG)
LET s(3)=s(3)+FLG
CALL MtxR90(B2,B) !270°
CALL MtxIsEqual(M,B, FLG)
LET s(4)=s(4)+FLG
CALL MtxLR(M,B2) !左右裏返し
CALL MtxIsEqual(M,B2, FLG)
LET s(5)=s(5)+FLG
CALL MtxR90(B2,B) !左右 + 90°
CALL MtxIsEqual(M,B, FLG)
LET s(6)=s(6)+FLG
CALL MtxR90(B,B2) !左右 + 180°
CALL MtxIsEqual(M,B2, FLG)
LET s(7)=s(7)+FLG
CALL MtxR90(B2,B) !左右 + 270°
CALL MtxIsEqual(M,B, FLG)
LET s(8)=s(8)+FLG
SUB MtxIsEqual(A(,),B(,), FLG) !A=Bか確認する ※FLG=1なら、一致
LET FLG=0
FOR i=1 TO N
FOR j=1 TO N
IF A(i,j)<>B(i,j) THEN EXIT SUB
NEXT j
NEXT i
LET FLG=1 !すべてが一致する
END SUB
SUB MtxLR(M(,), B(,)) !左右裏返し（列の順序を逆にする） ※変数名M≠変数名B
FOR i=1 TO N
FOR j=1 TO N
LET B(i,N-j+1)=M(i,j)
NEXT j
NEXT i
END SUB
SUB MtxR90(M(,), B(,)) !反時計回りに90°回転 ※変数名M≠変数名B
FOR i=1 TO N
FOR j=1 TO N
LET B(N-j+1,i)=M(i,j)
NEXT j
NEXT i
END SUB
END SUB
EXTERNAL FUNCTION GCD(a,b) !最大公約数
DO WHILE b<>0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET GCD=a
END FUNCTION
補足
N=6
●●・・・・ １
・・・●・●
・●・・●・
●・●・・・
・・・・●●
・・●●・・
●●・・・・ ２
・・・●・●
・・●・●・
●・●・・・
・●・・・●
・・・●●・
●・●・・・ ３
・・●・●・
●●・・・・
・・・・●●
・●・●・・
・・・●・●
●・●・・・ ４
・・・●●・
・●・・・●
●●・・・・
・・・・●●
・・●●・・
●・●・・・ ５
・・・・●●
・●・・●・
●●・・・・
・・・●・●
・・●●・・
・●●・・・ ６
●・・・●・
●・●・・・
・・・●・●
・●・・・●
・・・●●・
・●●・・・ ７
・・●・●・
●・・・・●
●・・・・●
・●・●・・
・・・●●・
・●●・・・ ８
・・●・・●
・・・・●●
●●・・・・
●・・●・・
・・・●●・
・●●・・・ ９
・・・・●●
●・●・・・
・・・●・●
●●・・・・
・・・●●・
・●・●・・ 10
・・●・・●
●・・・●・
・●・・・●
●・・●・・
・・●・●・
・●・●・・ 11
・・・●・●
●●・・・・
・・・・●●
●・●・・・
・・●・●・
|
|
|
|
投稿者：山中和義
投稿日：2011年 5月23日(月)11時27分46秒
|
|
|
|
> No.1548[元記事へ]
調査結果
+-----+
+-----+ +-----+
N s1 s2 s3 s4 s5 s6 s7 s8 異なる解
1 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1=(1+1+1+1+1+1+1+1)/8
3 2 0 2 0 0 2 0 2 1
4 11 1 7 1 3 3 3 3 4
5 32 0 0 0 0 4 0 4 5
6 50 6 18 6 0 4 0 4 11
7 132 0 40 0 0 2 0 2 22
8 380 8 36 8 2 10 2 10 57
9 368 0 28 0 0 6 0 6 51
10 1135 13 67 13 1 9 1 9 156
11
12 0
13
14 0
15
16 0
17
18 0
19
20 0
21
22
左右対称（s5）より、180°回転対称（s3）が多いようです。
異なる解を求めるように修正してみました。２進モードで実行してください。
!線上無三問題（No-Three-in-Line問題）
LET t0=TIME
PUBLIC NUMERIC N !N×N個の格子 ※N≧1
LET N=6
PUBLIC NUMERIC s !解の数
LET s=0
PUBLIC NUMERIC C(50),C2(100),C3(100) !列、斜め方向の数（チェック用） ※n個、2n個
MAT C=2*CON
MAT C2=2*CON
MAT C3=2*CON
PUBLIC NUMERIC XX(100),YY(100) !「点」の座標 ※2n個
PUBLIC NUMERIC XX_sav(5000),YY_sav(5000) !解の記録 ※
PUBLIC NUMERIC TBL_GCD(50,50) !GCD(i,j)の値
FOR i=1 TO N-1
FOR j=i TO N-1
LET t=GCD(i,j)
LET TBL_GCD(i,j)=t !上三角
LET TBL_GCD(j,i)=t !下三角 ※対角線は上書きされる
NEXT j
NEXT i
DIM M(N,N) !「点」の配置
MAT M=ZER
CALL try(1,M)
IF s=0 THEN PRINT "解なし"
PRINT "計算時間=";TIME-t0
END
EXTERNAL SUB try(p,M(,)) !バックトラック法（深さ優先）で検索する
LET T=2*p !「点」の数
LET YY(T-1)=p !p×nの矩形内の「点」を抽出する
LET YY(T)=p
FOR i=1 TO N-1 !１つの行p（水平線）で２個選ぶ ※COMB(N,2)
IF C(i)>0 AND C2(p+i)>0 AND C3(p-i+N)>0 THEN !１つの列（垂直線）、斜め（±45°）でも２個までとなる
LET FLG=0 !１行目と２行目なら、無条件に追加する
IF p>2 THEN CALL check(p,i,T-4,M, FLG) !３行目以上なら、斜めの直線を考慮する
IF FLG=0 THEN !※T-4： dy=-1では、GCD=1となるので、対象から除外してよい
LET M(p,i)=1 !１つ目の点をとる
LET C(i)=C(i)-1 !列
LET C2(p+i)=C2(p+i)-1 !45°斜め
LET C3(p-i+N)=C3(p-i+N)-1 !-45°斜め
LET XX(T-1)=i !※Tすなわちpによるスタックとなる
FOR j=i+1 TO N !（組合せ）
IF C(j)>0 AND C2(p+j)>0 AND C3(p-j+N)>0 THEN
LET FLG=0
IF p>2 THEN CALL check(p,j,T-4,M, FLG)
IF FLG=0 THEN
LET M(p,j)=1 !２つ目の点をとる
LET C(j)=C(j)-1
LET C2(p+j)=C2(p+j)-1
LET C3(p-j+N)=C3(p-j+N)-1
LET XX(T)=j
IF p=N THEN !全ての行が揃ったら
CALL MtxSymmetry(M,s, FLG) !解の対称性
IF FLG=0 THEN
LET pt=2*N*s+1 !既出の解を記録する
FOR x=1 TO 2*N
LET YY_sav(pt+x)=YY(x)
LET XX_sav(pt+x)=XX(x)
NEXT x
LET s=s+1 !結果を表示する
PRINT "No."; s
FOR y=1 TO N
FOR x=1 TO N
IF M(y,x)=1 THEN PRINT "●"; ELSE PRINT "・";
NEXT x
PRINT
NEXT y
!PRINT
!!!STOP !※１つのみ ←←←←←
END IF
ELSE
CALL try(p+1,M) !次の行へ
END IF
LET M(p,j)=0 !元に戻す
LET C(j)=C(j)+1
LET C2(p+j)=C2(p+j)+1
LET C3(p-j+N)=C3(p-j+N)+1
END IF
END IF
NEXT j
LET M(p,i)=0 !元に戻す
LET C(i)=C(i)+1
LET C2(p+i)=C2(p+i)+1
LET C3(p-i+N)=C3(p-i+N)+1
END IF
END IF
NEXT i
END SUB
EXTERNAL SUB check(Y0,X0,T,M(,), FLG) !斜めの直線に関して
LET FLG=1 !NG
FOR i=1 TO T !追加する点と既存の点を選ぶ
LET dx=XX(i)-X0 !傾き
LET ax=ABS(dx)
IF ax>1 THEN !垂直線（チェック済み）以外 ※またdx=±1では、GCD=1となるので、対象から除外してよい
LET dy=YY(i)-Y0 !※行が異なるため、Y0≠YY(i)からdy≠0（水平線以外）である。
LET ay=ABS(dy)
IF ABS(ax-ay)>1 THEN !斜め（±45°）の直線（チェック済み）以外 ※また|dx|-|dy|=±1では、GCD=1となるので、対象から除外してよい
!!IF ax<>ay THEN !斜め（±45°）の直線（チェック済み）以外
!線上の格子点の個数
! ２つ端点が(x1,y1)、(x2,y2)なら、この端点を除いて、GCD(|x1-x2|,|y1-y2|)-1 個
LET G=TBL_GCD(ay,ax)
IF G>1 THEN !格子点の数が１以上なら
LET y=Y0 !始端
LET x=X0
FOR j=1 TO G-1
LET y=y+dy/G !線上の格子点
LET x=x+dx/G
IF M(y,x)=1 THEN EXIT SUB !もう１個が見つかったら、ＮＧ！
NEXT j
END IF
END IF
END IF
NEXT i
LET FLG=0 !すべての線分で確認したら、ＯＫ！
END SUB
EXTERNAL SUB MtxSymmetry(M(,),s, FLG) !解の対称性
DIM A(N,N),B(N,N),B2(N,N)
LET FLG=1 !NG
FOR x=0 TO s-1 !既出の解と比較する
MAT A=ZER !解を復元する
LET pt=2*N*x+1
FOR y=1 TO 2*N
LET A(YY_sav(pt+y),XX_sav(pt+y))=1
NEXT y
CALL MtxR90(A,B) !90°回転対称な解
CALL MtxIsEqual(M,B, v)
IF v=1 THEN EXIT SUB !一致するなら
CALL MtxR90(B,B2) !180°
CALL MtxIsEqual(M,B2, v)
IF v=1 THEN EXIT SUB
CALL MtxR90(B2,B) !270°
CALL MtxIsEqual(M,B, v)
IF v=1 THEN EXIT SUB
CALL MtxLR(A,B2) !左右裏返し
CALL MtxIsEqual(M,B2, v)
IF v=1 THEN EXIT SUB
CALL MtxR90(B2,B) !左右 + 90°
CALL MtxIsEqual(M,B, v)
IF v=1 THEN EXIT SUB
CALL MtxR90(B,B2) !左右 + 180°
CALL MtxIsEqual(M,B2, v)
IF v=1 THEN EXIT SUB
CALL MtxR90(B2,B) !左右 + 270°
CALL MtxIsEqual(M,B, v)
IF v=1 THEN EXIT SUB
NEXT x
LET FLG=0 !すべて確認したら、ＯＫ！
SUB MtxIsEqual(A(,),B(,), c) !A=Bか確認する ※FLG=1なら、一致
LET c=0
FOR i=1 TO N
FOR j=1 TO N
IF A(i,j)<>B(i,j) THEN EXIT SUB
NEXT j
NEXT i
LET c=1 !すべてが一致する
END SUB
SUB MtxLR(M(,), B(,)) !左右裏返し（列の順序を逆にする） ※変数名M≠変数名B
FOR i=1 TO N
FOR j=1 TO N
LET B(i,N-j+1)=M(i,j)
NEXT j
NEXT i
END SUB
SUB MtxR90(M(,), B(,)) !反時計回りに90°回転 ※変数名M≠変数名B
FOR i=1 TO N
FOR j=1 TO N
LET B(N-j+1,i)=M(i,j)
NEXT j
NEXT i
END SUB
END SUB
EXTERNAL FUNCTION GCD(a,b) !最大公約数
DO WHILE b<>0
LET t=b
LET b=MOD(a,b)
LET a=t
LOOP
LET GCD=a
END FUNCTION
|
|
|
|
投稿者：GAI
投稿日：2011年 5月25日(水)06時11分38秒
|
|
|
|
> No.1558[元記事へ]
山中和義さんへのお返事です。
> !線上無三問題（No-Three-in-Line問題）
のプログラムでいろいろ楽しませてもらいました。
特にn＝９のパターンは将棋盤で１８個の”歩”を配置するゲームとして
行うと面白いかも・・・
ところで、ではNo-Four-in-Line問題（３個ずつが並ぶ）
のパターンが知りたくなりました。
プログラムに素人の私には、どこをどう変更したらよいものか、
また変更したらどれくらい面倒なことが発生するのかも検討が
つきません。
原理は似ているような気もします。
もし簡単に変更可能なら、山中さん作って頂けないでしょうか？
|
|
|
戻る