0〜1000に含まれる0をカウントする

quiz .groovy

0〜1000に含まれる0をカウントする

という問題。
参考

他にもいろいろな言語で解かれているみたいだ。


Groovy は String#count メソッドがあるのでそれで数えることができる(Ruby 由来？)。

groovy:000> (0..1000).join().count('0')
===> 193


高校数学を復習中(勉強中?)なのでこの問題を

0〜10のn乗に含まれる0をカウントする

と変更してみた。

groovy:000> f = { n -> (0..10**n).join().count('0') }
===> groovysh_evaluate$_run_closure1@4aee260b
groovy:000> f(3)
===> 193
groovy:000> f(4)
===> 2894
groovy:000> f(5)
===> 38895
groovy:000> f(6)
===> 488896
groovy:000> f(7)
===> 5888897
groovy:000> f(8)
ERROR java.lang.OutOfMemoryError:

f(10) を求められるようにしたい。


まずは観察から。
1000 までの 193 個というのは半端な数字なので 3 桁の 999 までに 190 個あると考え方がよさそうだ。
同じように 99 までを調べる

groovy:000> (0..99).join().count('0')
===> 10

100 から 199 までは

groovy:000> (100..199).join().count('0')
===> 20

どうやら桁が変わるまでとその後で同じ幅でも 0 の数が変わっている。


他も調べる。

groovy:000> (0..9).join().count('0')
===> 1
groovy:000> (10..19).join().count('0')
===> 1
groovy:000> (1000..1999).join().count('0')
===> 300
groovy:000> (10000..19999).join().count('0')
===> 4000

1桁だけ1固定で他は (n-1)*10^(n-2) のようだ。


再帰を使って n 桁以下のすべての数に含まれる 0 の数の関数が書ける。

groovy:000> g = { n -> n < 2 ? 1 : g(n-1) + 9*(n-1)*10G**(n-2) }
===> groovysh_evaluate$_run_closure1@7591777e
groovy:000> g(3)
===> 190


でも求めたいのは 10 の n 乗までなので

groovy:000> f = { n -> g(n) + n }
===> groovysh_evaluate$_run_closure1@75fc25e5
groovy:000> f(3)
===> 193
groovy:000> f(4)
===> 2894
groovy:000> f(5)
===> 38895
groovy:000> f(10)
===> 8888888900


これでもいいのだが一般項を求めれば n 加えるだけなので 1 つのメソッドにできる。
漸化式から求めるのだがそこは Wolfram|Alpha: Computational Intelligence に解決していただく。

a(n)=a(n-1)+9*(n-1)*10^(n-2),a(1)=1

と入力すれば一般項を計算してくれるのでそのまま Groovy に書き換えて

f = { n -> 10G**(n-1)*n - 10G**n/9 + 10/9 + n }
groovy:000> f = { n -> 10G**(n-1)*n - 10G**n/9 + 10/9 + n }
===> groovysh_evaluate$_run_closure1@7bf52460
groovy:000> f(3)
===> 193.0000000000


10**n-10 は 9 で割り切れるので

groovy:000> f = { n -> 10G**(n-1)*n - (10G**n-10).intdiv(9) + n }
===> groovysh_evaluate$_run_closure1@45b3278a
groovy:000> f(3)
===> 193
groovy:000> f(4)
===> 2894
groovy:000> f(5)
===> 38895
groovy:000> f(10)
===> 8888888900

完成。