卡特兰数
2010年8月08日 23:29 | Comments(12) | Category:C语言 | Tags:c 数学 递归式 高精度 排列组合
#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 数学 康托 排列组合 转换
根据康托展开公式:
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; }