面试遇到的算法题:两个杯子量水

Question

2个杯子  容积分别为a和b （int型 大于0）  想用这两个杯子称出c升水(c也是int型 大于0）
要求 a b c全部由用户输入  然后写出每一步的详细情况   并且 每一步只能动一个杯子
比如 a=1 b=2 要求称3升水 步骤为
1,0
1,2
每次只能给一个杯子装水(即不能直接输出1,2)   倒水也一样
最后再屏幕上输出这些步骤  要求是最简步骤这个算法 怎么做哇......有什么思路么......

Answer 1

求模的运算，
c%（a+b）   c%|(a-b)|
|| 是绝对值也有可能无解。
本人愚见，也请高人斧正。

Answer 2

终于搞定static void Main(string[] args)
        {
            
            int a, b, c;
            Console.WriteLine("请先输入A容器大小：");
            a = Int32.Parse(Console.ReadLine());
            Console.WriteLine("输入B容器大小：");
            b = Int32.Parse(Console.ReadLine());            Console.WriteLine("输入C大小：");
            c = Int32.Parse(Console.ReadLine());            int mod = 0,count;            count = c / (a > b ? a : b);
            mod = c % (a > b ? a : b) ;
            if (mod == 0)
            {
                for (int i = 1; i <= count; i++)
                {
                    Console.WriteLine("第" + i.ToString() + "步：" + (a > b ? a : b).ToString() + ":" + (a > b ? a : b).ToString() + "     " + ((a > b ? b : a).ToString()) + ":0");
                }
            }
            else
            {
                bool flog = false;
                for (int i = count; i > 0; i--)
                {
                    if ((c - i * (a > b ? a : b)) % (a > b ? b : a) == 0)
                    {
                        for (int j = 1; j <= i; j++)
                        {
                            Console.WriteLine("第" + j.ToString() + "步：" + (a > b ? "a" : "b") + ":" + (a > b ? a : b).ToString() + "     " + (a > b ? "b" : "a") + ":0");
                        }
                        for (int j = i + 1; j < (c - i * (a > b ? a : b)) / (a > b ? b : a) + i + 1; j++)
                        {
                            Console.WriteLine("第" + j.ToString() + "步：" + (a > b ? "a" : "b") + ":0     " + (a > b ? "b" : "a") + ":" + (a > b ? b : a).ToString());
                        }
                        flog = true;
                    }
                }
                if (!flog)
                {
                    Console.WriteLine("无法测量！最后剩余：" + ((c % (a > b ? a : b)) % (a > b ? b : a)).ToString());                }
            }
            Console.ReadLine();
        }

Answer 3

用宽搜可以，用欧几里德扩展求模逆也可以（解一个模方程），有解的前提是c % gcd(a,b) = 0。

Answer 4

改进版，特殊情况判断：static void Main(string[] args)
        {
            
            int a, b, c;
            Console.WriteLine("请先输入A容器大小：");
            a = Int32.Parse(Console.ReadLine());
            Console.WriteLine("输入B容器大小：");
            b = Int32.Parse(Console.ReadLine());            Console.WriteLine("输入C大小：");
            c = Int32.Parse(Console.ReadLine());            int mod = 0,count;
            
            if (c < (a > b ? b : a))
            {
                Console.WriteLine("无法测量！最后剩余：" + (a > b ? b : a).ToString());
                Console.ReadLine();
                return;
            }
            else if (c < (a > b ? a : b))
            {
                mod = c % (a > b ? b : a);
                count = c / (a > b ? b : a);
                if (mod == 0)
                {
                    for (int i = 1; i <= count; i++)
                    {
                        Console.WriteLine("第" + i.ToString() + "步：" + (a > b ? "a" : "b") + ":0     " + (a > b ? "b" : "a") + ":" + (a > b ? b : a).ToString());
                    }
                }
                else
                {
                    Console.WriteLine("无法测量！最后剩余：" + (c  % (a > b ? b : a)).ToString());
                }
                Console.ReadLine();
                return;
            }
            else
            {
                count = c / (a > b ? a : b);
                mod = c % (a > b ? a : b);
                if (mod == 0)
                {
                    for (int i = 1; i <= count; i++)
                    {
                        Console.WriteLine("第" + i.ToString() + "步：" + (a > b ? "a" : "b") + ":" + (a > b ? a : b).ToString() + "     " + (a > b ? "b" : "a") + ":0");
                    }
                }
                else
                {
                    bool flog = false;
                    for (int i = count; i > 0; i--)
                    {
                        if ((c - i * (a > b ? a : b)) % (a > b ? b : a) == 0)
                        {
                            for (int j = 1; j <= i; j++)
                            {
                                Console.WriteLine("第" + j.ToString() + "步：" + (a > b ? "a" : "b") + ":" + (a > b ? a : b).ToString() + "     " + (a > b ? "b" : "a") + ":0");
                            }
                            for (int j = i + 1; j < (c - i * (a > b ? a : b)) / (a > b ? b : a) + i + 1; j++)
                            {
                                Console.WriteLine("第" + j.ToString() + "步：" + (a > b ? "a" : "b") + ":0     " + (a > b ? "b" : "a") + ":" + (a > b ? b : a).ToString());
                            }
                            flog = true;
                            break;
                        }
                    }
                    if (!flog)
                    {
                        Console.WriteLine("无法测量！最后剩余：" + ((c % (a > b ? a : b)) % (a > b ? b : a)).ToString());                    }
                }
            }
            Console.ReadLine();
        }

Answer 5

可惜好像还是无法测量啊。其实算法应该跟输出分离开。算法就是搜索出“倒满、倒入、倒空”这三种操作行为的一个IEnumeable<MyAction>列表，实际上使用.net迭代器，可能用不了15行语句就能枚举出操作序列来。当然要是求最简，则需要另外一个Linq查询来遍历所有解答。

Answer 6

无解的情况 就是
c%|(a+b)| 和 c %|(a-b)| 有余数的情况。
c%a   c%b 这些都不等于0时，就无解了。 总结下就是 c%(na+mb) <> 0 (任何一组都不成立时)
这只是特例，其实还有（Na-b) 或（nb - b)等等。
如： a = 5 b = 5 c = 1就是无解的情况 。
情况 比我刚看到时估计的复杂些。
 

Answer 7

我的思路是先按照最大的测量，假如A，B，中A是较大的，
先算出C和A的余数mod，C/A的值count，
如果mod和B取余不等于0说明不可行，然后C=（count-1）乘A，然后再判断C和B的余数，如果仍不为0，则继续。知道C=C的时候在判断C和B的余数，如果还是不为零，则说明不能测量。
中间只要出现等于0的情况，就说明可以测量的，并且肯定是最简步骤，因为，在循环中已经用A最大可能性的量出。

Answer 8

就是上面的数据，a=3、b=7、c=5，没有给出答案。

Answer 9

你这组数据对着呢呀，3,7,5是无法测量。
我改进后的是答案是：
请先输入A容器大小：
3
输入B容器大小：
7
输入C大小：
5
无法测量！最后剩余：2

Answer 10

用递归可以，我写的代码确实多了。
刚开始是按照自己的思路一行一行的写，没有考虑到代码优化。
不过当C特别大，A和B特别小，比如都等于1 的时候，我现在写的代码是不是要比用递归效率高些？毕竟少了来回调用函数了么、O(∩_∩)O~

Answer 11

这是用数学方法解的，后面逻辑还可以优化。
using System;namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 3, b = 5, c = 7;
            int countA, countB;
            EuclidExtend(a, b, out countA, out countB);
            countA *= c;
            countB *= c;            int temp = countA / b;
            countA -= temp * b;
            countB += temp * a;            if (Math.Abs(countA) + Math.Abs(countB) > Math.Abs(countA + b) + Math.Abs(countB - a))
            {
                countA += b;
                countB -= a;
            }            if (Math.Abs(countA) + Math.Abs(countB) > Math.Abs(countA - b) + Math.Abs(countB + a))
            {
                countA -= b;
                countB += a;
            }            Console.WriteLine("{0} = ({1}*{2}) + ({3}*{4})", c, a, countA, b, countB);
        }        public static int EuclidExtend(int X, int Y, out int A, out int B)
        {
            if (Y == 0) { A = 1; B = 0; return X; }            int quotient = X / Y;
            int gcd = EuclidExtend(Y, X - Y * quotient, out A, out B);            int Temp = A; A = B; B = Temp - quotient * A;
            return gcd;
        }
    }
}

Answer 12

为什么我用了
c%(na-mb), 有这么一种情况，象 a = 2 b = 5  c = 1,
是否有解，其实 你看 5 - 2*2 = 1了。
因为c只有一个，一次只能移一个杯，所以，
c%(na-mb)中，n,m 必有一个为1.

Answer 13

这贴挺有意思的，喜欢这种讨论。
我觉得你可能要搜索四种情况 ：
c%a c%b c%(ma-nb) c%(ma+nb)
考虑，让 n = 0 ,1,3式就相等了。 让m = 0, 2 4式就相等了。
只考虑两种情况 (m,n必须一个为1），
递推下去应该可以解决。

Answer 14

        void test(int a, int b, int c) { 
            //swap a,b resut = a > b
            if(a < b){
                int k = b;
                b = a;
                a = k;
            }            int m = 1,n = 0;            if (c % a == 0 || c % b == 0) {
                Debug("OK");
                return;
            }            // n = 1, m >= 1
            m = 1;
            while (c > m * a - b) {
                if (c % (m * a - b) == 0) {
                    Debug(string.Format("{0} * {1} - {}2",m,a,b));
                    return;
                }                m++;
            }
            //m = 1,n >= 1
            n = 1;
            while (c > a - n*b && a - n*b > 0) {
                if (c % (a - n*b) == 0) {
                    Debug(string.Format("{0} - {1} * {2}",a,n,b));
                    return;
                }
                n++;
            }            //-------------------------
            // m = 1,n >= 1
            n = 1;
            while (c > a - n*b) {
                if (c % (a - n*b) == 0) {
                    Debug(string.Format("a - n*b = {0} - {1}* {2}",a,n,b));
                    return;
                }                n++;
            }            //3  n = 1, m >= 1
            m = 1;
            while (c > m*a + b ) {
                if (c % (m*a + b) == 0) {
                    Debug(string.Format("m*a + b = {0}*{1} + {2}",m,a,b));
                    return;
                }
                m++;
            }            Debug("无解");
        }        void Debug(string s) {
            MessageBox.Show(s);
        }这个应该可以了， 只是没有打印出来过程。
在循环中加入debug
debug()重载成输出，就应该可以了。

Answer 15

            //-------------------------
            // m = 1,n >= 1
            n = 1;
            while (c > a + n*b) {
                if (c % (a + n*b) == 0) {
                    Debug(string.Format("a + n*b = {0} + {1}* {2}",a,n,b));
                    return;
                }                n++;
            }
还是有个地方错了， 用这个替换 。

Answer 16

还是贴个完整版吧。 不知是否有漏洞，请大家指正。        void test(int a, int b, int c) { 
            //swap a,b resut = a > b
            if(a < b){
                int k = b;
                b = a;
                a = k;
            }            int m = 1,n = 0;            if (c % a == 0 || c % b == 0) {
                Debug("OK");
                return;
            }            // n = 1, m >= 1
            m = 1;
            while (c > m * a - b) {
                if (c % (m * a - b) == 0) {
                    Debug(string.Format("{0} * {1} - {}2",m,a,b));
                    return;
                }                m++;
            }
            //m = 1,n >= 1
            n = 1;
            while (c > a - n*b && a - n*b > 0) {
                if (c % (a - n*b) == 0) {
                    Debug(string.Format("{0} - {1} * {2}",a,n,b));
                    return;
                }
                n++;
            }            //-------------------------
            // m = 1,n >= 1
            n = 1;
            while (c > a + n*b) {
                if (c % (a + n*b) == 0) {
                    Debug(string.Format("a + n*b = {0} + {1}* {2}",a,n,b));
                    return;
                }                n++;
            }            //3  n = 1, m >= 1
            m = 1;
            while (c > m*a + b ) {
                if (c % (m*a + b) == 0) {
                    Debug(string.Format("m*a + b = {0}*{1} + {2}",m,a,b));
                    return;
                }
                m++;
            }            Debug("无解");
        }
         
        void Debug(string s) {
            MessageBox.Show(s);
        }

Answer 17

修改了一下，似乎可以求最优解了（还得测试一下，谁叫我总是眼高手低呢！唉！），不过数据还是不能太大，有溢出的可能，换成long应该可以处理int范围内的数据。不过输出的仍然是奇怪的数学公式，具体还原成步骤不是咱的长项，嘿嘿。
using System;namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 1597, b = 2584, c = 198787;
            int countA, countB;            if (!Linear(a, b, c, out countA, out countB))
                Console.WriteLine("无解");            int temp = a > b ? Math.Abs(countB / a) : Math.Abs(countA / b);
            int flag = countA < 0 ? 1 : -1;
            int minA = 0, minB = 0, minSum = int.MaxValue;            for (int i = temp - 1; i <= temp + 1; i++)
            {
                int sum = Math.Abs(countA + (i * b) * flag) + Math.Abs(countB - (i * a) * flag);
                if (sum < minSum)
                {
                    minA = countA + (i * b) * flag;
                    minB = countB - (i * a) * flag;
                    minSum = sum;
                }
            }            Console.WriteLine("{0} = ({1}*{2}) + ({3}*{4})", c, a, minA, b, minB);
        }        public static int EuclidExtend(int X, int Y, out int A, out int B)
        {
            if (Y == 0) { A = 1; B = 0; return X; }            int quotient = X / Y;
            int gcd = EuclidExtend(Y, X - Y * quotient, out A, out B);            int Temp = A; A = B; B = Temp - quotient * A;
            return gcd;
        }        public static bool Linear(int X, int Y, int N, out int A, out int B)
        {
            int gcd = EuclidExtend(X, Y, out A, out B);
            int K = N / gcd;            if (N != K * gcd) { A = 0; B = 0; return false; }            A *= K; B *= K;
            return true;
        }
    }
}

Answer 18

果然有bug，发现了，顺便改成了long，自己再测测！using System;namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = 1597, b = 2584, c = 198787;
            long countA, countB;            int gcd = EuclidExtend(a, b, out countA, out countB);
            int K = c / gcd;            if (c != K * gcd)
            {
                Console.WriteLine("无解");
                return;
            }            countA *= K; countB *= K; a /= gcd; b /= gcd;            int temp = a > b ? (int)Math.Abs(countB / a) : (int)Math.Abs(countA / b);
            int flag = countA < 0 ? 1 : -1;
            long minA = 0, minB = 0, minSum = int.MaxValue;            for (int i = temp - 1; i <= temp + 1; i++)
            {
                long sum = Math.Abs(countA + (i * b) * flag) + Math.Abs(countB - (i * a) * flag);
                if (sum < minSum)
                {
                    minA = countA + (i * b) * flag;
                    minB = countB - (i * a) * flag;
                    minSum = sum;
                }
            }            Console.WriteLine("{0} = ({1}*{2}) + ({3}*{4})", c, a * gcd, minA, b * gcd, minB);
        }        public static int EuclidExtend(int X, int Y, out long A, out long B)
        {
            if (Y == 0) { A = 1; B = 0; return X; }            int quotient = X / Y;
            int gcd = EuclidExtend(Y, X - Y * quotient, out A, out B);            long Temp = A; A = B; B = Temp - quotient * A;
            return gcd;
        }
    }
}

Answer 19

看见楼主的题目，感觉自己变NC了，
A=30；
B=70;
C=2;
仅仅在脑海里输入这3个参数，我都无法得出答案，别说编程了

Answer 20

3个以上的杯子用DP可以，前提是C不能太大，100万以内的话可以，实际上是一个背包问题，也是算法问题，还不涉及“智能”

Answer 21

可以试想有3个容器A B 和C
C是假想的无穷大的容器
杯子的属性： 容积 水量 剩余容积
方法 从杯子x向杯子y倒入z升的水
我的思路 数据库 表 存储过程/函数 递归 事务 
回滚条件：出现已出现过的杯子存水状态，
终止条件：出现解/杯子1所有操作都递归过  

Answer 22

to：sp1234牛您把问题弄复杂了，按照LZ原题的要求，我的程序只输出了“奇怪的数学公式”，比如58 = 5 * 11 + 3(5和3是杯子的容量)，但这个真的很难理解么？讨论算法点到为止即可，我只是说这个算法的思路，并不是要替LZ写出具体程序。如果真的按照ACM的标准，您给出的输出同样是不合标准的，LZ要求的是：1,0
1,2况且您真的认为您给出的那么长的序列会比我给出的“奇怪的数学公式”更好验证么？不要说3个杯子，就是100个杯子，求最优都可以用动态规划来解（DP），只要C不是很大，都可以在内存中完成计算。这只是一个入门级的算法题，相信里人工智能还有很远的距离，最多也就是考察一下算法设计者的“智能”。可以放心的是，绝对不会惊动到数学家的，像我这样的小程序员就可以搞定。作为程序员讨论这个算法，我可以说，用欧几里得扩展的方法，时间复杂度是O（Log(n)）的，用动态规划的方法，时间复杂度要高很多，是O(m*n)的，其中n是c取值的范围，m是杯子的个数。以上两个程序都可以在100行代码以内解决问题，绝不是什么高科技。而您所提到的“人工智能搜索”，复杂度如何呢？