|
|
> No.1008[元記事へ]
GAIさんへのお返事です。
> 例の 24!＝620448401733239439360000 という天文学的調査が必要になるんでしょうか？
並びが大きい順から考えると、最初は、24,23,22,21,…,3,2,1 となる。
左上から順に文書を読むように右へ、24,23,22 と置けるが、21を１行80桁目に置けない。
したがって、ここでこの手は終了して、次の24,23,22,21,…,3,1,2 となる。
ここで、同様に21は置けない。
これは、24,23,22,21,20,19,18,…,2,1 から 24,23,22,21,1,2,3,…,19,20 までが置けないことを意味する。
したがって、24,23,22,21,… （20!通り）は検証を省くことができる。（枝刈り）
このような処理をバックトラック法に組込んでいるので、場合の数はベタな値ではありません。
でもスキップされた結果が、まだ天文学的な数値ならお手上げです。
サンプルプログラム No.1001 [元記事へ] 先頭部分を次のように変更する。
（これ以前は略）
PUBLIC NUMERIC a,b !長方形の縦、横の長さ
LET a=70
LET b=70
PUBLIC NUMERIC M !相異なる大きさの正方形
LET M=24
DIM S(M) !未使用の個数
MAT S=CON !すべて１個ずつ
（以下同じ）
逆の問題
いくつかの長方形（正方形も含む）を並べる。それを囲む最小（面積）の長方形（正方形も含む）は？
+--------+
| ┌─┐|
|┌┤ │|
|├┴─┤|
|│ │|
|│ │|
|└──┘|
+--------+
補足
1^3+2^3+3^3+ … +n^3=1*1^2+2*2^2+3*3^2+ … +n*n^2=(n*(n+1)/2)^2 の場合
（これ以前は略）
PUBLIC NUMERIC a,b !長方形の縦、横の長さ
LET N=12 !←←←←←
LET a=N*(N+1)/2
LET b=a
PUBLIC NUMERIC M !相異なる大きさの正方形
LET M=N
DIM S(M) !未使用の個数
FOR i=1 TO M
LET S(i)=i
NEXT i
（以下同じ）
何年か後に求まります。（笑い）
|
|