package com.dengzm.lib;
import java.text.NumberFormat;
/**
* @Description 060 n个骰子的点数
* 把n个骰子扔在地上，所有骰子朝上的一面的点数之和为s。输入n，打印出所有可能出现的值出现的概率
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi060 {
private static int MAX_VALUE = 6; // 骰子的最大值
public static void main(String[] args) {
System.out.println("解法一");
printProbability(10);
System.out.println();
System.out.println("解法二");
printProbability2(10);
}
/**
* 解法一：基于递归求骰子点数，时间效率不高
* 想求出n个骰子的点数和，可以先把n个骰子分为两堆，第一堆只有一个，另一堆有n-1个。
* 单独的一堆，可能出现1～6的点数，并与另一堆的点数来计算点数和。
* n-1的堆，通过递归，再分出1和n-2，最后递归的结束条件为只剩下一个骰子
*
* @param n number of touzi
*/
private static void printProbability(int n) {
if (n < 1) {
return;
}
int maxSum = n * MAX_VALUE;
// 可能出现的值：n —— 6n，长度为 6n-n+1
int[] probabilities = new int[maxSum - n + 1];
for (int i = 0; i < maxSum - n + 1; i ++) {
probabilities[i] = 0;
}
probability(n, probabilities);
double total = Math.pow(MAX_VALUE, n);
for (int i = 0; i < maxSum - n + 1; i ++) {
double ratio = probabilities[i] / total;
NumberFormat format = NumberFormat.getPercentInstance();
format.setMaximumFractionDigits(10);
System.out.println((i+n) + " : " + format.format(ratio));
}
}
/**
* 第一个骰子，对应1～MAX_VALUE，分别求对应出现的次数
*
* @param n number
* @param probabilities 出现的次数
*/
private static void probability(int n, int[] probabilities) {
for (int i = 1; i <= MAX_VALUE; i ++) {
probability(n, n, i, probabilities);
}
}
/**
* 统计每种情况出现的次数
*
* @param original 一共有多少个
* @param current 目前分堆有多少个
* @param sum 目前的和是多少
* @param probabilities 可能出现的次数
*/
private static void probability(int original, int current, int sum, int[] probabilities) {
if (current == 1) {
// 只剩下一个骰子，与上面函数中第一个骰子对应
probabilities[sum - original] ++;
} else {
for (int i = 1; i <= MAX_VALUE; i ++) {
// 再次分堆，去掉一个骰子，将对应的数值增加到sum上
probability(original, current - 1, i + sum, probabilities);
}
}
}
/**
* 解法二：基于循环求骰子点数，时间性能好
* 用两个数组来储存骰子的每个总数出现的次数
* 在一轮循环中，第一个数组中的第n个数字表示骰子和为n出现的次数；
* 在下一轮循环中，我们增加一个新的骰子，此时和为n的骰子出现的次数应该等于n-1、n-2、...、n-6出现的次数的总和
*
* @param n number of touzi
*/
private static void printProbability2(int n) {
if (n < 1) {
return;
}
// 两个数组，循环赋值
int[][] probabilities = new int[2][n * MAX_VALUE + 1];
for (int i = 0; i < n * MAX_VALUE + 1; i ++) {
probabilities[0][i] = 0;
probabilities[1][i] = 0;
}
// 标识当前使用的数组为哪个
int flag = 0;
// 第一个骰子，每个数字出现的次数为1
for (int i = 1; i <= MAX_VALUE; i ++) {
probabilities[flag][i] = 1;
}
// 增加骰子
for (int k = 2; k <= n; k ++) {
// 将另一个数组先清空
for (int i = 0; i < k; i ++) {
probabilities[1 - flag][i] = 0;
}
// 增加一个新的骰子，此时和为n的骰子出现的次数应该等于n-1、n-2、...、n-6出现的次数的总和
for (int i = k; i <= MAX_VALUE * k; i ++) {
probabilities[1 - flag][i] = 0;
for (int j = 1; j <= i && j <= MAX_VALUE; j ++) {
probabilities[1 - flag][i] += probabilities[flag][i - j];
}
}
// 切换数组
flag = 1 - flag;
}
double total = Math.pow(MAX_VALUE, n);
for (int i = n; i < MAX_VALUE * n + 1; i ++) {
double ratio = probabilities[flag][i] / total;
NumberFormat format = NumberFormat.getPercentInstance();
format.setMaximumFractionDigits(10);
System.out.println((i) + " : " + format.format(ratio));
}
}
}
Result
解法一
10 : 0.0000016538%
11 : 0.0000165382%
12 : 0.0000909599%
13 : 0.0003638398%
14 : 0.0011824793%
15 : 0.003310942%
16 : 0.0082608168%
17 : 0.0187542867%
18 : 0.0392946959%
19 : 0.076770193%
20 : 0.1409515297%
21 : 0.244665712%
22 : 0.4034073529%
23 : 0.6341892697%
24 : 0.9535330959%
25 : 1.374659446%
26 : 1.9041554736%
27 : 2.5386755068%
28 : 3.2623693617%
29 : 4.04573294%
30 : 4.8464367914%
31 : 5.6124104822%
32 : 6.2870438508%
33 : 6.8158105451%
34 : 7.1532719383%
35 : 7.2692805975%
36 : 7.1532719383%
37 : 6.8158105451%
38 : 6.2870438508%
39 : 5.6124104822%
40 : 4.8464367914%
41 : 4.04573294%
42 : 3.2623693617%
43 : 2.5386755068%
44 : 1.9041554736%
45 : 1.374659446%
46 : 0.9535330959%
47 : 0.6341892697%
48 : 0.4034073529%
49 : 0.244665712%
50 : 0.1409515297%
51 : 0.076770193%
52 : 0.0392946959%
53 : 0.0187542867%
54 : 0.0082608168%
55 : 0.003310942%
56 : 0.0011824793%
57 : 0.0003638398%
58 : 0.0000909599%
59 : 0.0000165382%
60 : 0.0000016538%
解法二
10 : 0.0000016538%
11 : 0.0000165382%
12 : 0.0000909599%
13 : 0.0003638398%
14 : 0.0011824793%
15 : 0.003310942%
16 : 0.0082608168%
17 : 0.0187542867%
18 : 0.0392946959%
19 : 0.076770193%
20 : 0.1409515297%
21 : 0.244665712%
22 : 0.4034073529%
23 : 0.6341892697%
24 : 0.9535330959%
25 : 1.374659446%
26 : 1.9041554736%
27 : 2.5386755068%
28 : 3.2623693617%
29 : 4.04573294%
30 : 4.8464367914%
31 : 5.6124104822%
32 : 6.2870438508%
33 : 6.8158105451%
34 : 7.1532719383%
35 : 7.2692805975%
36 : 7.1532719383%
37 : 6.8158105451%
38 : 6.2870438508%
39 : 5.6124104822%
40 : 4.8464367914%
41 : 4.04573294%
42 : 3.2623693617%
43 : 2.5386755068%
44 : 1.9041554736%
45 : 1.374659446%
46 : 0.9535330959%
47 : 0.6341892697%
48 : 0.4034073529%
49 : 0.244665712%
50 : 0.1409515297%
51 : 0.076770193%
52 : 0.0392946959%
53 : 0.0187542867%
54 : 0.0082608168%
55 : 0.003310942%
56 : 0.0011824793%
57 : 0.0003638398%
58 : 0.0000909599%
59 : 0.0000165382%
60 : 0.0000016538%
Process finished with exit code 0
package com.dengzm.lib;
import java.util.Arrays;
/**
* @Description 061 扑克牌中的顺子
* 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的
* 2-10为数字本身，A为1，JQK为11，12，13，大小王可以看成任意数字
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi061 {
public static void main(String[] args) {
int[] data1 = new int[] {1,2,3,4,5};
int[] data2 = new int[] {1,2,3,3,5};
int[] data3 = new int[] {1,2,3,4,6};
int[] data4 = new int[] {0,2,3,4,5};
int[] data5 = new int[] {0,1,2,4,5};
System.out.println(isContinuous(data1));
System.out.println(isContinuous(data2));
System.out.println(isContinuous(data3));
System.out.println(isContinuous(data4));
System.out.println(isContinuous(data5));
}
/**
* 通过计算数组中空隙的数量与0的数量，比较大小
*
* @param numbers pokers
* @return is continuous
*/
private static boolean isContinuous(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
// 将数组排序
Arrays.sort(numbers);
int numberOfZero = 0;
int numberOfGap = 0;
// 统计出0的数量，同时也是非零数字开始的下标
for (int i = 0; i < numbers.length && numbers[i] == 0; i ++) {
numberOfZero ++;
}
int small = numberOfZero;
int big = small + 1;
while (big < numbers.length) {
// 有相同的牌时，为对子，不是顺子
if (numbers[small] == numbers[big]) {
return false;
}
numberOfGap += numbers[big] - numbers[small] - 1;
small = big ++;
}
return numberOfGap <= numberOfZero;
}
}
package com.dengzm.lib;
import java.util.LinkedList;
/**
* @Description 062 圆圈中最后剩下的数字
* 0～n-1，共n个数字，排成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字，求出这个圆圈里剩下的最后一个数字
*
* Created by deng on 2019/11/1.
*/
public class Jianzhi062 {
public static void main(String[] args) {
System.out.println(lastRemaining(5, 3));
System.out.println(lastRemaining(15, 13));
System.out.println(lastRemaining2(5, 3));
System.out.println(lastRemaining2(15, 13));
}
/**
* 解法一：环形链表模拟圆圈
*
* @param n num
* @param m delete position
* @return last remaining number
*/
private static int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
// 圆圈——双向链表
// 这里参考了网上的方式，并不需要使用循环链表，只需要计算出需要删除的节点下标即可
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i ++) {
queue.addLast(i);
}
// 上一次删除的位置
int removeIndex = 0;
while (queue.size() > 1) {
removeIndex = (removeIndex + m - 1) % queue.size();
queue.remove(removeIndex);
}
return queue.getFirst();
}
/**
* 解法二：数学公式
* 首先，定义一个关于n和m的方程f(n,m)，表示每次在n个数字0～n-1中删除第m个数字最后剩下的数字
* 在n个数字中，第一个被删除的数字是(m-1)%n，记为k，则第二次删除开始时，从k+1开始，序列为k+1, ..., n-1, 0, 1,..., k-1
* 将该序列与0～n-2进行映射可得到映射函数p(x)=(x-k-1)%n。该函数的逆映射为p-1(x)=(x+k+1)%n
* 映射后的序列与最初的序列类似，记为f(n-1,m)。将删除第一个数字后的函数代入，
* 得到f(n,m)=f'(n-1,m)=p-1[f(n-1,m)]=[f(n-1,m)+k+1]%n,把k=(m-1)%n代入得到，f(n,m)=[f(n-1,m)+m]%n
*
* 经过上面的分析，得到了递归公式：
* f(n,m) = 0 (n = 1)
* = [f(n-1,m) + m] % n (n > 1)
*
* @param n num
* @param m delete position
* @return last remaining number
*/
private static int lastRemaining2(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
int last = 0;
for (int i = 2; i <= n; i ++) {
last = (last + m) % i;
}
return last;
}
}
