|
投稿者：山中和義
投稿日：2016年 4月10日(日)08時35分47秒
|
|
|
|
> No.4033[元記事へ]
> 問題
> 1から4の数字を使って n桁の整数を作ります。このとき、9の倍数となるものを考えましょう。
> 例えば n=3であれば、234、333、441、などが9の倍数です。必ずしも1から4の全ての数字を使う必要はありません。
> 1から4の数字を使って作るn桁の整数のうち、9の倍数となるものの個数をF(n)と定義します。
> 例えば、F(1)=F(2)=0、F(3)=10、F(4)=40 となることが確かめられます。
> 自然数n（1≦n≦20）が与えられます。
> F(n)の値を出力するプログラムを書いてください。
考察
1から4の数字を使って作るn桁の整数のうち、9で割った余りがrとなるものの個数をG(n,r)とする。
次の漸化式が成り立つ。 G(n,0)=G(n-1,8)+G(n-1,7)+G(n-1,6)+G(n-1,5)
同様に、G(n,1), G(n,2), …, G(n,8)を求める。
（終わり）
LET N=20
DIM A(9,9),B(9,9),M(9,9)
DATA 0,0,0,0,0,1,1,1,1 !G(n,0)
DATA 1,0,0,0,0,0,1,1,1 !G(n,1)
DATA 1,1,0,0,0,0,0,1,1 !G(n,2)
DATA 1,1,1,0,0,0,0,0,1 ! :
DATA 1,1,1,1,0,0,0,0,0
DATA 0,1,1,1,1,0,0,0,0
DATA 0,0,1,1,1,1,0,0,0
DATA 0,0,0,1,1,1,1,0,0
DATA 0,0,0,0,1,1,1,1,0
MAT READ A
MAT M=IDN !A^n
MAT B=A
DO UNTIL N=0 !2進法による
IF MOD(N,2)=1 THEN MAT M=M*B
MAT B=B*B
LET N=INT(N/2)
LOOP
MAT PRINT M;
END
|
|
|