[已解决]考察英国货币面值的组合问题(以及为什么我的数组传不进去）

叶落了

/*
在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
要构造 ￡2 可以用如下方法：

1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？
*/

//总体思路是判断一种货币可能出现的情况(主函数判断哪种货币，从大到小)
//利用递归完成，200-该货币（余额）的情况
#include<stdio.h>

int array[8]={1,2,5,10,20,50,100,200};
int count=0;//定义一个全局变量，用来统计数量

void Count(int m,int sum,int *array,int a)
{
        if(array[m]!=array[0])//没有 只剩下一种货币供选择。
        {
                if(a==1)
                {
                        for(int k=1;k<=sum/array[m];k++)//第一次不能取0;其他时候可以取。
                  {
                        if(sum-k*array[m]==0)//如果余额为零
                        {
                                count++;
                                return;
                        }
                        else//对余额情况进行递归
                        {
                                Count(m-1,sum-k*array[m],array,0);
                        }
                  }
                }
                else
                {
                        for(int k=0;k<=sum/array[m];k++)//第一次不能取0;其他时候可以取。
                  {
                        if(sum-k*array[m]==0)
                        {
                                count++;
                                return;
                        }
                        else
                        {
                                Count(m-1,sum-k*array[m],array,0);
                        }
                  }
                }
        }
        else
        {
                count++;
                return;
        }
}


int main(void)
{
        for(int i=7;i>=1;i--)
        {
                Count(i,200,array,1);
        }
       
        count++;//把全部是1的加入
       
        printf("一共有%d种构造 面额为200 的方法",count);
       
        return 0;
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-6-25 16:22:03

你的代码大体上是正确的，主要思路就是递归处理各种货币组合的问题。这里我对你的代码做了一些微小的修改，以增加代码的可读性，并修复了一些可能导致错误的地方。这是修改后的代码：

#include<stdio.h>

int array[8] = {1, 2, 5, 10, 20, 50, 100, 200};
int count = 0;

void Count(int m, int sum, int *array)
{
    if(m >= 0) {
        for(int k = 0; k <= sum / array[m]; k++) {
            if(sum - k * array[m] == 0) {
                count++;
            }
            else {
                Count(m - 1, sum - k * array[m], array);
            }
        }
    }
}

int main(void)
{
    Count(7, 200, array);
    printf("一共有%d种构造 面额为200 的方法", count);
    return 0;
}

这个程序的主要工作就是在函数  Count  中进行，它采用了递归的方式处理所有可能的货币组合。注意，在递归调用  Count  函数时，我并没有用到你在原始代码中的  a  参数。对于每一种面值的货币，我们都尝试用不同数量的它来组合，如果剩余的面额（sum - k * array[m]）等于0，就说明我们找到了一种组合方式，计数器  count  就会加1。如果剩余的面额不等于0，我们就递归地尝试用更小的面值的货币来组合剩余的面额。

这个程序运行的效率可能不会很高，因为它需要尝试所有可能的货币组合。如果面额较大，可能会花费较长的时间。但是对于面额为200的情况，这个程序应该是可以在合理的时间内得出结果的。

跳转到最佳答案楼层

isdkz

你的代码大体上是正确的，主要思路就是递归处理各种货币组合的问题。这里我对你的代码做了一些微小的修改，以增加代码的可读性，并修复了一些可能导致错误的地方。这是修改后的代码：

#include<stdio.h>

int array[8] = {1, 2, 5, 10, 20, 50, 100, 200};
int count = 0;

void Count(int m, int sum, int *array)
{
    if(m >= 0) {
        for(int k = 0; k <= sum / array[m]; k++) {
            if(sum - k * array[m] == 0) {
                count++;
            }
            else {
                Count(m - 1, sum - k * array[m], array);
            }
        }
    }
}

int main(void)
{
    Count(7, 200, array);
    printf("一共有%d种构造 面额为200 的方法", count);
    return 0;
}

这个程序的主要工作就是在函数  Count  中进行，它采用了递归的方式处理所有可能的货币组合。注意，在递归调用  Count  函数时，我并没有用到你在原始代码中的  a  参数。对于每一种面值的货币，我们都尝试用不同数量的它来组合，如果剩余的面额（sum - k * array[m]）等于0，就说明我们找到了一种组合方式，计数器  count  就会加1。如果剩余的面额不等于0，我们就递归地尝试用更小的面值的货币来组合剩余的面额。

这个程序运行的效率可能不会很高，因为它需要尝试所有可能的货币组合。如果面额较大，可能会花费较长的时间。但是对于面额为200的情况，这个程序应该是可以在合理的时间内得出结果的。

sfqxx

关于数组无法传递的问题，需要先了解一下具体情况。在这段代码中，你定义了一个名为 “array” 的数组，但是并没有明确指明其大小，也就是说，它的长度无法被编译器自动检测出来。因此，在进行调用时，就需要通过其他手段来告知函数数组的长度。

有两种方法可以解决这个问题：

1. 在函数参数中显式地传递数组长度

这种方式要求你修改 Count 函数的声明，将其第三个参数改为一个指向 int 类型变量的指针，并添加一个表示数组长度的整型参数，可以使用如下代码实现：

void Count(int m, int sum, int *array, int len, int a)

然后在调用的时候，在 Count 函数中增加一行代码，对数组指针进行偏移，即可获得数组长度，例如：

Count(i, 200, array + i, 8 - i, 1);

2. 使用全局变量

由于在这个程序中，数组的长度（8）是已知的，可以通过定义一个全局变量来获取这个值：

int len = 8; // 定义一个全局变量保存数组长度

void Count(int m,int sum,int *array,int a)
{
    //...
}

// 在 main 函数中使用 len 来代替具体的长度值
for(int i=7;i>=1;i--)
{
    Count(i,200,array,len-i,1);
}

总之，无论选择哪种方法，在调用函数时都需要确保正确传递进数组的长度。

求最佳答案

叶落了

isdkz 发表于 2023-6-25 16:22
你的代码大体上是正确的，主要思路就是递归处理各种货币组合的问题。这里我对你的代码做了一些微小的修改， ...

谢谢大佬，我的逻辑菜的像一坨死。那个递归的作用被我忽视了好多，运行效率不高是采用了递归吗？

叶落了

好吧，时间复杂度太大了，去动态规划了