分油问题

Question

设有大小不等的X，Y，Z三个无刻度的油桶，分别能够盛满油X，Y，Z(例如，X=80，Y=50，Z=30)，并约定X>Y>Z。初始时，仅X油桶盛满油，Y和Z油桶为空。要求程序寻找一种最少的分油步聚，在某个油桶中分出T升油(例如T=40)。 
1。用深度遍历实现 
2。用广度遍历实现 
3。用队列实现 
4。面向对象方法实现
唐山迪锐公司：www.tsp2c.cn

Answer 1

4,貌似可以..1,2,3不懂。关于算法，我想用java的别太去考虑这个东西。关键在于，你用java就注定你必须会损失一定的效率。当然，算法不能太丑陋。大众的，最好效率的还是应该要懂。比如红黑树。。

Answer 2

public static List<subOilType> subOil(int X, int Y, int Z, int T)
        {
            List<subOilType> value = null;
            if (X > 0 && Y > 0 && Z > 0 && T > 0 && X >= T)
            {
                int mod = maxMod(X, Y);
                if (mod != 1) mod = maxMod(mod, Z);
                if (mod == 1 || (T % mod) == 0)
                {
                    subOilInfo info;
                    Dictionary<long, subOilInfo> minValue = new Dictionary<long, subOilInfo>();
                    subOil(X, X, Y, 0, Z, 0, T, minValue, int.MaxValue);
                    value = new List<subOilType>();
                    int subValue = 0, xValue = X, yValue = 0, zValue = 0;
                    for (long valueKey = ((long)xValue) << 32; minValue.ContainsKey(valueKey); valueKey = (((long)xValue) << 32) + yValue)
                    {
                        value.Add((info = minValue[valueKey]).type);
                        if (info.type == subOilType.XtoY)
                        {
                            xValue -= (subValue = Math.Min(xValue, Y - yValue));
                            yValue += subValue;
                        }
                        else if (info.type == subOilType.XtoZ)
                        {
                            xValue -= (subValue = Math.Min(xValue, Z - zValue));
                            zValue += subValue;
                        }
                        else if (info.type == subOilType.YtoX)
                        {
                            yValue -= (subValue = Math.Min(yValue, X - xValue));
                            xValue += subValue;
                        }
                        else if (info.type == subOilType.YtoZ)
                        {
                            yValue -= (subValue = Math.Min(yValue, Z - zValue));
                            zValue += subValue;
                        }
                        else if (info.type == subOilType.ZtoX)
                        {
                            zValue -= (subValue = Math.Min(zValue, X - xValue));
                            xValue += subValue;
                        }
                        else if (info.type == subOilType.ZtoY)
                        {
                            zValue -= (subValue = Math.Min(zValue, Y - yValue));
                            yValue += subValue;
                        }
                        Console.WriteLine(info.type.ToString() + " : " + subValue.ToString() + " => " + xValue.ToString() + " , " + yValue.ToString() + " , " + zValue.ToString());
                    }
                }
                else value = null;
            }
            return value;
        }
        private static int subOil(int X, int xValue, int Y, int yValue, int Z, int zValue, int T, Dictionary<long, subOilInfo> minValue, int maxCount)
        {
            int value = -1;
            long valueKey = (((long)xValue) << 32) + yValue;
            if (minValue.ContainsKey(valueKey))
            {
                if (minValue[valueKey].count != -1) value = minValue[valueKey].count;
            }
            else if (xValue == T || yValue == T || zValue == T) value = 0;
            else
            {
                int nextValue, subValue, nextCount = maxCount - 1;
                subOilInfo info = new subOilInfo { count = -1 };
                minValue.Add(valueKey, info);
                if (xValue != 0 && nextCount > 0 && Y != yValue && (nextValue = subOil(X, xValue - (subValue = Math.Min(xValue, Y - yValue)), Y, yValue + subValue, Z, zValue, T, minValue, nextCount)) != -1)
                {
                    info.type = subOilType.XtoY;
                    value = nextValue + 1;
                    nextCount = nextValue - 1;
                }
                if (xValue != 0 && nextCount > 0 && Z != zValue && (nextValue = subOil(X, xValue - (subValue = Math.Min(xValue, Z - zValue)), Y, yValue, Z, zValue + subValue, T, minValue, nextCount)) != -1)
                {
                    info.type = subOilType.XtoZ;
                    value = nextValue + 1;
                    nextCount = nextValue - 1;
                }
                if (yValue != 0 && nextCount > 0 && X != xValue && (nextValue = subOil(X, xValue + (subValue = Math.Min(yValue, X - xValue)), Y, yValue - subValue, Z, zValue, T, minValue, nextCount)) != -1)
                {
                    info.type = subOilType.YtoX;
                    value = nextValue + 1;
                    nextCount = nextValue - 1;
                }
                if (yValue != 0 && nextCount > 0 && Z != zValue && (nextValue = subOil(X, xValue, Y, yValue - (subValue = Math.Min(yValue, Z - zValue)), Z, zValue + subValue, T, minValue, nextCount)) != -1)
                {
                    info.type = subOilType.YtoZ;
                    value = nextValue + 1;
                    nextCount = nextValue - 1;
                }
                if (zValue != 0 && nextCount > 0 && X != xValue && (nextValue = subOil(X, xValue + (subValue = Math.Min(zValue, X - xValue)), Y, yValue, Z, zValue - subValue, T, minValue, nextCount)) != -1)
                {
                    info.type = subOilType.ZtoX;
                    value = nextValue + 1;
                    nextCount = nextValue - 1;
                }
                if (zValue != 0 && nextCount > 0 && Y != yValue && (nextValue = subOil(X, xValue, Y, yValue + (subValue = Math.Min(zValue, Y - yValue)), Z, zValue - subValue, T, minValue, nextCount)) != -1)
                {
                    info.type = subOilType.ZtoY;
                    value = nextValue + 1;
                    nextCount = nextValue - 1;
                }
            }
            return value;
        }
        public enum subOilType
        {
            XtoY,
            YtoX,
            XtoZ,
            ZtoX,
            YtoZ,
            ZtoY,
        }
        private class subOilInfo
        {
            public int count;
            public subOilType type;
        }
        private static int maxMod(int theMod, int mod)
        {
            if (mod == 1) theMod = 1;
            else if (theMod > 1 && theMod != mod)
            {
                bool leftOrRight;
                int nextMod = mod;
                for (leftOrRight = (theMod > nextMod); (leftOrRight ? nextMod : theMod) > 1; leftOrRight = !leftOrRight) { if (leftOrRight) theMod %= nextMod; else nextMod %= theMod; }
                if ((leftOrRight ? nextMod : theMod) == 0) { if (!leftOrRight) theMod = nextMod; }
                else theMod = 1;
            }
            return theMod;
        }

Answer 3

80->50,50->30,30->80,50(20)->30,80->50,50-(10)>30(20),50(40)