用母函数解组合问题

你的名字 2024-04-18 02:45 94阅读 0赞

## 1.引言 ##

母函数是解组合问题的工具，关于母函数的介绍参考百度百科：[http://baike.baidu.com/view/2415279.htm][http_baike.baidu.com_view_2415279.htm]

杭电OJ平台与母函数相关的编程题有1028、1085、1171、1398

北大OJ平台与母函数相关的编程题有1664

## 2.HD1028 ##

这道题的意思就是将一个数n，分为1,2,3…,n的组合，允许重复，求组合的种数。

#include<stdio.h>
    int a1[121],a2[121];//系数数组
    int main()
    {
        int i,j,k,n;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<=n;i++)/*初始化第一个函数，把第一个函数的系数都赋值为1，(1+x^a1+x^2a1+x^3a1+……)*/
    		{
    			a1[i]=1;
    			a2[i]=0;
    		}
    		for(i=2;i<=n;++i)  //求第i个表达式(1+x^ai+x^2ai+x^3ai+...)   
    		{          
    			for(j=0;j<=n;++j)
    			//j 从0到n遍历，这里j就是(前面i个表达式累乘的表达式)里第j个变量，         
    				for(k=0;k+j<=n;k+=i)
    				// k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。             
    					a2[j+k]+=a1[j];           
    			// 每次前i个表达式累乘求完后都把中间变量a2赋值给a1 
    			for(j=0;j<=n;++j)          
    			{  
    				a1[j]=a2[j];               
    				a2[j]=0;
    			}     
    		}        
    		printf("%d\n",a1[n]); 
    	}   
    	return 0;
    }

### 3.PKU1664 ###

这道题的意思就是将n个一样的苹果放入，m个一样的盘子，盘子允许空。问有多少种放法。

#include <iostream>
    using namespace std;
    int main()
    {
    	int row,i;
    	cin >> row;
    	int *p=new int[row];
    	for(i=0;i<row;i++)
    	{
    		int apples,dishes;
    		int j,k,s;
    		cin >> apples;
    		cin >> dishes;
    		int *p1=new int[apples+1];
    		int *p2=new int[apples+1];
    		for(j=0;j<=apples;j++)
    		{
    			p1[j]=1;
    			p2[j]=0;
    		}
    		for (j=2;j<=dishes;j++)
    		{
    			for(k=0;k<=apples;k++)
    				for (s=0;s+k<=apples;s+=j)
    					p2[s+k]+=p1[k];
    			for (k=0;k<=apples;k++)
    			{
    				p1[k]=p2[k];
    				p2[k]=0;
    			}
    		}
    		p[i]=p1[apples];
    		delete [] p1;
    		delete [] p2;
    	}
    	for (i=0;i<row;i++)
    		cout << p[i]<<endl;
    	delete [] p;
    	return 0;
    }

### 4.HD1085 ###

这一题的意思是有num1个1，num2个2，num5个5，问有这些数字（numX（X=1,2,5）是个数上限），不能组合出的最小值。

int main()
    {
    	int number[3]={1,2,5};
    	int num[3]={0};  //因为循环中要用到循环数i来索引，所以定义为数组
    	int i,j,k;
    	while (scanf("%d %d %d",&num[0],&num[1],&num[2]),num[0]||num[1]||num[2])
    	{
    		int max=num[0]+2*num[1]+5*num[2];//最大值
    		int *p=(int*)calloc(max+1,sizeof(int));//包括0所以max+1
    		int *q=(int*)calloc(max+1,sizeof(int));
    //调用calloc是因为calloc初始化为0，malloc不初始化
    		for (i=0;i<=num[0];i++)     //初始化第一组
    		{
    			p[i]=1;
    			q[i]=0;
    		}
    		int array_size=num[0];//循环次数
    		for(i=2;i<=NUM;i++)   //一共3个数
    		{
    			for (j=0;j<=array_size;j++)
    				for (k=0;k+j<=array_size+number[i-1]*num[i-1];k+=number[i-1])
    					q[k+j]+=p[j];
    			array_size+=number[i-1]*num[i-1];
    			for (j=0;j<=array_size;j++)
    			{
    				p[j]=q[j];
    				q[j]=0;
    			}
    		}
    		for (i=0;i<=max;i++)
    		{
    			if (p[i]==0)
    				break;
    		}
    		if (i==max)
    			printf("%d\n",max+1);
    		else
    			printf("%d\n",i);
    		free(p);
    		free(q);
    	}
    	return 0;
    }

### 5.HD1398 ###

这题的意思是有17种硬币，面值分别是1至17的平方，输入一个数（不大于300），求组成这个数的硬币种数。

#include <iostream>
    using namespace std;
    int const coins[18]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289};//0作为哨兵
    int p[301],q[301]={0};
    int main()
    {
    	int i,j,k;
    	int sum,kinds;
    	while(cin>>sum,sum!=0)
    	{
    		for(i=0;i<=sum;i++)		
    			p[i]=1;
    		for(kinds=1;kinds<=17;kinds++)
    			if (kinds*kinds>sum) break;
    		for (i=2;i<kinds;i++)       //剪枝，可能有多少种类的硬币
    		{	
    			for (j=0;j<=sum;j++)
    				for (k=0;k+j<=sum;k+=coins[i])
    					q[k+j]+=p[j];
    			for (j=0;j<=sum;j++)
    			{
    				p[j]=q[j];
    				q[j]=0;
    			}
    		}
    		cout<<p[sum]<<endl;
    	}
    	return 0;
    }

[http_baike.baidu.com_view_2415279.htm]: http://baike.baidu.com/view/2415279.htm