8000 完成剑指offer色子问题。 · ssjssh/javaalgorithm@c23e66d · GitHub
[go: up one dir, main page]
Skip to content

Commit c23e66d

Browse files
author
shengshijun
committed
完成剑指offer色子问题。
1 parent e3de22f commit c23e66d

File tree

2 files changed

+77
-2
lines changed

2 files changed

+77
-2
lines changed

‎src/main/java/ssj/algorithm/math/MathUtil.java

Lines changed: 66 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,7 @@ private static double powCore(double base, int exponent) {
8686
return result;
8787
}
8888

89-
private static boolean doubleEqual(double one, double two) {
89+
public static boolean doubleEqual(double one, double two) {
9090
return Math.abs(one - two) < 0.0000001;
9191
}
9292

@@ -404,6 +404,7 @@ private static boolean checkUnique(int[] arr, int ele) {
404404

405405
/**
406406
* 在一个排好序的int数组中查找连续子数组其和为指定的值。
407+
*
407408
* @param arr
408409
* @param value
409410
* @return
@@ -432,4 +433,68 @@ public static List<Tuple2<Integer, Integer>> findSumInOrder(int[] arr, int value
432433
}
433434
return result;
434435
}
436+
437+
/**
438+
* 从投色子问题来，一个色子有6个面，丢n个色子和的每种可能性和概率
439+
*
440+
* @param n
441+
* @param max
442+
* @return
443+
*/
444+
public static double[] probability(int n, int max) {
445+
Preconditions.checkArgument(n >= 1);
446+
Preconditions.checkArgument(max > 0);
447+
448+
int[] sum_count = probabilitySumCount(n, max);
449+
double sum = Math.round(pow(max, n));
450+
double[] result = new double[sum_count.length];
451+
for (int i = 0; i < sum_count.length; i++) {
452+
result[i] = sum_count[i] / sum;
453+
}
454+
return result;
455+
}
456+
457+
public static int[] probabilitySumCount(int n, int max) {
458+
Preconditions.checkArgument(n< 8000 /span> >= 1);
459+
Preconditions.checkArgument(max > 0);
460+
461+
int[] result = new int[n * max + 1];
462+
int[] result_tmp = new int[result.length];
463+
for (int i = 1; i <= max; i++) {
464+
result_tmp[i] = 1;
465+
result[i] = 1;
466+
}
467+
468+
for (int i = 1; i < n; i++) {
469+
for (int j = 1; j < result_tmp.length; j++) {
470+
result[j] = 0;
471+
for (int k = 1; k <= max && k < j; k++) {
472+
result[j] += result_tmp[j - k];
473+
}
474+
}
475+
476+
int[] tmp = result_tmp;
477+
result_tmp = result;
478+
result = tmp;
479+
}
480+
return result_tmp;
481+
}
482+
483+
public static double sum(double[] arr) {
484+
Preconditions.checkNotNull(arr);
485+
double result = 0;
486+
for (double num : arr) {
487+
result += num;
488+
}
489+
return result;
490+
}
491+
492+
public static int sum(int[] arr) {
493+
Preconditions.checkNotNull(arr);
494+
int result = 0;
495+
for (double num : arr) {
496+
result += num;
497+
}
498+
return result;
499+
}
435500
}

‎src/test/java/ssj/algorithm/math/MathUtilTest.java

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,8 @@
33
import org.junit.Test;
44
import ssj.algorithm.lang.Tuple2;
55

6+
import java.util.Arrays;
7+
68
import static org.junit.Assert.*;
79

810
/**
@@ -89,6 +91,14 @@ public void testUniqueInt() {
8991
@Test
9092
public void testFindSumInOrder() {
9193
System.out.println(MathUtil.findSumInOrder(new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 15));
92-
System.out.println(MathUtil.findSumInOrder(new int[]{1,4,7,8,11}, 20));
94+
System.out.println(MathUtil.findSumInOrder(new int[]{1, 4, 7, 8, 11}, 20));
95+
}
96+
97+
@Test
98+
public void testProbabilitySumCount() {
99+
System.out.println(Arrays.toString(MathUtil.probabilitySumCount(2, 6)));
< 4F06 /td>
100+
System.out.println(Arrays.toString(MathUtil.probability(2, 6)));
101+
System.out.println(MathUtil.sum(MathUtil.probabilitySumCount(11, 6)));
102+
System.out.println(MathUtil.sum(MathUtil.probabilitySumCount(2, 6)));
93103
}
94104
}

0 commit comments

Comments
 (0)
0