足す、掛ける、括弧と30個の1があれば任意の4桁の数を作ることができる

眠くてたまらないのに思いついてしまったので実装。むう。 まずは問題を説明しよう。足す掛ける括弧となるべく合計の少ない数を組み合わせた式で与えられた数を表現するにはどうしたらいいか？ たとえば5は「5」と書くしかない(どうあがいても減らない)が、 6なら「2 * 3」と書けば数の合計は5だから「6」と書くより少ない。 17なら「3 * 3 + 4 * 2」と書けば合計は12。

で、20分ほどで合計が最小になる式を導くプログラムが書けたので、いろいろ見てたのだけど9999までで一番合計の大きくなるのは6299の時で、合計は30。9999までは30より小さい合計で数を作ることが出来る。

しかも7以上の素数は全部、それ自身を書くよりも小さい表記が存在することが気づいてみればごく簡単に証明できるので、実は最終的には1〜5しか使わない。

さらにたとえば5を(1+1+1+1+1)で置き換えても問題はそのまま成立するので「なるべく少ない個数の1と、足し算、掛け算、括弧を用いて与えられた数を表現せよ」となるわけだ。で、この問題は4桁までの数ならば30個以下で表現できる、と。

ちなみに以下はNと「表現するのにN個の1が必要な最小の数」のリスト。

1 1
2 2
3 3
4 4
5 5
6 7
7 10
8 11
9 17
10 22
11 23
12 41
13 47
14 59
15 89
16 107
17 167
18 179
19 263
20 347
21 467
22 683
23 719
24 1223
25 1438
26 1439
27 2879
28 3767
29 4283
30 6299

ちなみにこの中からいくつか問題をピックアップすると、初級：22を10個で、中級：347を20個で、上級1439を26個で、といったところかな。コードが20分で書けるんだから、論理的に考えられて適当な紙を記憶領域に使えばそんなに難しくはないんだけども、紙なしでは僕もちょっと自信がないなぁｗ

メモ。亜種：「使う数字の合計」に変える。つまり111は1+1+1なので3。22は11 * (1 + 1)だから4。

使いまわせば一瞬だと気づいたので5分で実装。うーん、こっちはいまいち面白くないかも。いや、小さい数の難易度は下がったので面白くないと思ったけど、大きい数の難易度は上がったかもしれない。普通の人間にとって31での割り算を暗算でやるのは難易度が高い、という意味で。9999まででもっとも合計が多くなるのは2995の時で、13。答えは→((21 * 4 + 11) * 21 + 1000)←。いやいや、これは自信を持って「僕には無理だ」と言えるｗ　何度か挑戦するとわかるようになるのか？僕には初手からかなりの難関だと思えるのだけど。あー、まぁもっと簡単なほうから徐々に解いていかないからどこから手をつけたらいいのかがわからないのか。数Iをやる前に流体力学の本を読んでみたようなものかｗ

Powered by COREBlog

Contact me: coreblog"at mark"nishiohirokazu.org
Access counter: This Page:713086 Total:1827798 during 2004/01/23-2006/03/26