f(Program,Poet)=Programet

6.常用数学方法
a.排列组合
b.递推与通项的选用

a.排列组合

在解决问题时，我们常常使用一些比较固定的“工具式”的算法，将它们作为算法的一部分。这样的工具常常包括排序、高精度运算、数学方法、二分查找等等。
其中的一些在前面已经介绍，接下来我们还会介绍一些。

NOIP要求我们会运用一些数学方法。这些方法往往是离散数学中的经典方法、定理。现在我们介绍一些。
数学方法包括求素数（用不大于sqrt(n)的正整数除一下），求最大公约数（欧几里得算法，第一章讲过），排列组合等。

最基本的方法就是排列组合。高中数学已经介绍了排列组合，最有用的结论如下：
* n个球中选出m个有序地排成一列，排法种数为A(n,m)，在这里1≤m≤n。A(n,m)=n!/(n-m)!=n(n-1)(n-2)…(n-m+1)
* n个球中选出m个无序地分成一组，分法种数为C(n,m)，在这里1≤m≤n。C(n,m)=n!/[(n-m)!m!]=A(n,m)/m!
* 组合数性质：C(n,m)=C(n-1,m)+C(n-1,m-1)
* 插空法：n个相同的A球和m个相同的B球排成一行（m≤n+1），要求B球两两不相邻，排法种数为C(n+1,m)
* 杨辉三角的组合数形式：
1
1 1
1 2 1
1 3 3 1
…
上面的杨辉三角可写成如下形式
1
C(1,0) C(1,1)
C(2,0) C(2,1) C(2,2)
C(3,0) C(3,1) C(3,2) C(3,3)
…
* 球盒问题和第二类Stirling数
有一类问题可以用“n个球放入m个盒子的放法种数”来描述。这里讨论盒子均不留空的情况，盒子可留空时的情形可据此推导。
相同球放入不同盒子的放法种数为C(n+1,m)（运用插空法）。
不同球放入相同盒子的放法种数L(n,m)=L(n-1,m-1)+m*L(n-1,m),L(n,1)=L(n,n)=1（L(i,j),i≥j组成的一系列数称作第二类Stirling数）。
相同球放入不同盒子的放法种数为m!L(n,m)。
* Catalan数
h(1)＝1,h(n)=h(1)h(n-1)+h(2)h(n-2)+…+h(n-1)h(1)的通项为h(n)=C(2n-2,n-1)/n。
注意以下的结论——
n个数连乘，根据结合律，用括号把它们分成两个因子相乘、不可再添加括号的形式，如abcde写成((ab)((cd)e))。这样的写法种数为h(n)。
一个足够大的栈入栈序列为1,2,…,n，可能的出栈序列有h(n)种。
将凸n边形区域划分成三角形区域的方法数为h(n)。

在分析问题时，注意看清问题的本质，把实际问题抽象成数学模型，看看有没有数学方法可用。

b.递推与通项的选用

先来看一个问题——2^k进制数（NOIP2006）。
设r是个2^k进制数，并满足以下条件：
（1）r至少是个2位的2^k进制数。
（2）作为2^k进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k<W≤30000）是事先给定的。问：满足上述条件的不同的r共有多少个？
分析——
如果你的基础知识过关，那么你应该可以从（3）中知道，q的总位数是r的总位数的k倍。（如果你没反应过来，请翻翻以前学习进制转换时的资料吧。）
现在命c=[w/k]（[]是取整数部分函数），即r的位数上限是c。当然，若c<w/k，会有首位数字比较小的情形，这可在之后分开讨论。
下面仔细分析c=w/k时的情况。
现在，把r看成由i个数字组成（2≤i≤c）。i个数字可从1至2^k-1任取并进行组合，每种组合方式对应一个数，即有C(2^k-1,i)个数。
那么，r共有n=C(2^k-1,2)+C(2^k-1,3)+…+C(2^k-1,c)个。
c<w/k，读者自己想想吧～这里给出源代码。

现在的问题是计算。显然，高精度运算是不可避免的。这里还要算C(2^k-1,i)。
如果用公式C(n,m)=n!/[(n-m)!m!]，往往会有高精度除法，很难办。这里的好办法是——递推，用C(n,m)=C(n-1,m)+C(n-1,m-1)吧！
高精度加法很容易实现，虽然要做的加法比较多，但CPU算加法比乘法快得多，所以总时间比使用通项C(n,m)=n!/[(n-m)!m!]还可能短一些！
事实上，执行时间惊人的短。这里给出源代码。

// C Program "Digital" written by LastLeaf
 
#include <stdio.h>
 
#define H_Bit 51
 
int times(m,n)
{
	int i,a=1;
	for(i=1;i<=n;i++)a*=m;
	return a;
}
 
unsigned *HPrint(unsigned *N)
{
	FILE *fp;
	int i;
 
	fp=fopen("digital.out","w");
 
	for(i=H_Bit-N[0]+1;i<=H_Bit;i++)
		if(N[i]!=0)
		{
			fprintf(fp,"%u",N[i]);
			break;
		}
	for(i++;i<=H_Bit;i++)
		fprintf(fp,"%u%u%u%u",N[i]/1000,N[i]/100%10,N[i]/10%10,N[i]%10);
	fprintf(fp,"\n");
 
	fclose(fp);
 
	return N;
}
 
unsigned *HInitialize(unsigned *N,int value)
{
	N[0]=1;
	N[H_Bit]=value;
	return N;
}
 
unsigned *HAdd(unsigned *N1,unsigned *N2)
{
	int up=0,i;
 
	if(N2[0]>N1[0])
	{
		for(i=N1[0];i<N2[0];i++)N1[i]=0;
		N1[0]=N2[0];
	}
	for(i=0;i<N2[0];i++)
	{
		N1[H_Bit-i]+=N2[H_Bit-i];
		if(N1[H_Bit-i]>=10000)N1[H_Bit-i]-=10000,up=1;
		else up=0;
	}
	for(i=H_Bit-i;i>H_Bit-N1[0] && up==1;i--)
	{
		N1[i]++;
		if(N1[i]==10000)N1[i]=0;
		else up=0;
	}
	if(i!=0 && up==1)
	{
		N1[0]--;
		N1[i]=1;
	}
	return N1;
}
 
int main()
{
	int i,k,c,j,imax,hmax,bmax,w;
	unsigned A[513][H_Bit],Ans[H_Bit];
	FILE *fp;
 
	fp=fopen("digital.in","r");
	fscanf(fp,"%d %d",&k,&w);
	fclose(fp);
 
	bmax=times(2,k)-1;
	if(w%k==0)
		c=w/k,hmax=bmax;
	else
		c=w/k+1,hmax=times(2,w%k)-1;
	HInitialize(Ans,0);
	for(i=1;i<=bmax;i++)HInitialize(A[i],1);
	imax=bmax;
	for(j=2;j<=c;j++,imax--)
		for(i=2;i<=imax;i++)
			HAdd(A[i],A[i-1]);
	for(i=bmax-1;i>imax-hmax && i>0;i--)
		HAdd(Ans,A[i]);
 
	HPrint(Ans);
 
	return 0;
}

高中数学经常求通项，不过对于计算机，往往递推式更有用！去寻找递推式吧～

本章无附件

本文由 最后的叶子 创作，转载或引用前请联系我们。

相关文章：

1. NOIP实用算法 目录
2. 五年NOIP提高组复赛算法及难度分析
3. NOIP实用算法·教程 下载版
4. NOIP实用算法·教程 下载版 2.0
5. NOIP实用算法 下载版 纠错通知

2009年8月21日 星期五