find 1,5,10,25,50 센트를 사용하여 총 17cents (예 :)를 얻는 방법의 수

Question

왜 스택 오버플로 오류가 발생합니까? 제가이 문제를 시작으로 재귀 적으로 해결하려고 시도하는 이유는 무엇입니까? 동적 인 프로그래밍을 사용하여 시작합니다. 방법 동전에서 "a"는 내가 원하는 총을 형성 할 동전을 보유하는 배열이고, sum은 내가 원하는 총 (예 : 17)이고, i는 그 배열의 색인을 나타냅니다. 오전에

import java.util.*; 
public class dp2 {//RECURSIVE WAY THEN OPTIMIZE TO DP 
    public static int coins (int [] a, int sum,int i){ 

    if (sum==0) 
     return 1; 
    else if (i==a.length){ 
     return 0; 
    } 
    else if (i>a.length&&sum<a[i]){ 
     return coins(a,sum,i++); 
    } 

    else { 
     return coins(a,sum-a[i],i++)+coins(a,sum-a[i],i); 
    } 
    } 

    public static void main (String [] args){ 
    Scanner sc = new Scanner (System.in); 

    while (sc.hasNext()){ 
     int x = sc.nextInt(); 
     int y=x; 
     int [] a ={1,5,10,25,50}; 
     int w = coins(a,y,0); 
     System.out.println("There are " +w+ " ways to produce "+x + " coins change."); 
    }    
    } 

} 

Answer 1

무한 루프에 문제가 있습니다.

첫 번째 확인, 실제로 반환 할 수있는 것은 실제로 1 또는 0 만 반환 할 수 있기 때문입니다. 다른 조건은 어디에 있습니까? 예 : i == a.length - 1 또는 합계 <? 제 생각에, 당신은 합계를 돌려주고 싶습니다.

다음으로 예 17을 입력하면 배열에서 마녀 동전을 선택할 메커니즘을 선택할 수 있습니까?

그리고 다음, 내가이 항상 있기 때문에 코드에서, return coins(a,sum-a[i],++i)+coins(a,sum-a[i],i);을 변경하십시오 0

그래서, 어쩌면 당신을 위해 좋은 exaple 코드 : 난 당신의 코드를 하나 개의 문장을 추가

class dp2 {//RECURSIVE WAY THEN OPTIMIZE TO DP 
    public static int coins (int [] a, int sum,int i){ 
    if (sum==0) 
     return 1; 
    else if (i==a.length){ 
     return 0; 
    }else if(i + 1 == a.length || sum < 0 || sum - a[i] < 0){ //Your break condition ? 
     return sum; 
    } 
    else if (i>a.length&&sum<a[i]){ 
     return coins(a,sum,i++); 
    } 

    else { 
     return coins(a,sum-a[i],++i)+coins(a,sum-a[i],i); 
    } 
    } 
    public static void main (String [] args){ 
    Scanner sc = new Scanner (System.in); 

    while (sc.hasNext()){ 
     int x = sc.nextInt(); 
     int y=x; 
     int [] a ={1,5,10,25,50}; 
     int w = coins(a,y,0); 
     System.out.println("There are " +w+ " ways to produce "+x + " coins change."); 
    } 
    } 
} 

Answer 2

, 행 4에서 :

System.out.println(sum + ", " + i); 

입력 27 보내기 출력이었다

,

27, 0 
26, 0 
25, 0 
.... decreasing by one each time... 
3, 0 
2, 0 
1, 0 
0, 0 
-4, 1 
-9, 1 
-14, 1 

sum < 0을 확인하지 않았으므로 중지되지 않습니다.

당신은 ... 거기에서 println 그것을 알아낼 수 있어야한다 : 이것은 아마도 무한 재귀 호출이다