n对夫妻跳舞问题

路过

有n对夫妻跳舞，每人要有一个舞伴，但夫妻不能互为舞伴，请问有多少种组合？
n=10 n=100 n=1000?
========================
(转自csdn)

gladrain

高明!!

gladrain

高明啊!!!

gladrain

哈哈!!

http://[UserCP=1000][/UserCP][SHADOW=255,blue,1]文字[/SHADOW]

路过

<转>
一个简单的实现
#include<iostream>
using namespace std;
int com2(int n)
{return (n*(n-1))/2;}

void main()
{
        int n,m;
        cout<<"lease input the number:";
        cin>>n;
        cout<<endl;
        m=com2(n)-1;
    cout<<m<<endl;
}

路过

<转>
可以这么想，
1、对于第一个男人，供他选择的舞伴有9个（因为不能则其配偶），选择其中之一，并将该女人的配偶作为第二个进行选择的男人；

2、对于第二个男人，供他选择的舞伴有9个（因为他的配偶已被第一个男人选走，他可以在剩下的9个女人中任意选取），选择其中之一，并将该女人的配偶作为第三个进行选择的男人；

3、对于第三个男人，供他选择的舞伴有8个（因为他的配偶已被第二个男人选走，而且第一个男人也选走了一个，所以可以在剩下的8个女人中任意选取），选择其中之一，并将该女人的配偶作为第四个进行选择的男人；

4、对于第四个男人，供他选择的舞伴有7个（因为他的配偶已被第三个男人选走，而且最前两个男人选走了两个，所以可以在剩下的7个女人中任意选取），选择其中之一，并将该女人的配偶作为第五个进行选择的男人；

5、依次类推。。。
   对于第九个男人，供他选择的舞伴有2个，选择其中之一，并将该女人的配偶作为第十个进行选择的男人；

6、对于第十个男人，只有一个选择了
   那么可以得到10对夫妻跳舞的组合有9×9×8×7×...×2×1种选择；

7、通过简单归纳，可以得到对于100对夫妻跳舞的组合方式有
   99×99×98×97×...×2×1；

8、对于N对夫妻跳舞的组合方式有
   (N-1)(N-1)(N-2)(N-3)...2*1=(N-1)(N-1)!

路过

<转>

假设有3对夫妻Aa,Bb,Dd;

A选b后 ， B有两种选择a和d 。 但是B选a 后，D就只能选d了。
所以(3-1)*(3-1)!是不对的。

======================
//计算公式
//f(n)=n!-C(n,1)*f(n-1)-C(n,2)*f(n-2)-……-C(n,n-2)*f(2)-1
//计算思路：所有夫妻男女组合的总数（n!）-只有一对夫妻在一块的组合-
//2对夫妻在一起的组合…………
#include <stdio.h>
#define NUM 10
long P(long n)
{
        if(n==1)        return 1;
        else return n*P(n-1);
}
long C(int n,int m)
{
        return (P(n)/(P(m)*P(n-m)));
}
long sub(int n,int F[])
{
        int i;
        long result=0;
        if(n==2)
                return 1;
        else
        {
                for(i=1;i<n;i++)
                        result+=C(n,i)*F;
                return result+1;
        }
}
void main()
{
        int i,result=0,F[NUM];
        F[0]=0;
        F[1]=0;
        for(i=2;i<=NUM;i++)
        {
                result=P(i)-sub(i,F);
                F=result;
                printf("\n%2d   %ld",i,result);
        }
}
结果：
2   1
3   2
4   9
5   44
6   265
7   1854
8   14833
9   133496
10   1334961
例：
2:21      total 1
3:312     231     total 2
4:2143    4123    3142    2413    3412    4312    2341    3421    4321   
   total 9
5:21534   21453   31254   51234   41253   31524   41523   51423   31452   41532
  51432   23154   25134   24153   35124   53124   45123   54123   34152   43152
  45132   54132   23514   24513   25413   35214   53214   45213   54213   34512
  35412   43512   53412   23451   24531   25431   34251   43251   45231   54231
  34521   35421   43521   53421   
  total 44
说明：21的意思是 2号->1号  1号->2号
      312的意思：3->1  1->2  2->3
      2143     ：2->1  1->2  4->3   3->4
      25413    ：2->1  5->2  4->3  1->4  3->5

golden

如果第二个男人选的是第一个男人的老婆呢，则第三个男人只有七种选择了。

路过

<转>
经典的错位排列问题，由容斥原理可解，其结果n!-c(n,1)*(n-1)!+c(n,2)*(n-2)!-...，也就n!(1-1/1!+1/2!-1/3!+...)

golden

好，谢谢楼主了。