1

たとえば、20 + 15 を加算するには、2 つの配列が必要です。

a = {2, 0}
b = {1, 5}

そして、結果として次の配列を取得する必要があります。

outcome = {3, 5} // or {5, 3} and read it in reverse order

難しいのは、これらの配列の最初の要素しか使用できないため、配列がスタックのように動作することです。

私の例では比較的簡単ですが{1, 0, 0, 0} + {5}、それとも{9, 9} + {9, 9}？

これを行うための特定の方法を実際に見つけることはできません。言うまでもなく、解決する方法が見つかりません{1, 0, 0, 0} + {5}。

実際にこれを C 言語で記述する必要があるため、C タグがここにありますが、解決策についてのアイデアは歓迎されます (必ずしも C プログラムではなく、説明を意味します)。

4

3 に答える 3

3

数字を逆にして、最下位桁が最初で最上位桁が最後になるようにします。加算のアルゴリズムは、最下位から最上位へと機能します。

a = {0, 0, 0, 1}
b = {5}

これらの数値を追加するのは簡単です。それぞれから数字をポップして追加し、結果を結果スタックにプッシュします。

a = {9, 9}
b = {9, 9}

99 + 99 を処理するには、キャリーを追跡する必要があります。これは、どちらのスタックにも移動しない、保存する 1 つの追加の変数になります。9 と 9 をポップし、それらを加算して 18 を取得します。8 を結果スタックにプッシュし、キャリー ディジットを格納します。

a = {9}
b = {9}
outcome = {8}
carry = 1

次に、次の 2 桁の 9 と 9 をポップし、それらを加算して 18 を取得します。キャリーの数字を加算して 19 を取得します。9 を結果スタックにプッシュし、キャリーを再び追跡します。

a = {}
b = {}
outcome = {9, 8}
carry = 1

入力スタックに数字が残っていないので、最後に最後のキャリー数字を結果スタックにプッシュします。

outcome = {1, 9, 8}
于 2013-04-13T15:46:33.770 に答える
1

これを試してください（テストされていません）（キャリーを処理するように更新されました）：

Stack Add(Stack a, Stack b, bool carry) {
  if (a.Empty && b.Empty) return (carry ? a.Push(1) : a);
  int c = (a.Empty ? 0 : a.Pop)
        + (b.Empty ? 0 : b.Pop)
        + (carry ? 1 : 0);
  if (c>=10) 
    return Add(a,b,true).Push(c-10)
  else
    return Add(a,b,false).Push(c);
}

もちろん、関数呼び出しスタックと a および b を暗黙的に使用しています。

于 2013-04-13T15:43:32.113 に答える
1

あなたの最善の希望は次のようなアルゴリズムだと思います：

pop digits from stack a and compute number n1
pop digits from stack b and compute number n2
add n1 and n2 giving n3
push digits from n3 onto stack outcome

それができない場合は、スタックを適切に整列できるように、各スタックaおよびに含まれる桁数を知る必要があります。b

別の、しかし直感的ではない表現も役に立ちます。

a = { 0, 2 }
b = { 5, 1 }

c = { 0, 0, 0, 1 }
d = { 5 }

最下位桁が最初に格納されます。これで、必要に応じてスタックの先頭から追加して運ぶことができます。

于 2013-04-13T15:49:47.320 に答える