Article From:https://www.cnblogs.com/yongh/p/9967578.html

 

This article refers to the book “Sword Finger offer”, the code is in Java language.

More: Sword Finger Offer Java Implementation Collection 

subject

  Throw n dices on the floor. The sum of the points facing the upper side of all dices is s. Input N and print out the probability of all possible values of S.

thinking

  For n dices, to calculate the probability of the sum of each number of points, we know that the total number of throwing n dices is 6 ^ n, so we can calculate the probability of the sum of points only by calculating the sum of a number of points.

  Method 1:Recursion-based method is inefficient

  It is easy to see that the minimum value of the sum of points s is n and the maximum value is 6*n. Therefore, we consider using an array of sizes (6*n-n+1) to store the sum of different points. If the sum of points is x, then the total number of occurrences of points is put into the element of the array with the subscript of x-n.。

  After determining how many times to store the sum of different points, we need to calculate these times. We divide n dices into one dice and N-1 dice, which is 1

Each dice may have 1 to 6 points, and the total points can be calculated from the points of the dice and the points of the N-1 dice behind it; and the N-1 dice behind can be divided into 1 and n-2 points, adding the points of the last dice to the points of the present dice, and then comparing with the points of the remaining n-2 dices.Add and you get the total number of points… That is, it can be implemented recursively. After obtaining the points of the last dice, the total points of several dices can be calculated, so that the number of cases of the total points in the array + 1, can end the traversal.

  Method two:Finding the number of dice points based on the cycle has good time performance.

  Use arrays to store the number of points and occurrences of each dice. Make the number of elements in an array marked N and the number of times n is stored. We set up a cycle, each cycle throws an extra dice, assuming that in a cycle, we know the number of points and occurrences; in the next cycle, we throw a new dice.Dice, then the number of occurrences of the number of points and the sum of n is equal to the sum of occurrences of the previous round of points and the sum of n-1, n-2, n-3, n-4, n-5, n-6. Starting with the first dice, the number of points and occurrences of the N dice can be obtained by cycling n times.

  Here we use two arrays to store the number of points and occurrences of the current cycle and the next cycle, and use them alternately.

 

Test example 

  1.Functional testing (1, 2, 3, 4 dice)

  2.Special Tests (0)

  3.Performance Tests (11)

JavaCode

import java.text.NumberFormat;

//Title: Throw n dices on the ground. The sum of the points facing the upper side of all dices is s. Input n, print out sThe probability of all possible values appearing.Public class DicesProbability {PriVate static final int maxValue = 6;* ** Method 1: Recursive Solution* /Public static void print probabilitiesTy1 (int number) {If (number< =0)Return; / / errorInt [] probabilities = New Int [maxValue*nu]Mber-number+1];// Subscript is i, and the corresponding value represents the total number of occurrences of I + number.// Points from number to maxValue * number, so the array size is 6 * numbEr-number+1For (int I = 0; I & lt; probabilities. length; I + +)Probabilities[i]=0;// Calculating the occurrence of different pointsfrequencyFor (int I = 1; I & lt; = maxValue; i++)CalP (probabilities, number, number-1, i); // First roll of dice, total points can only be 1-mAxValue (that is, 6)Int totalP = (int) Math. pow (maxValue, number); // Total number of occurrences of all casesFor (int i=0; i&)Lt; probabilities. length; i++) {Double ratio = (double) probabilities [i] / total P;NumberFormatFormat = NumberFormat. getPercentInstance ();Format. setMaximum FractionDigits (2); //Set to reserve several decimal placesSSystem. out. println ("sum of points"+ (i + number)+"probability: +format. format (ratio);}}* ** Calculate the number of occurrences of each number of pointsnumber* Param number: total number of dices* Param curNumber: Number of currently remaining dice* Param sum: Total number of dices added up* /PrivatE static void calP (int [] probabilities, int number, int curNumber, int sum) {If (curNumber==0) {Probabilities [sum-number]+; the case of // total sum is stored in the sum-number subscriptReturn;}For (int i=1; i< =m)AxValue; i++)CalP (probabilities, number, curNumber-1, sum + i); // equivalent to the remaining dice less, total points increased.}/ / =============================================================* ** Method 2: Finding the number of dice points based on cycle, which has good time performance* /Public static voidPrint Probability 2 (int number) {If (number< =0)Return; / / errorInt [][] probabilities = neW int [2] [number * maxValue + 1];//[2] represents the alternation of two arrays, and [number * maxValue + 1] refers to the total number of occurrences of points when the number of points is the subscript.//probaAbilities [*] [0] is useless, just to make subscripts correspond to pointsFor (int I = 0; I & lt; 2; I + +) {For (int J = 0; j< number * maxValue; j++){Probabilities [i] [j] = 0;}}For (int I = 1; I & lt; = 6; I ++)Probabilities [0] [i] = 1// What happens to the first diceInt flag=0;For (int curNumber = 2; curNumber & lt; = number; curNumber ++) {//currentThe first few dice.For (int I = 0; I & lt; curNumber; I ++)Probabilities [1-flag] [i]= 0; // Zero of previous dataFor (Int i = curNumber; i< = curNumber * maxValue; i++) {For (int J = 1; J & lt; = 6 & amp; & amp; J & lt; = i; j + +) {Probabilities [1-flag] [i]+ = probabilities [flag] [i-j];}}Flag=1-flag;}Int totalP = (int) Math. pow (maxValue, number); // Total number of occurrences of all casesFor (int I = number; I & lt; = numb)Er*6; i++) {Double ratio = (double) probabilities [flag] [i] / total P;NumberFormat format = NumbErFormat. getPercentInstance ();Format. setMaximum FractionDigits (8); //Set to reserve several decimal placesSystem.out.prinTLN ("sum of points"+ (i + number) +"probability: +format. format (ratio);}}Public static void main (String)[[args] {System. out. println ("================= Method 1===============");For (int I = 0; I & lt; = 3; I + +) {SystEm. out. println ("------- Dice number"+i + "Time---");Print Probability 1 (i);}System. out. println ("- - dice"When the number of children is "+11+"---";Print Probability 1 (11);System. out. println ("================ Method 2==============");For (int I = 0; I & lt; = 3; I + +) {System. out. println ("------- number of dice"+i + "time---");PrintProbability2 (I);}System. out. println ("----- Dice number"+11 + "Time---");Print Probability 1 (11);}}

  

=========Method 1====================When the number of dices is zero - ------------------------------------------------------------------------------------------------------When the number of dices is 1 - ------------------------------------------------------------------------------------------------------
The probability that the sum of points is 1 is:16.66666667%
The probability that the sum of points is 2 is:16.66666667%
The probability that the sum of points is 3 is:16.66666667%
The probability that the sum of points is 4 is:16.66666667%
The probability of the sum of points to 5 is:16.66666667%
The probability that the sum of points is 6 is:16.66666667%
-----When the number of dice is 2 - - -
The probability that the sum of points is 2 is:2.77777778%
The probability that the sum of points is 3 is:5.55555556%
The probability that the sum of points is 4 is:8.33333333%
The probability of the sum of points to 5 is:11.11111111%
The probability that the sum of points is 6 is:13.88888889%
The probability that the sum of points is 7 is:16.66666667%
The probability that the sum of points is 8 is:13.88888889%
The probability that the sum of points is 9 is:11.11111111%
The probability that the sum of points is 10 is:8.33333333%
The probability that the sum of points is 11 is:5.55555556%
The probability that the sum of points is 12 is:2.77777778%
-----When the number of dices is 3 - --------------------------------------------------------------------------------------------------
The probability that the sum of points is 3 is:0.46296296%
The probability that the sum of points is 4 is:1.38888889%
The probability of the sum of points to 5 is:2.77777778%
The probability that the sum of points is 6 is:4.62962963%
The probability that the sum of points is 7 is:6.94444444%
The probability that the sum of points is 8 is:9.72222222%
The probability that the sum of points is 9 is:11.57407407%
The probability that the sum of points is 10 is:12.5%
The probability that the sum of points is 11 is:12.5%
The probability that the sum of points is 12 is:11.57407407%
The probability that the sum of points is 13 is:9.72222222%
The probability that the sum of points is 14 is:6.94444444%
The probability that the sum of points is 15 is:4.62962963%
The probability that the sum of points is 16 is:2.77777778%
The probability that the sum of points is 17 is:1.38888889%
The probability that the sum of points is 18 is:0.46296296%
-----When the number of dices is 11 - - -
The probability that the sum of points is 11 is:0.00000028%
The probability that the sum of points is 12 is:0.00000303%
The probability that the sum of points is 13 is:0.00001819%
The probability that the sum of points is 14 is:0.00007883%
The probability that the sum of points is 15 is:0.00027591%
The probability that the sum of points is 16 is:0.00082774%
The probability that the sum of points is 17 is:0.00220426%
The probability that the sum of points is 18 is:0.00532722%
The probability that the sum of points is 19 is:0.01186118%
The probability of the sum of points is 20:0.02459557%
The probability that the sum of points is 21 is:0.04789041%
The probability that the sum of points is 22 is:0.08811621%
The probability that the sum of points is 23 is:0.15397396%
The probability that the sum of points is 24 is:0.25654646%
The probability that the sum of points is 25 is:0.40891953%
The probability that the sum of points is 26 is:0.6252344%
The probability that the sum of points is 27 is:0.91910173%
The probability that the sum of points is 28 is:1.30143669%
The probability that the sum of points is 29 is:1.77793036%
The probability that the sum of points is 30 is:2.34652097%
The probability that the sum of points is 31 is:2.99533825%
The probability that the sum of points is 32 is:3.70163009%
The probability that the sum of points is 33 is:4.43211149%
The probability that the sum of points is 34 is:5.14496733%
The probability that the sum of points is 35 is:5.79345109%
The probability that the sum of points is 36 is:6.33070903%
The probability that the sum of points is 37 is:6.71518156%
The probability that the sum of points is 38 is:6.91574824%
The probability that the sum of points is 39 is:6.91574824%
The probability that the sum of points is 40 is:6.71518156%
The probability that the sum of points is 41 is:6.33070903%
The probability that the sum of points is 42 is:5.79345109%
The probability that the sum of points is 43 is:5.14496733%
The probability that the sum of points is 44 is:4.43211149%
The probability that the sum of points is 45 is:3.70163009%
The probability that the sum of points is 46 is:2.99533825%
The probability that the sum of points is 47 is:2.34652097%
The probability that the sum of points is 48 is:1.77793036%
The probability that the sum of points is 49 is:1.30143669%
The probability that the sum of points is 50 is:0.91910173%
The probability that the sum of points is 51 is:0.6252344%
The probability that the sum of points is 52 is:0.40891953%
The probability that the sum of points is 53 is:0.25654646%
The probability that the sum of points is 54 is:0.15397396%
The probability of the sum of points and 55 is:0.08811621%
The probability that the sum of points is 56 is:0.04789041%
The probability of the sum of points to 57 is:0.02459557%
The probability that the sum of points is 58 is:0.01186118%
The probability of the sum of points is 59:0.00532722%
The probability that the sum of points is 60 is:0.00220426%
The probability that the sum of points is 61 is:0.00082774%
The probability that the sum of points is 62 is:0.00027591%
The probability of the sum of points is 63:0.00007883%
The probability that the sum of points is 64 is:0.00001819%
The probability that the sum of points is 65 is:0.00000303%
The probability that the sum of points is 66 is:0.00000028%
=========Method 2====================When the number of dices is zero - ------------------------------------------------------------------------------------------------------When the number of dices is 1 - ------------------------------------------------------------------------------------------------------
The probability that the sum of points is 2 is:16.66666667%
The probability that the sum of points is 3 is:16.66666667%
The probability that the sum of points is 4 is:16.66666667%
The probability of the sum of points to 5 is:16.66666667%
The probability that the sum of points is 6 is:16.66666667%
The probability that the sum of points is 7 is:16.66666667%
-----When the number of dice is 2 - - -
The probability that the sum of points is 4 is:2.77777778%
The probability of the sum of points to 5 is:5.55555556%
The probability that the sum of points is 6 is:8.33333333%
The probability that the sum of points is 7 is:11.11111111%
The probability that the sum of points is 8 is:13.88888889%
The probability that the sum of points is 9 is:16.66666667%
The probability that the sum of points is 10 is:13.88888889%
The probability that the sum of points is 11 is:11.11111111%
The probability that the sum of points is 12 is:8.33333333%
The probability that the sum of points is 13 is:5.55555556%
The probability that the sum of points is 14 is:2.77777778%
-----When the number of dices is 3 - --------------------------------------------------------------------------------------------------
The probability that the sum of points is 6 is:0.92592593%
The probability that the sum of points is 7 is:1.85185185%
The probability that the sum of points is 8 is:3.24074074%
The probability that the sum of points is 9 is:5.09259259%
The probability that the sum of points is 10 is:6.94444444%
The probability that the sum of points is 11 is:9.72222222%
The probability that the sum of points is 12 is:11.57407407%
The probability that the sum of points is 13 is:12.5%
The probability that the sum of points is 14 is:12.5%
The probability that the sum of points is 15 is:11.57407407%
The probability that the sum of points is 16 is:9.72222222%
The probability that the sum of points is 17 is:6.94444444%
The probability that the sum of points is 18 is:4.62962963%
The probability that the sum of points is 19 is:2.77777778%
The probability of the sum of points is 20:1.38888889%
The probability that the sum of points is 21 is:0.46296296%
-----When the number of dices is 11 - - -
The probability that the sum of points is 22 is:0.00121693%
The probability that the sum of points is 23 is:0.00298376%
The probability that the sum of points is 24 is:0.00638621%
The probability that the sum of points is 25 is:0.01258472%
The probability that the sum of points is 26 is:0.02324523%
The probability that the sum of points is 27 is:0.04090248%
The probability that the sum of points is 28 is:0.06852398%
The probability that the sum of points is 29 is:0.11056181%
The probability that the sum of points is 30 is:0.17250802%
The probability that the sum of points is 31 is:0.26102196%
The probability that the sum of points is 32 is:0.38391023%
The probability that the sum of points is 33 is:0.54975226%
The probability that the sum of points is 34 is:0.76760849%
The probability that the sum of points is 35 is:1.04620281%
The probability that the sum of points is 36 is:1.39300386%
The probability that the sum of points is 37 is:1.81311477%
The probability that the sum of points is 38 is:2.30801735%
The probability that the sum of points is 39 is:2.87442713%
The probability that the sum of points is 40 is:3.50323763%
The probability that the sum of points is 41 is:4.17879659%
The probability that the sum of points is 42 is:4.87880723%
The probability that the sum of points is 43 is:5.57487572%
The probability that the sum of points is 44 is:6.23383532%
The probability that the sum of points is 45 is:6.8198307%
The probability that the sum of points is 46 is:7.29713005%
The probability that the sum of points is 47 is:7.63343598%
The probability that the sum of points is 48 is:7.80322374%
The probability that the sum of points is 49 is:7.79077491%
The probability that the sum of points is 50 is:7.59241029%
The probability that the sum of points is 51 is:7.21750041%
The probability that the sum of points is 52 is:6.68797654%
The probability that the sum of points is 53 is:6.03632186%
The probability that the sum of points is 54 is:5.3023148%
The probability of the sum of points and 55 is:4.52891823%
The probability that the sum of points is 56 is:3.75794284%
The probability of the sum of points to 57 is:3.02613646%
The probability that the sum of points is 58 is:2.3622405%
The probability of the sum of points is 59:1.78534552%
The probability that the sum of points is 60 is:1.3046269%
The probability that the sum of points is 61 is:0.92032941%
The probability that the sum of points is 62 is:0.62564372%
The probability of the sum of points is 63:0.40903116%
The probability that the sum of points is 64 is:0.25656879%
The probability that the sum of points is 65 is:0.15397644%
The probability that the sum of points is 66 is:0.08811621%
The probability that the sum of points is 67 is:0.04789041%
The probability that the sum of points is 68 is:0.02459557%
The probability that the sum of points is 69 is:0.01186118%
The probability that the sum of points is 70 is:0.00532722%
The probability that the sum of points is 71 is:0.00220426%
The probability that the sum of points is 72 is:0.00082774%
The probability that the sum of points is 73 is:0.00027591%
The probability of the sum of points is 74:0.00007883%
The probability that the sum of points is 75 is:0.00001819%
The probability that the sum of points is 76 is:0.00000303%
The probability that the sum of points is 77 is:0.00000028%

DicesProbability

 

Harvest

  1.intTo get a double type, you need to change one of them to a double type ahead of time.

   For example: double ratio = (double) probabilities [i] / total P;

  2.Output percentage method, using NumberFormat

			NumberFormat format = NumberFormat.getPercentInstance();
			format.setMaximumFractionDigits(8);//Set to reserve several decimal placesSystem. out. println ("sum of points"+ (i + number)+"probability: +format. format (ratio);

  3.The second method, not from the point of view of dice points, but from the sum of points, the sum of points: f (n) = f (n-1) +… F (n-6), very clever.

  4.Alternate two arrays, learn to use the variable flag, flag = 1-flag.

  5.Instead of hard coding the maximum number of dice points to 6, the code is represented by the variable maxValue, which is extensible. In the future, we should also pay attention to whether these quantities can be programmed without hard coding, so as to improve scalability.

  6.In order to improve the ability of mathematical modeling, no matter which way of thinking we take, we should first think of using arrays to store every point of N dices and the number of times they appear.

 

  

  

More: Sword Finger Offer Java Implementation Collection 

Leave a Reply

Your email address will not be published. Required fields are marked *