「2^a を与えられたときに a を求める(ただし 1≦ a ≦9)」記事へのコメント

別解

[t-nissie (8647)]

if (x.eq.1) return 0
if (x.eq.2) return 1
if (x.eq.4) return 2
if (x.eq.8) return 3
（中略）
if (x.eq.512) return 9
stop 'illegal x'

こっちの方が見通しがよいしx=1に対応できますが、
ぼくがなにか勘違いしているのかな。

--
love && peace && free_software
t-nissie

Re:

[TarZ (28055)]

　合っていると思います。が、元々の問題の要請が、なるべくループやlogを使わない（でもってできればステップも減らしたい）なのです。
　ということで、1, 2, 4, ... 512 の完全最小ハッシュを作る、というのが最小の解のようです。（乗算x1, ビットシフトx1, インデックスメモリ参照x1）

Re:別解

[okky (2487)]

多分その解は『何をもって最小と言うのか』に強く依存していると思う。
例えば、ハッシュテーブルを作るための計算量が丸々無視されている。

メモリをいくら使っても構わないのであれば 0..512 の 513エントリの表を持てばいいだけです。そういう意味ではTable Lookupは最後の手段だと思いますね。

.

いや、実生活で本当にこういう問題があるなら話は別だけどさ。誰がどう見ても『学生演習』の類だもの。こういうのは趣味丸出しにしないと＼(^o^)／

--
fjの教祖様