|
|
問題
1～9の数字をいくつか足して、和が9の倍数となるような場合の数を求めたい。
ただし、足す順番は無視するものとする。
(1) 1～9の数字を最大1回だけ使えるときは何通りあるか。
答え
●「払える金額の問題」として数え上げる
その１ 組合せ
LET S=0
FOR C1=0 TO 1 !数字1を0,1個
FOR C2=0 TO 1
FOR C3=0 TO 1
FOR C4=0 TO 1
FOR C5=0 TO 1
FOR C6=0 TO 1
FOR C7=0 TO 1
FOR C8=0 TO 1
FOR C9=0 TO 1
IF MOD(C1*1+C2*2+C3*3+C4*4+C5*5+C6*6+C7*7+C8*8+C9*9,9)=0 THEN LET S=S+1
NEXT C9
NEXT C8
NEXT C7
NEXT C6
NEXT C5
NEXT C4
NEXT C3
NEXT C2
NEXT C1
PRINT S; "通り"
END
その２ 動的計画法
DATA 9 !種類
DATA 1,2,3,4,5,6,7,8,9 !硬貨
DATA 1,1,1,1,1,1,1,1,1 !枚数
READ N
DIM A(N),B(N)
MAT READ A
MAT READ B
LET T=0
FOR K=1 TO N
LET T=T+A(K)*B(K)
NEXT K
PRINT "総額="; T; "円"
DIM F(0 TO T)
MAT F=ZER
LET F(0)=1 !0円
FOR K=1 TO N
FOR i=T TO 0 STEP -1 !今までに支払える金額に対して
LET Fi=F(i)
IF Fi>0 THEN
LET W=i
FOR C=1 TO B(K) !新しい硬貨を追加する
LET W=W+A(K)
LET F(W)=F(W)+Fi
NEXT C
END IF
NEXT i
NEXT K
MAT PRINT F;
LET S=0
FOR i=0 TO T
IF MOD(i,9)=0 THEN LET S=S+F(i)
NEXT i
PRINT S; "通り"
END
●m進法n桁に対応させて数え上げる
個数がすべて同じなので、「m^n通り」に対応させられる。
LET S=0
FOR i=0 TO 2^9-1 !場合の数の候補
LET T=i
LET W=0
FOR X=1 TO 9 !2進法9桁
LET W=W+MOD(T,2)*X
LET T=INT(T/2)
NEXT X
IF MOD(W,9)=0 THEN LET S=S+1
NEXT i
PRINT S; "通り"
END
●対称性を利用して数え上げる
1+2+3+4+5+6+7+8=36より、数字9の有無で2つに分けられ、それぞれの場合の数は同じである。
よって、1から8までの数字で考える。
・数字を0個使う場合
0
1通り
・数字を1個使う場合
0通り
・数字を2個使う場合
最小値1+2=3＞0、最大値7+8=15＜18なので、倍数は9
1+8、2+7、3+6、4+5
4通り
・数字を3個使う場合
最小値1+2+3=6＞0、最大値6+7+8=21＜27なので、倍数は9,18
1+2+6、1+3+5、2+3+4
3+7+8、4+6+8、5+6+7
6通り
・数字を4個使う場合
最小値1+2+3+4=10＞9、最大値5+6+7+8=26＜27なので、倍数は18
1+2+7+8、1+3+6+8、1+4+5+8、1+4+6+7、
2+3+5+8、2+3+6+7、2+4+5+7、3+4+5+6
8通り
8個の数字からk個選んで9の倍数をつくれる個数をN(k)とすると、N(k)=N(8-k)から、
5,6,7,8個は、6,4,0,1個となる。
これより、1+0+4+6+8+6+4+0+1=30通り
したがって、2*30=60通り
LET n=8 !1から8までの数字
DIM a(n)
MAT a=ZER
PUBLIC NUMERIC S
FOR r=0 TO n !r個を選ぶ
LET S=0
CALL comb(a,1,r)
PRINT S; "通り"
NEXT r
END
EXTERNAL SUB comb(a(),k,r) !1～nの集合からr個を選ぶ組合せを生成する
IF r=0 THEN
LET w=0
FOR i=1 TO UBOUND(a)
LET w=w+a(i)*i
NEXT i
IF MOD(w,9)=0 THEN LET S=S+1
ELSE
FOR i=k TO UBOUND(a)-r+1 !k以降の数からr個を選択する
LET a(i)=1
CALL comb(a,i+1,r-1)
LET a(i)=0
NEXT i
END IF
END SUB
|
|