구두 산술/알파벳에 대한보다 효율적인 접근 방법은 무엇입니까?

Question

아마도 대부분의 사람들이 Send + More = Money를 알고 있습니다. 글쎄요, 저는 현재 자바를 배우고 있고 연습 문제 중 하나는 HES + THE = BEST를 해결해야한다는 것입니다.

지금까지는 if-for-do-do 루프를 사용할 수 있습니다. 그것을 해결할 수있는 여러 가지 방법이 있다고 확신하지만, 그것은 제가 경험하고있는 운동의 요점이 아닙니다. if-for-do-do 루프를 가장 효율적인 방법으로 사용할 수 있어야합니다.

내 문제는 무엇입니까? 나는 그것을 해결하는 효율적인 방법을 생각할 수 없다! 그것은이 퍼즐을 해결하기 위해 총 약 15,000 이상한 루프 사이클 소요

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 
    } 
} 

: 나는 퍼즐을 해결, 그러나 아마 그렇게 할 수있는 최악의 효율적인 방법 인이 함께 왔어요. 그것은 내 의견으로는 많이있다. 어떤 포인터라도주세요?

편집자님께 : "숙제"를 태그로 추가하지 않으시겠습니까? 숙제가 아닙니다. 이것은 자기 운동입니다. 뭐? 나는 책을 읽을 수없고 그것에 따라 운동을합니까? 숙제가 있어야합니까? ... 진지하게 그만하십시오.

Answer 1

표준 접근 방식이 brute force 인 경우 효율성이 창 밖으로 나옵니다. 여기에 나와 있습니다. 루프를 사용하는 가장 효율적인 방법은 포괄적 인 가능성을 계산하고 저장 한 다음 각각을 반복하여 작동하는지 확인하는 것입니다.

Answer 2

문자의 모든 값을 루핑하는 대신 S, E 및 T에 가능한 값을 반복하십시오. S + E % 10은 T가되어야합니다. 잠재적 인 S, E, T 솔루션 세트를 얻으면, 가능한 E + H + (S + E가 9보다 큰지 여부에 따라 0 또는 1) = S 솔루션 ... 등을 통해 루프를 찾습니다.

Answer 3

큰 질문은 여기 있습니다 : 논리적으로 특정 제약 조건을 추론하여 알고리즘에 적용 할 수 있습니까? 아니면 무차별 적으로 적용 하시겠습니까? 전자를 가정하면, 그들 중 일부는 매우 명백하다 :

• B = 1
• T은 (는 먼저 때문에) 0, 따라서도 S 나 E 중 하나는 0이 될 수 없을 수있다.
• T = E + S %의 따라서는하면 (576)이 있다는 사실에 추가하다 최대 9 * 8 * 8의 조합을 제공 통해 루프 S, E, H가 10

즉 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; 
    } 
} 

Answer 4

음 당신은 당신의 접근 방식에 최적화의 형태로 많은 것을 할 수 있습니다.

먼저 "최고"의 최대 값을 얻으십시오. "HES"가 가능한 가장 높은 값인 987을 갖고 있다고 가정하면 "THE"는 X98이므로 "THE"의 가장 높은 값은 698이며 987 + 698 = 1685가됩니다.

THE 값이 가장 높으면 THE는 987이고 HES는 876 -> 876 + 987 = 1863이되며 이는 1685보다 높습니다. 따라서 1863은 "최고"의 상한입니다. 따라서 프로그램에서 "B"의 상한을 1로 조정할 수 있습니다 (이 경우 이미 첫 번째 숫자가됩니다).

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 
    } 
} 

당신은 루프 내부에서 바로 값을 통해 불가능한 조합을 많이 버리고 이런 식으로 : 당신은 같은 것을 할 다음 1023

을의로 BEST에 대한 하한은, 쉽게 . 및 가능한 솔루션의 공간을 더 많이 제약하는 유사한 방법이 있다고 생각합니다.

그리고 프로그램은 이렇게 복잡하지 않습니다.

Answer 5

문제 클래스는 쿼리 최적화를위한 포스터 자식입니다. 자바는 그렇지 않다.

수십억 개 미만의 주 (state)가있는 경우이를 강제로 수행하십시오. 은 최적의 쿼리 엔진을 만드는 것보다 무차별 검색을 실행할 시간이 적습니다.

Answer 6

저는 전문가 아니지만 Prolog와 같은 제약 조건을 관리하는 언어를 살펴 보는 것이 좋습니다. 이 매우 비슷한 문제는 여기 :

Compute a list of distinct odd numbers (if one exists), such that their sum is equal to a given number

프롤로그 언어의 다른 유형이지만, 당신이 당신의 자신의 교육을 위해이 일을하는 경우 그것은 확실히

:-) 당신의 두뇌를 행사할 것이 될 것입니다 알파 매틱스에 대한 일반적인 접근법을 코딩 할 수 있습니다.

유전자 알고리즘과 같은 최적화 기술을 사용하는 것이 대안입니다. 결과를 제공하지 않을 수도 있습니다. 여러 솔루션을 추측하고 올바른 솔루션과 얼마나 가까운지 계산 한 다음 조정하십시오. 이 방법으로 부분 솔루션을 얻을 수 있습니다.

Answer 7

아마도이 저장소를보고 싶을 수도 있습니다. JavaFX를 사용하여 언어 계산 문제를 해결하는 솔루션입니다. Firefly Algorithm for Verbal-arithmetics problem [GitHub]