十進BASIC第2掲示板過去ログ

おねえさんのコンピューター

投稿者：山中和義投稿日：2012年10月 1日(月)19時46分53秒

ネット上で大きな話題だそうですね。 > 小さなサイズ（7×7程度）であれば「深さ優先検索（DFS）」というアルゴリズムで解けます。 !問題 !m行n列の格子状の道がある。 !同じ交差点を通らないようにして、左上から右下へ向かうときの道順は何通りか。 !例　m=n=3の場合 !　始点─・─・ !　　│　│　│ !　　・─・─・ !　　│　│　│ !　　・─・─終点 !のとき、 !　始点─・　・ !　　　　│ !　　・　・─・ !　　　　　　│ !　　・　・　終点 !のような最短経路は条件を満たす。 !また、 !　始点　・─・ !　　│　│　│ !　　・─・　・ !　　　　　　│ !　　・　・　終点 !のような遠回りも条件を満たす。 !求める道順は、12通りある。 !参考サイト　http://mathworld.wolfram.com/Self-AvoidingWalk.html LET t0=TIME LET M=6 !行 LET N=M !列 PUBLIC NUMERIC C !解の個数 LET C=0 DIM P(0 TO M-1,0 TO N-1) !経路 p(y,x) MAT P=(-1)*CON LET P(0,0)=0 !左上がスタート位置 LET P(0,1)=1 !左斜めの対角線で折り返すと対称になる　(0,0)→(0,1) CALL try(0,1,2,P,M,N) !(0,1) PRINT 2*C;"通り" PRINT "計算時間=";TIME-t0 END EXTERNAL SUB try(y,x,s,P(,),M,N) !バックトラック法で検索する IF x=N-1 AND y=M-1 THEN !ゴール（右下）に到達したなら LET C=C+1 !経路を表示する !!PRINT "No.";C !!MAT PRINT P; ELSE IF y=0 OR y=M-1 THEN !上壁沿いか下壁沿いなら、左側は袋小路なので進入禁止とする ELSE IF x>0 THEN !左端以外なら左へ LET xx=x-1 IF P(y,xx)=-1 THEN !未踏なら LET P(y,xx)=s !仮に進む CALL try(y,xx,s+1,P,M,N) !次へ LET P(y,xx)=-1 !戻す END IF END IF END IF IF x<N-1 THEN !右へ LET xx=x+1 IF P(y,xx)=-1 THEN LET P(y,xx)=s CALL try(y,xx,s+1,P,M,N) LET P(y,xx)=-1 END IF END IF IF x=0 OR x=N-1 THEN !左壁沿いか右壁沿いなら、上側は袋小路なので進入禁止とする ELSE IF y>0 THEN !上へ LET yy=y-1 IF P(yy,x)=-1 THEN LET P(yy,x)=s CALL try(yy,x,s+1,P,M,N) LET P(yy,x)=-1 END IF END IF END IF IF y<M-1 THEN !下へ LET yy=y+1 IF P(yy,x)=-1 THEN LET P(yy,x)=s CALL try(yy,x,s+1,P,M,N) LET P(yy,x)=-1 END IF END IF END IF END SUB

Re: おねえさんのコンピューター

投稿者：山中和義投稿日：2012年10月 6日(土)07時18分57秒

> No.1985[元記事へ] > 小さなサイズ（7×7程度）であれば「深さ優先検索（DFS）」というアルゴリズムで解けます。 C言語などのサンプルでは、漸化式による表現で計算しています。 LET t0=TIME PUBLIC NUMERIC M,N LET M=6 !行 LET N=M !列 PUBLIC NUMERIC P(0 TO 8,0 TO 8) !経路 p(y,x) MAT P=ZER(M+2,N+2) !-1:通路、0:壁（番兵） FOR y=1 TO M FOR x=1 TO N LET P(y,x)=-1 NEXT x NEXT y LET P(1,1)=0 !左上がスタート位置 MAT PRINT P; !debug PRINT 2*calc(1,2);"通り" !(1,1)→(1,2)　※左斜めの対角線で折り返すと対称になる PRINT "計算時間=";TIME-t0 END EXTERNAL FUNCTION calc(x,y) !漸化式として計算する IF x=N AND y=M THEN !ゴールなら LET calc=1 ELSEIF P(y,x)<0 THEN !通路なら LET P(y,x)=1 !仮に進む LET w=0 IF NOT(y=1 OR y=M) THEN LET w=w+calc(x-1,y) !左へ　※上壁沿いか下壁沿いなら、左側は袋小路なので進入禁止とする LET w=w+calc(x+1,y) !右へ IF NOT(x=1 OR x=N) THEN LET w=w+calc(x,y-1) !上へ　※左壁沿いか右壁沿いなら、上側は袋小路なので進入禁止とする LET w=w+calc(x,y+1) !下へ LET calc=w LET P(y,x)=-1 !元に戻す ELSE !通過していたら LET calc=0 END IF END FUNCTION

Re: おねえさんのコンピューター

投稿者：山中和義投稿日：2012年10月 7日(日)18時47分24秒

> No.1986[元記事へ] > 小さなサイズ（7×7程度）であれば「深さ優先検索（DFS）」というアルゴリズムで解けます。次のようなアルゴリズムでも算出可能なようです。 !0:右,1:上,2:左,3:下の進行方向、-1:通路を表すとする。 !N行N列の格子状の道は、N=7の場合、 !　-1 2 2 2 2 2 2 2 -1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　-1 2 2 2 2 2 2 2 -1 !と表される。 !左斜めの対角線での線対称を考慮して、左上（スタート位置）の進路方向を右と限定できる。 !そして、求める値は算出した結果を2倍すればよい。 !よって、 !　-1 2 2 2 2 2 2 2 -1 !　 1 0 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　-1 2 2 2 2 2 2 2 -1 !を初期値とする。 ! !●外壁との袋小路の判定 !たとえば、3行6列目で右端の壁に接した場合、 !　-1 2 2 2 2 2 2 2 -1 !　 1 0 3 -1 -1 -1 -1 -1 1 !　 1 -1 3 -1 -1 -1 -1 ? 1 !　 1 -1 0 0 0 0 0 * 1 !　 1 -1 -1 -1 -1 -1 -1 ? 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　-1 2 2 2 2 2 2 2 -1 !より、 !上側（2行6列目）は、右下（ゴール位置）への道順はないので進入禁止と判断するれば、 !その分だけ計算量は少なくなる。 ! !●自分が通った経路による袋小路の判定 !たとえば、3行2列目で接した場合、 !　-1 2 2 2 2 2 2 2 -1 !　 1 0 3 -1 -1 -1 -1 -1 1 !　 1 -1 0 0 0 0 0 3 1 !　 1 ? * ? -1 -1 -1 3 1 !　 1 -1 1 -1 -1 -1 -1 3 1 !　 1 -1 1 -1 -1 -1 -1 3 1 !　 1 -1 1 2 2 2 2 2 1 !　 1 -1 -1 -1 -1 -1 -1 -1 1 !　-1 2 2 2 2 2 2 2 -1 !より、 !右側（3行3列目）は、右下（ゴール位置）への道順はないので進入禁止と判断する。 ! !これらは、 !　進行方向に対して右または左隣接で、同じ方向の経路が並行するかどうか !で判定できる。 LET t0=TIME PUBLIC NUMERIC M,N LET M=6 !行 LET N=M !列 PUBLIC NUMERIC C !解の個数 LET C=0 PUBLIC NUMERIC P(0 TO 8,0 TO 8) !経路 p(y,x) MAT P=(-1)*CON(M+2,N+2) !通路とする FOR y=1 TO M !外の辺は壁（番兵）とする LET P(y,0)=1 LET P(y,N+1)=1 NEXT y FOR x=1 TO N LET P(0,x)=2 LET P(M+1,x)=2 NEXT x LET P(1,1)=0 !左上がスタート位置 MAT PRINT P; !debug CALL try(1,2) !(1,1)→(1,2)　※左斜めの対角線で折り返すと対称になる PRINT 2*C;"通り" PRINT "計算時間=";TIME-t0 END EXTERNAL SUB try(y,x) !バックトラック法で検索する IF x=N AND y=M THEN !ゴール（右下）なら LET C=C+1 !経路を表示する !!PRINT "No.";C !!MAT PRINT P; ELSE LET xx=x-1 !左へ IF P(y,xx)=-1 THEN !未踏なら IF NOT( P(y-1,x)=2 OR P(y+1,x)=2 ) THEN !※袋小路 LET P(y,x)=2 !仮に進む（進行方向） CALL try(y,xx) LET P(y,x)=-1 !戻す END IF END IF LET xx=x+1 !右へ IF P(y,xx)=-1 THEN IF NOT( P(y-1,x)=0 OR P(y+1,x)=0 ) THEN !※袋小路 LET P(y,x)=0 CALL try(y,xx) LET P(y,x)=-1 END IF END IF LET yy=y-1 !上へ IF P(yy,x)=-1 THEN IF NOT( P(y,x-1)=1 OR P(y,x+1)=1 ) THEN !※袋小路 LET P(y,x)=1 CALL try(yy,x) LET P(y,x)=-1 END IF END IF LET yy=y+1 !下へ IF P(yy,x)=-1 THEN IF NOT( P(y,x-1)=3 OR P(y,x+1)=3 ) THEN !※袋小路 LET P(y,x)=3 CALL try(yy,x) LET P(y,x)=-1 END IF END IF END IF END SUB

Re: おねえさんのコンピューター

投稿者：山中和義投稿日：2012年10月 9日(火)10時47分5秒

> No.1987[元記事へ] > 1×1、2×2、3×3とマスの数を増やしていくお姉さん。 > 5×5からはパソコンで計算し、 > 7×7からは処理が間に合わないとしてスーパーコンピュータが登場しました。 4×4マス（5×5ノード）の8512通りまでは、手計算で行っている。 DFSのような総当りなのだろうか。 3×3ノードの場合・─・─・ │　│　│ ・─・─・ │　│　│ ・─・─・次のように分割する。Ｓ─　・─・ │　　│　│ ・─　・─・ │　　│　│ ・─　・─Ｇ左斜めの対角線による線対称を考えて、左上（スタート位置）から右に進むとする。Ｓ─　・─・　　　│　│ ・─　・─・ │　　│　│ ・─　・─Ｇ左側は、次の2通り（連結部の個数が1つ,3つのもの）が考えられる。Ｓ─　●─・　　Ｓ─　●─・　　Ｓ─　●　・　　Ｓ─　●　・　　　　　│　　　　　　　│　　　　　│　　　　　　　│ ・　　・　・　　・　　・─・　　・　　・─・　　・　　・　・　　　　　│　　　　　│　　　　　　　　　│　　　　　│ ・　　・　Ｇ　　・　　・─Ｇ　　・　　・　Ｇ　　・　　・─Ｇこの場合の右側は、2^(3-1)=4通りＳ─　●─・　　Ｓ─　●　・　　　　　│　　　　　│ ・─　●─・　　・─　●　・ │　　　　　　　│ ・─　●─Ｇ　　・─　●─Ｇこの場合の右側は、2通りよって、4+2=6通りしたがって、6*2=12通り補足　連結部・個数について　左側から右側への移動の個数を「出」、右側から左側への移動の個数を「入」とすると、「出」=「入」+1 となり、個数は1,3,5,7,…である。・向きの「場合の数」個数が1の場合は、→●の1通り個数が3の場合は、3=2+1から、3!/(2!1!)=3通り　　←●　　→●　　→● 　　→●　　←●　　→● 　　　：　　　：　　　：　　→●　　→●　　←● である。 3×3の場合では、　Ｓ←● × 　　→● 　　　：　　→● 　　→● ────┐ 　　→● 袋小路　│ 　　　：　　　　│ 　　←● ────┘Ｇは、不適なので、　　→● 　　←● 　　　：　　→● のみとなる。（終り）補足　袋小路・外壁との袋小路 5×5の場合では、　Ｓ─・　・　・　・　　　│ 　・　・　・　・　× 　　　│　　　　　↑ 　・　・─・─・─● 　　　　　　　　　↓ 　・　・　・　・　○ 　　　　　　　　　│ 　・　・　・　・　Ｇなので、　Ｓ→・→・→・→・　↓　│　│　│　↓ 　・─・─・─・─・　↓　│　│　│　↓ 　・─・─・─・─・　↓　│　│　│　↓ 　・─・─・─・─・　↓　│　│　│　↓ 　・→・→・→・→Ｇのように、一方通行となる。・自分が通った経路による袋小路　Ｓ─・→・─・─・　　　　　　　　　│ 　○←●→×　・　・　│　│　　　　　│ 　・　・─・─・─・　│ 　・─・─・─・─Ｇこれは、　進行方向に対して右または左隣接で、同じ方向の経路が並行するかどうかで判定できる。（終り） 4×4ノードの場合・─・─・─・ │　│　│　│ ・─・─・─・ │　│　│　│ ・─・─・─・ │　│　│　│ ・─・─・─・次のように分割する。Ｓ─・─　・─・　　│　　│　│ ・─・─　・─・ │　│　　│　│ ・─・─　・─・ │　│　　│　│ ・─・─　・─ＧＳ→・→　・→・　　│　　│　↓ ・─・─　・─・ ↓　│　　│　↓ ・─・─　・─・ ↓　│　　│　↓ ・→・→　・→Ｇ連結部が1個の場合、位置はC(4,1)=4通り、向きは1通りＳ─・→　　　　●─・　　　　　　　　│　│ ・　・　　　　　・─・　　　　　　　　│　│ ・　・　　　　　・─・　　　　　　　　│　│ ・　・　　　　　・─Ｇ　　　　　　　　8通り 1×8=8通りＳ─・　　　　　・　・　　・─・　　・─・　　│　　　　　　　　　　│　│　　│　│ ・　・→　　　　●─・　　●　・　　●　・　　　　　　　　│　│　　　　│　　　　│ ・　・　　　　　・─・　　・　・　　・─・　　　　　　　　│　│　　　　│　　│ ・　・　　　　　・─Ｇ　　・　Ｇ　　・─Ｇ　　　　　　　　4通り　　└─ 2通り ─┘ 1×(4+2)=6通りＳ─・　　　Ｓ─・　　　Ｓ─・　　　　　・　・　　・　・　　・─・　　│　　　　　│　　　　　│　　　　　　　　　　　　　　　│　│ ・　・　　　・─・　　　・─・　　　　　・　・　　・─・　　・　・　　│　　　│　　　　　│　　　　　　　　　　　　│　│　　│　│ ・　・→　　・─・→　　・　・→　　　　●─・　　●　・　　●　・　　　　　　　　　　　　│　│　　　　　│　│　　　　│　　　　│ ・　・　　　・　・　　　・─・　　　　　・─Ｇ　　・　Ｇ　　・　Ｇ　　　　　　　　　　　　　　　　　　　　2通り　　└─ 2通り ─┘ 3×(2+2)=12通りＳ─・　　　Ｓ─・　　　Ｓ─・　　　Ｓ─・　　　　　・　・　　　・　・　　　・　・　　　・─・　　│　　　　　│　　　　　│　　　　　│　　　　　　　　　　　　　　　　　　　　　　　│　│ ・─・　　　・─・　　　・　・　　　・　・　　　　　・　・　　　・　・　　　・─・　　　・　・ │　　　　　│　　　　　　　│　　　　　│　　　　　　　　　　　　　　　　　│　│　　　│　│ ・　・　　　・─・　　　・─・　　　・　・　　　　　・　・　　　・─・　　　・　・　　　・　・ │　　　　　　　│　　　│　　　　　　　│　　　　　　　　　　　│　│　　　│　│　　　│　│ ・─・→　　・　・→　　・─・→　　・　・→　　　　●─Ｇ　　　●　Ｇ　　　●　Ｇ　　　●　Ｇ　　　　　　　　　　　　　　　　　　　　　　　　　　└─────── 4通り ────────┘ 4×4=16通り計42通り連結部が3個の場合、位置はC(4,3)=4通り、それぞれ向きは3!/(2!1!)=3通り（1通りのみが適となる）Ｓ─・→　　Ｓ─・→　　Ｓ─・→　　　　●─・　　　　　　　　　　　　　　　　　　　　│　│ ・　・←　　・─・←　　・─・←　　　　●─・　　│　　　│　　　　　│ ・　・→　　・─・→　　・　・→　　　　●─・　　　　　　　　　　　　│　│　　　　　│　│ ・　・　　　・　・　　　・─・　　　　　・─Ｇ　　　　　　　　　　　　　　　　　　　　2×2=4通り 3×4=12通りＳ─・→　　Ｓ─・→　　Ｓ─・→　　Ｓ─・→　　　　●─・　　●─・　　　　　　　　　　　　　　　　　　　　　　　　　　　　│　　　　│ ・　・←　　・　・←　　・─・←　　・─・←　　　　●─・　　●　・　　│　　　　　│　　　│　　　　　│　　　　　　　　　　　　│　│ ・　・　　　・─・　　　・─・　　　・　・　　　　　・─・　　・─・　　│　　　│　　　　　　　│　　　│　　　　　　　│　│ ・　・→　　・─・→　　・　・→　　・─・→　　　　●─Ｇ　　●─Ｇ　　　　　　　　　　　　　　　　　　　　　　　　　　4通り　　1通り 4×(4+1)=20通りＳ─・→　　Ｓ─・→　　Ｓ─・→　　　　●─・　　　　　　　　　　　　　　　　　　　　│　│ ・　・　　　・　・　　　・─・　　　　　・─・　　　　　　　　　　　　│　│　　　　　│　│ ・　・←　　・─・←　　・　・←　　　　●─・　　│　　　│　　　　　│ ・　・→　　・─・→　　・─・→　　　　●─Ｇ　　　　　　　　　　　　　　　　　　　　4通り 3×4=12通りＳ─・　　　Ｓ─・　　　　　・　・　　・─・　　│　　　　　│　　　　　　　　　　│　│ ・　・→　　・　・→　　　　●─・　　●　・　　　　　　　　　　　　　　│　│　　　　│ ・　・←　　・─・←　　　　●─・　　●─・　　│　　　│ ・　・→　　・─・→　　　　●─Ｇ　　●─Ｇ　　　　　　　　　　　　　　2通り　　1通り 2×(2+1)=6通り計50通りよって、42+50=92通りしたがって、92*2=184通り

Re: おねえさんのコンピューター

投稿者：山中和義投稿日：2012年10月12日(金)10時42分42秒

> No.1988[元記事へ] （続き） > 1×1、2×2、3×3とマスの数を増やしていくお姉さん。 > 5×5からはパソコンで計算し、 > 7×7からは処理が間に合わないとしてスーパーコンピュータが登場しました。以上のまとめとして、次のことが見えてくる。補足　経路の略図右向きの矢印（2個以上あるなら）に着目すると、・1つは左上（スタート位置）に繋がっている。・もう1つは右下（ゴール位置）に繋がっている。・残りは、中継である。となる。連結部が1つの場合、1通りＳ─ ⇒ ┐ 　　　 │ 　　　Ｇ連結部が3つの場合、2通りＳ┐┌ ⇒ ─┐ 　│└ ← ┐│ 　└─ → ┘ＧＳ─ → ┐ 　┌ ← ┘ 　└ ⇒ ─Ｇ（終り） 4×4ノードの場合実際の格子に割り当てる。Ｓ→・→　・→・　　│　　│　↓ ・─・─　・─・ ↓　│　　│　↓ ・─・─　・─・ ↓　│　　│　↓ ・→・→　・→Ｇ ■連結部が1つの場合Ｓ─ ⇒ ┐ 　　　 │ 　　　Ｇ行の位置は、C(4,1)=4通り　Ｓ→・⇒　●→・　　　Ｓ→・　　・→・　　　Ｓ→・　　・→・　　　Ｓ→・　　・→・　　　　　　│　↓　　　　　│　　│　↓　　　　　│　　│　↓　　　　　│　　│　↓ 　・　・　　・─・　　　・　・⇒　●─・　　　・─・　　・─・　　　・─・　　・─・　　　　　　│　↓　　　　　　　　│　↓　　　↓　│　　│　↓　　　↓　│　　│　↓ 　・　・　　・─・　　　・　・　　・─・　　　・─・⇒　●─・　　　・─・　　・─・　　　　　　│　↓　　　　　　　　│　↓　　　↓　│　　│　↓　　　↓　│　　│　↓ 　・　・　　・→Ｇ　　　・　・　　・→Ｇ　　　・→・　　・→Ｇ　　　・→・⇒　●→Ｇ　　1×2^3=8通り　　　1×(2^2+1*2^1)=6通り　3×(2^1+2*2^0)=12通り　2^2×(2^0+3*2^0)=16通り　計8+6+12+16=42通り ■連結部が3つの場合Ｓ┐┌ ⇒ ─┐ 　│└ ← ┐│ 　└─ → ┘Ｇ行の位置は、C(4,3)=4通り　Ｓ→・⇒　●→・　　　Ｓ→・⇒　●→・　　　Ｓ→・⇒　●→・　　　Ｓ→・　　・→・　　　│　　　　↓　　　　　│　　　　↓　　　　　│　　│　↓　　　　　│　　│　↓ 　・─・←　・　・　　　・─・←　・　・　　　・─・　　・─・　　　・─・⇒　●─・　↓　│　　│　↓　　　↓　│　　│　↓　　　↓　│　　　　↓　　　↓　│　　　　↓ 　・─・→　・　・　　　・─・　　・　・　　　・─・←　・　・　　　・─・←　・　・　↓　│　　　　↓　　　↓　│　　│　↓　　　↓　│　　│　↓　　　↓　│　　│　↓ 　・→・　　・　Ｇ　　　・→・→　・　Ｇ　　　・→・→　・　Ｇ　　　・→・→　・　Ｇ　　　　0通り　　　　　　　　0通り　　　　　　　　　0通り　　　　　　　　0通り　計0通り　※1,2行目で「スタート」が「ゴール」と繋がって、残り2本と結ぶことができない。Ｓ─ → ┐ 　┌ ← ┘ 　└ ⇒ ─Ｇ行の位置は、C(4,3)=4通り　Ｓ→・→　・→・　　　　Ｓ→・→　・→・　　Ｓ→・→　・→・　　　　Ｓ→・→　・→・　　　　Ｓ→・　　・→・　　　　　　│　↓　　　　　　　　　│　↓　　　　　　　　　↓　　　　　　　　　│　↓　　　　　　│　　│　↓ 　・─・←　・─・　　　　・─・←　・─・　　・─・←　・　・　　　　・─・　　・─・　　　　・　・→　・─・　↓　│　　　　　　　　　↓　│　　　　　　　↓　│　　│　↓　　　　↓　│　　│　↓　　　　　　　　　│　↓ 　・─・⇒　●─・　　　　・─・　　・─・　　・─・　　・─・　　　　・─・←　・─・　　　　・─・←　・─・　↓　│　　│　↓　　　　↓　│　　│　↓　　↓　│　　　　　　　　　↓　│　　　　　　　　　↓　│ 　・→・　　・→Ｇ　　　　・→・⇒　●→Ｇ　　・→・⇒　●→Ｇ　　　　・→・⇒　●→Ｇ　　　　・→・⇒　●→Ｇ　　3×2*2=12通り　　　　　2^2×2*2=16通り　　　2^2×1=4通り　　　　　3×2^2=12通り　　　　　　2×(2^1+1*2^0)=6通り　計12+(16+4)+12+6=50通りよって、42+50=92通りしたがって、92*2=184通り 5×5ノードの場合連結部が5つの場合、8通りＳ┐┌ ⇒ ─┐ 　│└ ← ┐│ 　│┌ → ┘│ 　│└ ← ┐│ 　└─ → ┘ＧＳ┐┌─ ⇒ ──┐ 　││┌ ← ─┐│ 　││└ → ┐││ 　│└─ ← ┘││ 　└── → ─┘ＧＳ┐┌ ⇒ ──┐ 　│└ ← ─┐│ 　└─ → ┐││ 　　┌ ← ┘││ 　　└ → ─┘ＧＳ── → ┐ 　┌─ ← ┘ 　│┌ ⇒ ─┐ 　│└ ← ┐│ 　└─ → ┘ＧＳ┐┌─ → ┐ 　││┌ ← ┘ 　││└ ⇒ ─┐ 　│└─ ← ┐│ 　└── → ┘ＧＳ─ → ┐ 　┌ ← ┘ 　└ → ┐ 　┌ ← ┘ 　└ ⇒ ─ＧＳ── → ─┐ 　┌─ ← ┐│ 　│┌ → ┘│ 　│└ ← ─┘ 　└─ ⇒ ─ＧＳ┐┌ → ─┐ 　│└ ← ┐│ 　└─ → ┘│ 　　┌ ← ─┘ 　　└ ⇒ ─Ｇを併せて考えれば求まるだろう。

畳の敷き方

投稿者：山中和義投稿日：2012年10月14日(日)21時40分32秒

> No.1985[元記事へ] > 『フカシギの数え方』おねえさんといっしょ！みんなで数えてみよう！ 6畳の敷き方に違和感が、、、　フカシギ !畳の敷き方 !例 !1畳（2×1） !┌┐ !││ !└┘ !3畳（2×3） !┌┬┬┐　┌┬─┐　┌─┬┐ !││││　│├─┤　├─┤│ !└┴┴┘　└┴─┘　└─┴┘ !3通り !参考サイト !　　図形問題　シリーズ ! !　畳の敷き方数 !　http://www.geocities.jp/ikuro_kotaro/koramu/603_t2.htm !　http://www.geocities.jp/ikuro_kotaro/koramu/2185_s4.htm !　コマ大数学科120講：畳 PUBLIC NUMERIC M,N LET M=4 !行　※偶数 LET N=3 !列 DIM P(0 TO M+1,0 TO N+1) FOR i=0 TO M+1 !0,m+1は壁（番兵） FOR J=0 TO N+1 !0,n+1は壁（番兵） LET P(i,J)=0 !0:置けない NEXT J NEXT i FOR i=1 TO M FOR J=1 TO N LET P(i,J)=-1 !-1:置ける NEXT J NEXT i MAT PRINT P; !debug PUBLIC NUMERIC DX(0 TO 1),DY(0 TO 1) !配置方向 DATA 0,1 !縦、横 DATA 1,0 MAT READ DX MAT READ DY PUBLIC NUMERIC C !解の個数 LET C=0 CALL try(1,M*N,1,1,p) !左上から順に PRINT C;"通り" !検算 LET S=1 !2^(m*n/2)Π[i=1,m]Π[j=1,n]{cos(i*π/(m+1))^2+cos(j*π/(n+1))^2}^1/4 FOR i=1 TO M FOR J=1 TO N LET S=S*SQR(SQR(COS(i*PI/(M+1))^2+COS(J*PI/(N+1))^2)) NEXT J NEXT i PRINT 2^(M*N/2)*S END EXTERNAL SUB try(D,Q,X,Y,P(,)) !バックトラック法で検索する FOR K=0 TO 1 !各方向 IF P(Y,X)=-1 AND P(Y+DY(K),X+DX(K))=-1 THEN !y行x列目（左上が基準）に置けるなら LET P(Y,X)=D !d番目を仮に敷いてみる LET P(Y+DY(K),X+DX(K))=D LET W=Q-2 !残りの枚数 IF W=0 THEN !すべて敷き詰められたなら LET C=C+1 !!PRINT "No.";C !結果を表示する !!MAT PRINT P; ELSE FOR i=Y TO M !空き位置を見つける FOR J=1 TO N IF P(i,J)=-1 THEN EXIT FOR !i行J列目 NEXT J IF J<=N THEN EXIT FOR NEXT i IF i<=M THEN CALL try(D+1,W,J,i,P) !次へ END IF LET P(Y,X)=-1 !元に戻す LET P(Y+DY(K),X+DX(K))=-1 END IF NEXT K END SUB

戻る

十進BASIC 第2掲示板 過去ログ

おねえさんのコンピューター

Re: おねえさんのコンピューター

Re: おねえさんのコンピューター

Re: おねえさんのコンピューター

Re: おねえさんのコンピューター

畳の敷き方

十進BASIC 第2掲示板過去ログ