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