共计 10217 个字符，预计需要花费 26 分钟才能阅读完成。
一、相应游戏可微信搜寻 球球排序
二、效果图
三、实现代码
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title> 球球排序最优解 </title>
<style>
.mt20 {margin-top: 20px;}
.boll {width:50px;height:50px;border-radius: 50%;display: inline-block;margin-right:10px;position:relative}
.bollNum {width:20px;height:20px;text-align:center;line-height: 20px;position:absolute;top:0;right:0;border-radius: 50%;background: #FF00FF;}
.contain{width:52px;height:210px;border: 1px solid #C0C0C0;margin-right:20px;float:left;display: flex;flex-direction: column-reverse;}
.active{border: 2px solid #FF00FF;}
.bgeee{background: #eeeeee;}
.btn{width: 160px;height: 30px;text-align: center;line-height: 30px;border: 1px solid #eeeeee;background: #00FF00;position: absolute;top: 140px;left: 600px;}
.btn:hover{cursor: pointer;color:#fff;}
.t110{top:110px;}
.bg0000FF {background: #0000FF;}
.box{width:1000px;height:350px;background: #fff;position:absolute;top:150px;left:200px;padding:30px;border:10px solid #eee;}
.box_contain{width:100%;height:70px;}
.close{width:30px;height:30px;text-align:center;line-height:30px;position:absolute;top:0;right:0;border-radius:50%;background:#FF0000;}
.l800{left: 800px;}
.l1000{left: 1000px;}
.w60{width:60px;}
</style>
</head>
<body>
<div> 相应游戏可微信搜寻 球球排序 </div>
<div> 最好用谷歌浏览器按 F12，关上调试，找到 console 模块，查看以后计算状态 </div>
<div> 依赖的 vue.js 文件为线上的，可下载到本地，切换依赖 </div>
<div id="mvvm" class="mt20">
<div>
管子数量：<input type="text" v-model="pipeNum">
空管子数量：<input type="text" v-model="emptyNum">
最大步数：<input type="text" v-model="maxStepSet">
最大后果数量：<input type="text" v-model="maxNum">
遍历开始数：<input type="text" v-model="startIndex">
</div>
<div class="mt20">
<div v-for="(item, index) in colorArr" class="boll" :style="{background: item.name}" @click="bollClick(index)" :key="index">
<div class="bollNum">{{item.value}}</div>
</div>
</div>
<div class="mt20">
<div class="contain" :class="{'active': activeNum == index,'bgeee': index > pipeNum}" v-for="index of totalNum" @click="containClick(index)" :key="index">
<div v-for="item in containArr[index-1]" class="boll" :style="{background: colorStoreArr[item-1]}" :key="item"></div>
</div>
</div>
<div class="btn" @click="startClick(2)" title="间接算出起码的步数，耗时"> 从起码两步开始计算 </div>
<div class="btn l800" @click="startClick(1)" title="可缩小计算的次数"> 从最大步数开始计算 </div>
<div class="btn l1000 w60 bg0000FF" @click="reset"> 重置 </div>
<div>
后果：<div> 步数：{{resArr.length?steps: ''}}</div>
门路：点击可动画展现解法
<div v-for="item in resArr" @click="animate(item)">
{{item}}
</div>
</div>
<div v-if="isShow" class="box">
<div class="box_contain">
<div class="boll" :style="{background: colorStoreArr[index_ani-1], transform:'translate('+ activeX +'px)'}" v-show="isShowActive"></div>
</div>
<div class="contain" :class="{'active': activeNum_ani == index}" v-for="index of totalNum_ani" :key="index">
<div v-for="item in arr[index-1]" class="boll" :style="{background: colorStoreArr[item-1]}" :key="item"></div>
</div>
<div class="close" @click="close">X</div>
</div>
</div>
<script src="https://cdnjs.cloudflare.com/ajax/libs/vue/2.1.8/vue.min.js"></script>
<!-- <script src="./vue.js"></script> -->
<script>
var vm = new Vue({
el: '#mvvm',
data: {
pipeNum: 3,
emptyNum: 2,
colorArr: [],
colorStoreArr: ["#EE1111", "#FCFC9D", "#77FF77", "#0029CC", "#00FFFF", "#FF99FF", "#990099", "#88CE20", "#999999"],
containArr:[],
activeNum: 1,
startIndex: 0,
maxNum: 1,
maxStepSet: 30,
maxStep: 2,
isFirst: true,
resNum: 0,
loadObj: {},
arr: [],
isShow: false,
activeNum_ani: 1,
totalNum_ani: 5,
arrCopy: [],
index_ani: 1,
isShowActive: true,
activeX: 0,
resArr: [],
steps: 0
},
created: function () {
var self = this
self.colorStoreArr.forEach(function(item) {var obj = {}
obj.name = [item]
obj.value = 4
self.colorArr.push(obj)
})
},
computed: {totalNum: function() {var tmpVal = parseInt(this.pipeNum) + parseInt(this.emptyNum)
return tmpVal
}
},
methods: {isPlainObject(obj) {return Object.prototype.toString.call(obj) === '[object Object]';
},
isArray(obj) {return Object.prototype.toString.call(obj) === '[object Array]';
},
copy(obj, deep) {
var self = this
if (obj === null || typeof obj !== "object") {return obj}
var i, target = Array.isArray(obj) ? [] : {}, value;
for (i in obj) {value = obj[i]
if (deep && (self.isArray(value) || self.isPlainObject(value))) {target[i] = self.copy(value, true);
} else {target[i] = value;
}
}
return target
},
// 判断数组行的数量是否满员，且子成员都相等
isSame(arr) {if (arr.length != 4) {return false}
return arr.every(function(value, index, arr) {return value === arr[0]
})
},
// 判断数组行的子成员从 0 开始就相等，前期不做挪动 如[[1,1,1]]
isHalfSame(arr, val) {if (!arr.length || arr.length === 4) {return false}
return arr.every(function(value, index, arr) {return val? (value === val) : (value === arr[0])
})
},
// 二重数组按长度及值大小排序
sortLen(arr1, arr2) {if (arr1.length < arr2.length) {return 1;} else if (arr1.length > arr2.length) {return -1;}
var num1 = parseInt(arr1.join("") || 0)
var num2 = parseInt(arr2.join("") || 0)
if(num1 < num2) {return 1} else if (num1 > num2) {return -1;} else {return 0}
},
// 判断是否完结
isOver(arr) {
let res = true
for (var i = 0; i < arr.length; i++) {if (arr[i].length) {if (arr[i].length !== 4) {
res = false;
break;
} else {var tmpRes = arr[i].every(function(curVal, index, array) {return curVal === array[0]
})
if (!tmpRes) {
res = false;
break;
}
}
}
}
return res
},
// 验证反复元素，有反复返回元素值；否则返回 false
repeatArr(arr) {var hash = {};
var tmpArr = []
for(var i in arr) {if(hash[arr[i]]) {tmpArr.push(arr[i]);
}
// 不存在该元素，则赋值为 true，能够赋任意值，相应的批改 if 判断条件即可
hash[arr[i]] = true;
}
if(tmpArr.length) {return tmpArr} else {return false;}
},
// 是否死循环
isDead (arr) {
var self = this
let res = true
let tmpArr = []
// 将数组的最初一项，从新组成一个数组
for (var i = 0; i < arr.length; i++) {
// 有空数组间接跳出循环，返回 false
if(!arr[i].length) {
res = false;
break;
}
tmpArr.push(arr[i][arr[i].length - 1])
}
// 无空数组
if (res) {
// 最初一项数组都无反复
let repeatArrRes = self.repeatArr(tmpArr)
if (!repeatArrRes) {return res = true} else {for (var i = 0; i < repeatArrRes.length; i++) {var tmpRes = arr.some(function(item, index, array) {return (item[item.length - 1] == repeatArrRes[i]) && (array[index].length < 4)
})
if (tmpRes) {
res = false;
break;
}
}
}
}
return res
},
factorial(arr, circle, id) {
var self = this
// 备份数组，不更改原来的
var copyArr = self.copy(arr, true)
circle = circle || 0
circle += 1
if (self.resNum >= self.maxNum) {return}
if(self.isDead(copyArr)) {console.log('isDead(copyArr)=======')
return
}
if(self.isOver(copyArr)) {console.log('isOver(copyArr)=======')
self.steps = circle - 1
self.resArr.push(id)
self.resNum += 1
return
}
// 第一次从第几行开始遍历
let startI = self.isFirst? parseInt(self.startIndex): 0
for (var i = startI; i < copyArr.length; i++) {
self.isFirst = false
// []不做解决
if (!copyArr[i].length) {continue}
// 已实现不做解决，如[1,1,1,1]
if (self.isSame(copyArr[i])) {continue}
// console.log("circle - i====" + circle + '-' + i)
for (var j = 0; j < copyArr.length; j++) {if (i == j) {continue}
let copyArrJ = self.copy(copyArr, true)
var arrI = copyArrJ[i]
var arrJ = copyArrJ[j]
// 满员不做接管项
if(arrJ.length == 4) {continue}
// 最初一项不相等 且 arrJ 不为空数组 间接跳过
if (arrI[arrI.length - 1] !=arrJ[arrJ.length - 1] && arrJ.length) {continue}
let isHalfSameI = self.isHalfSame(copyArr[i])
// 如果 copyArr[i]是 isHalfSame，copyArr[j]是 [] 不做挪动，间接跳过
if (isHalfSameI && !arrJ.length) {continue}
// 如果 copyArr[i]是 isHalfSame，copyArr[j]是 isHalfSame，且 i 个数大于 j, 间接跳过
if (isHalfSameI && self.isHalfSame(arrJ) && (arrI.length > arrJ.length)) {continue}
if(id) {let tmpArr = id.split('+')
let lastArr = tmpArr[tmpArr.length - 1].split('-')
// A > B 后 不能再 B > A
if (lastArr[0] == (j + 1) && lastArr[1] == (i + 1)) {continue}
// 超出最大步数要求
if (tmpArr.length > (self.maxStep - 1)) {console.log('超出最大步数 ===' + self.maxStep + 'id==' + id)
continue
}
}
console.log("circle -- i+1 -- j+1====" + circle + '--' + (i + 1) + "--" + (j + 1))
var popVal
popVal = arrI.pop()
arrJ.push(popVal)
// 已存在当前情况，且循环步数比以后少，间接跳过 疏忽第二重数组的排序
var tmpArrJ1 = self.copy(copyArrJ, true)
tmpArrJ1.sort(self.sortLen)
var loadItem = self.loadObj[JSON.stringify(tmpArrJ1)]
if (loadItem && loadItem <= circle) {continue} else {var tmpArrJ2 = self.copy(copyArrJ, true)
tmpArrJ2.sort(self.sortLen)
self.loadObj[JSON.stringify(tmpArrJ2)] = circle
}
var tmpId
tmpId = id? (id + '+' + (i + 1) + '-' + (j + 1)): ((i + 1) + '-' + (j + 1))
self.factorial(self.copy(copyArrJ, true), circle, tmpId)
}
}
},
containClick(index) {
var self = this
if (self.activeNum == index && self.containArr[index - 1] && self.containArr[index - 1].length) {var popVal = self.containArr[index - 1].pop()
self.colorArr[popVal - 1].value += 1
} else {if (index > self.pipeNum) {return}
self.activeNum = index
}
},
bollClick(index) {
var self = this
if (!self.colorArr[index].value || (self.containArr[self.activeNum-1] && self.containArr[self.activeNum-1].length >= 4)) {return}
self.colorArr[index].value -= 1
if (self.isArray(self.containArr[self.activeNum-1])) {self.containArr[self.activeNum - 1].push(parseInt(index) + 1)
} else {self.containArr[self.activeNum - 1] = []
self.containArr[self.activeNum - 1].push(parseInt(index) + 1)
}
},
start() {
var self = this
console.log('start==============')
// console.log(JSON.stringify(self.colorArr))
// console.log(JSON.stringify(self.containArr))
self.resArr = []
self.resNum = 0
self.isFirst = true
self.loadObj = {}
var isColorArrOk = self.colorArr.every(function(item, index) {return item.value == 4 || item.value == 0})
var isContainArrOk = self.containArr.every(function(item, index) {return item.length == 4})
if(isColorArrOk && isContainArrOk && self.containArr.length == self.pipeNum) {var arr = self.copy(self.containArr, true)
for (var i = 0; i < self.emptyNum; i++) {arr.push([])
}
self.arrCopy = self.copy(arr, true)
self.factorial(arr)
console.log('resArr========maxStep=======================' + self.maxStep)
console.log(JSON.stringify(self.resArr))
return self.resArr
} else {alert('数据不对，请从新抉择')
}
},
startClick(index) {
var self = this
self.maxStep = 2
if (index == 1) {self.maxStep = self.maxStepSet}
self.loop()},
loop () {
var self = this
var resArr = self.start()
if(!resArr.length && self.maxStep < self.maxStepSet) {
self.maxStep += 1
self.loop()}
},
reset () {
var self = this
self.containArr = []
self.colorArr.forEach(function(item) {item.value = 4})
self.resArr = []
self.resNum = 0
self.isFirst = true
self.loadObj = {}},
animate(key) {
var self = this
self.arr = self.copy(self.arrCopy, true)
self.totalNum_ani = self.arr.length
self.isShow = true
var tmpArr = key.split("+")
var timer_step = null
var i = 0
function step() {window.clearTimeout(timer_step)
if (i >= tmpArr.length) {return}
var currentArr = tmpArr[i].split("-")
i += 1
self.index_ani = self.arr[parseInt(currentArr[0]) - 1].pop()
self.activeNum_ani = parseInt(currentArr[0])
self.activeX = 75 * (parseInt(currentArr[0]) - 1)
self.isShowActive = true
var resX = 75 * (parseInt(currentArr[1]) - 1)
var rate = 50 / 1500 * (resX - self.activeX) // 每 50 毫秒挪动量, 挪动 1 秒达到
var timer = null;
function move () {window.clearTimeout(timer)
if (self.activeX >= resX) {setTimeout(function() {self.arr[parseInt(currentArr[1]) - 1].push(self.index_ani)
self.isShowActive = false
},50)
return
}
self.activeX += rate
timer = window.setTimeout(move,50)
}
move()
timer_step = window.setTimeout(step, 3000)
}
step()},
close() {this.isShow = false}
}
});
</script>
</body>
</html>四、名词阐明
管子数量》》》色彩品种的数量，如 29 关是 7
最大步数》》》达到设置的值，往后的状况间接跳过，太大可能不是最优解，太小可能找不到解
最大后果数量》》》最优解的数量或最大步之内后果的数量，倡议取 1
遍历开始数》》》第一次从哪根管子开始计算，正当利用此参数可大大缩短计算工夫，如 29 关从 0 计算要三十多分钟，从 1 计算只有一分钟
从起码两步开始计算》》》容许的步数从 2 步开始始终算到最大步数，可间接找到起码步数值，但计算多，耗时长
从最大步数开始计算》》》间接容许最大步数的解法，计算量减少，但可能错过最优解
正文完
发表至： javascript
2020-08-01
