C – 删除递归函数中的重复结果

我必须创建一个递归函数，告诉你可以改变一些分数的方式。 （使用四分之一，硬币和硬币）。

到目前为止，我有一个递归function，但它不止一次计算相同的组合，所以数字太大。 如何删除重复的组合？

码：

#include  //Prototypes int coins(int); int main(void){ //Declarations int num; //Get user input printf("Enter an amount of change in cents: "); scanf("%d", &num); //Change to fgets //Call function printf("There are %d ways to make change for %d cents.\n", (coins(num)), num); } int coins(int amt){ //Declarations int ways=0; //Base Case if(amt == 0){ return 1; } //int ways=0; More efficient after base case. if(amt >= 1){ ways+=coins(amt-1); } if(amt >= 5){ ways+=coins(amt-5); } if(amt >= 10){ ways+=coins(amt-10); } if(amt >= 25){ ways+=coins(amt-25); } return ways; } 

例：

输入：17（美分）

输出：80路**输出应为6路

Answer 1

 #include  int coins(int, int); int main(void){ int num; printf("Enter an amount of change in cents: "); scanf("%d", &num); printf("There are %d ways to make change for %d cents.\n", coins(num, 0), num); return 0; } int coins(int amt, int kind){ static int kinds[4] = {25, 10, 5, 1}; int ways=0, i, n; if(kinds[kind] == 1)//always divisible return 1; n = amt / kinds[kind]; for(i = 0; i <= n; ++i) ways+=coins(amt-kinds[kind]*i, kind + 1); return ways; }