NetaTaneMenu?
例えば3^7を計算するのに、単純に掛ければ6回の掛け算が必要になりますよね。
3×3×3×3×3×3×3
でも、実際には 3×3=9 9×9=81 81×3=243 243×3=729 という具合に計算するわけですから、4回の掛け算で済みます。
質問その1、7乗を掛け算だけで計算するのに掛け算は4回「必要」か?
(掛け算3回で8乗を計算してから3で「割る」なんてのは無しです。)
質問その2、n乗するときに必要な掛け算の回数を求める関数?プログラム?アルゴリズム?あるいは表?・・・を教えて下さい。
(2003.7.30.むらい)
この問題をみると,昔のプログラミングの心得で,演算の回数をいかに減らすかに気を使ったことを思い出しますね。3^7のケースで4回というのは,他のやりかたもあるけれど,いずれにしても最小回数であるようです。一般の場合に拡張した場合の答えは,整数をn進法で表現することと何か関係がありそうな。