|
|
問題
自然数を直線状に並べます。
その状態で、連続して並んだいくつかの自然数の合計をとります。
合計をとる自然数はいくつ選んでもかまいません。
1つだけでも、全部でもかまいません。
ただし、続いて並んでいなければならず、飛び飛びに合計することはできません。
(1) 5個の自然数をうまく選んで並べると、1から13までの合計をつくることができます。
(2) 6個の自然数をうまく選んで並べると、1から17までの合計をつくることができます。
(3) 7個の自然数をうまく選んで並べると、1から23までの合計をつくることができます。
例
1個の場合
1 として、1
2個の場合
1,2 として、3
3個の場合
1,3,2 として、6
4個の場合
1,1,4,3 として、9
1,3,3,2 として、9
http://math.a.la9.jp/jyougi.htm
考察
p進法を利用した数字の並び
① ※丸数字がk個並ぶ 1からkまで 通常の目盛り
1② 2k+1
11③ 3k+2
111④ 4k+3
1111⑤ 5k+4
：
さらに、
②1 2k+1
1③2 3k+3
11④3 4k+5
111⑤4 5k+7
1111⑥5 6k+9
：
と展開できる。これは、いわゆる近似解である。
（終り）
数字の並びの組み合わせは、次の問題と同値なので、それを元に作成する。
問題：n個の球をm個の箱に分ける方法 (5)
LET N=13
LET M=5
DIM B(M) !各箱の中の球の個数
MAT B=CON
PUBLIC NUMERIC C !場合の数
LET C=0
CALL try(2,N-M, N,M,B) !※1の位置を固定する
PRINT C;"通り"
END
EXTERNAL SUB try(P,T, N,M,B())
IF P=M THEN !R番目なら
LET B(P)=B(P)+T !set it
FOR i=1 TO INT(M/2) !対称性（直線状）
IF B(i)<>B(M-i+1) THEN EXIT FOR
NEXT i
IF B(i)<B(M-i+1) OR i>INT(M/2) THEN
DIM F(N) !1～nの数字
MAT F=ZER
FOR i=1 TO M !i番目から
FOR K=0 TO M-i !続くk個の数字
LET S=0
FOR X=0 TO K !その和
LET S=S+B(i+X)
NEXT X
LET F(S)=1
NEXT K
NEXT i
FOR i=1 TO N !すべて表されるかどうか確認する
IF F(i)=0 THEN EXIT FOR
NEXT i
IF i>N THEN
LET C=C+1 !結果を表示する
MAT PRINT B;
END IF
END IF
LET B(P)=B(P)-T !restore it
ELSE
FOR i=0 TO T !p番目
LET B(P)=B(P)+i !set it
CALL try(P+1,T-i, N,M,B)
LET B(P)=B(P)-i !restore it
NEXT i
END IF
END SUB
実行結果 (1)
1 1 4 4 3
1 3 1 6 2
1 5 3 2 2
3 通り
|
|