题目
一共八个村庄，已有前一天所在村庄将要去其他村庄的概率，有矩阵表示
int[][] rule = { //定义规则
{0,1,0,1,1,0,0,0}, //A
{1,0,1,0,0,1,0,0}, //B
{0,1,0,1,0,0,1,0}, //C
{1,0,1,0,0,0,0,1}, //D
{1,0,0,0,0,1,0,1}, //E
{0,1,0,0,1,0,1,0}, //F
{0,0,1,0,0,1,0,1}, //G
{0,0,0,1,1,0,1,0} //H
};由玩家给出第一天所去村庄及将要推测的天数，输出程序根据已有数据的推测及概率。
解析（不带概率）
定义变量
static String village = "ABCDEFGH"; //定义八个村庄
static int[] advance = {0,0,0,0,0,0,0,0}; //可能去的村庄
static int[][] rule = { //定义规则
{0,1,0,1,1,0,0,0}, //A
{1,0,1,0,0,1,0,0}, //B
{0,1,0,1,0,0,1,0}, //C
{1,0,1,0,0,0,0,1}, //D
{1,0,0,0,0,1,0,1}, //E
{0,1,0,0,1,0,1,0}, //F
{0,0,1,0,0,1,0,1}, //G
{0,0,0,1,1,0,1,0} //H
};village中的八个字顺序正好对应二维数组中可能每个村庄可能去其他村庄的序号advance表示前一天可能去的村庄
main函数
public static void main(String[] args) {
System.out.println("Please input the Village Mark (A~H):\t"); //输入在哪个村子
Scanner sc = new Scanner(System.in);
String startVillage = sc.nextLine().trim(); //B
System.out.println("\nPlease input the days of the one walks(number)"); //输入一共预测几天
int dayNo = sc.nextInt(); //20
start(startVillage,dayNo); //执行函数
}输入第一天所在村庄及想要预测的天数，开始预测
start函数
/**
* @Author fghwett
* @DataTime 2019-05-21T21:59:54+0800
* @param startVillage 开始的村庄的名字
* @param dayNo 一共预测几天
*/
public static void start(String startVillage, int dayNo) {
int villageNumber = village.indexOf(startVillage);
advance[villageNumber] = 1;
for (int i = 1; i <= dayNo; i++) {
advance = forecast(advance);
output(i);
}
}将第一天去的村庄标记为“1”，并开始预测。
每预测一次，输出一次预测结果。
forecast预测函数
/**
* @Author fghwett
* @DataTime 2019-05-21T22:01:10+0800
* @param adva 需要预测的范围
* @return 预测完的范围
*/
public static int[] forecast(int[] adva) {
int[] tmpAdvance = {0,0,0,0,0,0,0,0};
for (int j = 0; j < 8; j++) {
if (adva[j] == 1) {
for (int i = 0; i < 8; i++) {
if (rule[j][i] == 1 && tmpAdvance[i] != 1) {
//System.out.print(village.charAt(i) + "\t");
tmpAdvance[i] = 1;
}
}
}
}
return tmpAdvance;
}先定义一个临时变量tmpAdvance存放预测到村庄
对每个前一天可能在的村庄进行预测，对于已经预测到的村庄，如果临时变量中不存在，就将预测到的村庄放入其中。
返回临时变量及预测到的村庄，作为下一次需要预测的变量。
output输出函数
/**
* @Author fghwett
* @DataTime 2019-05-21T22:07:29+0800
* @param num 输出第几天的预测
*/
public static void output(int num) {
System.out.print("The " + num + " day:\t");
for (int j = 0; j < 8; j++) {
if (advance[j] == 1) {
System.out.print(village.charAt(j) + "\t");
}
}
System.out.println("");
}每次预测完就输出（因为advance值一直在变）。
完整代码（无概率）
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
class VillageRoot {
static String village = "ABCDEFGH"; //定义八个村庄
static int[] advance = {0,0,0,0,0,0,0,0}; //可能去的村庄
static int[][] rule = { //定义规则
{0,1,0,1,1,0,0,0}, //A
{1,0,1,0,0,1,0,0}, //B
{0,1,0,1,0,0,1,0}, //C
{1,0,1,0,0,0,0,1}, //D
{1,0,0,0,0,1,0,1}, //E
{0,1,0,0,1,0,1,0}, //F
{0,0,1,0,0,1,0,1}, //G
{0,0,0,1,1,0,1,0} //H
};
public static void main(String[] args) {
System.out.println("Please input the Village Mark (A~H):\t"); //输入在哪个村子
Scanner sc = new Scanner(System.in);
String startVillage = sc.nextLine().trim(); //B
System.out.println("\nPlease input the days of the one walks(number)"); //输入一共预测几天
int dayNo = sc.nextInt(); //20
start(startVillage,dayNo);
}
/**
* @Author fghwett
* @DataTime 2019-05-21T21:59:54+0800
* @param startVillage 开始的村庄的名字
* @param dayNo 一共预测几天
*/
public static void start(String startVillage, int dayNo) {
int villageNumber = village.indexOf(startVillage);
advance[villageNumber] = 1;
for (int i = 1; i <= dayNo; i++) {
advance = forecast(advance);
output(i);
}
}
/**
* @Author fghwett
* @DataTime 2019-05-21T22:01:10+0800
* @param adva 需要预测的范围
* @return 预测完的范围
*/
public static int[] forecast(int[] adva) {
int[] tmpAdvance = {0,0,0,0,0,0,0,0};
for (int j = 0; j < 8; j++) {
if (adva[j] == 1) {
for (int i = 0; i < 8; i++) {
if (rule[j][i] == 1 && tmpAdvance[i] != 1) {
//System.out.print(village.charAt(i) + "\t");
tmpAdvance[i] = 1;
}
}
}
}
return tmpAdvance;
}
/**
* @Author fghwett
* @DataTime 2019-05-21T22:07:29+0800
* @param num 输出第几天的预测
*/
public static void output(int num) {
System.out.print("The " + num + " day:\t");
for (int j = 0; j < 8; j++) {
if (advance[j] == 1) {
System.out.print(village.charAt(j) + "\t");
}
}
System.out.println("");
}
}解析（带概率）
思路
只需要加一个概率就可以。我的思路是把二维数组中的“1”变成概率，节省空间。
但是问题随之而来。
概率用什么表示
可选小数和分数，但是概率是1/3，如果用小数，最终的结果将不准。
所以我采用了分数的形式。
java没有分数的定义
可以用过构造对象的形式来构建分数，可参考我之前发的java分数构造
注意事项
- 所有的int都改为fraction，用来表示概率
- 计算概率时需要逻辑清晰
完整代码（有概率）
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;
class VillageRootProbability {
static Fraction f1 = new Fraction(1, 3);
static Fraction f2 = new Fraction(0, 1);
static Fraction f3 = new Fraction(1, 1);
static String village = "ABCDEFGH"; //定义八个村庄
static Fraction[] advance = {f2,f2,f2,f2,f2,f2,f2,f2}; //可能去的村庄
static int[][] rule = { //定义规则
{0,1,0,1,1,0,0,0}, //A
{1,0,1,0,0,1,0,0}, //B
{0,1,0,1,0,0,1,0}, //C
{1,0,1,0,0,0,0,1}, //D
{1,0,0,0,0,1,0,1}, //E
{0,1,0,0,1,0,1,0}, //F
{0,0,1,0,0,1,0,1}, //G
{0,0,0,1,1,0,1,0} //H
};
static Fraction[][] probability = { //更改标记为概率
{f2,f1,f2,f1,f1,f2,f2,f2}, //A
{f1,f2,f1,f2,f2,f1,f2,f2}, //B
{f2,f1,f2,f1,f2,f2,f1,f2}, //C
{f1,f2,f1,f2,f2,f2,f2,f1}, //D
{f1,f2,f2,f2,f2,f1,f2,f1}, //E
{f2,f1,f2,f2,f1,f2,f1,f2}, //F
{f2,f2,f1,f2,f2,f1,f2,f1}, //G
{f2,f2,f2,f1,f1,f2,f1,f2} //H
};
public static void main(String[] args) {
System.out.println("Please input the Village Mark (A~H):\t"); //输入在哪个村子
Scanner sc = new Scanner(System.in);
String startVillage = sc.nextLine().trim(); //B
System.out.println("\nPlease input the days of the one walks(number)"); //输入一共预测几天
int dayNo = sc.nextInt(); //20
start(startVillage,dayNo);
}
/**
* @Author fghwett
* @DataTime 2019-05-21T21:59:54+0800
* @param startVillage 开始的村庄的名字
* @param dayNo 一共预测几天
*/
public static void start(String startVillage, int dayNo) {
int villageNumber = village.indexOf(startVillage); //1
advance[villageNumber] = f3;
for (int i = 1; i <= dayNo; i++) {
advance = forecast(advance);
output(i);
}
}
/**
* @Author fghwett
* @DataTime 2019-05-21T22:01:10+0800
* @param adva 需要预测的范围
* @return 预测完的范围
*/
public static Fraction[] forecast(Fraction[] adva) { //advance = {f2,f3,f2,f2,f2,f2,f2,f2};
Fraction[] tmpAdvance = {f2,f2,f2,f2,f2,f2,f2,f2};
for (int j = 0; j < 8; j++) {
if (adva[j] != f2) {
for (int i = 0; i < 8; i++) {
if (probability[j][i] != f2) {
//System.out.print(village.charAt(i) + "\t");
tmpAdvance[i] = tmpAdvance[i].add(adva[j].multiply(probability[j][i])).simplify();
}
}
}
}
return tmpAdvance;
}
/**
* @Author fghwett
* @DataTime 2019-05-21T22:07:29+0800
* @param num 输出第几天的预测
*/
public static void output(int num) {
System.out.print("The " + num + " day:\t");
for (int j = 0; j < 8; j++) {
if (advance[j] != f2) {
System.out.print(village.charAt(j) + "的概率：" + advance[j] + "\t");
}
}
System.out.println("");
}
}
class Fraction {
private Integer numerator; // 分子;
private Integer denominator; // 分母
/**
* 构造器
*/
public Fraction() {
}
public Fraction(Integer numerator, Integer denominator) {
this.numerator = numerator;
this.denominator = denominator;
}
public Integer getDenominator() {
return denominator;
}
public void setDenominator(Integer denominator) {
this.denominator = denominator;
}
public Integer getNumerator() {
return numerator;
}
public void setNumerator(Integer numerator) {
this.numerator = numerator;
}
/**
* 求最大公约数
*
* @return
*/
private int getGCD(int a, int b) {
int max = Math.max(a, b);
int min = Math.min(a, b);
int mod = max % min;
if (mod == 0) {
return min;
} else {
return this.getGCD(mod, min);
}
}
/**
* 简化和约分
*
* @return
*/
public Fraction simplify() {
// 格式化
if (this.numerator == 0) {
this.denominator = null;
return this;
} else if (this.denominator * this.numerator > 0 && this.denominator < 0) {
this.denominator = Math.abs(this.denominator);
this.numerator = Math.abs(this.numerator);
return this;
} else if (this.denominator < 0) {
this.denominator = Math.abs(this.denominator);
this.numerator = -this.numerator;
return this;
}
// 约分
int gcd = this.getGCD(Math.abs(denominator), Math.abs(numerator));
if (gcd == 1) {
return this;
} else {
this.denominator = this.denominator / gcd;
this.numerator = this.numerator / gcd;
return this;
}
}
/**
* 加法
*
* @param fraction
* @return
*/
public Fraction add(Fraction fraction) {
Integer resultDenominator = Math.abs(this.denominator) * Math.abs(fraction.getDenominator());
Integer resultNumerator = this.numerator * fraction.getDenominator()
+ this.denominator * fraction.getNumerator();
Fraction result = new Fraction(resultNumerator, resultDenominator);
return result.simplify();
}
/**
* 减法
*
* @param fraction
* @return
*/
public Fraction minus(Fraction fraction) {
Integer resultDenominator = Math.abs(this.denominator) * Math.abs(fraction.getDenominator());
Integer resultNumerator = this.numerator * fraction.getDenominator()
- this.denominator * fraction.getNumerator();
Fraction result = new Fraction(resultNumerator, resultDenominator);
return result.simplify();
}
/**
* 乘法
*
* @param fraction
* @return
*/
public Fraction multiply(Fraction fraction) {
Fraction result = null;
if (this.numerator == 0 || fraction.numerator == 0) {
result = new Fraction(0, null);
}
Integer resultDenominator = this.denominator * fraction.getDenominator();
Integer resultNumerator = this.numerator * fraction.getNumerator();
result = new Fraction(resultNumerator, resultDenominator);
return result.simplify();
}
/**
* 除法
*
* @param fraction
* @return
*/
public Fraction divide(Fraction fraction) {
Fraction result = null;
if (this.numerator == 0) {
result = new Fraction(0, null);
}
Integer resultDenominator = this.denominator * fraction.getNumerator();
Integer resultNumerator = this.numerator * fraction.getDenominator();
result = new Fraction(resultNumerator, resultDenominator);
return result.simplify();
}
@Override
public String toString() {
// return "[分子]" + this.numerator + "-[分母]" + this.denominator;
return this.numerator + "/" + this.denominator;
}
}存在问题
- 分数形式，不明确
- int表示分子分母，10此预测后就超范围
效果
最后更新 2019-05-28