数字1,2,3,4の並び

 投稿者：山中和義  投稿日：2016年 4月 9日(土)19時34分51秒
  問題
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)の値を出力するプログラムを書いてください。

考察
(x+x^2+x^3+x^4)^n を展開したときの、x^(9*k)（kは正整数）の係数をすべて足し合わせたもの
（終わり）


LET N=20
LET F=0
FOR A=0 TO N !1の個数
   FOR B=0 TO N-A !2の個数
      FOR C=0 TO N-(A+B) !3の個数
         LET D=N-(A+B+C) !4の個数
         IF D>=0 THEN
            IF MOD(A+2*B+3*C+4*D,9)=0 THEN !9の倍数なら
               LET F=F+FACT(N)/FACT(A)/FACT(B)/FACT(C)/FACT(D) !同じものを含む順列
            END IF
         END IF
      NEXT C
   NEXT B
NEXT A
PRINT F !f(n)
END


 		 

Re: 数字1,2,3,4の並び

 投稿者：山中和義  投稿日：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

 		 

Re: 数字1,2,3,4の並び

 投稿者：山中和義  投稿日：2016年 4月10日(日)13時28分2秒
  > No.4034[元記事へ]

> 問題
> 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)とする。

動的計画法による
（終わり）


LET N=20

DIM G(0 TO 8)
DATA 1,0,0,0,0,0,0,0,0 !G(0,r)
MAT READ G

DIM B(0 TO 8)
FOR K=1 TO N
   MAT B=ZER !G(k,r)

   FOR i=1 TO 4
      FOR J=0 TO 8 !Gを右へローテイトさせて加算する
         LET M=i+J
         IF M>8 THEN LET M=M-9
         LET B(M)=B(M)+G(J)
      NEXT J
   NEXT i
   MAT PRINT B; !debug

   MAT G=B
NEXT K
MAT PRINT G; !G(0)
END


実行結果

0  1  1  1  1  0  0  0  0

0  0  1  2  3  4  3  2  1

10  6  3  2  3  6  10  12  12

40  44  40  31  21  14  14  21  31

80  106  136  155  155  136  106  80  70

392  336  336  392  477  552  582  552  477

2163  2003  1757  1541  1456  1541  1757  2003  2163

7464  8086  8332  8086  7464  6757  6295  6295  6757

26104  26811  28602  30639  31968  31968  30639  28602  26811

118020  112156  108328  108328  112156  118020  123177  125214  123177

489588  489588  478567  461681  446832  440968  446832  461681  478567

1828048  1876668  1919424  1936310  1919424  1876668  1828048  1796313  1796313

7297342  7248722  7297342  7420453  7560450  7651826  7651826  7560450  7420453

30284555  29930071  29526967  29263859  29263859  29526967  29930071  30284555  30424552

120166145  120923733  120923733  120166145  119005452  117984756  117581652  117984756  119005452

472556616  474738005  478080086  481019063  482179756  481019063  478080086  474738005  472556616

1906393770  1897931323  1894589242  1897931323  1906393770  1916016910  1922297968  1922297968  1916016910

7676629756  7667006616  7642639971  7614931245  7596845658  7596845658  7614931245  7642639971  7667006616

30521423490  30601207588  30653282959  30653282959  30601207588  30521423490  30451262532  30423553806  30451262532

121847502360  121847502360  121997447416  122227176569  122429196996  122508981094  122429196996  122227176569  121997447416

121847502360  121847502360  121997447416  122227176569  122429196996  122508981094  122429196996  122227176569  121997447416





 		 

Re: 数字1,2,3,4の並び

 投稿者：山中和義  投稿日：2016年 4月11日(月)20時12分42秒
  > No.4035[元記事へ]

> 問題
> 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)とする。


再帰＋メモ化で高速化


DECLARE EXTERNAL FUNCTION G.G
PRINT G(20,0)
END
MODULE G
SHARE NUMERIC mem(0 TO 50, 0 TO 8) !g(n,r)
MAT mem=(-1)*CON !メモ化
PUBLIC FUNCTION G
EXTERNAL FUNCTION G(n,r)
   LET T=mem(n,r)
   IF T<0 THEN !まだ計算していない
      IF n=0 THEN !g(0,r)
         LET T=0
         IF r=0 THEN LET T=1
      ELSE
         IF r=0 THEN !漸化式による
            LET T=G(n-1,8)+G(n-1,7)+G(n-1,6)+G(n-1,5) !g(n,0)
         ELSEIF r=1 THEN
            LET T=G(n-1,0)+G(n-1,8)+G(n-1,7)+G(n-1,6) !g(n,1)
         ELSEIF r=2 THEN
            LET T=G(n-1,1)+G(n-1,0)+G(n-1,8)+G(n-1,7)
         ELSEIF r=3 THEN
            LET T=G(n-1,2)+G(n-1,1)+G(n-1,0)+G(n-1,8)
         ELSEIF r=4 THEN
            LET T=G(n-1,3)+G(n-1,2)+G(n-1,1)+G(n-1,0)
         ELSEIF r=5 THEN
            LET T=G(n-1,4)+G(n-1,3)+G(n-1,2)+G(n-1,1)
         ELSEIF r=6 THEN
            LET T=G(n-1,5)+G(n-1,4)+G(n-1,3)+G(n-1,2)
         ELSEIF r=7 THEN
            LET T=G(n-1,6)+G(n-1,5)+G(n-1,4)+G(n-1,3)
         ELSEIF r=8 THEN
            LET T=G(n-1,7)+G(n-1,6)+G(n-1,5)+G(n-1,4)
         END IF
      END IF
      LET mem(n,r)=T !再計算を避けるためにメモしておく
   END IF
   LET G=T
END FUNCTION
END MODULE

 		 

戻る