过桥问题
【题目描述】
今天无意中看见一道微软面试题，很有意思，大家一起来看一下：
四人夜过桥，步行时间分别为 1、2、5、10 分钟，四人只有一台手电筒，一趟最多两人过桥，一趟过桥须持手电筒，时间以最慢者计，问 17 分钟内可否过桥，如何过桥？
【本题答案】
这个是一位其他的博主做的答案，我先分享给大家：
#define STATE char
#define PATH char
const int TimeLimit = 17;
STATE State[16] = { 1 };
PATH Path[16];
const int Cop[10] = { 1, 2, 4, 8, 3, 5, 9, 6, 10, 12 };
const char* Cops[10] =
{
"1，耗时 1 分",
"2，耗时 2 分",
"5，耗时 5 分",
"10，耗时 10 分",
"1 和 2，耗时 2 分",
"1 和 5，耗时 5 分",
"1 和 10，耗时 10 分",
"2 和 5，耗时 5 分",
"2 和 10，耗时 10 分",
"5 和 10，耗时 10 分"
};
const int Time[10] = { 1, 2, 5, 10, 2, 5, 10, 5, 10, 10 };
void Ferry ( int state, int dir, int p, int time )
{
int i, cop, j;
for ( i = 0; i < 10; i++ )
{
if ( Cop[i] != (cop = state & Cop[i] ) ) continue;
state &= ~cop;
time += Time[i];
if ( State[ dir ? ~state & 15 : state ] ||
time > TimeLimit )
{
state |= cop;
time -= Time[i];
}
else if ( dir && !state )
{
Path[p] = i;
printf ( "过桥过程，共往返 %d 次：/n", p + 1 );
for ( j = 0; j <= p; j++ )
printf ( "%s: %s/n", ( j & 1 ? "右往左" : "左往右" ), Cops[Path[j]] );
printf ( "/n" );
break;
}
else
{
State[ dir ? ~state & 15 : state ] = 1;
Path[p] = i;
Ferry ( ~state & 15, !dir, p + 1, time );
State[ dir ? ~state & 15 : state ] = 0;
time -= Time[i];
state |= cop;
}
}
}
// 调用时
Ferry ( 15, 1, 0, 0 ); 今天无意中想起递归算法，突生灵感，如果用Java语言实现“n人过桥”问题，那就有意思了。
递归的出口是：“2人过桥”情况。2人过桥，不需要有人返回，所以非常简单，总时间就是单人所需时间中的最大值。
如果是“n人过桥”(n>=3)，那完全可以递归了。
假设是从桥头A至桥头B，桥头A的人群为一个集合，桥头B的人群为另一个集合。
那么首先可以从A中任意选择2个人从A到B；则A集合中减少2个人，B集合中增加2个人；
然后需要一个人从B返回A，这个可以分析出如果想要比较少的时间，一定是从B中选一个单独需时最短的；此时B中减少一个人，A集合中增加一个人；
之后情况变成了“n-1人过桥”问题。
递归思想就开始起作用了。
但是需要注意一点，我在这里的思想是每次返回的人都是从B集合中选出需时最少的；如果想找出需时最多的，就从B中选出一个需时最大的；如果想找到所有情况，那就需要遍历B集合，那就比较复杂了，我没有考虑。
如下是我的代码，由于时间仓促，没有规范化处理。。。比如passMethod中的参数列表中第三个参数其实是可以去掉的，因为它就是桥头A端得人数，可以从第一个参数中获得。
由于时间有限，我在这里就不改动了。
读者可以自己个界面，允许人/机交互，如果深入思考，还是很有意思的。
package blog;
import java.util.Vector;
/**
* @author yesr
* @create 2018-04-22 上午12:05
* @desc
**/
public class BridgePass {
private Vector v_source = null;
private Vector v_destination = null;
private static int time_total = 0;
public BridgePass() {
v_source = new Vector();
v_destination = new Vector();
}
public void setSource(int[] array, int num) {
for (int i = 0; i < num; i++) {
v_source.addElement(array[i]);
}
}
public Vector getSource() {
return v_source;
}
public Vector getDestination() {
return v_destination;
}
/**
* the recursive algorithm.
*
* @param src : the set of persons in A-side
* @param des : the set of persons in B-side
* @param size : the number of persons in A-side
* @param totalTime : the totalTime has used
*/
public void passMethod(Vector src, Vector des, int size, int totalTime) {
//If only 2 persons in A-side, just pass bridge together in one time.
if (size == 2) {
System.out.println("A->B:" + src.elementAt(0) + " AND " + src.elementAt(1));
System.out.println("*****Total Time: " + (totalTime + Math.max((Integer) src.elementAt(0), (Integer) src.elementAt(1))) + "****");
} else if (size >= 3) {
// if more than 2 persons in A-Side, use the recursive algorithm.
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
System.out.println("i=" + i + "j=" + j);
//Pass, A->B
Vector _src = new Vector();
Vector _des = new Vector();
_src = (Vector) src.clone();
_des = (Vector) des.clone();
int time1 = 0;
int time2 = 0;
time1 = (Integer) _src.elementAt(i);
_des.addElement(time1);
time2 = (Integer) _src.elementAt(j);
_des.addElement(time2);
System.out.print("A->B:" + time1);
System.out.println(" AND " + time2);
_src.removeElement(time1);
_src.removeElement(time2);
//BACK, B->A
int minValue = (Integer) _des.elementAt(0);
for (int k = 0; k < _des.size(); k++) {
if (((Integer) _des.elementAt(k)).intValue() < minValue) {
minValue = (Integer) _des.elementAt(k);
}
}
_src.addElement(minValue);
_des.removeElement(minValue);
System.out.println("B->A:" + minValue);
passMethod(_src, _des, _src.size(), totalTime + Math.max(time1, time2) + minValue);
}
}
}
}
public static void main(String[] cmd) {
BridgePass test = new BridgePass();
//the persons want to pass bridge:
int source[] = {1, 2, 5, 10};
test.setSource(source, source.length);
test.passMethod(test.getSource(), test.getDestination(), source.length, 0);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年04月22日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读