求助各位高人：面试题目：一个桶中有12斤油，要求倒出6斤，可现在另外只有两个桶，分别可装8斤与5斤，请问应如何来倒？（急啊）
求助各位高人：分油算法：一个桶中有12斤油，要求倒出6斤，可现在另外只有两个桶，分别可装8斤与5斤，请问应如何来倒？
补充：这里的12,6,8,5都是变量，应该可以自己设置，输出是每一次分油的步骤。
[解决办法]
加入了过程描述
public Form1() { InitializeComponent(); //瓶子的实际容量 int[] bottlesRealityNum = { 12, 0, 0 }; falloil(ref bottlesRealityNum); MessageBox.Show(string.Format("b1:{0} b2:{1} b3:{2}", bottlesRealityNum[0], bottlesRealityNum[1], bottlesRealityNum[2])); } private void falloil(ref int[] source) { //瓶子的额定容量 int[] bottlesRating = { 12, 8, 5 }; if (source[0] != 6) { int temp = source[0]; source[0] = source[0] - bottlesRating[1]; if (source[0] < 0) { source[0] = 0; source[1] = temp; } else { source[1] = bottlesRating[1]; } MessageBox.Show(string.Format("A桶倒入B桶;A＝{0},B={1},C={2}", source[0], source[1], source[2])); int temp0 = source[1]; source[1] = source[1] - bottlesRating[2]; if (source[1] < 0) { source[1] = 0; source[2] = temp0; } else { source[2] = bottlesRating[2]; } MessageBox.Show(string.Format("B桶倒入C桶,再把B桶倒掉;A＝{0},B={1},C={2}", source[0], source[1], source[2])); source[1] = 0; source[0] = source[0] + source[2]; MessageBox.Show(string.Format("C桶倒入A桶;A＝{0},B={1},C={2}", source[0], source[1], source[2])); falloil(ref source); } else { return; } }
[解决办法]
给一个用bfs的,解出来的结果是:
120000
040800
040305
090300
090003
010803
010605
比较长,是根据以前的一道倒酒的题改的!解法基本上就是穷举!
private void button5_Click(object sender, EventArgs e) { //初始状态和结束状态 int[] begin = new int[] { 12, 0, 0 }; int end = 6; int[][] allStatus = new int[][] { begin }; //所有步骤都记录在logHash里面 Dictionary<int, int> logHash = new Dictionary<int, int>(); int hashCode = GetHashCode(begin); logHash.Add(hashCode, hashCode); PouringStep(allStatus, end, logHash); hashCode = -1; int value = 0; List<string> logStep = new List<string>(); while (true) { logHash.TryGetValue(hashCode, out value); if(hashCode != -1) logStep.Add(hashCode.ToString("000000")); if (hashCode == value) break; hashCode = value; } logStep.Reverse(); } //获取所有下一步的状态 private void PouringStep(int[][] allPouringStatus, int end, Dictionary<int, int> logHash) { List<int[]> allStatus = new List<int[]>(); int hashcode; int[] newStatus; foreach (int[] status in allPouringStatus) { for (int i = 0; i < status.Length; i++) { for (int j = 0; j < status.Length; j++) { if (j == i) continue; newStatus = PouringFromTo(status, i, j); if (newStatus == null) continue; hashcode = GetHashCode(newStatus); if (logHash.ContainsKey(hashcode)) continue; allStatus.Add(newStatus); logHash.Add(hashcode, GetHashCode(status)); if (CompareArray(newStatus, end)) { //如果满足了条件,加入-1标识 logHash.Add(-1, hashcode); return; } } } } PouringStep(allStatus.ToArray(), end, logHash); } //查找是否有符合条件的结果 private bool CompareArray(int[] Array1, int end) { for (int i = 0; i < Array1.Length; i++) { if (Array1[i] == end) return true; } return false; } //倒油 private int[] PouringFromTo(int[] currentStatus, int fromBottle, int toBottle) { //桶的容量写在这里 int[] bottleVol = new int[] { 12, 8, 5 }; //如果from为0或者to已经满了 if (currentStatus[fromBottle] <= 0 || currentStatus[toBottle] == bottleVol[toBottle]) return null; int[] newStatus = (int[])currentStatus.Clone(); //要么把当前桶倒空,要么把目标桶倒满 if (currentStatus[fromBottle] + currentStatus[toBottle] <= bottleVol[toBottle]) { newStatus[toBottle] += newStatus[fromBottle]; newStatus[fromBottle] = 0; } else { newStatus[fromBottle] -= (bottleVol[toBottle] - currentStatus[toBottle]); newStatus[toBottle] = bottleVol[toBottle]; } return newStatus; } //计算状态的hash private int GetHashCode(int[] status) { //如果桶的容积较大,需要对baseArray做相应的调整 int[] baseArray = new int[] { 1, 100, 10000 }; int code = 0; for (int i = 0; i < status.Length; i++) { code += status[i] * baseArray[status.Length - i - 1]; } return code; }
[解决办法]
我算出来了，用死循环和最小值算法：
public static void change(){
int n_12 = 12;//12桶里现在有多少油
int n_8 = 0;//8桶里现在有多少油
int n_5 = 0;//5桶里现在有多少油
while(true){
//设置第一个参数为12倒到8中多少
int t1 = Math.min(n_12,(8-n_8));
System.out.println("从12的桶里面倒入8的桶里面"+t1+"公斤");
//倒完之后给各个桶赋植
n_12 = n_12 - t1;
n_8 = n_8 + t1;
//设置第二个参数为8倒入5中多少
int t2 = Math.min(n_8, (5-n_5));
System.out.println("从8的桶里面倒入5的桶里面"+t2+"公斤");
//倒完后给各个桶负值
n_8 = n_8 - t2;
n_5 = n_5 + t2;
//此时判断8桶里面的油是不是6，不是的继续循环
if(n_8==6){
System.exit(0);
}else{
//设置第3个参数为5倒入12中多少
int t3 = Math.min(n_5, (12-n_12));
System.out.println("从5的桶里面倒入12的桶里面"+t3+"公斤");
n_12 = n_12 + t3;
n_5 = n_5 - t3;
//设置第4个参数为8倒入5中多少
int t4 = Math.min(n_8, (5-n_5));
System.out.println("从8的桶里面倒入5的桶里面"+t4+"公斤");
n_8 = n_8 - t4;
n_5 = n_5 + t4;
}
}
}
这样每次都用最小的那个倒，而且动态改变参数，设置个死循环，直到算出来为止！！
[解决办法]
public class GetTPath{ private bool iswhile = true; private string checkedstr = ";"; public string GetPath(int[] nowarray, int t1, int t2, int t3, int remain) { string laststr = ToStr(nowarray) + ";"; checkedstr += laststr; string nowpath = ""; if (nowarray[0] == remain) { iswhile = false; } else { string cns = ","; while (iswhile) { nowpath = ""; //取最大值 int mn = 0; int mi = 0; for (int i = 0; i < 3; i++) { if (nowarray[i] > mn && cns.IndexOf("," + nowarray[i].ToString() + ",") < 0) { mn = nowarray[i]; mi = i; cns += mn.ToString() + ","; } } if (mn == 0) { break; } //倒 for (int i = 0; i < 3; i++) { if (i != mi) { int tn = nowarray[i]; int t = 0; if (i == 0) { t = t1; } else if (i == 1) { t = t2; } else if (i == 2) { t = t3; } int[] newinta = new int[3]; nowarray.CopyTo(newinta, 0); newinta[i] = ((tn + mn) > t) ? t : tn + mn; newinta[mi] = ((tn + mn) > t) ? tn + mn - t : 0; if (!IsExits(newinta)) { //下一步 nowpath += GetPath(newinta, t1, t2, t3, remain); break; } } } } } return laststr + nowpath; } private string ToStr(int[] array) { string str = ""; for (int i = 0; i < array.Length; i++) { str += array[i].ToString() + ","; } return str; } private bool IsExits(int[] array) { if (checkedstr.IndexOf(";" + ToStr(array)) < 0) { return false; } else { return true; } }} protected void Page_Load(object sender, EventArgs e) { int t1 = 12; int t2 = 8; int t3 = 5; int remain = 6; int[] bints = new int[] { 12, 0, 0 }; GetTPath gtp = new GetTPath(); string str = gtp.GetPath(bints, t1, t2, t3, remain); Response.Write(str.Replace(";","<br>"));}