6

Send + More = Money をご存知の方も多いと思います。さて、私は現在 Java を学んでおり、演習の 1 つは HES + THE = BEST を解かなければならないことです。

さて、これまでのところ、if-for-while-do ループを使用できる/使用する必要がありますが、他には何もありません。それを解決するにはさまざまな方法があると思いますが、それは私が行っている演習のポイントではありません。最も効率的な方法で if-for-while-do ループを使用できる必要があります。

私の問題？それを効率的に解決する方法が思い浮かびません！私はこれを思いつきました。これはパズルを解決しますが、おそらく最悪の効率的な方法です。

public class Verbalarithmetics {

    public static void main (String args[]) {
        // Countint Variables
        int index_h = 0;
        int index_e = 0;
        int index_s = 0;
        int index_t = 0;
        int index_b = 0;

        // Start with h = 1 and increase until the else-if statement is true
        for(int h = 1; h <= 9; h++) { // h = 1, because first Symbol can't be zero
            index_h++;
                // Increase e so long until e equals h
                for(int e = 0; e <= 9; e++) {
                    index_e++;
                 if (e == h) {
                    continue;
                 }

                 // Increase s so long until s equals h or e
                 for(int s = 0; s <= 9; s++) {
                     index_s++;
                    if (s == h || s == e) {
                       continue;
                    }//end if

                    // Increase t so long until t equals h or e or s.
                    for(int t = 1; t <= 9; t++) { // t = 1, because 1st Symbol cant be zero
                        index_t++;
                      if(t == h || t == e || t == s) {
                         continue;
                      }// end if

                      // Increase b so long until b equals h, e, s or t.
                      for(int b = 1; b <= 9; b++) { // b = 1, weil das 1. Symbol nicht für eine 0 stehen darf
                          index_b++;
                          if (b == h || b == e || b == s || b == t) {
                              continue;
                          }// end if

                          // x = 100*h + 10*e + s
                          // y = 100*t + 10*h + e
                          // z = 1000*b + 100*e + 10*s + t
                          // Check if x+y=z, if true -> Print out Solution, else continue with the upper most loop
                          else 
                              if (100*h + 10*e + s + 100*t + 10*h + e == 1000*b + 100*e +10*s + t) {
                                  System.out.println("HES + THE = BEST => " + h + e + s + " + " + t + h + e + " = " + b + e + s + t);
                                  System.out.println("With H=" + h + ", E=" + e + ", S=" + s + ", T=" + t + ", und B=" + b + ".");
                                  System.out.println("It took " + index_h + 
                                          " Loop-Cycles to find 'h' !");
                                  System.out.println("It took " + index_e + 
                                          " Loop-Cycles to find 'e' !");
                                  System.out.println("It took " + index_s + 
                                          " Loop-Cycles to find 's' !");
                                  System.out.println("It took " + index_t + 
                                          " Loop-Cycles to find 't' !");
                                  System.out.println("It took " + index_b + 
                                          " Loop-Cycles to find 'b' !");
                                  System.out.println("This is a total of " + (index_h + index_e + index_s + index_t + index_b) + 
                                          " Loop-Cycles");
                          }// end else if
                      }//end for
                    }//end for
                 }//end for
              }//end for
        }//end for
    }   
}

このパズルを解くには、合計で約 15000 回の奇妙なループ サイクルが必要です。それは私の意見ではたくさんあります。ポインタはありますか？

4

7 に答える 7

4

ここでの大きな問題は、特定の制約を論理的に推測してアルゴリズムに適用できるか、それともブルートフォースしたいのかということです。前者を想定すると、それらのいくつかはかなり明白です：

  • B = 1
  • Tを0にすることはできません（THEの最初であるため）。したがって、SもEも0にすることはできません。
  • T = E + S％10

したがって、ループするS、E、Hがあり、最大で9 * 8 * 8の組み合わせ（576）が得られます。さらに、H + Tは9以上でなければならず、これをさらに減らすことができます。

更新これが迅速で醜い解決策です。上記の3つの制約のみに基づいています。

public class Puzzle {
  public static void main(String[] args) {
    for (int S = 1; S<10; S++) {
      for (int E = 1; E<10; E++) {
        if (S==E) continue; // all letters stand for different digits
        for (int H = 1; H<10; H++) {
          if (H==E || H==S) continue; // all letters stand for different digits
          checkAndPrint(S, E, H);
        }
      } // for
    } // for
  } // main

  private static boolean checkAndPrint(int S, int E, int H) {
    int T = (S + E) % 10;
    int S1 = (E + H) + (S + E) / 10; // calculates value for 'S' in 'BEST' (possibly + 10)
    if (S1 % 10 != S) return false;
    int E1 = H + T + S1 / 10; // calculates value for 'E' in 'BEST' (possibly + 10)
    if (E1 % 10 != E) return false;
    System.out.println(H + "" + E + "" + S + " + " + T + "" + H + "" + E + " = 1" + E + "" + S + "" + T);
    return true;
  }
}
于 2009-11-19T20:50:34.243 に答える
2

たぶん、このリポジトリを見たいと思うかもしれません: JavaFX を使用して言語算術の問題を解決するためのソリューションです。動詞算術問題に対する Firefly アルゴリズム [GitHub]

于 2016-06-11T20:40:17.410 に答える
1

私は専門家ではありませんが、Prolog などの制約を管理する言語を調べる価値があるかもしれません。ここに非常によく似た問題があります：

それらの合計が指定された数に等しくなるように、個別の奇数 (存在する場合) のリストを計算します

プロローグは別のタイプの言語ですが、自分の教育のためにこれを行っているのであれば、確かに頭の体操になるでしょう :-)

アルファベット学への一般的なアプローチをコーディングすることが可能になります - ここでのかなり単純なものだけではありません.

結果が保証されていない別の方法は、遺伝的アルゴリズムなどの最適化手法を使用することです。いくつかの解を推測し、それらが正しい解にどれだけ近いかを計算してから、それらを調整します。この方法で部分解が得られる場合があります。

于 2009-11-29T17:05:54.290 に答える
1

文字のすべての値をループする代わりに、S、E、および T の可能な値をループします。S + E % 10 は T である必要があります。潜在的な S、E、T ソリューションのセットを取得したら、次のループを見つけます。考えられる E+H+(S+E が 9 より大きいかどうかに応じて 0 または 1)=S の解...などなど。

于 2009-11-19T20:35:52.443 に答える
0

うーん、アプローチの最適化の形で多くのことができます。

まず、「BEST」の最大値を取得します。「HES」の最大値が 987 であるとすると、「THE」は X98 となり、「THE」の最大値は 698 となり、987+698=1685 となります。

「THE」の値が最大の場合、THE は 987 になり、HES は 876 -> 876+987=1863 になり、1685 より高くなるため、1863 が「最良」の上限になります。したがって、プログラムで "B" の上限を 1 に調整することができます (この場合、すでに最初の数字が得られます..)。BEST の下限は 1023 なので簡単です。

次に、次のようにします。

for(i=102;i<=987;i++)
{
    for(j=1023-i;j<=(1863-i < 987 ? 1863-i:987);j++)
    {
        //check if the solution matches and doesn't have duplicate digits
    }
}

このようにして、内側の for ループの値を使用して、多くの不可能な組み合わせをすぐに破棄します。可能なソリューションのスペースをさらに制限する同様の方法があるに違いありません。

そして、プログラムはこのように複雑ではありません。

于 2009-11-19T20:55:43.233 に答える
0

そのクラスの問題は、クエリ最適化の代表的なものです。Javaはそうではありません。

状態の数が数百億未満の場合は、力ずくで実行してください。ブルート フォース検索を実行する方が、最適化クエリ エンジンを作成するよりもはるかに短い時間で済みます。

于 2009-11-19T21:22:59.607 に答える
0

ここで提案されているように、標準的なアプローチがブルートフォースである場合、効率は窓の外に出ます。ループのみを使用する最も効率的な方法は、可能性のすべてを計算し、それらを保存してから、それぞれを反復して機能するかどうかを確認することです。

于 2009-11-19T20:31:26.620 に答える