首页 > 试题广场 >

发邮件

[编程题]发邮件
  • 热度指数：4607 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？
即没有人收到属于自己的邮件。

输入描述:
输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。


输出描述:
对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。
示例1

输入

2<br/>3

输出

1<br/>2
算法知识视频讲解
添加回答
推荐
战斗啊阿西吧头像 战斗啊阿西吧
错排问题。

当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.
第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
综上得到
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1.

有了递推公式，一切就迎刃而解了。
#include<stdio.h>
int main (void)
{
    long long der[ 21 ] = { 0, 0, 1 };
    int i;
    for ( i = 3; i < 21; i++ ){
        der[ i ] = ( i - 1 ) * ( der[ i - 2] + der[ i - 1 ] );
    }
   
    int n;
    while ( scanf( "%d", &n ) != EOF ){
        printf("%lld\n", der[ n ] );
    }
    return 0;
}



编辑于 2016-08-23 18:42:02 回复(9)
我不是董皓宇。头像 我不是董皓宇。 
//递归思想，第n个收件人可以递归到n-1个收件人与n-2个收件人之和
#include<iostream>
using namespace std;

long int Failrec(int n)
{
    if(n<2)
        return 0;
    if(n==2)
        return 1;
    if(n==3)
        return 2;
    return (n-1)*(Failrec(n-1)+Failrec(n-2));
}

int main()
{
    int n;
    while(cin>>n)
    {
        int count=0;
        cout<<Failrec(n)<<endl;
    }
    return 0;
}

发表于 2019-07-25 13:05:17 回复(0)
会呼吸旳痛头像 会呼吸旳痛 
错排问题，推导如下,
若前n-1个数已经满足错排，现考虑第n个数：
（1）第n个数可以和前n-1个中任意一个数互换，结果仍然是错排，所以有(n-1)*D(n-1)种；
（2）第n个数可以放到前n-1任意一个位置，但是原来位置的数不能放到最后，
     则其只可以能放在其他n-2个位置，并且保证这n-2的位置是错排，所以有(n-1)*D(n-2)

综上，一共有 D(n) =（n-1）*(D(n-1)+D(n-2))

编辑于 2016-08-24 19:23:36 回复(0)
熊朝春头像 熊朝春 
// 主要是练练语法，这种题目的思想总是很难想到。所谓的动态规划问题：假设a放进了B中：分两种情况，
//一种情况是b放在A中，有D（n-2）种方法，另一种情况是b没有放在A中，实际上就是把b,c,d...放进
//A,C,D...中也就是有D(n-1)放法，而把a放进C,D,E...中有同样的D(n-1) + D(n-2)种放法，所以有n封信
//就应该有(n-1)[D(n-1) + D(n-2)]种放法。
lst = [0, 0, 1]
for i in range(3,21):
    lst.append((i-1)*(lst[i-1]+lst[i-2]))
while True:
    try:
        N = int(input())
        print(lst[N])
    except:
        break
        
#include <stdio.h>
#define maxN 21
int main()
{
    int i;
    int N;
    long long a[maxN] = {0, 0, 1, 2};
    for(i=4;i<maxN;i++)
    {
        a[i] = (i-1)*(a[i-1] + a[i-2]);
    }
    while(scanf("%d", &N)!=EOF)
    {
        printf("%lld\n", a[N]);
    }
}

发表于 2017-12-03 22:50:28 回复(0)
Python
华科平凡头像 华科平凡

python解法

這是一個錯排問題

公式：f(n)=(n-1)*(f(n-1)+f(n-2))

import sys


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():
    print(dislocationNumber(int(i)))
发表于 2017-11-17 11:21:17 回复(0)
元气の悟空头像 元气の悟空 
#include<stdio.h>
int N=0;
void dfs(int,int);
int book[100]={0};
int main()
{
	int n;
	scanf("%d",&n);
	dfs(0,n);
	printf("%d",N);
}

void dfs(int step,int n)
{
	if(step==n) N++;
	else
	{
		int i;
		for(i=0;i<n;i++)
			if(book[i]==0&&i!=step) //没访问过并且自己的位置的编号不等于自己的值
			{
				book[i]=1;
				dfs(step+1,n);
				book[i]=0;
			}
	}
}//这是不需要什么数学公式推导的最暴力的方法

发表于 2016-08-24 17:37:35 回复(0)
困困头像 困困
这道题的核心在于 递归的思想
也就是经典的装错信封问题
 用A、B、C……表示写着ｎ位友人名字的信封，a、b、c……表示ｎ份相应的写好的信纸。把错装的总数为记作D(n)。假设把ａ错装进Ｂ里了，包含着这个错误的一切错装法分两类：
(1)b装入Ａ里，这时每种错装的其余部分都与A、B、a、b无关，应有D(n－2)种错装法。
(2)ｂ装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）n－1份信纸ｂ、ｃ……装入（除B以外的）n－1个信封A、C……，显然这时装错的方法有D(n－1)种。
总之在ａ装入B的错误之下，共有错装法D(n－2)＋D(n－1)种。
a装入C，装入D……的n－2种错误之下，同样都有D(n－1)＋D(n－2)种错装法，因此D(n)＝(n－1)[D(n－1)＋D(n－2)]

发表于 2015-08-13 17:36:31 回复(5)
尤鱼哥头像 尤鱼哥 

	







	import java.util.Scanner;





	







	//用的是单步最优的考虑想法，从最后一步开始考虑。





	//为了方便理解，假设有5个人ABCDE，原来只有4个人ABCD。则多出来的一个人E，





	//多出来的邮件E必定发错给ABCD中一个，共四种方法。假设给E的邮件发给了D，则





	//  人 ：   A  B  C  D  E





	// 邮件：            E





	//则发给D的邮件D有两种情况：一是正好发给了人E，二是发给了E以外的人（ABC）





	//若情况一：变成了3人各自错收了邮件。





	//若情况二：由于D不能发给E，我们可以假象D就是E（和原来等价），则此时变成了ABCE错发给ABCE，就等价于4人错收邮件。





	//这样就很明白了，f（n）=（n-1）*[f（n-2）+f（n-1）]





	public class Main {





	







	 public static void main(String[] args) {





	  Scanner in= new Scanner(System.in);





	  





	  long c[]=new long[22];





	  c[2]=1;





	  c[3]=2;





	  for(int i=4;i<22;i++){





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





	  }





	  while(in.hasNext()){





	   int n=in.nextInt();





	   System.out.println(c[n]);





	  }





	  





	 }





	







	}

发表于 2016-09-10 10:02:33 回复(1)
来学习的小张头像 来学习的小张 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            long[] arr = new long[21];
            arr[0] = 0;
            arr[1] = 0;
            arr[2] = 1;
            for(int i = 3;i < arr.length;i++){
                arr[i] = (i - 1) * (arr[i - 1] + arr[i - 2]);
            }
            System.out.println(arr[n]);
        }
    }
}

。
编辑于 2022-06-03 10:51:09 回复(0)
C/C++
AlbatrossLy头像 AlbatrossLy
错排公式：v[n] = (n - 1) * (v[n - 1] + v[n - 2]) 
#include <iostream>
#include <vector>
using namespace std;

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


编辑于 2021-11-24 22:09:56 回复(0)
Java
落尘QAQ头像 落尘QAQ 
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        long[] a = new long[22];
        a[2] = 1;
        a[3] = 2;
        for (int i = 4; i < 22; i++){
            a[i] = (i-1)*(a[i-1]+a[i-2]);
        }
        while (scan.hasNext()){
            int n = scan.nextInt();
            System.out.println(a[n]);
        }
    }
}

发表于 2021-07-28 21:14:49 回复(0)
峰峰的牛客头像 峰峰的牛客 
//详细解说看博客
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            long sum = count(n);
            System.out.println(sum);
        }

    }

    //计算所有人都收不到自己的邮件的情况情况：错排算法
    private static long count(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return (n - 1) * (count(n - 1) + count(n - 2));
        }
    }
}
————————————————
版权声明：本文为CSDN博主「峰回路转」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44840148/article/details/104723196

发表于 2020-03-07 22:16:22 回复(0)
価闙头像 価闙 
while True:
    try:
        n, num = int(input()), [1, 2]
        cout = 2
        while len(num) < n:
            num.append((num[-1] + num[-2])*(cout+1))
            cout += 1
        print(num[-2])
    except:
        break

#include <iostream>
using namespace std;

int main() {     long long num[20] = {1, 2};          for (int i = 2; i < 20; i++)         num[i] = (num[i-1] + num[i-2]) * (i + 1);               int n;          while (cin >> n) {         cout << num[n-2] << endl;     }          return 0;
} 

发表于 2019-02-12 22:34:41 回复(0)
SupritYoung头像 SupritYoung
详细题解
发表于 2018-11-18 13:39:13 回复(0)
C/C++
Neuqer头像 Neuqer
#include<stdio.h>
longwrong(longn)
{
    if(n==1)
        return0;
    elseif(n==2)
        return1;
    else
        return(n-1)*(wrong(n-1)+wrong(n-2));
}
intmain()
{
    intn;
    while(scanf("%d",&n)!=EOF)
        printf("%ld\n",wrong(n));
    return0; 
}

发表于 2018-08-13 16:38:41 回复(1)
C/C++
Caffeine头像 Caffeine 
思路：转载楼上的  #include <iostream>
using namespace std;
int main()
{
    int n;
    long long a[21] = {0,0,1};
    for (int i = 3; i < 21; i++)
    {
        a[i] = (i - 1)*(a[i - 1] + a[i - 2]);
    }
    while (cin >> n)
    {
        cout << a[n] << endl;
    }
}

发表于 2018-08-12 18:12:50 回复(0)
MemoryC头像 MemoryC
这一题为数列题：
设数列A(n)为当有n个人时，全部错收邮件的情况数量；
则可推：

解释：
 表示全排列，即无论对错 所有的分发情况数量；

而表示有个人收到正确的邮件时的分发情况，表示从个人中抽取个人的种类数，而则是剩下个人全部收错的种类数；

由于当时，不可能只有1个人收错邮件，所以此时总数应该 减去,省略；

对于最后一个 ,是 “全部收对”邮件的情况。

综上所述，我的代码如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
 * @author MemoryC
 * */
public class Main {

    public static void main(String[] args) {

        Scanner scanner=new Scanner(System.in);
        
        List<Long>numbers=new ArrayList<>();
        numbers.add((long) 0);
        numbers.add((long) 0);
        numbers.add((long) 1);
        numbers.add((long) 2);
        
        while(scanner.hasNext()) {
            int n=scanner.nextInt();
            
            if(n>numbers.size()-1) {
                for(int i=numbers.size();i<=n;i++) {
                    long ann=Ann(i);
                    for(int j=1;i-j>=2;j++) {
                        ann-=Cni(i,j)*numbers.get(i-j);
                    }
                    numbers.add(ann-1);
                }
            }
            
            System.out.println(numbers.get(n));
        }
        scanner.close();
    }
    
    static long Ann(int n) {
        long A=1;
        for(int i=n;i>1;i--) {
            A*=i;
        }
        return A;
    }
    
    static long Cni(int n,int i) {
        if(i>n/2) {
            return Cni(n, n-i);
        }
        long A=1;
        for(int j=n;j>n-i;j--) {
            A*=j;
        }
        for(int j=i;j>0;j--) {
            A/=j;
        }
        return A;
    }
}

这个代码区每次换行都会乱掉，所以就直接粘贴文字了，见谅；
编辑于 2018-08-09 14:33:11 回复(0)
我要过pat头像 我要过pat
装错信封的问题:
我们假设:
A      B      C    D......n个信
装进
a     b        c     d......n个邮箱
一共n个;
我们假设一个函数  D(x)  为x 个元素的时候放错信封的数量;

现在把A 放进除a外的的邮箱如b:     这里一个n-1 中情况;

那么B 放在哪里呢?分两种情况:
1.B 放在a,那么等于两者互换,就排除2个元素;剩下等情况继续满足D(x)的函数,剩下的元素n-2;所以这种情况是;    D(n-2);

2.我们先把A -b 去掉:
 B      C    D......n-1个信
装进
a        c     d......n-1个邮箱
B假如放在a才是正确的那么放错的情况同时满足;  D(n-1);

所以D(n)=(n-1)(D(n-2)+D(n-1)) 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;



int main()
{     int n,i;     long long a[25]={0,0,1};               for(i=3;i<=20;i++)      {         a[i] =(i-1)*(a[i-2]+a[i-1]);     }          while(cin>>n)     {         cout<<a[n]<<endl;      }          return 0;      }


发表于 2018-02-13 17:36:29 回复(0)
RicardoZi头像 RicardoZi 
#include <stdio.h>

int main(){
	int n, i;
	long long a[20] = {0, 0, 1};
	for(i=3;i<=20;i++){
		a[i] = (i-1)*(a[i-1] + a[i-2]);
	}
	while(scanf("%d",&n)!=EOF){
		printf("%lld\n", a[n]);
	}
}

很典型的错装问题。
发表于 2017-07-22 18:55:20 回复(0)
请别叫我河神头像 请别叫我河神 
#include<stdio.h>
int main()//典型的错排问题；
{
	int n,i;
	long long a[25]={0,0,1};
	for(i=3;i<=20;i++)
	{
		a[i]=(i-1)*(a[i-1]+a[i-2]);
	}
	while(~scanf("%d",&n))
	{
		printf("%lld\n",a[n]);
	}
	return 0;
}

发表于 2017-05-13 22:35:31 回复(0)
Java
StudyOfSlagD头像 StudyOfSlagD 
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println(count(n));
		}
	}
	/**
	 * 错排算法,注意是long型
	 * @param n
	 * @return
	 */
	public static long count(int n) {
		if (n == 1) {
			return 0;
		} else if (n == 2) {
			return 1;
		} else {
			return (n - 1) * (count(n - 1) + count(n - 2));
		}

	}
}

编辑于 2016-08-27 15:53:35 回复(0)
提交观点

问题信息

查找
难度：
23条回答 18578浏览

热门推荐

通过挑战的用户

相关试题

发邮件

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号