验证中...
本周日【珠海源创会】一起聊聊:PingCAP分布式事务、支付宝移动端实践、GSBN技术框架选型,点此报名占座
片段 1 片段 2
index.html
原始数据 复制代码
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>智力测试“打灯过桥”问题解析</title>
</head>
<body>
<script>
let person = [
{name:'A',time:1},
{name:'B',time:2},
{name:'C',time:7},
{name:'D',time:8},
]
// 需求:有ABCD需要过桥且只有一盏灯,每个人过桥的时间不相同,
// 桥最多只能够承受两人,每次必须有一人回来送灯,求出过桥最短时长以及过桥方案
// 注意:两人过桥的时候取时间最长的
// 分析:
// 第一步:选出AB过桥 剩余 CD;
// 第二步:选出A送灯 剩余 ACD
// 第三步:选出AC过桥 剩余 D;
// 第四步:选出A送灯 这一步需要想清楚(参照物为已经过桥的人且在第二步没有回来的人)
// 第五步:AD全过桥
// 方案数据结构 [[A,B],[A],[A,C],A,[A,D]]
// 实现方法
class goBridge{
constructor(data){
this.data = data; // 传入数据结构
this.selectData = []; // 选出的数据结构
this.init()
}
init(){
//按照步骤来进行选择吧
this.data.forEach((one,oneIndex) => {
let surplus1 = this.cloneObject(this.data);
surplus1.splice(oneIndex,1)
surplus1.forEach((two,twoIndex)=>{
// console.log(one.name+two.name) // 第一步
let goArr1 = [one,two]; // 在这两个人中间选一个送灯
goArr1.forEach((go1,go1Index)=>{
let surplus2 = this.cloneObject(surplus1);
surplus2.splice(twoIndex,1)
surplus2.push(go1); // 把回来送灯的列入下次过桥的人次
// console.log(one.name+two.name+'->'+go1.name) // 第二步
surplus2.forEach((three,threeIndex)=>{
let surplus3 = this.cloneObject(surplus2);
surplus3.splice(threeIndex,1) //选两个人过桥
surplus3.forEach((four,fourIndex)=>{
// console.log(one.name+two.name+'->'+go1.name+'->'+three.name+four.name); // 第三步
let leave; // 谁回来是个问题(找出留在河对岸的那个人)
if(go1Index==0) leave = two; // 找出第二次没回来的那个人
else leave = one;
let goArr2 = [three,four,leave]; // 在这三个人中找一个送灯
goArr2.forEach((go2,go2Index)=>{
let surplus4 = this.cloneObject(surplus3);
surplus4.splice(fourIndex,1) // 找出还有谁没过河
// console.log(one.name+two.name+'->'+go1.name+'->'+three.name+four.name+'->'+go2.name); //第四步
surplus4.push(go2); // 将送灯的那个人算进来
// 第四步之后就不用循环了[此时只有两个人只能一块过桥]
console.log(one.name+two.name+'->'+go1.name+'->'+three.name+four.name+'->'+go2.name+'->'+surplus4[0].name+surplus4[1].name); //第五步
// 数据整理一下吧
let scheme = [],time=0;
scheme.push([one,two])
if(one.time>two.time) time += one.time;
else time += two.time;
scheme.push(go1)
time += go1.time;
scheme.push([three,four])
if(three.time>four.time) time += three.time;
else time += four.time;
scheme.push(go2)
time += go2.time;
scheme.push(surplus4)
if(surplus4[0].time>surplus4[1].time) time += surplus4[0].time;
else time += surplus4[1].time;
let schemeAndTime = {
'scheme':scheme,
'time':time
}
this.selectData.push(schemeAndTime); //打印出过桥总方案与时间
})
})
})
})
})
});
// 通过排序很容易找出最佳方案
let best = this.selectData.sort(this.compare('time'))
console.log('--------------------------------------------------------')
console.log(`
最佳方案是:
一:${best[0].scheme[0][0].name}和${best[0].scheme[0][1].name}过桥 共用时间${best[0].scheme[0][1].time}分钟
二:${best[0].scheme[1].name}回来送灯 共用时间${best[0].scheme[1].time}分钟
三:${best[0].scheme[2][0].name}和${best[0].scheme[2][1].name}过桥 共用时间${best[0].scheme[2][1].time}分钟
四:${best[0].scheme[3].name}回来送灯 共用时间${best[0].scheme[3].time}分钟
五:${best[0].scheme[4][0].name}和${best[0].scheme[4][1].name}过桥 共用时间${best[0].scheme[4][1].time}分钟
一共用时:${best[0].scheme[0][1].time+best[0].scheme[1].time+best[0].scheme[2][1].time+best[0].scheme[3].time+best[0].scheme[4][1].time}分钟
`)
console.log('--------------------------------------------------------')
}
compare(key) { //排序
return function (a, b) {
let nameA = a[key];
let nameB = b[key];
if (nameA < nameB) return -1;
if (nameA > nameB) return 1;
return 0;
}
}
cloneObject(obj){ //深拷贝
return JSON.parse(JSON.stringify(obj))
}
}
new goBridge(person)
</script>
</body>
</html>
效果预览.png

评论列表( 1 )

1329024_hjm100
鸿基梦 2018-11-09 18:26

你可以在登录后,发表评论

搜索帮助

12_float_left_people 12_float_left_close