プログラマーへの道

プログラミング初心者の備忘録

忌み数を取り除くアルゴリズム

忌み数とは死を連想させる4とか13日の金曜日で有名な13などです。病院ではこういう忌み数の部屋番号は不吉ということで取り除かれていることが多いです。

 

今回はそんな忌み数を取り除いたら部屋番号は何番になるかというアルゴリズムについて考えていきます。1番目は1、2番目は2、3番目は3、だけど4番目の部屋の部屋番号は5になりますね。じゃあｎ番目の部屋の部屋番号は何番になるかは気になります。ではc++で解いてみましょう。

 

入力をn番目の部屋のnとし、出力をその部屋の部屋番号とします。1 <= n <= 1,000,000,000 （十億）とします。ここでは意味数は4と6にします。

 

これを直接解く解き方は、入力の整数をstringに変換してその中に4か6が含まれていたら入力した整数に1を足していくというものです。しかしこれでは入力が10億ともなると計算量が膨大で時間がかかってしまいます。

 

なので、ここでは8進数の考え方を導入します。

ところで10進数の数を8進数の数に変える時、たとえば100を8進数に変える時どうするかというと、

100 == 1 × 8^2 + 4 × 8^1 + 4 × 8^0　== 144(8)

としますよね。これと同じ考え方で今回の問も解くことができます。

 

つまり1~nの整数の内4と6が含まれている整数があれば飛ばすということなので、各桁の数は0, 1, 2, 3, 5, 7, 8, 9の8つしか存在しないことになります。8進数の場合各桁の数は0, 1, 2, 3, 4, 5, 6, 7なのでこれを上の数に対応させていきます。

つまり、

100 == 1 × 8^2 + 5 × 8^1 + 5 × 8^0  == 155

となります。

 

この考えで解くと入力が10億でもかなりすっきり解くことができます。

 

ぜひ参考にしてください。