star

搜索

RSS

RSS Link

计数器

139726

卡特兰数

2010年8月08日 23:29 | Comments(12) | Category:C语言 | Tags:

$$C(0) = 1$$

$$C(n) = \frac{C(n-1)(4n-2)}{n+1} (n>0)$$

#include <stdio.h>
int C[101][101], len[101];

int main(void)
{
	int i, j, r, t, l;
	C[0][0] = 1;
	len[0]  = 1;
	l       = 1;        //长度
	
	for(i = 1; i <= 100; ++i)
	{
		for(j = 0; j < l; ++j)        //乘法
			C[i][j] = C[i-1][j] * (4*i-2);
		for(r=j = 0; j < l; ++j)
		{
			t       = C[i][j] + r;
			C[i][j] = t % 10;
			r       = t / 10;
		}
		while(r)
			C[i][l++] = r % 10, r /= 10;
		for(j = l-1, r = 0; j >= 0; --j)        //除法
		{
			t       = r*10 + C[i][j];
			C[i][j] = t / (i+1);
			r       = t % (i+1);
		}
		while(!C[i][l-1])
			--l;
		len[i] = l;
	}
			
	for(i = 1; i <= 100; ++i)
	{
		printf("%d:", i);
		for(j = len[i]-1; j >= 0; --j)
			printf("%d", C[i][j]);
		putchar(10);
	}
	
	return 0;
}

求一个数是第几个排列数

2010年8月06日 00:47 | Comments(81) | Category:C语言 | Tags:

根据康托展开公式:$$C = \left\sum_{i=1}^{n}a_i(i-1)!\right$$

a[i]为第i个数比后面的都小的个数。

#include <stdio.h>
#include <string.h>
int FAC[10] = {1,1,2,6,24,120,720,5040,40320,362880};
int CantorExp(char *s, int n)
{
	int i, j, t, num = 0;
	for(i = 0; i < n; ++i)
	{
		t = 0;
		for(j = i+1; j < n; ++j)
			if(s[j] < s[i])
				++t;
		num += FAC[n-i-1]*t;
	}
	return num+1;
}
int main(int argc, char *argv[])
{
	char s[] = "1324";	//输入一个排列数的字符串序列 
	printf("%d", CantorExp(s, strlen(s)));
	return 0;
}