年会抽奖

import java.text.DecimalFormat;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		double[] num = new double[21];
		num[0] = 0.00;
		num[1] = 0.00;
		num[2] = 50.00;
		double[] notAward = new double[21];
		notAward[0] = 0;
		notAward[1] = 0;
		notAward[2] = 1;
		long total = 2;
		for (int i = 3; i < 21; i++) {
			notAward[i] = (i - 1) * (notAward[i - 1] + notAward[i - 2]);
			total = total * i;
			num[i] = (double) notAward[i] / total * 100;
		}
		DecimalFormat df = new DecimalFormat(".00");
		while (scan.hasNextInt()) {
			int n = scan.nextInt();
			if (n < 0 || n > 20) {
				System.out.println("error");
			} else {
				System.out.println(df.format(num[n]) + "%");
			}

		}
		scan.close();
	}
}

//详细解说看博客：链接在回答最下边
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();
             double sum1=factorial(n);
             double sum2=count(n);
             double result=(sum2/sum1)*100; //计算成%的形式
            System.out.println(String.format("%.2f",result)+"%");
        }
    }
    //计算所有人都抽不到奖的情况：错排算法
    private static double count(int n) {
      if(n==1){
          return 0;
      }else if(n==2){
          return 1;
      }else {
          return (n-1)*(count(n-1)+count(n-2));
      }
    }

    //计算阶乘：迭代写法
    private static double factorial(int n) {
        double sum=1;
        while(n>1){
           sum=sum*n;
           n--;
        }
        return sum;
    }
    //计算阶乘：递归写法
    private  static double factorical2(int n){
       if(n==0||n==1){
           return 1;
       }
       return n*factorical2(n-1);
    }
}

————————————————
版权声明：本文为CSDN博主「峰回路转」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44840148/article/details/104706415

//主要是为了复习复习python的语法，题目很简单。python写起来确实要不C简单那么一点
lst = [0, 0, 1]
for i in range(3,21):
    lst.append((i-1)*(lst[i-1]+lst[i-2]))
while True:
    SUM = 1
    try:
        N = int(input())
        count = lst[N]
        while N>0:
            SUM *= N
            N -= 1
        res = (1.0*count/SUM)*100
        print("{0:.2f}%".format(res))
    except:
        break

#include "stdio.h"
double gener(short x) {
	double item = 0.5; double result = item;
	for (short i = 3; i <= x; i++) {
		item /= -i;
		result += item;
	}
	return result;
}

int main()
{
	short n;
	while (~scanf("%2hd", &n)) {
		printf("%5.2f%%\n", 100 * gener(n));
		
	}
    return 0;
}

方法推导
P(n) = D(n)/n!

其中D(n)是错排的数目，错排的意思就是1-n个数的一个排列，
它满足任意一个数不在序号等于自己的位置上,公式推导见
http://www.nowcoder.com/questionTerminal/95e35e7f6ad34821bc2958e37c08918b?toCommentId=187402

import java.util.Scanner;
//代码已通过测试，还望各位牛友批评指正
public class Main{
    //这道题着实让我折腾了好半天，首先要明白这是一个排列组合问题，
    //我们拿5来说事，首先5个人来进行抽奖，有多少种抽法？
    //因为是不放回抽，所以第一个人有5种抽法，
    //第二个人有4种抽法，依次类推
    //总共就是5！ 对有5的阶乘种抽法。这是分母
    //那可想而知分子就是存在多少种情况每个人拿不到自己的名字。
    //这里要应用错排算法。
    //简单的做个介绍
    //当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.
    //那么D(5)=4*[D(3)+D(4)]；依次求得D(3)、D(4),最后D(5)=44
    //所以5个人拿不到奖的概率就是44/120=36.67%
    //这里只是简单介绍，具体想弄明白还是去百度错排算法吧
    //下面看代码
    public static float count(int n) {
        //这个函数用来得到有多少种可能，每个人拿不到自己的名字，
        //也就是得到分子
        if(n==1){
            //n=1的时候返回0
            return 0;
        }
        if(n==2){
            //n=2的时候返回1
            return 1;
        }else{
            //否则就递归。
            return (n-1)*(count(n-1)+count(n-2));
        }
    }
    //下面的函数用来求阶乘，也是递归，最后得到分母
    public static float probability(int n){
       if(n==0){
           //0的阶乘等于1，不用多说吧
           return 1;
       }else{
           //阶乘表示，进行递归
           return n*probability(n-1);
       }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        do {
            int n = sc.nextInt();
            //将得到的分子分母进行相除，就可以得到概率了。
            float result = (count(n)/probability(n))*100;
            System.out.println(String.format("%.2f", result) + "%");
        } while (sc.hasNext());
    }
}

#include<stdio.h>
int main()
{
	long long der[21] = { 0,0,1 }, fun[21] = { 0,1,2 };
	int i, n;
	for (i = 3; i < 21; i++)
	{
		der[i] = (i - 1) * (der[i - 2] + der[i - 1]);
		fun[i] = i*fun[i - 1];
	}
	while (~scanf("%d", &n))
	{
		printf("%.2f%c\n", 1.0*der[n] /fun[n] * 100, '%');
	}
	return 0;
}

思路

n个人取到的都不是自己名字的概率=n个人取到的不是自己名字的序列个数 / n个人可能抽取的所有可能性
因此分两步计算：
1.n个人可能抽取的所有结果:
2.n个人取到的都不是自己名字的序列个数：

• 假设第一个人取到的不是自己的个数为，
• 假设第二个人这个时候拿到了第一个人的名字，那么对于第二个人的名字有两种情况：
  • 第一种：第二个人的名字是被第一个人拿到了，也就是a和b互相拿到了对方的名字，那么对于其他的N-1个人来说互相拿错又是一个子问题 ;
  • 第二种：第二个人的名字没有被第一个人拿到，则剩下的问题是子问题.

#include<iostream>
#include<cmath>
using namespace std;
//1.概率：n个人取到的不是自己名字的序列个数/n个人可能抽取的所有可能性
long long NotSelf(int n)
{
    if (n == 1 )
        return 0;
    if (n == 2)
        return 1;
    return (n - 1) * (NotSelf(n - 1) + NotSelf(n - 2));
}
long long Count(int n)
{
    double s = 1;
    double m = 1;
    for (int i = 2; i <= n; ++i)
    {
        m *= i;
    }
    return m;
}

int main()
{
    int n;
    while (cin >> n)
    {
        double ret = (double)NotSelf(n)/Count(n);         //计算概率
        printf("%2.2f%%\n", ret * 100);
    }
    return 0;
}

解这道题，我们需要明白什么时候才算做都不获奖？全部都不获奖的概率如何计算？
对于什么时候才算做都不获奖，当然是所有人都拿到了别人的名字，没有拿到自己的名字。
全部都不获奖的概率必定是由 n个人都拿错的情况种数 除 n个人拿出的所有排列情况数。
n个人拿出的所有排列情况数显然是n的阶乘。
n个人都拿错的情况种数与上一道题 PAT乙级(Basic Level)练习题 发邮件 是一样的。
假设a的名字没有被a拿到，其他n - 1个人都有可能拿到，即有n - 1种情况。假设b拿到了a的名字，那么对于b的名字有两种情况，

第一种是b的名字被a拿到了，也就是a、b互相拿到了对方的名字，那么对于其他n - 2个人互相拿错又是一个子问题f(n - 2).

第二种是b的名字没有被a拿到，则剩下的问题是子问题f(n - 1).
因此可得递推公式f(n) = (n - 1) * (f(n - 1) + f(n - 2)).

最终得出公式n人都不获奖的概率h(n) = (n - 1) * (f(n - 1) + f(n - 2)) / (n!).

#include <iostream>
(720)#include <math.h>
using namespace std;

int main(int argc, const char * argv[]) {
    int n = 0;
    //fTable[n]记录n个人都拿错（全不获奖）的情况种数，allTable[n]记录所有可能的组合情况n的阶乘
    long long fTable[21] = {0, 0, 1}, allTable[21] = {0, 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", &n) != - 1) {
        //注意%属于控制字符，两个连续的%%才表示真正的%字符
        printf("%4.2lf%%\n", 100 * double(fTable[n]) / allTable[n]);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104688841

#include<stdio.h>
char *p[]={"0%","0%","50.00%","33.33%","37.50%","36.67%","36.81%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%","36.79%"};
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		printf("%s\n",p[n]);
	}
	return 0;
}

#include<iostream>
using namespace std;

int main()
{
    long long d[21] = {0,0,1}; //根据参与抽奖的人数n，计算得到总的错误情况d[n]
    long long f[21] = {0,1,2}; //根据参与抽奖的人数n，计算得到所有的情况 n!
    
    for(int i = 3; i <= 20; i++)
    {
        d[i] = (i-1)*(d[i-1] + d[i-2]);  //错排的递推公式
        f[i] = i * f[i-1];  //阶乘的递推公式
    }
    
    int n;
    while(cin >> n)
    {
        printf("%.2f%%\n",100.00*d[n]/f[n]);  //用100.00来把结果处理成double,.2f保留两位小数
    }
    return 0;
}

// write your code here

import java.util.*;

public class Main{
    private static long f(int n) {
        long ret = 1;
        for (int i = 1; i <= n; i++) ret *= i;
        return ret;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            int n = sc.nextInt();
            //求阶乘
            long h = f(n);
            long[] f = new long[n + 1];
            f[2] = 1;
            for (int i = 3; i <= n; i++) {
                //不可能抽到自己编号的情况数为f(n)=(n-1)*(f(n - 1) + f(n - 2))
                f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
            }
            double ans = 100.0 * f[n] / f(n);
            System.out.printf("%.2f%s\n", ans, "%");
        }
    }
}

import java.util.*;
public class Main{
    public static long notSelf(int n){
        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]);
        }
        return arr[n];
    }
    public static float fun(int n){
        if(n == 0){
            return 1;
        }
        float res = 1;
        for(int i = 1;i <= n;i++){
            res *= i;
        }
        return res;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            float s = (float)notSelf(n)/fun(n);
            System.out.printf("%2.2f%%\n",s*100);
        }
    }
}

import java.util.*;
public class Main {
    static long[] ans = new long[21];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ans[0] = 0;
        ans[1] = 0;
        ans[2] = 1;
        lottery();
        while (scanner.hasNext()) {
            int num = scanner.nextInt();
            double sum1 = factorial(num);
            double sum2 = ans[num];
            double result = (sum2 / sum1) * 100;
            System.out.println(String.format("%.2f", result) + "%");
        }
    }
     private static double factorial(int num) {
        double ans = 1;
        while (num > 0) {
            ans *= num;
            num--;
        }
        return ans;
    }

    private static void lottery() {
        for (int i = 3; i < ans.length; i++) {
            ans[i] = (i - 1) * (ans[i - 1] + ans[i - 2]);
        }
    }
}

 
// write your code here
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            if (n == 1)
                System.out.println("00.00%");
            else if (n == 2)
                System.out.println("50.00%");
            else if (n == 3)
                System.out.println("33.33%");
            else if (n == 4)
                System.out.println("37.50%");
            else if (n == 5)
                System.out.println("36.67%");
            else if (n == 6)
                System.out.println("36.81%");
            else if (n == 7)
                System.out.println("36.79%");
            else if (n == 8)
                System.out.println("36.79%");
            else if (n == 9)
                System.out.println("36.79%");
            else if (n == 10)
                System.out.println("36.79%");
            else if (n == 11)
                System.out.println("36.79%");
            else if (n == 12)
                System.out.println("36.79%");
            else if (n == 13)
                System.out.println("36.79%");
            else if (n == 14)
                System.out.println("36.79%");
            else if (n == 15)
                System.out.println("36.79%");
            else if (n == 16)
                System.out.println("36.79%");
            else if (n == 17)
                System.out.println("36.79%");
            else if (n == 18)
                System.out.println("36.79%");
            else if (n == 19)
                System.out.println("36.79%");
            else if (n == 20)
                System.out.println("36.79%");
        }
    }
}