3

加算、減算、比較のみを使用して、Javaで2つの数値の乗算を再帰的に見つけたいと思います。それで、私はグーグルで検索Egyptian Algorithmし、それが質問の要件を満たしていることを発見しました。

ただし、に到達した後の乗算結果を見つける方法がわかりませんbase case。

例：

13 x  30

1  -- 30

2  -- 60

4  -- 120

8  -- 240 //we stop here because the double of 8 is larger than 13

結果を見つけるために、left columnそれらが13に等しいからの数を追加し、一方、結果であるそれらが何であるかと1+4+8は反対の数を追加します。right column30+120+240 = 390

しかし、今、プログラムで最後の部分を行う方法は？追加する番号を確認する方法は？皆さんが私の主張を理解してくれることを願っています。ヒントだけが必要です。

4

4 に答える 4

1

問題を解決するための擬似コードは次のとおりです。

function egyptian(left, right)
  prod := 0
  while (left > 0)
    if (left is odd)
      prod := prod + right
    left := halve(left)
    right := double(right)
  return prod

基本的に、最後まで待つのではなく、作成時にテンプレートの各行をチェックし、出力に含まれるかどうかを合計する方が簡単です。このアルゴリズムについては、ブログで説明しています。

于 2012-11-01T14:32:23.693 に答える
0

作成された結果を逆の順序でループします

毎回、乗数の余り（乗数と同じ数から始まる）が左の列の数値よりも大きい場合は、乗数から左の列を減算し、結果に右の列を追加します（ゼロから始まります）。

于 2012-11-01T13:55:34.570 に答える
0

このウィキペディアの記事を見つけたかもしれません。

「分解」と呼ばれるセクションの最後の部分を見てください。実装する必要のあるサブアルゴリズムが見つかります。

于 2012-11-01T13:55:46.970 に答える
0

さて、私はブルートフォースアルゴリズムを使用してそれを行いました。それはBigOです-（n）しかし。私はそれを実装するためのより効率的な方法があると確信しています。今のところ。私はこれで解決しています。

みんなありがとう！

于 2012-11-05T22:06:33.783 に答える