6

暗号算術パズルを表す 3 つの文字列を取る C++ プログラムを計画しています。たとえば、TWO、TWO、および FOUR が与えられた場合、プログラムは、数式が

   TWO 
+  TWO 
------
  FOUR

は true で、入力は右揃えであると想定されます。これに対処する 1 つの方法は、もちろん、答えが最終的に見つかるまで、ネストされたループを使用して各文字に可能なすべての置換を割り当て、合計を繰り返し試行するなど、力ずくで実行することです。

これは非常に非効率的ですが、各変数のドメインを制限するために一連の演繹が実行された後、根底にあるループチェックは実行可能な (または必要でさえある) 方法である可能性があると思います。視覚化するのはちょっと難しいと思いますが、最初にこのような一般的な/パディングされた構造を想定するのが合理的でしょうか (各 X は必ずしも明確ではない数字を表し、各 C は桁上げ数字です。この場合、 0 または 1 のいずれかになります)? :

   CCC.....CCC
   XXX.....XXXX
+  XXX.....XXXX
----------------
  CXXX.....XXXX

それを念頭に置いて、さらにいくつかの計画的な考えを以下に示します。

-問題では先頭のゼロは指定されませんが、オペランドを一致させる/一致させるために、適切な場所に十分な数を追加する必要があります。

-おそらく「ドメイン」テーブルにベクトルとして保存されている、各文字の可能な値0〜9のセットから始めて、控除が行われるときにこれから値を削除する必要があると考えています。たとえば、このように文字が並んでいるのを見たら

 A
 C
--
 A

、 C がゼロであることがわかり、これにより、そのドメインから他のすべての値が削除されます。かなりの数の推論を思いつくことができますが、それらをあらゆる種類の小さな状況に一般化してコードに入れることは、一見すると難しいように思えます。

-物事を実行し、ドメインテーブルから多くの値を起動する一連の優れた推論があると仮定すると、すべてをループして、状態空間が合理的なソリューションを生成するのに十分小さいことを願っています時間の長さ。しかし、それ以上のものがあるはずだと感じています！-- 設定するための巧妙な方程式か、それに沿ったものかもしれません。

ヒントをいただければ幸いです。

4

3 に答える 3

1

この問題を右から左に繰り返すことができます。つまり、実際の操作を実行する方法です。一番右の列から始めます。遭遇するすべての数字について、その数字の割り当てが既にあるかどうかを確認します。ある場合は、その値を使用して続行します。そうでない場合は、可能なすべての数字のループに入り (おそらく、全単射写像が必要な場合は既に使用されている数字を省略します)、可能な割り当てごとに再帰的に続行します。合計行に到達したら、そこに指定された桁の変数が既に割り当てられているかどうかを再度確認します。そうでない場合は、現在の合計の最後の桁を割り当て、キャリーを持って次に高い値の列に進みます。既に割り当てがあり、結果の最後の桁と一致する場合は、同じ方法で処理を進めます。

このアプローチの利点は、多くの変数が事前に推測されるのではなく、合計によって決定されることです。特に、合計行にのみ出現する文字の場合、これは大きなメリットになる可能性があります。さらに、エラーを早期に発見できる可能性があるため、これまでに行った選択がすでに矛盾している場合に、文字の選択を回避できます。欠点は、プログラムの再帰構造が少し複雑になることです。しかし、それが正しく理解できれば、思考をコードに変換することについても多くのことを学んだことになります。

于 2013-06-21T11:18:10.467 に答える