把一元钞票换成一分、二分、五分硬币（每种至少一枚），有多少种换法？---使用递归

Question

我用3个for循环嵌套做了一次，但老师要求用递归，我是菜鸟，不太明白递归怎么用，求高手们指点，先谢谢啦~

Answer 1

C++代码哈#include<iostream>
using namespace std;
#define LEN 3int a[] = {1, 2, 5};
int remain(int i){
int total = 0;
for(int j=LEN-1;j>i;j--)
total += a[j];
return total;
}
long dfs(int total, int i){
if(i>=3){
if(total==0)
return 1;
return 0;
}
 
long res = 0;
for(int num=1;total-a[i]*num>=remain(i);++num){
res += dfs(total-num*a[i], i+1);
} return res;
}
int main(){
printf("%ld\n", dfs(100, 0));}

Answer 2

我也知道答案是461，我用for循环做了，可是老师要我改成递归的，不会啊?求助啊！！

Answer 3

代码有问题，排出来的分配方案有重复，求高手指点如何去重...另外感谢1楼提供的C++代码
import java.util.List;
import java.util.ArrayList;public class TestOnly {

static int count = 0;

public static void main(String[] arg)
{
List<Integer> Cost = new ArrayList<Integer>();

// 用10块试试！
Pay(10, Cost);
System.out.println("种数=" + count);
}

static void Pay(int number, List<Integer> c)
{
int[] numbers = new int[3];
numbers[0] = 1;
numbers[1] = 2;
numbers[2] = 5;
for (int i = 0; i < 3; i++)
{
if (number - numbers[i] == 0)
{
for (int j = 0; j < c.size(); j++)
{
System.out.print(c.get(j));
}
System.out.println(numbers[i]);
count++;
}
else if (number - numbers[i] > 0)
{
List<Integer> n = new ArrayList<Integer>();
n.addAll(c);
n.add(numbers[i]);
Pay(number - numbers[i], n);
}
}

}
}

Answer 4

你不是要递归？怎么又用for了。另外，你要看的是怎么做，别把重点放在用语言上。

Answer 5

按照面值从大到小处理，一张张累加，剩下的能被最小面值整除，则是一种组合。public class PayType { private static int count=0;
private static int coins[]={1,2,5};
public static void main(String[] args) {
int amount=1*100;
int coinsCount[]=new int[coins.length];
//先每种至少一张
for(int i=coinsCount.length-1;i>=0;i--)
{
amount-=coins[i];
coinsCount[i]=1;
}
//从最大开始付
pay(amount,coinsCount.length-1,coinsCount);
System.out.println("count:"+count);
} private static void print(int coinsCount[])
{
count++;
String str="";
int total=0;
for(int i=coinsCount.length-1;i>=0;i--)
{
if(i==coinsCount.length-1)
str+=coins[i]+"*"+coinsCount[i];
else
str+="+"+coins[i]+"*"+coinsCount[i];
total+=coins[i]*coinsCount[i];
}
System.out.println(str+"="+total);
} private static void pay(int amount,int coinIdx,int srcCoinsCount[])
{
int coin=coins[coinIdx];
int[] coinsCount=new int[srcCoinsCount.length];
for(int i=0;i<coinsCount.length;i++)
{
coinsCount[i]=srcCoinsCount[i];
}
//如果是最小一种
if(coinIdx==0)
{
//整除，则合适
if(amount%coin==0)
{
coinsCount[coinIdx]+=amount/coin;
print(coinsCount);
}
return;
}
if(amount>=coin)
{
//用下一种面值付
pay(amount,coinIdx-1,coinsCount);
//继续用当前面值付
coinsCount[coinIdx]++;
amount-=coin;
pay(amount,coinIdx,coinsCount);
}
//不够，则用下一种面值付
else
{
pay(amount,coinIdx-1,coinsCount);
}

}
}

Answer 6

public class Money_digui_2 { /**
 * @param args
 */
private static final int LEN = 3;

static int[]  a={1,2,5}; 

public static void main(String[] args) {
System.out.println("种数="+pay(100,0));
}

public static  int remain(int i){
//求出当前未使用的钞票之和  7 5
    int total = 0;
    for(int j=LEN-1;j>i;j--)
        total += a[j];
    return total;
}

private static int pay(int total, int i) {
int count = 0;
if(i>2){
if(total == 0){
//当总钱数减完时，一种方案完成，返回1
return 1;
}
return 0;
}
else {
//判断余额是否小于于等于没用的钞票，如果没有，不能再选当前的钞票了
for(int n=1;total-n*a[i]>=remain(i);n++){
count += pay(total-n*a[i],i+1);
}
}
return count;
}