이 재귀 - 백 트랙 솔루션은 산술 표현을 해결하기 위해 어떻게 작동합니까?

Question

이 연산 식 문제를 해결하려고합니다. 배열에서 n (여기서는 5) 개의 요소를 취하여 (+ - *)의 연산자 조합을 모두 시도하여식이 101로 나눌 수 있는지 찾습니다. 여기에서 우리는 BODMAS 를 사용 operators..not 순서 입력

5

55 3 45 33 25

출력

+ 55 * 33-25 3-45

염려하지

나는 재귀 및 역 추적에서 새로운 편이다. 내가 라인 2에서 변경하고 다음 조작, 변경 작업을 시도하는 루프 내부에 갈 때, 되돌아 후 다음

public static boolean solve(char []operators,long[]nums,long res,int index,Stack<Character>st){ 


    if(index+1==nums.length){ //reached end of number array 
     if(res%101==0){ 
      System.out.println(res); 
      return true; 
     } 
     return false; 
    } 

    for(int i=0;i<operators.length;i++){ 
     char op=operators[i]; //try the operator 
     long num1=nums[index]; 
     long num2=nums[index+1]; //LINE1 

     System.out.println("trying "+num1+""+op+" num2="+num2); 
     res=performOp(op,num1,num2); 
     nums[index+1]=res; 

     st.push(op); 
     if(solve(operators,nums,res,index+1,st)){ 
      return true; 
     } 
     //backtrack 
     //return to earlier state than try another operator 

     //LINE2 
     nums[index+1]=performBackTrack(op,num1,num2); //restoring number 
     System.out.println("num2="+num2+" num1="+num1+" after backtrack"); 
     st.pop(); 

    } 

    return false; 
} 

    public static long performBackTrack(char op,long num1,long num2){ 
    //trying to restore numbers 
    switch(op){ 
     case '+':return num2-num1; 
     case '-':return num1-num2; 
     case '*':return num1/num2; 
     default:return 0L; 
    } 
} 

public static long performOp(char op,long num1,long num2){ 
    switch(op){ 
     case '+':return num1+num2; 
     case '-':return num1-num2; 
     case '*':return num1*num2; 
     default:return 0L; 
    } 
} 

: 나는 문제의 어떤 부분을 이해하려고하는 것은 잘못된 것입니다 여기에

내 코드입니다 괜찮아요 내가 LINE2에서 orignal 번호를 다시 얻었지만 그것은 LINE1에 반영되지 않습니다. LINE1에 연산자를 시도하기 전에 복원하려고하는 마지막 번호가 반영되지 않습니다.

도움 help..Any 종류가 이해할 수있을 것이다하시기 바랍니다 ...

Answer 1

당신은 다시 추적 방법에 버그가 있습니다.

res=performOp(op,num1,num2)을 수행하고 nums[index+1]의 결과를 할당합니다.

그들을 반대하는 방법은 가능한 모든 작업을 고려하자 :

res = num1 + num2  -> num2 = res - num1 
res = num1 - num2  -> num2 = num1 - res 
res = num1 * num2  -> num2 = res/num1 

따라서 performBackTrack하지 num1 및 num2에 res 및 num1을 통과해야한다. 게다가

, performBackTrack은 다음과 같아야합니다

public static long performBackTrack(char op,long res,long num1) { 
//trying to restore numbers 
    switch(op){ 
     case '+':return res - num1; 
     case '-':return num1 - res; 
     case '*':return res/num1; 
     default:return 0L; 
    } 
} 

및 performBackTrack에 대한 호출은 다음과 같아야합니다

:

nums[index+1]=performBackTrack(op,res,num1); 

이 (당신의 주어진 입력에 대한) 다음과 같은 출력을 생성합니다

trying 55+ num2=3 
trying 58+ num2=45 
trying 103+ num2=33 
trying 136+ num2=25 
num2=25 num1=136 after backtrack 
trying 136- num2=25 
num2=25 num1=136 after backtrack 
trying 136* num2=25 
num2=25 num1=136 after backtrack 
num2=33 num1=103 after backtrack 
trying 103- num2=33 
trying 70+ num2=25 
num2=25 num1=70 after backtrack 
trying 70- num2=25 
num2=25 num1=70 after backtrack 
trying 70* num2=25 
num2=25 num1=70 after backtrack 
num2=33 num1=103 after backtrack 
trying 103* num2=33 
trying 3399+ num2=25 
num2=25 num1=3399 after backtrack 
trying 3399- num2=25 
num2=25 num1=3399 after backtrack 
trying 3399* num2=25 
num2=25 num1=3399 after backtrack 
num2=33 num1=103 after backtrack 
num2=45 num1=58 after backtrack 
trying 58- num2=45 
trying 13+ num2=33 
trying 46+ num2=25 
num2=25 num1=46 after backtrack 
trying 46- num2=25 
num2=25 num1=46 after backtrack 
trying 46* num2=25 
num2=25 num1=46 after backtrack 
num2=33 num1=13 after backtrack 
trying 13- num2=33 
trying -20+ num2=25 
num2=25 num1=-20 after backtrack 
trying -20- num2=25 
num2=25 num1=-20 after backtrack 
trying -20* num2=25 
num2=25 num1=-20 after backtrack 
num2=33 num1=13 after backtrack 
trying 13* num2=33 
trying 429+ num2=25 
num2=25 num1=429 after backtrack 
trying 429- num2=25 
404 

그리고 true을 반환합니다.

는 편집 :

사실이 훨씬 더 간단합니다. performBackTrack은 필요하지 않습니다. 그냥 당신이 nums[index+1]에 정확하게 num2입니다 할당 nums[index+1]=res;, 전의 그 값을 할당하려고, 결국

nums[index+1]=num2; 

와

nums[index+1]=performBackTrack(op,num1,num2); //restoring number 

를 교체합니다.