|
|
问题描述：
参加任何一项比赛，都会涉及到排名统计问题，由此可见排名统计是多么的重要．这里假设有一项比赛，共有n(1<=n<=200)个人参加，那么请问共有多少种不同的排名(注意:可以很多参赛者在同一个名次，即参赛者名次可以并列)?
数据输入n，输出为不同的排名总数．
如输入
1
2
3
输出为
1
3
13
//程序的性能还不行，算法基本没问题了
==================code================
/**
*Copyright (C) aprin at Xiamen University
*2005-4-24
*/
#include <stdio.h>
#define MAX_N 200
#define MAX_LEN 1000
int cheng(int *a1, int len_a1, int *a2, int len_a2);
int c_fun(int n, int r, int *c) {
int i, j, k, len, temp[3], len_temp, shang[MAX_LEN], len_shang;
/*计算pr/n*/
len=1;
c[0]=1;
for(i=0; i<r; i++) {
j=n-i;
len_temp=0;
while(j!=0) {
temp[len_temp]=j%10;
len_temp++;
j/=10;
}
len=cheng(c, len, temp, len_temp);
}
/*/r!*/
for(i=0; i<MAX_LEN; i++)
shang[i]=0;
for(i=2; i<=r; i++) {
int temp=len-1, yushu;
len_shang=0;
yushu=c[temp];
while(temp>=0) {
shang[len_shang]=yushu/i;
len_shang++;
yushu%=i;
temp--;
yushu=yushu*10+c[temp];
}
/*ji suan du yu de 0*/
k=0;
while(shang[k]==0)
k++;
/*倒转，转移*/
for(j=0; j<MAX_LEN; j++)
if(j<(len_shang-k))/* 实际的长度*/
c[j]= shang[len_shang-1-j];
else
c[j]= 0;
len= len_shang-k;
}
return len;
}
int cheng(int *a1, int len_a1, int *a2, int len_a2) {
int temp[MAX_LEN], i, j;
for(i=0; i<MAX_LEN; i++)
temp[i]=0;
for(i=0; i<len_a2; i++) {
for(j=0; j<len_a1; j++) {
temp[i+j]=temp[i+j]+a1[j]*a2[i];
temp[i+j+1]=temp[i+j+1]+temp[i+j]/10;
temp[i+j]=temp[i+j]%10;
}
if(temp[i+len_a1]>10) {/*ke neng cun zai de zui gao wei chu li*/
temp[i+len_a1+1]=temp[i+len_a1+1]+temp[i+len_a1]/10;
temp[i+len_a1]=temp[i+len_a1]%10;
}
}
i=MAX_LEN-1;
while(temp[i]==0)
i--;
for(j=0; j<MAX_LEN; j++)
a1[j]=temp[j];
return i+1;
}
int add(int *a1, int len_a1, int *a2, int len_a2) {
int i,len;
len=(len_a1>len_a2)?len_a1:len_a2;
for(i=0; i<len; i++) {
a1[i+1]+=(a1[i]+a2[i])/10;
a1[i]=(a1[i]+a2[i])%10;
}
len=MAX_LEN;
while(a1[len-1]==0)
len--;
return len+1;
}
int ok(int *renshu, int i, int n) {
int tot, j;
tot=0;
for(j=0; j<=i; j++)
tot+=renshu[j];
return tot==n;
}
void output(int *result, int len) {
int i;
for(i=len-2; i>=0; i--)
printf("%d", result[i]);
putchar('\n');
}
int main(void) {
int n, i, j, k;
int renshu[MAX_N];
int result[MAX_LEN], len;
scanf("%d", &n);
for(i=0; i<MAX_LEN; i++)
result[i]=0;
len=0;
for(i=0; i<n; i++) {
for(j=0; j<=i; j++)
renshu[j]=1;
do {
if(ok(renshu, i, n)) {
int result_mid[MAX_LEN], len_mid, temp, total_temp;
len_mid=1;
result_mid[0]=1;
total_temp=n;
for(temp=0; temp<i; temp++) {
int zuhe[MAX_LEN], len_zuhe;
len_zuhe=c_fun(total_temp, renshu[temp], zuhe);
total_temp-=renshu[temp];
len_mid=cheng(result_mid, len_mid, zuhe, len_zuhe);
}
len=add(result, len, result_mid, len_mid);
}
renshu[0]++;
for(j=0; j<i; j++)
if(renshu[j]>(n-i)) {
renshu[j+1]++;
renshu[j]=1;
}
}
while(renshu[i]<=(n-i));
}
output(result, len);
getch();
return 0;
}
|
|
