蓝桥杯 试题 算法训练 印章 java实现

本文主要是介绍蓝桥杯 试题 算法训练 印章 java实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、试题 算法训练 印章    dp题(动态规划题)
     
    资源限制
    时间限制：1.0s   内存限制：256.0MB
    问题描述
    　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
    输入格式
    　　一行两个正整数n和m
    输出格式
    　　一个实数P表示答案，保留4位小数。
    样例输入
    2 3
    样例输出
    0.7500
    数据规模和约定
    　　1≤n，m≤20

    思路：dp题一般使用数组寻找规律，一维数组，二维数组都很常见，甚至是三维n维
            此题建议使用二维数组
          1、当m<n时几率为0，当n=1时m>n几率为1
          2、当n>1，m>n时，开始寻找规律
          建立数组dp[m+1][n+1]因为要使用到d[m][n]所以进行+1操作
          当我们买了i张印章时集齐1种的概率是不是(1/n)^(i-1)（此时n种印章）
          当我们买了i张印章时要集齐j种是不是要分情况？
          1、买到重复的时候
          2、没有买到重复的时候？

          当买到重复的时候是不是意味着我还要抽到之前抽到过的某一种印章？
          此时我已经有了j种那么此时我购买到重复的概率是j/n
          此时我在和买i-1张集齐j种的概率相乘才意味着我在买i张的时候集齐了j种
          dp[i][j]=d[i-1][j]*(j/n)
          此时为一种概率

          再看第二种不买重复的
          即此时我买i-1张的时候有了j-1种印章，我要在买i张的时候买到不是重复的概率是(n-(j-1))/n
          在与之前的概率进行相乘，才能意味着我在买i张的时候集齐了j种

          把两者相加，便是买到第i张集齐第j种的概率
          即d[i][j]可以算出来，那么当i=m,j=n时是不是也可以算出来？

          下面上代码：

import java.util.Scanner;

public class YinZ {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int m=s.nextInt();
        double p=1.0/n;

        double[][] b=new double[m+1][n+1];
        if (n==1){  //当n=1时m>n几率为1
            b[m][n]=1;
            System.out.printf("%.4f",b[m][n]);
            return;
        }
        if (n>1&&m<n){ //当m<n时几率为0
            b[m][n]=0;
            System.out.printf("%.4f",b[m][n]);
            return;
        }
        for (int i = 1; i <=m; i++) {
            for (int j = 1; j <=n; j++) {
                if (i<j) b[i][j]=0;       //当m<n时几率为0
                if (j==1){
                    b[i][j]=Math.pow(p,i-1);        //当i张集齐1种的概率
                }else {
                    b[i][j]=b[i-1][j]*(j*1.0/n)+b[i-1][j-1]*((n-j+1)*1.0/n);        //当i张集齐j种的概率
                }

            }

        }

        System.out.printf("%.4f",b[m][n]);

    }
}

可能会有不足，望指正！

这篇关于蓝桥杯 试题 算法训练 印章 java实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！