两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两和一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好合打了一斤油，在回家的路上，二人想平分这一斤油，可是又没有其它工具。现只用这三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。
/*
* 两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两和一个三两的空瓶。
* 原计划各打一斤油，可是由于所带的钱不够，只好合打了一斤油，在回家的路上，二人想平分这一斤油，可是又没有其它工具。
* 现只用这三个瓶子(一斤、七两、三两)精确地分出两个半斤油来
* (1斤 = 10两)
*/
public class SpearateOil
{
/// <summary>
/// 设置每个瓶子最大容量
/// </summary>
static int[] MaxOil = { 10, 7, 3 };
/// <summary>
/// 存放每个瓶子历史容量
/// </summary>
static List<int[]> History = new List<int[]>() { new int[] { 10, 0, 0 } };
/// <summary>
/// 存放每个历史步骤
/// </summary>
/// <remarks>仅供查看</remarks>
static List<int[]> Steps = new List<int[]>();
/// <summary>
/// 运行
/// </summary>
public static void Go()
{
//初始化油的容量
int[] initialOil = { 10, 0, 0 };
//用于记录上一步骤
int[] lastStep = null;
//循环“倒油”,直到出现平均为止
while (!(initialOil[0] == 5 && initialOil[1] == 5))
{
lastStep = Step(ref initialOil, lastStep);
//防止死循环
if (lastStep ==null)
{
break;
}
}
//显示结果
for (int i = 0; i < History.Count; i++)
{
var item = History[i];
if(i > 0)
{
Console.WriteLine("{3} {0},{1},{2}", item[0], item[1], item[2]
, Steps[i - 1][0] + "->" + Steps[i - 1][1]);
}
}
}
/// <summary>
/// “倒油 ”
/// </summary>
/// <param name="fromIndex">源油瓶索引</param>
/// <param name="toIndex">目标油瓶索引</param>
/// <param name="oilStatus">油状态</param>
public static void SwichOil(int fromIndex, int toIndex, ref int[] oilStatus)
{
int toMax = MaxOil[toIndex] - oilStatus[toIndex];
int from = oilStatus[fromIndex];
if (from >= toMax)
{
oilStatus[fromIndex] = oilStatus[fromIndex] - toMax;
oilStatus[toIndex] = MaxOil[toIndex];
}
else
{
oilStatus[toIndex] += oilStatus[fromIndex];
oilStatus[fromIndex] = 0;
}
}
/// <summary>
/// 对比两个油的状态是否一样
/// </summary>
/// <param name="oil1"></param>
/// <param name="oil2"></param>
/// <returns></returns>
private static bool Compare(int[] oil1, int[] oil2)
{
for (int i = 0; i < 3; i++)
{
if(oil1[i] != oil2[i])
{
return false;
}
}
return true;
}
/// <summary>
/// 倒油步骤
/// </summary>
/// <param name="oil">倒油前的油瓶状态</param>
/// <param name="lastStep">上一个步骤</param>
/// <returns>返回新的步骤</returns>
public static int[] Step(ref int[] oil, int[] lastStep)
{
//新步骤
int[] step = null;
//把油瓶状态做一个备份
int[] recordOil = new int[3];
oil.CopyTo(recordOil, 0);
//循环源油瓶索引
for (int from = 0; from < 3; from++)
{
if (oil[from] == 0)
{
//如果源油瓶为0，则continue
continue;
}
//循环目标油瓶索引
for (int to = 0; to < 3; to++)
{
//是否找到步骤
bool isFindStep = true;
if (from == to)
{
//源与目标相同的话，略过
continue;
}
if (lastStep != null && lastStep[1] == from && lastStep[0] == to)
{
//步骤与上一次步骤lastStep是反操作的，略过
continue;
}
if (oil[to] == MaxOil[to])
{
//目标油瓶容量已达到极限，掠过
continue;
}
//“倒油”
SwichOil(from, to, ref oil);
//查看新状态是否存在历史存在过
foreach (var item in History)
{
if (Compare(item, oil))
{
//如果有，则跳出并复原
isFindStep = false;
recordOil.CopyTo(oil, 0);//复原
break;
}
}
//如果已找寻到步骤
if (isFindStep)
{
//记录步骤，以及记录新油瓶容量状态
step = new int[] { from, to };
int[] newOil = new int[3];
oil.CopyTo(newOil, 0);
History.Add(newOil);
break;
}
}
//如果找寻到步骤，就跳出循环
if (step != null)
{
Steps.Add(step);
break;
}
}
return step;
}
}
输出结果：
0->1 3,7,0
0->2 0,7,3
1->0 7,0,3
2->1 7,3,0
0->2 4,3,3
2->1 4,6,0
0->2 1,6,3
2->1 1,7,2
1->0 8,0,2
2->1 8,2,0
0->2 5,2,3
2->1 5,5,0