首页 > 代码库 > 一个货币组合的问题（二）——母函数解法
一个货币组合的问题（二）——母函数解法
10月23号的时候，写了用递归和动态规划的方式解决货币组合的方法（见《一个货币组合的问题》）
这两天看到《组合数学》中，使用母函数（生成函数）解决排列组合问题的方法，觉得可以用在货币组合问题上。试验了一下，果然可以。
（这里空出，详细地写一下母函数的方法，加深自己的理解。）
代码如下：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAXITEMS 128 5 6 int v[6] = {1, 2, 5, 10, 20, 50}; 7 int c1[MAXITEMS]; // 被乘的多项式的系数 8 int c2[MAXITEMS]; // 作为乘数的多项式的系数 9 int result[MAXITEMS]; // 存放结果 10 // 两个多项式相乘 11 void12 MultiplePoly(int c1[], int max1, int c2[], int max2)13 {14 int i, j;15 for (i = 0; i <= max1; i++) {16 for (j = 0; j <= max2; j++) {17 result[i + j] += c1[i] * c2[j];18 }19 }20 }21 22 int 23 main(int argc, char** argv)24 {25 int i, j; 26 // 初始化1元 27 memset(c1, 0, sizeof(int) * MAXITEMS);28 for (i = 0; i <= 100; i++) {29 c1[i] = 1;30 }31 // 初始化2到50元，并作乘法32 for (i = 1; i < 6; i++) { 33 memset(c2, 0, sizeof(int) * MAXITEMS);34 for (j = 0; j <= 100; j += v[i]) {35 c2[j] = 1;36 }37 memset(result, 0, sizeof(int) * MAXITEMS);38 MultiplePoly(c1, 100, c2, 100);39 memmove(c1, result, sizeof(int) * MAXITEMS);40 }41 42 printf("1元、2元、5元、10元、20元、50元组成100元的方法一共有%d种。\n ", result[100]);43 44 system("pause"); 45 return 0;46 }
-
一个货币组合的问题（二）——母函数解法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。