※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

只今解説準備中

Problem 162 「16進数」 †


問題

16進法では, 数は以下の16個の数字によって表される
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

16進数の AF は, 10進法での 10x16 + 15 = 175 と等しい.
3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A の全てが現れている.
10進数で書くときと同様に, 先頭の0は書かないことにする.

0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか?
16進数で答えよ.
(A,B,C,D,E,F は大文字とし, 先頭や末尾の16進数であることを表す記号や先頭の0は許されない. つまり, 1A3F ならOK. 1a3f, 0x1a3f, $1A3F, #1A3F, 0000001A3Fは許されない. )



解法
一桁ずつ伸ばしながら組み合わせ数を計算していきます。
n桁目で重要となるのはn桁目までに。
0が0回でたか1回以上出たかの2通り
1が0回でたか1回以上でたかの2通り
Aが0回でたか1回以上でたかの2通り
の2*2*2の全8通りで管理すればよいと分かります。

memo[16][2][2][2]=memo[n桁目][n桁目までに0が出た回数0回か1回以上][n桁目までに1が出た回数0回か1回以上][n桁目までにAが出た回数0回か1回以上か]
で組み合わせ数を管理して漸化式を立てれば完了です。

漸化式は私の場合Prologで半自動生成しましたが。
式にするとかなりめんどくさいことになります。
ループやコードなどを使って半自動化することをお勧めします。


それでも参考になると思いますので漸化式を全部書いてみましょう。


漸化式

memoの値は最初すべて0設定
memo[1][0][1][0]=1
memo[1][0][0][1]=1
memo[1][0][0][0]=13
と設定してから計算開始。

memo[n+1][0][0][0]=memo[n][0][0][0]*13
memo[n+1][1][0][0]=memo[n][1][0][0]*14+memo[n][0][0][0]
memo[n+1][0][1][0]=memo[n][0][1][0]*14+memo[n][0][0][0]
memo[n+1][0][0][1]=memo[n][0][0][1]*14+memo[n][0][0][0]

memo[n+1][0][1][1]=memo[n][0][1][1]*15+memo[n][0][0][1]+memo[n][0][1][0]
memo[n+1][1][0][1]=memo[n][1][0][1]*15+memo[n][1][0][0]+memo[n][0][0][1]
memo[n+1][1][1][0]=memo[n][1][1][0]*15+memo[n][1][0][0]+memo[n][0][1][0]

memo[n+1][1][1][1]=memo[n][1][1][1]*16+memo[n][1][0][1]+memo[n][1][1][0]+memo[n][0][1][1]


最後に
memo[16][1][1][1]を答えとすればよい。


書いてみましたがなんだかめんどくさくてきちんと漸化式が立っているか自信がありません。
簡単な問題ですし好みの方法で頑張ってください。