n个人排名，允许并列名次，共有多少种排名结果。(100分)
如题
[解决办法]
如果没有并列，有n!种。
如果有1组2个人并列，有(n!/2!)*(n-1)!种
如果有2组2个人并列，有(n!/2!)*((n-1)!/2!)*(n-2)!种
如果有i组j个人并列，有.........
如果有i[m]组j[n]个人并列，有........
好复杂............
[解决办法]
每个都有n个选择.共有n^n个
[解决办法]
#include <iostream.h>
const int NUM = 3; //设定人数为3个人
int a[NUM]; //存储每个人的排名次序
/**
递归函数实现排名
**/
void fun(int n)
{
if(n == 0)
{
for(int k=0; k <NUM; k++)
{
cout < <a[k] < < ' ';
}
cout < <endl;
}
else
{
for(int i=1; i <= NUM; i++)
{
a[NUM-n] = i;
fun(n-1);
}
}
}
void main()
{
fun(NUM);
}
输出结果：
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3
Press any key to continue
[解决办法]
我想....
当没有并列时，有n!种
当用两个人并列时，原来的n个排名就变成n-1种排名，即有(n-1)!
如此类推...
到有n个人并列时，就只有1种
所以总共有：n!+(n-1)!+(n-2)!+......1
不知道对不对
[解决办法]
太复杂了！
[解决办法]
n的n次方吧！n人有n个选择！
[解决办法]
关注一下，是挺复杂的
[解决办法]
经典问题了，可以考虑递推：
假设n个人，排出了m个名次，有f(n,m)种结果（1 <=m <=n）
当m=1
f(n,m)=1
当n <m
f(n,m)=0
当1 <m <=n
假设n-1个人，排出了m个名次；新来1人，与前面某名次并列，有f(n-1,m)*m种结果
假设n-1个人，排出了m个名次；新来1人，与前面名次都不并列，有f(n-1,m-1)*m种结果
f(n,m)= f(n-1,m)*m + f(n-1,m-1)*m
综合上述，递推式:
0 n <m||m <1
f(n,m) = 1 1=m <=n
(f(n-1,m) + f(n-1,m-1))*m 1 <m <=n
n个人的排名就是f(n,1)+f(n,2)+f(n,3)+...+f(n,n)
[解决办法]
1*n!+(n(n-1)/2)*(n-1)!+((n-1)(n-2)/2)*(n-2)!+...+(3*2/2)*2!+1
-------------------------
这个肯定是错的
[解决办法]
终于看到正解了，不用递推思路还真是理不顺
学习ing......
[解决办法]
呵呵 好贴收藏了！
[解决办法]
mmmcd(超超) GG
[解决办法]
mark!
[解决办法]
mark
[解决办法]
mark
[解决办法]
我觉得mmmcd(超超)的算法对,并验证了一个1:1种,2:3种,3:13种,4:75种
并用这个算法写程序验证
function bar($n,$m)
{
if($m==1)return 1;
if($m> $n)return 0;
return $m*(bar($n-1,$m-1)+bar($n-1,$m));
}
function foo($n)
{
$s = 0;
for($i=1;$i <=$n;$i++)
{
$s+=bar($n,$i);
}
return $s;
}
echo foo(4);
[解决办法]
好厉害的递归！
[解决办法]
应该是这样：
当没有并列时当然是 n! 啦
当有两个并列时，除了并列那两个剩下的排列有(n-1)!种，而两个并列就的组合数就是
n(n-1)/2!。因此这时候的排名结果就有：(n-1)! * n(n-1)/2!
如此类推：
当有k个并列时，有：(n-k)!(n(n-1)(n-2)...(n-k))/(k+1)！ 种排列结果
当有n个并列时，有1种
总的排列结果应该是：
n! + (n-1)!n(n-1)/2! + (n-2)!n(n-1)(n-2)/3! + ...+ (n-k)!(n(n-1)(n-2)...(n-k))/(k+1)!+...+ 1
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
我觉得这个想法也是对的，只要把说法变一下，把有k个并列说成是分成k组就对了，这样就把多组的情况考虑在内了。
[解决办法]
算法思路：
当n=4，如下图，其中[i]表示i的排名结果
4 [0]
3 [1] 留下3个人，其余1个人再排
2 [2] 留下2个人，其余2个人再排
1 [3] 留下3个人，其余3个人再排
从上图看出，用递推可节省时间，4 用到1，2，3的结果，但空间就...
还是用递归吧：
class allsort{
public static void main(String args[]){
int n=Integer.valueOf(args[0]);
AllSort( " ",n);
}
public static void AllSort(String prefix,int n){
if (n==0)
System.out.println(prefix);
for(int i=0;i <n;i++){
AllSort(((prefix== " ")? " ":prefix+ " ")+String.valueOf(n-i),i);
}
}
}
测试：javac allsort 20 > tmp.txt
tmp.txt有11M!!! 有524288行!!!
20
19 1
18 2
18 1 1
17 3
17 2 1
17 1 2
17 1 1 1
16 4
16 3 1
16 2 2
16 2 1 1
16 1 3
16 1 2 1
16 1 1 2
16 1 1 1 1
15 5
15 4 1
15 3 2
15 3 1 1
...
...
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[解决办法]
我觉得此题实质和百度之星第三题是一样的。
