NetaTaneMenu
*質問！情報求む？のコーナー(1)
**累乗の計算の回数について

　例えば3^7を計算するのに、単純に掛ければ６回の掛け算が必要になりますよね。

　　　　3×3×3×3×3×3×3

でも、実際には 3×3=9 9×9=81 81×3=243 243×3=729
という具合に計算するわけですから、４回の掛け算で済みます。

　質問その１、７乗を掛け算だけで計算するのに掛け算は４回「必要」か？

　　　（掛け算３回で８乗を計算してから３で「割る」なんてのは無しです。）

　質問その２、ｎ乗するときに必要な掛け算の回数を求める関数？プログラム？アルゴリズム？あるいは表？・・・を教えて下さい。

（2003.7.30.むらい）


COLOR(#006789){この問題をみると，昔のプログラミングの心得で，演算の回数をいかに減らすかに気を使ったことを思い出しますね。3^7のケースで4回というのは，他のやりかたもあるけれど，いずれにしても最小回数であるようです。一般の場合に拡張した場合の答えは，整数をn進法で表現することと何か関係がありそうな。}

COLOR(#fe891c){そうなんですよね。ネット上をいろいろと探すのですが、２進法でとりあえず減らしたからまあ好いやって言うのが殆ど。[[数列百科事典:http://www.research.att.com/~njas/sequences/indexjapanese.html]]でさえ役に立ちませんでした。33乗なんかは面白くて3x11で考えるより素直に2^5+1で考えるほうが少ない回数で計算できるのです。さてさて、どういうアルゴリズムが良いのでしょう。ほとほと困っているのですが、まあ楽しんでいます。でも分かった・分かっている人はもったいぶらずに教えてください。あと万が一「それは分かっていないことなんだ」ってことが分かっている場合も、、、}

COLOR(#006789){考えれば考えるほど、って大して時間をかけてはいないのですが・・・一般解のわからない問題に見えてきますねね。箱の中に球を何個詰め込めるかというタイプの問題とよく似ている。時間をとって数十までの範囲の解をとりあえず出してみたいのですが、村井さんはどこまでやってますか？}
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS