QuesTion

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.むらい）

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

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

考えれば考えるほど、って大して時間をかけてはいないのですが・・・一般解のわからない問題に見えてきますねね。箱の中に球を何個詰め込めるかというタイプの問題とよく似ている。時間をとって数十までの範囲の解をとりあえず出してみたいのですが、村井さんはどこまでやってますか？

やっぱり家の環境では書き込めなくて報告遅れました。十進ベーシックで総当たり的なプログラムを書いてみました。メモリの関係で７０ぐらいまでしか検証できていません。現在はpythonかLisp（schame）あるいはrubyでなんとかならんかなあと「思って」いる次第です。どうやら結構難しいことらしく、Knuthさんのart of programing(うろ覚え)の第三巻に記述があるようです。ご存じ・所持されている方は詳細を教えてください。

それから数列百科事典が役に立たなかったと書きましたが、嘘でした。ちゃんとありました。

ついでですから、途中までの表です。

さすが！やってますねえ。ちょっと興味を持ったのは，解の数の分布についてです。たとえば，9のケースでは解は2通りあり，どっちがよりよいというわけではない。ただし，途中に現れる数値の種類も含めると優劣を付けられる場合もあるでしょう。そういう問題を含めて，最良解から最悪解？まで何個ずつあるのか。

Ruby はAI的な言語ではないので，LISP とはセンスがちがいます。もっとも Ruby は多倍長整数がらくらくと扱えて 100!なんて屁でもないとか，eval という強力な関数があって式そのものを文字列としても実行文としても扱えるので，この種のプログラムを書くには便利でしょう。クラスも使えるし。ぜひこの機会に習得を。 このルビー電卓も，それを生かして作ってあります。たとえば下の式をコピー＆ペーストして実行してみてください。上の9のケースの計算のようすです。式の中の変数の種類とか '*' の数が答になっています。

a0 = 3; n = 9; a0 ^ n
sprintf("--------")
a1 = a0 * a0; a11 = a1 * a1; a11 * a11 * a0
sprintf("-------")
a2 = a0 * a0 * a0; a2 * a2 * a2

さあて、Rubyは最適なプログラム？を意識しなければとってもお気楽な言語ですね。ちょっとプログラムを書いて動かしてみました。LISPとは確かにその言語の作り方？動作原理？のセンスは違いますが、リストや連想配列などLISPを齧った事がある程度の僕には、こりゃあ楽だって思いました。そのあたりは駱駝でもPealとは違うなって感じですね。というわけで、少し長いですがプログラムとその結果です。

Rubyistな方は添削してみてください。再帰が効くので、Squeakでも面白いかもしれない。smalltalkが好きだった僕としてはあのインターフェイスがどうにもなじめないのでパスしているのですけど。

# The Shortest Addition Chain List Program
tsacl=[[1]]
newcl=[]
numl=[1]
ll=[[1]]
dcl=tsacl
k=0
while k<16　　<<<===ここはお好みの自然数を。ちなみに学校のPCでは11で詰まってました。
  k=k+1
  newnuml=[]
  for c in dcl
    t=c[-1]
    for x in c
      na=t+x
      if not numl.include?(na) then
        newc=c+[na]
        newcl=newcl+[newc]
        if not newnuml.include?(na) then
          newnuml=newnuml+[na]
        end
      end
    end
  end
  print "."
  tsacl=tsacl+newcl
  ll=ll+[newnuml]
  numl=numl+newnuml
  dcl=newcl
  newcl=[]
end
print "\n"
p numl
for l in ll
  p l
end

総当りのプログラムです。 tsaclはTheShortestAdditionChainのListです。 「最適」なものだけですが、複数あればすべて入ります。結果はShortestAdditionChainに