一诊杆、題目概述
師徒四人西天取經(jīng)，途中必需跨過一座橋何陆，四個(gè)人從橋的同一端出發(fā)晨汹，你得幫助他們到達(dá)另一端，天色很暗而他們只有一支手電筒贷盲，一次同時(shí)最多可以有兩個(gè)人一起經(jīng)過橋淘这。而過橋的時(shí)候必須持有手電筒，所以就得有人把手電筒帶來帶去巩剖，來回橋兩端铝穷。手電筒不能用丟的方式來傳遞，四個(gè)人的步行速度各不同球及，若兩人同行則以較慢者的速度為準(zhǔn)氧骤，大師兄需花1分鐘過橋，二師兄需花2分鐘過橋吃引，三師兄需花5分鐘過橋筹陵，師傅需花10分鐘過橋。請問他們最短在多少分鐘內(nèi)過橋镊尺？（）
A. 18
B. 17
C. 19
D. 16
二朦佩、思路
一開始直接想到，用最小的那個(gè)數(shù)來回跑庐氮，也就是大師兄來回跑语稠，算出來是19，可是又想了下弄砍，如下：
1仙畦、大師兄和二師兄過橋，算二師兄的時(shí)間也就是2分鐘
2音婶、大師兄獨(dú)自拿手電回來 1分鐘
3慨畸、三師弟和師傅那手電過橋，算師傅的時(shí)間也就是10分鐘
4衣式、二師弟拿手電回來 2分鐘
5寸士、最后大師兄和二師弟過橋 2分鐘
總共17分鐘
雖然結(jié)果出來了檐什，感覺有點(diǎn)不實(shí)在，這其中的規(guī)律是怎樣的呢弱卡？有沒有什么規(guī)律解決這類似的問題呢乃正，比如只有三個(gè)人過橋呢？二師兄不過橋婶博，結(jié)果又是什么呢瓮具？再比如，多一個(gè)人過橋呢凡人？多了個(gè)白龍馬過橋搭综，白龍馬過橋的時(shí)間時(shí)6分鐘，結(jié)果又是什么呢划栓？有沒有什么規(guī)律呢兑巾，或者說有沒有個(gè)公式來計(jì)算呢？用編程怎么解忠荞？
求教大神蒋歌？先睡了，嘗試下編程解決委煤！
三堂油、編程解決
2016年10月7日01:39:55
本來當(dāng)時(shí)寫博客的第二天就用編程解決了這個(gè)問題的，可是因?yàn)榉N種原因碧绞，還沒有時(shí)間把代碼貼上來!
import java.util.ArrayList;
public class Pilgrimage {
final static int times[] = { 1, 2, 5, 10 };// 花費(fèi)時(shí)間
final static String names[] = { "大師兄", "二師兄", "三師兄", "師傅" };// 人物
public static void main(String[] args) {
Integer other_bridges[] = { 0, 0, 0, 0 };// 橋另一邊
Integer bridges[] = { 1, 1, 1, 1 };// 當(dāng)前橋這邊 府框，1表示存在，0表示不在
// 開始遞歸
loop(bridges, other_bridges, 0, new StringBuffer());
}
private static void loop(Integer[] bridges, Integer[] other_bridges,
int time, StringBuffer msg) {
ArrayList<Integer> positions = new ArrayList<Integer>();// 記錄還在起始端人的下標(biāo)
for (int i = 0; i < bridges.length; i++) {
if (bridges[i] == 1) {
positions.add(i);// 記錄下標(biāo)
}
}
int len = positions.size();
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) { // 循環(huán)取結(jié)合
// 記錄狀態(tài)
Integer[] zt_bridges = bridges.clone();
Integer[] zt_other_bridges = other_bridges.clone();
int zt_time = time;
StringBuffer zt_msg = new StringBuffer(msg);
// 過橋---------
time += times[positions.get(j)];// 花費(fèi)時(shí)間直接取最大的
move(bridges, other_bridges, 1, positions.get(i));
move(bridges, other_bridges, 1, positions.get(j));
msg.append(" 過橋:" + names[positions.get(i)] + "&"
+ names[positions.get(j)]);
// System.out.print(" 過橋:" + names[positions.get(i)] + "_"
// + names[positions.get(j)]);
// 回來接人------
if (isend(other_bridges)) {
msg.append(" 總共花費(fèi):" + time);
System.out.println(msg.toString());
// System.out.println(" 總共花費(fèi):" + time);
return;
}
int k = 0;
for (int ii = 0; ii < other_bridges.length; ii++) {// 選擇最快的回來
if (other_bridges[ii] == 1) {
k = ii;
break;
}
}
time += times[k];
move(bridges, other_bridges, 0, k);
msg.append(" 回來:" + names[k]+" *** ");
// System.out.print(" 回來:" + names[k]);
// 繼續(xù)循環(huán)遍歷
loop(bridges.clone(), other_bridges.clone(), time,
new StringBuffer(msg));
// 還原狀態(tài)
bridges = zt_bridges;
other_bridges = zt_other_bridges;
time = zt_time;
msg = zt_msg;
}
}
}
/**
* 移動(dòng)的那個(gè)人
*
* @param bridges
* @param other_bridges
* @param direction
* 方向
* @param position
*/
private static void move(Integer[] bridges, Integer[] other_bridges,
int direction, int position) {
if (direction == 1) {// 往另一端走
bridges[position] = 0;
other_bridges[position] = 1;
} else {// 回來接人走
bridges[position] = 1;
other_bridges[position] = 0;
}
}
// 判斷是否已經(jīng)結(jié)束了
// 當(dāng)other_bridges {1,1,1,1}表示結(jié)束
private static boolean isend(Integer[] other_bridges) {
for (int i : other_bridges) {
if (i == 0)
return false;
}
return true;
}
}
運(yùn)行的結(jié)果：
