найти все возможные комбинации монет, реализации рекурсии

Question

Решить эту проблему с помощью рекурсии:

используя три типа монет включают в себя 1, 2 юаней юаней и 5 юаней, плюс 10 юаней, сколько комбинаций?

Ниже мой код:

int coinNum(int num){ 
    if(num>=0){ 
     if(num==0) 
      return 1; 
     else 
      return coinNum(num-5)+coinNum(num-2)+coinNum(num-1); 
    }else 
     return 0; 
} 

int main(){ 
    int num=coinNum(10); 
    printf("%d\n",num);//the result is 128 
    system("pause"); 
    return 0; 
} 

Что ошибка моего алгоритма рекурсии или то, что ваш правильный код?
вопрос дополнение:
1. (5,2,2,1) и (2,5,2,1) следует учитывать как 1 сочетание.
2. Ниже приведен мой код алгоритма перечисления.

void coin(){ 
    int i,j,k,count=0; 
    for(i=0;i<=10;i++) 
    for(j=0;j<=5;j++) 
     for(k=0;k<=2;k++) 
      if((i+2*j+5*k)==10){ 
       count++; 
       printf("one yuan :%d，2 yuan :%d，5 yuan :%d\n",i,j,k); 
      } 

    printf("总方法数%d\n",count);//the result is 10 
} 

Answer 1

Ваш код подсчет числа перестановок , которые добавляют до 10. Вы хотите комбинации. Это означает, что (5,2,2,1) и (2,5,2,1) следует считать 1 комбинацией.

В этом случае ответ должен быть 10: (5,5), (5,2,2,1), (5,2,1,1,1), (5,1,1,1), (5,1,1,1)), (2,2,2,2,2), (2,2,2,2,1,1), (2,2,2,1,1,1,1), (2,2,1 , .. 1), (2,1, ... 1) и (1, .. 1).

Попробуйте этот код:

int coinNum(int num, int *coins){ 
    if (num == 0) return 1; 
    if (num < 0 || !*coins) return 0; 
    return coinNum(num - *coins, coins) + coinNum(num, coins+1); 
} 

int main(){ 
    int coins[] = {5,2,1,0}; // don't forget the 0 or the program won't end 

    int num=coinNum(10,coins); 
    printf("%d\n",num); // the result is 10 
    system("pause"); 
    return 0; 
} 

Код выше пытается все комбинации, пока сумма не равна или превышает требуемую сумму. Обратите внимание, что это не самый эффективный алгоритм для решения этой проблемы, но самый простой. Для улучшения алгоритмов, вы должны, вероятно, искать его на Computer Science Stack Exchange.

Answer 2

Другой простой алгоритм, использующий идею генерации не уменьшающейся последовательности монет.

int coinNum(int num, int min_coin) { 
    if (num == 0) { 
    return 1; 
    } else if (num < 0) { 
    return 0; 
    } else { 
    int res = coinNum(num - 5, 5); 
    if (min_coin <= 1) { 
     res += coinNum(num - 1, 1); 
    } 
    if (min_coin <= 2) { 
     res += coinNum(num - 2, 2); 
    } 
    return res; 
    } 
} 

int main(){ 
    int num = coinNum(10, 1); 
    printf("%d\n", num); 
    return 0; 
}