特急すぺーしあ

数学が好きです。記載内容に間違い等がありましたらTwitter、コメント欄のどちらでも構いませんのでご連絡いただければ幸いです。

[tex:1 + 1 = 2]

増えていくパンダ

昨日こんな問題を人に出した。

1日目にパンダは1匹います。

2日目にパンダは前日の2倍に繁殖します。

3日目にパンダは前日の2倍に繁殖します。

...

さて、16日目にパンダは何匹いるでしょう?

 

何のことはない。n日目のパンダの数は2^{n-1}匹である。

答え合わせの雑談の中でこんな問題を思いついた。

 

最初に2のみが使える状態でスタートし、もっとも少ない乗算回数で2^nを求める。

具体例を挙げると、n = 15のときは、

2 * 2 = 2^2

2 * 2^2 = 2^3

2^2 * 2^2 = 2^4

2^4 * 2^4 = 2^8

2^4 * 2^8 = 2^{12}

2^3 * 2^{12} = 2^{15}

6回の操作で2^{15}を作れる。ちなみにこれは最小回数ではない!作った数がさらに利用できるようになる、といった具合だ。すぐに思い出したのだがProject Eulerに似たような問題があった。

projecteuler.net

この問題を考えながら昨日は眠りについた。朝起きて「おっしゃプログラミングで解いたろ」という気持ちになったので解いてみた。結果、1時間をかからないくらいで答えにたどり着いた。本当は一般のnについて最小回数が分かれば良いのだが、現状はそのような方法は見つけられていない。何か分かった人は教えていただけるとありがたい。

メモがてら考え方を書き残そう。

 

Problem122

2^nならば直感的にlog_{2}n回くらいで作れそうなことが分かる。となれば乗算回数自体はさして多くないので、何のひねりもない幅優先探索で事足りた。ただし途中、

・最小回数である数を作れたか

・探索済みの数列でないか

という観点で枝刈りをしている。Javaで3秒程度なので及第点と言えるのではないだろうか。

Congratulation!

 

余談

数学を中断する直前にこの記事を読んでいたのを思い出した。

integers.hatenablog.com

やる。

 

追記

少しググったところより良い解法を見つけた。その気になったら調べてみたい。

 

さらに追記

前項の追記により良い方法を見つけたと書いたが、それはあくまでヒューリスティックな解法らしい(下記参照)。詳しくはTACOP2巻とのこと・・・。私の解法は案外イケてたのではないだろうか。Project Eulerのフォーラムを見たり、もっと調べたらより良い方法が見つかるかもしれないが、今はやめておこう。いつか積読のTACOP3巻読みたいなぁ。

Evaluation of Powerscomeoncodeon.wordpress.com