java诸神之战游戏_mj回溯算法 - osc_7bgz0no1的个人空间 - OSCHINA - 中文开源技术交流社区...
1)js版本
?
/**
* 基本思路:
* 回溯法: 先挑選中將,再依次拆接出3個,3個的...直到結束,那么說明當前可以胡牌
*/
let mahjong = [
"1T", "2T", "3T", "4T", "5T", "6T", "7T", "8T", "9T", // 桶
"1S", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", // 條
"1W", "2W", "3W", "4W", "5W", "6W", "7W", "8W", "9W", // 萬
"DONG", "NAN", "XI", "BEI", // 風
"ZHONG", "FA", "BAI", // 箭
];
// 一張麻將牌,如: "2T", 轉化為34張牌中的一個索引為1
function convert(s) {
for (let i = 0; i < 34; i++) {
if (mahjong[i] == s) {
return i;
}
}
return -1;
}
// 一副手牌
function hand_mj() {
// 13張手牌
this.mj = ["1T", "1T", "3T", "4T", "5T", "5T", "5T", "7T", "7T", "7T", "9T", "9T", "9T"];
// 對應的拍的索引: 0 1 2 3 4 5 6 7 8 0 1 2 4, 以方便計算當前手牌都有幾張牌
this.mj_num = [];
// 34張牌,當前手牌中每張牌的數量
this.c = [];
}
// 基本數據初始化
hand_mj.prototype.init = function () {
// 34張牌, 每張數量都為0
for (let i = 0; i < 34; i++) {
this.c[i] = 0;
}
// 把每張牌轉化為34張牌中的數字索引
for (let i = 0; i < 13; i++) {
// 如: 第1T對應第0張
this.mj_num[i] = convert(this.mj[i]);
}
// 統計13張牌中每張牌的數量. 統計完就知道0位置有2張, 1位置有2張...其它位置則為0
for (let i = 0; i < 13; i++) {
this.c[this.mj_num[i]]++;
}
console.log();
}
// 去掉將牌
hand_mj.prototype.check = function () {
for (let i = 0; i < 34; i++) {
// 如果當前位置,牌數目>=2,則可以當將,拆出來(AA)
if (this.c[i] >= 2) {
this.c[i] -= 2;
if (this.search(0)) {
this.c[i] += 2;
return true;
} else {
this.c[i] += 2;
}
}
}
return false;
}
// 遞歸深度
hand_mj.prototype.search = function (dep) {
// 去掉刻子(AAA)
for (let i = 0; i < 34; i++) {
if (this.c[i] >= 3) {
if (dep == 3) {
return true;
}
this.c[i] -= 3;
if (this.search(dep + 1)) {
this.c[i] += 3;
return true;
} else {
this.c[i] += 3;
}
}
}
// 去掉順子(A A+1 A+2)
for (let i = 0; i < 34; i++) {
if (i % 9 <= 6 &&
this.c[i] >= 1 &&
this.c[i + 1] >= 1 &&
this.c[i + 2] >= 1) {
if (dep == 3) {
return true;
}
this.c[i]--;
this.c[i + 1]--;
this.c[i + 2]--;
if (this.search(dep + 1)) {
this.c[i]++;
this.c[i + 1]++;
this.c[i + 2]++;
return true;
} else {
this.c[i]++;
this.c[i + 1]++;
this.c[i + 2]++;
}
}
}
return false;
}
// 計算胡那些牌
hand_mj.prototype.cal_hu = function () {
let ret = [];
// 34張牌嘗試加一張,看看胡不胡
for (let i = 0; i < 34; i++) {
// 嘗試手牌加1張
this.c[i]++;
if (this.c[i] <= 4 && // 大于4張,不可能胡這張牌
this.check()) {
ret.push(mahjong[i]);
}
this.c[i]--;
}
return ret;
}
// 測試
let test_hand1 = new hand_mj();
test_hand1.init();
let s = new Date().getTime();
let ret = [];
for (let i = 0; i < 100000; i++) {
ret = test_hand1.cal_hu();
}
let e = new Date().getTime();
console.log(ret);
console.log("耗時:", (e - s))
?
2)java版本
HandCard.java
package com.my.mj_no_lz;
import java.util.ArrayList;
/**
* 自己的手牌
*/
public class HandCard {
/**
* 自己手牌中每一張牌的張數統計
*/
private int[] c = new int[]{
2, 0, 0, 0, 3, 0, 3, 0, 3, // 萬
0, 0, 0, 0, 0, 0, 0, 1, 1, // 餅
0, 0, 0, 0, 0, 0, 0, 0, 0, // 條
0, 0, 0, 0, 0, 0, 0 // 東 西 南 北 中 發 白
};
public ArrayList getHuCards() {
// TODO 調用工具函數,計算手牌
ArrayList huCards = Logic.cal_hu(c);
return huCards;
}
}
Logic.java
package com.my.mj_no_lz;
import java.util.ArrayList;
public class Logic {
/**
* 計算當前胡牌
*
* @return
*/
public static ArrayList cal_hu(int[] c) {
ArrayList ret = new ArrayList<>();
// 每張牌挨個遍歷,看是否胡這張牌
for (int i = 0; i < 34; i++) {
c[i]++;
if (c[i] >= 0 && c[i] <= 4 && check(c)) {
// TODO 胡第張牌
ret.add(i);
}
c[i]--;
}
return ret;
}
/**
* 檢查當前牌手牌信息c是否胡牌
*
* @param c
* @return
*/
private static boolean check(int[] c) {
for (int i = 0; i < 34; i++) {
// 去掉將
if (c[i] >= 2) {
c[i] -= 2;
if (search(0, c)) {
c[i] += 2;
return true;
} else {
c[i] += 2;
}
}
}
return false;
}
/**
* 判斷當前牌能不能組成撲
*
* @param dep
* @param c
* @return
*/
private static boolean search(int dep, int[] c) {
for (int i = 0; i < 34; i++) {
if (c[i] >= 3) {
if (dep == 3) {
return true;
}
c[i] -= 3;
if (search(dep + 1, c)) {
c[i] += 3;
return true;
} else {
c[i] += 3;
}
}
}
for (int i = 0; i < 31; i++) {
// TODO 注意連續性 9W和1餅是不能連續計算的
if ((i % 9 <= 6) && c[i] >= 1 && c[i + 1] >= 1 && c[i + 2] >= 1) {
if (dep == 3) {
return true;
}
c[i]--;
c[i + 1]--;
c[i + 2]--;
if (search(dep + 1, c)) {
c[i]++;
c[i + 1]++;
c[i + 2]++;
return true;
} else {
c[i]++;
c[i + 1]++;
c[i + 2]++;
}
}
}
return false;
}
}
Main.java
package com.my.mj_no_lz;
import java.util.ArrayList;
/**
* 不帶癩子麻將胡牌算法思路:
* 1.一個34個元素的數組,里面標記每個麻將的牌的個數
* 2.添加一張牌
* 3.找出將(回溯)
* 4.找出撲(回溯)
* 5.如果剩余牌最終為0,那么說明能胡這張牌
*/
public class Main {
public static void main(String[] args) {
HandCard handCard = new HandCard();
long s = System.currentTimeMillis();
ArrayList huCards = handCard.getHuCards();
long e = System.currentTimeMillis();
System.out.println(huCards);
System.out.println("cost=" + (e - s));
}
}
總結
以上是生活随笔為你收集整理的java诸神之战游戏_mj回溯算法 - osc_7bgz0no1的个人空间 - OSCHINA - 中文开源技术交流社区...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mybatis获取mysql源数据类型_
- 下一篇： java中apache安装与配置_Apa