一、相应游戏可微信搜寻 球球排序
二、效果图
三、实现代码
<!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步开始始终算到最大步数，可间接找到起码步数值，但计算多，耗时长
从最大步数开始计算 》》》 间接容许最大步数的解法，计算量减少，但可能错过最优解