- 2021-10-29 20:53
*views 21*- Algorithm practice
- probability theory
- Blue Bridge Cup
- algorithm

This question is 10 New questions added in January , There are no answers online , Label is dp dynamic programming , In fact, I think we can do it without dynamic programming , after all python Is a function for finding the number of combinations , Let's take a look .

test questions Algorithm training seal

Resource constraints

time limit ：1.0s Memory limit ：256.0MB

Problem description

share n A pattern seal , The probability of occurrence of each pattern is the same . Small A bought m Zhang seal , Seeking small A Gather together n Probability of seal .

Input format

Two positive integers in a row n and m

Output format

A real number P Indicates the answer , retain 4 Decimal place .

sample input

2 3

sample output

0.7500

Data scale and agreement

1≤n,m≤20

Problem solving ideas ：

In fact, it is a very basic probability problem , have n Kind of seal , bought m individual ; In fact, it can be transformed into m Put a small ball in n In a box , Unlimited quantity per box , Find the probability of at least one ball in each box , It's not easy to ask , Then convert into （1- Probability that at least one box is empty ）.

The event of setting a box empty is Ai, It can be concluded that ：

……

By compatible n The probability formula of the sum of events can be obtained , The probability that at least one box is empty is ：

So the probability that all boxes have balls （ Probability of collecting seals ） by ：

python realization , The code is as follows ：

n, m = map(int, input().split()) def quick_multi(n, m): #

Counting ,n of m Power , In fact, direct call python The exponentiation function of is also OK , I just want to practice res = 1 while m > 0: if m & 1: res *=

n n *= n m = m >> 1 return res def compose_dp(num): # Dynamic programming for combination number , utilize C(n,m) =

C(n-1, m) + C(n-1, m-1) You can find them one by one #

All initialized arrays are 1, And there will be one more row and one more column , As m=1 or n=1 Use in calculation , During operation C(n,m) It corresponds to the array dp_comb[n][m] dp_comb = [[1

for i in range(num + 1)] for j in range(num + 1)] #

The line serial number is set as n, The column number is set as m, from n Select from elements m Come out and combine ,m==n Shi Wei 1 for n in range(2, num + 1): for m in

range(1, n): dp_comb[n][m] = dp_comb[n-1][m] + dp_comb[n-1][m-1] #

Although we built from C(0,0) reach C(num,num) All combinations of possible , But this question will only be used C(num,1) reach C(num,num-1) return dp_comb

def probability(n, m): if n > m: # If you don't buy many kinds, you can't collect them prob = 0.0 else: # If you buy more than varieties

# Calculate the probability that at least one seal is not assembled p, use 1-p That is, the probability that all seals are assembled if n == 1: prob = 1.0 else: #

The combination number array of dynamic programming obtained first （ Just take the last line ） dp_comb = compose_dp(n)[n] #print(dp_comb) p = 0 for

i in range(1, n): p += dp_comb[i] * quick_multi((1 - i / n), m) *

quick_multi(-1, i - 1) prob = 1 - p return prob res = probability(n, m)

print('%.4f' % res)

ps： There should also be a way to directly calculate at least one probability for each box , But maybe I'm not in a good mind and I feel too troublesome , Welcome to discuss , improvement !

Technology

- Java242 blogs
- Python241 blogs
- Vue112 blogs
- algorithm96 blogs
- c language93 blogs
- Flow Chart81 blogs
- MySQL71 blogs
- C++64 blogs
- more...

Daily Recommendation

© ioDraw All rights reserved

It is necessary to work alone ： On embedded modular programming , Importance of drive separation computer network - Difference between router and switch Self made card drawing simulator QFont Quick sort （Quick sort） computer network - Agreement and hierarchy PTA— Read numbers （C language ） Two methods 【 Game summary 】2022 Summary of the 13th Blue Bridge Cup Android development Button Control usage details js of indexOf method