首页 > 试题广场 >

考新郎

[编程题]考新郎

热度指数：2419 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

过年期间，老家举行了一场盛大的集体婚礼，为了使婚礼进行的丰富一些，司仪临时想出了有一个有意思的节目，叫做“考新郎”，具体的操作是这样的：
1. 首先，给每位新娘打扮得几乎一模一样，并盖上大大的红盖头随机坐成一排；
2. 然后，让各位新郎寻找自己的新娘。每人只准找一个，并且不允许多人找一个；
3. 最后，揭开盖头，如果找错了对象就要当众跪搓衣板...
假设一共有n对新婚夫妇，其中有m个新郎找错了新娘，求发生这种情况一共有多少种可能。

输入描述:

输入包含多组数据。每组数据包含两个正整数n和m（2≤m≤n≤20）

输出描述:

对应每一组数据，输出一个正整数，表示n对新人中有m个新郎找错新娘的种数。

示例1

输入

2 2<br/>3 2

输出

1<br/>3

算法知识视频讲解

啥

代码如下：

#include <iostream>
#include <stdio.h>
#define N 21

using namespace std;

int main()
{
    long long f[N] = {1, 0, 1};
    long long fac[N] = {1, 1, 2};
    for(int i=3; i<N; i++) {
        f[i] = (i-1)*(f[i-1] + f[i-2]);
        fac[i] = i*fac[i-1];
    }
    int n, m;
    while(~scanf("%d %d", &n, &m)) {
        printf("%lld\n", fac[n]/fac[m]/fac[n-m]*f[m]);
    }
    return 0;
}

发表于 2016-01-10 20:07:09 回复(0)

Python

华科平凡

python solution

import sys
from math import factorial as f

 #求错位数的函数
def dislocationNumber(n):
    arr = [0, 1]
    while len(arr) < n:
        arr.append(len(arr) * (arr[-1] + arr[-2]))
    return arr[-1]


for i in sys.stdin.readlines():
    n, m = map(int, i.strip().split())
    print(dislocationNumber(m) * f(n) // (f(m) * f(n - m)))

发表于 2017-11-17 09:21:02 回复(0)

hestyle

$\color{blue}解题思路：$
首先我们需要从n对夫妻中选出m对夫妻，总共有Cm，n=n!/m!/(n - m)!种情况。
接着这m对夫妻的新郎全部选错的情况f(m) = (m - 1) * (f(m - 1) * f(m - 2))，这个公式上前面好几道都推过，请参考我的博客 PAT乙级(Basic Level)练习题发邮件
因此公式为：n!/m!/(n - m)! * f(m) $\color{blue}代码实现：$

#include <iostream>
using namespace std;

int main() {
    int m = 0, n = 0;
    //fTable[n]记录n个人都悬错的情况种数，allTable[n]记录n的阶乘
    long long fTable[21] = {0, 0, 1}, allTable[21] = {1, 1, 2};
    for (int i = 3; i < 21; ++i) {
        //递推计算i个人全部拿错
        fTable[i] = (i - 1) * (fTable[i - 1] + fTable[i - 2]);
        //递推计算i的阶乘
        allTable[i] = i * allTable[i - 1];
    }
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d %d", &n, &m) != - 1) {
        //组合公式Cm，n=n!/m!/(n - m)!，从n个中随机s选m个
        //从n对中选出m对，allTable[n] / allTable[m] /allTable[n - m]情况
        //选出的m对夫妻全部选错，fTable[m]种情况
        printf("%lld\n", allTable[n] / allTable[m] /allTable[n - m] * fTable[m]);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104690822

发表于 2020-03-06 10:51:54 回复(0)

kestars

import java.math.BigInteger;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        BigInteger[] der=new BigInteger[21];
        der[0]=new BigInteger("0");
        der[1]=new BigInteger("0");
        der[2]=new BigInteger("1");
        for(int i=3;i<21;i++){
            der[i]=(der[i-2].add(der[i-1])).multiply(new BigInteger(i-1+""));
        }
        while(sc.hasNext()){
            int n=sc.nextInt();
            int m=sc.nextInt();
            System.out.println(der[m].multiply(jiechen(n)).divide(jiechen(m).multiply(jiechen(n-m))));
        }
    }

    public static BigInteger jiechen(int n){
        BigInteger result=new BigInteger("1");
        for(int i=2;i<=n;i++){
            result=result.multiply(new BigInteger(i+""));
        }
        return result;
    }
}

发表于 2018-10-01 11:24:47 回复(0)

lienus

#include <iostream>

#include <cstdio>

using namespace std;

const int N = 1010;

long long f[25][25];

int main(){

f[1][0] = 1; f[1][1] = 0;

f[2][0] = 1; f[2][1] = 0; f[2][2] = 1;

for(int i = 3; i <= 20; i++){

f[i][0] = f[i - 1][0];

f[i][1] = f[i - 1][1];

for(int j = 2; j <= i; j++){

f[i][j] = f[i - 1][j] + f[i - 1][j - 1] * (j - 1) + f[i - 1][j - 2] * (i - j + 1);

}

int n, m;

while(scanf("%d%d", &n, &m) > 0){

cout << f[n][m] << endl;

}

f[i][j]表示有i对新婚夫妇有j个新郎找错新娘的种数
容易知道当前有i - 1对新婚夫妇时加一对新婚夫妇进来时无非有三种情况：
1）加进来的新郎找对了，该有多少人找错还是有多少人找错 --> f[i][j] += f[i - 1][j]
2）加进来的新郎与前i - 1个中找对的新郎互换，找错对数加2 -->f[i][j] += f[i - 1][j - 2] * (i - 1 - (j - 2))
3）加进来的新郎与前i - 1个中找错的新郎互换-，找错对数加1 -->f[i][j] += f[i - 1][j - 1] * (j - 1)

发表于 2016-04-30 12:28:02 回复(0)

C/C++

牛客691469011号

#include<stdio.h>
long long int fun2(int a,int b)
{
    int i,j;
    long long int con1=1,con2=1;
    for(i=b;i>0;i--)
    {
        con1*=a;
        a--;
    }
    for(j=1;j<=b;j++)
    {
        con2*=j;
    }
    return con1/con2;
}
int main()
{
    long long der[25] = { 0, 0, 1 };
int i;
for(i=3;i<21;i++)
    {
der[i] =(i-1)*(der[i-2]+der[i-1]);
}
    int n,m,a;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m>n/2) a=n-m;
        else a=m;
        printf("%lld\n",der[m]*fun2(n,a));
    }
    return 0;
}

发表于 2020-11-15 14:49:37 回复(0)

C/C++

不偷不抢安度因_

//n个中取m个，对m个错排
#include <stdio.h>
#include <stdlib.h>
 
long long int find[21] = {0, 0, 1, 2};
long long int func[20] = {1, 1, 2, 6};
//n!/(m!(n-m)!)
long long int fun(int);
 
int main()
{
    int i;
    for(i = 3; i < 21; i++)
    {
        find[i] = (i-1) * (find[i-1] + find[i-2]);
        func[i] = fun(i);
    }
    int m, n;
    while(~scanf("%d %d", &n, &m))
    {
        long long int result = find[m] * (func[n] / (func[m] * func[n-m]));
        printf("%lld\n", result);
    }
}
 
long long int fun(int i)
{
    if(i == 0 || i == 1)
        return 1;
    return i * fun(i-1)

编辑于 2020-03-03 18:50:09 回复(0)

Disconnect

def cal(a,b):
    con1,con2 = 1,1
    for i in range(1,b+1):
        con1 = con1*i
    for i in range(a,a-b,-1):
        con2 = con2*i
    return con2//con1*f[b] 
f = [0,0,1]+[0 for i in range(3,21)]
for i in range(3,21):
    f[i] = (i-1)*(f[i-1]+f[i-2])
try:
    while True:       
        n,m = map(int,input().split())
        print(cal(n,m))     
except:
    pass

发表于 2018-12-02 11:12:33 回复(0)

SupritYoung

https://blog.csdn.net/a1097304791/article/details/84304763

详细题解

发表于 2018-11-20 16:52:43 回复(0)

C/C++

Caffeine

思路 ： 本质上是信封问题。和排列组合问题的组合
#include <vector>
#include <iostream>
using namespace std;

vector<long long> v(22);

long long Fac(int n)
{
    register long long f = 1;
    while (n != 1 && n > 0)
    {
        f *= n;
        n--;
    }
    return f;
}

long long C_n_m(int n, int m)
{
    return Fac(n) / (Fac(n - m) * Fac(m));
}
int main()
{
    v[0] = 0;
    v[1] = 0;
    v[2] = 1;
    for (int i = 3; i < 21; i++)
    {
        v[i] = (i - 1)*(v[i - 1] + v[i - 2]);
    }
    int n, m;
    while (cin >> n >> m)
    {
        long long temp = n - m;
        temp = C_n_m(n, m)*v[m];
        cout << temp << endl;
    }
    return 0;
}

发表于 2018-08-12 22:03:34 回复(0)

C/C++

喻婷

/*
假设一共有n对新婚夫妇，其中有m个新郎找错了新娘，求发生这种情况一共有多少种可能。
错配问题加排列组合
*/
#include <stdio.h>
int main(void){
    int n,m;
    long long der[21]={0,0,1}, fun[21] = { 0,1,2 };
    for(int i=3;i<21;i++){
        der[i]=(i-1)*(der[i-1]+der[i-2]);
fun[i] = i*fun[i - 1];
    }
    while(~scanf("%d %d",&n,&m)){
        if(m==n)printf("%lld\n",der[m]);

        else printf("%lld\n",der[m]*(fun[n]/fun[n-m]/fun[m]));
    }
    return 0;
}

发表于 2018-01-25 07:55:07 回复(0)

Mr.Husky

import java.util.Scanner;

public class Main {
    
    public static long fn(int m){
        if(m == 1){
            return 0;
        }else if(m == 2){
            return 1;
        }else{
            return (m-1)*(fn(m-1)+fn(m-2));
        }
    }
    
    public static long JieCheng(int n){
        long num = 1;
        for(int i=n;i>=1;i--){
            num = num * i;
        }
        return num;
    }
    
    public static long C(int n,int m){
        long part1 = JieCheng(n);
        long part2 = JieCheng(m);
        long part3 = JieCheng(n - m);

        return part1 / (part2 * part3);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            long result = C(n,m)*fn(m);
            System.out.println(result);
        }
    }
}

发表于 2017-09-29 15:46:12 回复(0)

zatree

错排*组合C(n,m)

发表于 2017-06-01 16:52:43 回复(0)

请别叫我河神

只是变式的错排问题而已，无非多了一个组合数~
#include<stdio.h>
long long  jiecheng(int n)
{
	long long  ans=1;
    int i;
	for(i=1;i<=n;i++)
		ans*=i;
	return ans;
}
long long  C(int n,int m)
{
    return jiecheng(n)/(jiecheng(n-m)*jiecheng(m));
}
int main()
{
	long long  f[22];
    int i,m,n;
	f[1]=0;f[2]=1;
	for(i=3;i<=21;i++)
	{
		f[i]=(i-1)*(f[i-1]+f[i-2]);
	}
	while(~scanf("%d%d",&n,&m))
	{
		printf("%lld\n",C(n,m)*f[m]);
	}
	return 0;
}

发表于 2017-05-28 10:52:28 回复(0)

ahac

#include <stdio.h>

long long all(int n){
    if(n==2)
        return 1;
    if(n==3)
        return 2;
    else{
        return (all(n-1)+all(n-2))*(n-1);
    }
}

int main()
{
    int m,n,i;

    while(scanf("%d %d",&n,&m)!=EOF){
        long long  ms=1;
        long long  ns=1;
        long long  mns=1;

        long long s=all(m);
        if(m==n){
            printf("%lld\n",s);
        }else{
             for(i=1;i<=n;i++){
                ns*=i;
            }
            for(i=1;i<=m;i++){
                ms*=i;
            }
            for(i=1;i<=(n-m);i++){
                mns*=i;
            }
            printf("%lld\n",ns/ms/mns*s);
        }
    }
    return 0;
}

发表于 2015-12-20 17:47:31 回复(0)

夏雨天

#include <iostream>

using namespace std;

long long C(int a, int b)//计算a,b 组合 (a<=b)

{

long long result = 1;

for (int i = b; i > b - a;i--)

{

result *= i;

}

for (int i = a; i > 1;i--)

{

result /= i;

}

return result;

}

int main()

{

long long array[22];

array[1] = 0;

array[2] = 1;

for (int i = 3; i <= 20;i++)

{

array[i] = (i - 1)*(array[i - 1] + array[i - 2]);

}

int a = 0, b = 0;

while (scanf("%d%d",&b,&a)!=EOF)//先输入大的再输入小的

{

cout << C(a, b)*array[a] << endl;

}

return 0;

}

发表于 2015-11-03 10:48:03 回复(0)

wong2

发表于 2014-09-10 18:53:15 回复(1)

提交观点

问题信息

难度：

17条回答 8收藏 7500浏览

通过挑战的用户

zkingcode

2023-03-05 23:47:21
Thomas0000

2023-02-27 21:08:08
爱吃的丘比特被升职

2023-02-24 12:31:55
基你太稳

2023-02-20 09:29:59
白狸锆

2023-02-10 20:06:53

考新郎

输入描述:

输出描述:

输入

输出

python solution

问题信息

热门推荐

通过挑战的用户

相关试题