求助 简单的递归算法

一组数的规则如下：1、1、2、3、5、8、13、21、34.....，求第30位数是多少？用递归方式实现

另外还有两个面试题，求解答。
1、A说B说谎，B说C说谎，C说A、B说谎，请问到底谁说谎？
2、有一个三升的水杯和一个五升的水杯，如何倒四升的水？

智商拙计 真心求帮助 万分感谢！

37 个解决方案

#1

第一题是斐波那契数列
int Fibonacci(int n)
{
 if( n == 1 || n == 2) // 递归结束的条件，求前两项
  return 1;
 else
  return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。
}
第二题最笨的方法是三个for循环遍历
第三题是
方法一 
1.用3升的容器接满水，倒入5升容器中。 
2.再用3升的容器接满，倒入5升容器中。此时3升容器中还剩下1升水。 
3.将5升容器中的水倒掉，将3升容器中剩下的1升水倒入5升容器。 
4.再将3升容器接满水倒入5升容器中，此时5升容器中就是4升水。 

方法二 
1.用5升的容器接满水，倒入3升容器中。此时5升容器中有2升水。 
2.将3升容器中的水倒掉，在将5升容器中剩下的水倒入3升容器中。此时3升容器中有2升水。 
3.将5升容器接满水，把水再倒入3升容器中至满。此时5升容器中剩4升水。

#2

一组数的规则如下：1、1、2、3、5、8、13、21、34.....，求第30位数是多少？用递归方式实现

------
这些网上都有现成的答案 都是以前面试的题目 论坛也有 搜下

1、A说B说谎，B说C说谎，C说A、B说谎，请问到底谁说谎？
2、有一个三升的水杯和一个五升的水杯，如何倒四升的水？

1.C说谎了
2.好像要来回倒几次

--------------------- 这面试题目真没什么价值 网上泛滥答案

#3

引用 2 楼  的回复:

一组数的规则如下：1、1、2、3、5、8、13、21、34.....，求第30位数是多少？用递归方式实现

------
这些网上都有现成的答案 都是以前面试的题目 论坛也有 搜下

1、A说B说谎，B说C说谎，C说A、B说谎，请问到底谁说谎？
2、有一个三升的水杯和一个五升的水杯，如何倒四升的水？

1.C说谎了
2.好像要来回倒几次

------------------……

为什么是C说谎了啊？？

#4

菲波拉切数列，稍微知识面广一点的中学生都应该知道。

这个数列有一个有趣的性质，就是前一项/后一项逼近0.618黄金分割。

#5

1、A说B说谎，B说C说谎，C说A、B说谎，请问到底谁说谎？

if a 说谎， then b 不说慌， then c 说谎， then a or b 不说谎， 不矛盾
if a 不说谎, then b 说谎， then c 不说谎, then a and b 说谎， 矛盾

所以a,c说谎

分析不难，但想用prolog编个程序，请高人教我，谢谢！

#6

该回复于2012-04-19 11:15:32被版主删除

#7

既然prolog编不来，尝试用c#编，开始觉得不难，可是昨天搞了一下午，仍然有bug,今天又搞了一会，总算初步能工作了，代码又臭又长，只不过花了不少时间写的，敝帚自珍吧。如果有高手指导我改进或者给出更好的思路，不胜感激！

private void button1_Click(object sender, EventArgs e) //做了个win form程序
{
                //这里用xml来表示，p表示人, islie取值为t (表示说谎) 或者 f(表示没说谎)
                //say表示这个人说的话。"!b" 表示'b说谎'，"b" 表示'b没说谎'， "!a, !b"
                //表示'a, b都说谎'， "!a;!b"表示'a或者b说谎'，余类推。规定不能用!,;三
                //种符号结尾
                string xml = "<Data>"
                    + "<p name='a' islie='' say='!b' isset='0' />"
                    + "<p name='b' islie='' say='!c' isset='0'  />"
                    + "<p name='c' islie='' say='!a,!b' isset='0'  />"
                    + "</Data>";

                XDocument xdoc = XDocument.Parse(xml);
                var item = xdoc.Descendants("p").FirstOrDefault();
                //任一人只有两种可能，说谎或者不说谎，因此任取1人足矣
                    if (String.IsNullOrEmpty(item.Attribute("islie").Value))
                    {
                        item.SetAttributeValue("islie", "f");//假设该人没说谎
                        if (isLie(item) == false)
                        {//若返回false,说明假设错误
                            foreach (var item2 in xdoc.Descendants("p"))
                            {//复位
                                item2.SetAttributeValue("islie", "");
                                item2.SetAttributeValue("isset", "0");
                            }
                            item.SetAttributeValue("islie", "t");//重新假设
                            if (isLie(item) == false)
                            {//说明无解
                                displayAnswer(item, false);
                                break;
                            }
                            else
                            {
                                displayAnswer(item, true);
                                break;
                            }
                        }
                        else
                        {
                            displayAnswer(item, true);
                            break;
                        }
                    }
                
}

        private bool isLie(XElement item)
        {//测试的主函数，返回true说明没有出现矛盾，可能有解，否则出现了矛盾，可能无解
            string relationType = "and";//缺省关系为'与'
            bool result = true;
            var xdoc = item.Document;
            if (hasEmptyValue(xdoc))//检查是否满足结束递归条件
            {
                string v = item.Attribute("islie").Value;
                bool bIsLie = (v == "t") ? true : false;
                bool tIsLie = bIsLie;
                string say = item.Attribute("say").Value;
                List<char> tmp = new List<char>();
                string tmpString = null;
                bool? tmpResult = null;
                for (int i = 0; i < say.Length; i++)
                {//解析say属性字符串
                    switch (say[i])
                    {
                        case ' ':
                            continue;
                        case '!':
                            bIsLie = !bIsLie;
                            break;
                        case ';':
                            tmpString = new string(tmp.ToArray());
                            if (tIsLie)
                            {//若说谎，则关系需要改变，即;需变成,
                                relationType = "and";
                            }
                            else
                            {
                                relationType = "or";
                            }
                            tmpResult = checkNode(tmpString, xdoc, tmp, bIsLie, relationType, false);//这里递归检查是否有解
                            if (result == null)
                            {//若出现矛盾，说明此路不通
                                return false;
                            }
                            else
                            {
                                result = tmpResult.Value;
                            }
                            break;
                        case ',':
                            tmpString = new string(tmp.ToArray());
                            if (tIsLie)
                            {
                                relationType = "or";
                            }
                            else
                            {
                                relationType = "and";
                            }
                            tmpResult = checkNode(tmpString, xdoc, tmp, bIsLie, relationType, false);
                            if (result == null)
                            {
                                return false;
                            }
                            else
                            {
                                result = tmpResult.Value;
                            }
                            break;
                        default:
                            tmp.Add(say[i]);
                            break;
                    }
                }
                if (tmp.Count > 0)
                {
                    tmpString = new string(tmp.ToArray());
                    tmpResult = checkNode(tmpString, xdoc, tmp, bIsLie, relationType, true);
                    if (tmpResult == null)
                    {
                        return false;
                    }
                    else
                    {
                        result = tmpResult.Value;
                    }
                }

            }
            return result;
        }

        //递归检查是否有解的函数
        private bool? checkNode(string tmpString, XDocument xdoc, List<char> tmp, bool bIsLie, string newRelationType, bool isFinal)
        {//isFinal参数指定是否求出中间结果或最后结果
            //tmpResult = true;
            bool? tmpResult = true;
            var node = (from x in xdoc.Descendants("p")
                        where x.Attribute("name").Value == tmpString
                        select x).FirstOrDefault();
            //比如a说b说谎，xml表示为<p name='a' islie='' say='!b' isset='0' />,这里就取到<p name='b' ... />，然后递归地对b说的人等加以判断
            tmp.Clear();
            string islie = bIsLie ? "t" : "f";
            bIsLie = !bIsLie;
            int tset = Int32.Parse(node.Attribute("isset").Value);
            tset++;
            if (String.IsNullOrEmpty(node.Attribute("islie").Value))
            {//若还没有计算islie值，则填入
                node.SetAttributeValue("islie", islie);
                node.SetAttributeValue("isset", tset);
                tmpResult = (bool?)isLie(node);
                if (tmpResult != null && tmpResult.Value == false)
                {//返回false说明出现了矛盾，需要修正假设
                    if (islie == "t")
                    {
                        islie = "f";
                    }
                    else
                    {
                        islie = "t";
                    }
                    node.SetAttributeValue("islie", islie);
                }
            }
            else if (node.Attribute("islie").Value != islie)
            {//和已填的值不一致，出现了矛盾
                if (newRelationType == "and")
                {//若当前关系是'与'，则没有必要再计算下去，肯定无解
                    tmpResult = null;
                }
                else
                {
                    if (isFinal == false)
                    {//否则若是产生中间结果，尚不能确定是否有解
                        tmpResult = false;
                    }
                    else
                    {//否则，关系是'或'
                        if (tmpResult != null && tmpResult.Value == true)
                        {//若是最终结果，只要中间结果是true，最后结果还是true,因为true || false == true
                            node.SetAttributeValue("isset", tset);
                        }
                        else
                        {//否则，false || false == false
                            tmpResult = false;
                        }
                    }
                }
            }
            else
            {//若和已填结果一致
                if (!isFinal)
                {
                    tmpResult = true;
                    node.SetAttributeValue("isset", tset);
                }
                else
                {//若是最终结果
                    if (newRelationType == "or")
                    {//若关系是'或'，不管中间结果是什么都是true, 因为true || false == true; true && true == true
                        node.SetAttributeValue("isset", tset);
                        tmpResult = true;
                    }
                    else
                    {//否则取决于中间结果
                        if (tmpResult.Value == true)
                        {
                            node.SetAttributeValue("isset", tset);
                        }
                        else 
                        {
                            tmpResult = false;
                        }
                    }
                }
            }

            return tmpResult;
        }

        //检查结束递归条件的函数
        private bool hasEmptyValue(XDocument xdoc)
        {
            bool hasEmpty = false;
            foreach (var item in xdoc.Descendants("p"))
            {
                if (string.IsNullOrEmpty(item.Attribute("islie").Value)
                    || Int32.Parse(item.Attribute("isset").Value) < 2)
                {//若islie属性没填值，或者填了2次以下则认为还没处理完。这个2次的设置也许有问题，或者1次也够了，暂时不测
                    hasEmpty = true;
                    break;
                }
            }
            return hasEmpty;
        }

#8

        //显示结果的辅助函数
        private void displayAnswer(XElement item, bool hasAnswer)
        {
            if (!hasAnswer)
            {
                textBox1.Text = "no answer";
                return;
            }
            StringBuilder sb = new StringBuilder();
            string r = "";
            foreach (var node in item.Document.Descendants("p"))
            {
                if (node.Attribute("islie").Value == "t")
                {
                    r = "lie";
                }
                else if (node.Attribute("islie").Value == "f")
                {
                    r = "nolie";
                }
                sb.AppendLine(node.Attribute("name").Value + ":" + r);
            }
            textBox1.Text = sb.ToString();
        }

#9

第一题是面试经常出的。

二三题是高数的问题。看看高数的书。简单的太太！

#10

http://topic.csdn.net/u/20120420/11/ac898daf-bdf1-4185-8957-0ca0983f5e54.html?seed=606804668&r=78316949#r_78316949

#11

第一题，   private static int SubAdd(int j) 
        {
            if (j < 3) return 1;
            else return SubAdd(j - 1)+SubAdd(j-2);
        }
第2题，
c说谎了
1,如果a说谎，b,c矛盾
2，如b,ac矛盾
第3题，还真不会

#12

楼上推理错误。
对任一人来说，只有两种可能，要么说谎，要么不说谎，所以只要假设两次，然后看是否会引出矛盾，就可知道是否有解。

设a说谎，a说b说谎， 但a本身已说谎，所以推出b没说谎，同理推出 c说谎，既然c说a,b都说谎，那么反过来就是a或者b没说谎，和假设及前面的推理结果“a说谎，b没说谎”并不矛盾，所以这是一个解。（如果题目规定只有一个人说谎则无解）
同理可推出若a没说谎，则有矛盾，所以不成立。

设b或c说谎，推理结果也一样。

#13

第2题想了一下，感觉好像是个复杂度为2^n的问题，似乎没有什么好办法，c#代码如下：

        public class Cups
        {//模拟两个杯子的数据结构，用类是因为方便引用传参
            public int CupA {get; set;}//小杯里的水量
            public int CupB {get; set;}//大杯里的水量
        }

        private void outputSteps(List<string>[] quickestSteps)
        {//输出最快的2个结果
            StringBuilder sb = new StringBuilder();
            foreach (List<string> steps in quickestSteps)
            {
                foreach (string step in steps)
                {
                    if (!String.IsNullOrEmpty(step))
                    {
                        string[] results = step.Split(new string[] { ":" }, StringSplitOptions.RemoveEmptyEntries);
                        string type = "";
                        if (string.Compare(results[0], "true", true) == 0)
                        {//转换成友好的输出
                            type = "Small cup to big cup:";
                        }
                        else
                        {
                            type = "Big cup to small cup:";
                        }
                        type += results[1] + " l water;";
                        sb.AppendLine(type);
                    }
                }
                sb.AppendLine("---------------------------");//区分不同的方法
            }
            textBox1.Text += sb.ToString();
        }

        private void checkQuickest(int[] quickestCounts, List<string>[] tempResult, List<string> steps)
        {//检查结果是否是最快的2个，简单地用数组复制加移位
            int count = steps.Count;
            for (int i = 0; i < quickestCounts.Length; i++)
            {
                if (count <= quickestCounts[i])
                {
                    if (count == quickestCounts[i])
                    {
                        bool isDuplicated = true;
                        for (int t = 0; t < steps.Count; t++)
                        {
                            if (string.Compare(steps[t], tempResult[i][t], true) != 0)
                            {
                                isDuplicated = false;
                                break;
                            }
                        }
                        if (isDuplicated)
                        {
                            break;
                        }
                    }
                    List<string> temp = new List<string>();
                    for (int j = 0; j < steps.Count; j++)
                    {
                        temp.Add(steps[j]);
                    }
                    for (int j = quickestCounts.Length - 1; j > i; j--)
                    {
                        quickestCounts[j] = quickestCounts[j - 1];
                        tempResult[j] = tempResult[j - 1];
                    }
                    quickestCounts[i] = count;
                    tempResult[i] = temp;
                    break;
                    //quickestCounts[i] = count;
                }
            }
        }

#14

        private void waterProblem()
        {//主函数
            Cups cups = new Cups();
            cups.CupA = 3;
            cups.CupB = 5;//初始两个杯子都装满水
            bool result = false;
            bool[] types = new bool[2];//只有两种操作可能会获得结果：小杯倒大杯或者大杯倒小杯。小/大杯倒空/倒满只是过渡操作，对结果无影响。
            List<string> steps = new List<string>();//存储操作步骤
            types[0] = true;//小杯倒大杯
            types[1] = false;//大杯倒小杯
            int[] quickestCounts = new int[2];
            for (int i = 0; i < quickestCounts.Length; i++)
            {
                quickestCounts[i] = 99;
            }
            List<string>[] tempResult = new List<string>[2];//存储临时的最佳结果。如果只是想得到所有可能的结果，不需要这个。但是不容易区分重复的方案。比如小杯倒给大杯2升水，大杯再倒回来。这两个步骤是无意义的，但是判断起来比较麻烦，这里忽略。
            for (int a = 0; a < types.Length; a++)
            {//用7层循环，最多考虑7步操作，若需要7步以上才能获得结果，则无法求出
                cups.CupA = 3;
                cups.CupB = 5;
                steps.Clear();
                result = pullWater(types[a], cups, steps);
                if (result)
                {//如果求出一种方法，检查是不是最优方案，然后继续找其他方法
                    checkQuickest(quickestCounts, tempResult, steps);
                    continue;
                }
                for (int b = 0; b < types.Length; b++)
                {
                    int cupsa_b = cups.CupA;//备份杯子的状态，以便无解时复位
                    int cupsb_b = cups.CupB;
                    result = pullWater(types[b], cups, steps);
                    if (result)
                    {
                        checkQuickest(quickestCounts, tempResult, steps);
                        steps.RemoveAt(steps.Count - 1);
                        cups.CupA = cupsa_b;//rollback
                        cups.CupB = cupsb_b;
                        continue;
                    }
                    for (int c = 0; c < types.Length; c++)
                    {
                        int cupsa_c = cups.CupA;
                        int cupsb_c = cups.CupB;
                        result = pullWater(types[c], cups, steps);
                        if (result)
                        {
                            checkQuickest(quickestCounts, tempResult, steps);
                            steps.RemoveAt(steps.Count - 1);//删掉无用的步骤
                            cups.CupA = cupsa_c;
                            cups.CupB = cupsb_c;
                            continue;
                        }
                        for (int d = 0; d < types.Length; d++)
                        {
                            int cupsa_d = cups.CupA;
                            int cupsb_d = cups.CupB;
                            result = pullWater(types[d], cups, steps);
                            if (result)
                            {
                                checkQuickest(quickestCounts, tempResult, steps);
                                steps.RemoveAt(steps.Count - 1);
                                cups.CupA = cupsa_d;
                                cups.CupB = cupsb_d;
                                continue;
                            }
                            for (int e = 0; e < types.Length; e++)
                            {
                                int cupsa_e = cups.CupA;
                                int cupsb_e = cups.CupB;
                                result = pullWater(types[e], cups, steps);
                                if (result)
                                {
                                    checkQuickest(quickestCounts, tempResult, steps);
                                    steps.RemoveAt(steps.Count - 1);
                                    cups.CupA = cupsa_e;
                                    cups.CupB = cupsb_e;
                                    continue;
                                }
                                for (int f = 0; f < types.Length; f++)
                                {
                                    int cupsa_f = cups.CupA;
                                    int cupsb_f = cups.CupB;
                                    result = pullWater(types[f], cups, steps);
                                    if (result)
                                    {
                                        checkQuickest(quickestCounts, tempResult, steps);
                                        steps.RemoveAt(steps.Count - 1);
                                        cups.CupA = cupsa_f;
                                        cups.CupB = cupsb_f;
                                        continue;
                                    }
                                    for (int g = 0; g < types.Length; g++)
                                    {
                                        int cupsa_g = cups.CupA;
                                        int cupsb_g = cups.CupB;
                                        result = pullWater(types[e], cups, steps);
                                        if (result)
                                        {
                                            checkQuickest(quickestCounts, tempResult, steps);
                                        }
                                        steps.RemoveAt(steps.Count - 1);//不管是否获得结果都需复位，即删去上一步操作，杯子状态复位
                                        cups.CupA = cupsa_g;
                                        cups.CupB = cupsb_g;
                                    }
                                    //已穷尽第7步所有可能操作，需修改第6步操作，所以需将杯子状态复位，删去第5步操作之后记录的所有操作步骤
                                    cups.CupA = cupsa_f;
                                    cups.CupB = cupsb_f;
                                    while (steps.Count > 4)
                                    {
                                        steps.RemoveAt(steps.Count - 1);
                                    }
                                }
                                cups.CupA = cupsa_e;
                                cups.CupB = cupsb_e;
                                while (steps.Count > 4)
                                {
                                    steps.RemoveAt(steps.Count - 1);
                                }
                            }
                            //tried all e
                            cups.CupA = cupsa_d;
                            cups.CupB = cupsb_d;
                            while (steps.Count > 3)
                            {
                                steps.RemoveAt(steps.Count - 1);
                            }
                        }
                        cups.CupA = cupsa_c;
                        cups.CupB = cupsb_c;
                        while (steps.Count > 2)
                        {
                            steps.RemoveAt(steps.Count - 1);
                        }
                    }
                    cups.CupA = cupsa_b;
                    cups.CupB = cupsb_b;
                    while (steps.Count > 1)
                    {
                        steps.RemoveAt(steps.Count - 1);
                    }
                }
                //第1步操作在循环开始时复位，这里不需做
            }
            //所有7步之内的可能操作都已穷尽
            if (tempResult[0] != null && tempResult[0].Count > 0)
            {//若找到结果
                outputSteps(tempResult);
            }
        }

#15

因同一用户不能连续回贴3次，用马甲回。

        private bool pullWater(bool isFromSmallToBig, Cups cups, List<string> steps)
        {//模拟倒水操作
            int tofill = 0;
            if (cups.CupB == 4)
            {//若操作前大杯已有4升水，直接返回
                return true;
            }
            
            if (isFromSmallToBig)
            {//小杯倒大杯
                if (cups.CupB == 5)
                {//若大杯满，先倒空
                    cups.CupB = 0;
                }
                tofill = 5 - cups.CupB;//可向大杯里倒的水量
                if (cups.CupA == 0)
                {//若小杯空，先装满后再倒
                    cups.CupA = 3;
                }    
                if (cups.CupA <= 5 - cups.CupB)
                {//若小杯水倒不满大杯
                    tofill = cups.CupA;
                }
                steps.Add("true:" + tofill.ToString());//记录操作步骤
                cups.CupA -= tofill;
                cups.CupB += tofill;
            }
            else
            {//大杯倒小杯
                if (cups.CupA == 3)
                {//若小杯满，先倒空
                    cups.CupA = 0;
                }
                tofill = 3 - cups.CupA;//可往小杯倒的水量
                if (cups.CupB == 0)
                {//若大杯空，先倒满
                    cups.CupB = 5;
                }
                if (cups.CupB <= 3 - cups.CupA)
                {
                    tofill = cups.CupB;
                }
                steps.Add("false:" + tofill.ToString());
                cups.CupA += tofill;
                cups.CupB -= tofill;
            }
            if (cups.CupB == 4)
            {//若大杯有4升水
                return true;
            }
            else
            {
                return false;
            }
        }

#16

引用楼主  的回复:

一组数的规则如下：1、1、2、3、5、8、13、21、34.....，求第30位数是多少？用递归方式实现

另外还有两个面试题，求解答。
1、A说B说谎，B说C说谎，C说A、B说谎，请问到底谁说谎？
2、有一个三升的水杯和一个五升的水杯，如何倒四升的水？

智商拙计 真心求帮助 万分感谢！

题目本身很简单。这主要是看你受的计算机编程（和逻辑）教育水平，如果没有相应的正规教育，那么可能就算是能说出来、也不会编程。我不知道现在的教软件的教师怎样，如果你找个早先真正搞软件教育的老师，这类题目可以很容易得到答案。

随便写一种demo，从代码你就会发现其实很简单。所以，主要是不是这个程序有多难（只要你对c#3.0以后的语法不陌生的话），而是很多人竟然从来没有这样想过这类编程问题。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int, long> fib = null;
            fib = n =>
            {
                if (n <= 2)
                    return 1;
                else
                    return fib(n - 1) + fib(n - 2);
            };
            Console.WriteLine("第一题：{0}", fib(30));
            (from a in 真话()
             from b in 真话()
             from c in 真话()
             where a != b && b != c && c != (a && b)
             select new { A = a, B = b, C = c })
                         .ToList()
                         .ForEach(query =>
                         {
                             Console.WriteLine("第二题（说真话）：A={0}  B={1}  C={2}", query.A, query.B, query.C);
                         });
            Action<int, int> 倒水 = null;
            倒水 = (a, b) =>
            {
                if (b == 4)
                    return;
                else if (b == 5)    //如果5升的杯子满了
                {
                    Console.Write("到空5升杯子。");
                    倒水(a, 0);
                }
                else if (a == 0)   //3升的杯子是空的
                {
                    Console.Write("倒满3升杯子。");
                    倒水(3, b);
                }
                else if (a + b <= 5)     //倒水不会溢出
                {
                    Console.Write("{0}升水倒入杯子成{1}升。", a, a + b);
                    倒水(0, a + b);
                }
                else
                {
                    Console.Write("{0}升水其中{1}升倒入5升杯子。", a, 5 - b);
                    倒水(a + b - 5, 5);
                }
            };
            倒水(0, 0);
            Console.ReadKey();
        }

        static IEnumerable<bool> 真话()
        {
            yield return true;
            yield return false;
        }
    }

}

我出上机考试的题，不会出这种跟我们的工作差别太大的问题。

#17

引用 7 楼  的回复:

既然prolog编不来，尝试用c#编，开始觉得不难，可是昨天搞了一下午，仍然有bug,今天又搞了一会，总算初步能工作了，代码又臭又长，只不过花了不少时间写的，敝帚自珍吧。如果有高手指导我改进或者给出更好的思路，不胜感激！

C# code

private void button1_Click(object sender, EventArgs e) //做了个win form程序
{
  ……

我写了个简单c#的。

使用prolog显然应该比c#代码更简单，看来你的prolog没有学好。

#18

当然对于自然语言，我们的理解可能不同。你可能把

where a != b && b != c && c != (a && b)

写成

where a != b && b != c && c != (a || b)

这也是可能的。这就是不同人、或者同一人在不同情景下可能产生的歧义。

#19

该回复于2012-04-23 08:44:21被版主删除

#20

呵呵，对于第三题，这类问题求解就是：一直用一个杯子盛水向另外一个杯子里倒就行了，总是能解决问题（除非其它倒法也无解）。所以这里是个简化解法。


一方面，这个程序写成了尾递归。可以直接改为迭代，例如：

Action<int, int> 倒水 = null;
倒水 = (a, b) =>
{
begin:
    if (b == 4)
        return;
    else if (b == 5)    //如果5升的杯子满了
    {
        Console.Write("到空5升杯子。");
        b = 0;
        goto begin;
    }
    else if (a == 0)   //3升的杯子是空的
    {
        Console.Write("倒满3升杯子。");
        a = 3;
        goto begin;
    }
    else if (a + b <= 5)     //倒水不会溢出
    {
        Console.Write("{0}升水倒入杯子成{1}升。", a, a + b);
        b = a + b;
        a = 0;
        goto begin;
    }
    else
    {
        Console.Write("{0}升水其中{1}升倒入5升杯子。", a, 5 - b);
        a = a + b - 5;
        b = 5;
        goto begin;
    }
};

另一方面，如果是一个通用的只能求解问题，那么我们应该使用问题树来描述状态。假设以自底向上搜索方法（树顶就是问题的底——初始状态），我们将可能的操作分为8种：
    1. 倒空5升的杯子；（条件是杯子中有水）
    2. 倒满5升的杯子；（条件是杯子中的水不足5升）
    3. 倒空3升的杯子；（条件是杯子中有水）
    4. 倒满3升的杯子；（条件是杯子中的水不足3升）
    5. 将5升杯子里的水全部倒到3升杯子里；  （条件是杯中有水，并且倒后不会溢出）
    6. 将5升杯子里的部分水倒到3升杯子里直到满；  （条件是杯中有水，并且全倒入会溢出）
    7. 将3升杯子里的水全部倒到5升杯子里；  （条件是杯中有水，并且倒后不会溢出）
    8. 将3升杯子里的部分水倒到5升杯子里直到满；  （条件是杯中有水，并且全倒入会溢出）
那么从每一个状态开始，只要条件满足我们就可以使用8个操作中的方法得到下一个状态分枝，从而构造子目标问题树。

然后，如果得到目标状态，那么就可以（在这个分枝上）停止递归构造子树了，而且可以把目标状态到树顶的路径作为解答。

同时如果发现了与其它状态重复的状态，那么这个分枝也应该停止递归构造子树了。重复的子目标可以直接消除。

这就是一般的问题求解思路。各种解法不过是在“自顶向下还是自底向上、状态归结还是自动匹配、并行还是顺序处理、使用树结构还是连接图结构”等问题上的分歧。而此问题的最基本数据结构和最基本的算法思路并没有多大的变化。

#21

当然如果用c#来写一个通用的智能程序，那么可能你需要一个描述某一个“活物”的抽象父类（例如这里可以用“杯子”这个具体class来实现），其中有一个Action集合（这个“杯子”里边有四种动作），描述每一个动作的条件表达式、结果表达式。然后你创造一个通用的“问题空间”对象，把所有的“活物”插入问题空间，然后由这个空间去搜索出含有解答的树或者连接就行了。

这个程序（抽象核心数据结构和解题流程部分）写起来很容易，有个几十行代码足以。

#22

该回复于2012-04-23 10:22:44被版主删除

#23

赫赫，看来抛砖还真引来了玉。

说谎那个问题，sp1234的方法给我很大启发，函数式编程的思想很好，我对函数式编程理解太浅，所以想不到。谢谢指教！。
但是程序有点小问题，输出结果是：
第二题（说真话）：A = True, B = False, C = True。刚好和正确答案反了。
不过改正也很容易，都取反即可，即：
Console.WriteLine("第二题（说真话）：A={0}  B={1}  C={2}", !query.A, !query.B, !query.C);

倒水那个问题，sp1234有几个问题没考虑到：
1.把b == 4作为递归结束条件，在有解的情况下是可以的，但如果无解，将堆栈溢出。好像难以确定这个递归的结束条件，所以我在程序里硬性规定如果步骤大于N，就认为无解，不再考虑，当然这个N设成比较“合理”的一个数。因为这个算法复杂性好像是2^n，也就是说是无效算法，所以把N设得小一些，比如20。
2.这个解法，只要找到一个结果就结束。我的程序还考虑到更多的可能。比如该题就有两种解法，1楼已经提到了。当然，如何区分两种解法是否不同有点tricky的地方，比如我上面说的，先从大杯往小杯倒2升水，小杯再往大杯倒2升水，愚蠢的计算机认为是一种新的倒法，实际这是两步无效操作。如果定义和排除这种无效操作我还没想好。
3.只从一个杯子往另一个杯子倒，固然可能简化了思路，但也可能忽略了可能的解法。

当然，我上面的程序虽然经过修改，但是显然是很粗糙的，如果sp1234的简洁，这点必须承认。不过我思考了一下，又想出两种简化的方法，如下：

#24

这个改进的方法利用了2进制表示，程序简洁许多，而且可以定义最多搜索几步，找出最快的2种方法

        public class Cups
        {
            public int CupA { get; set; }
            public int CupB { get; set; }
        }

            Cups cups = new Cups();
            bool result = false;
            SortedList<string, string> steps = new SortedList<string, string>();//存储操作步骤
            List<string> quickest = new List<string>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 16; i++)
            {//只计算最多15步，所以这里初始成16步，相当于“无限大”
                sb.Append("1");
            }
            sb.Append("0");
            quickest.Add(sb.ToString());
            sb.Remove(98, 1);
            sb.Append("1");
            quickest.Add(sb.ToString());
            sb.Length = 0;
            for (int i = 0; i < 32768; i++)
            {//32768 = 2^15,也就是说最多计算15步
                //转化成2进制，每1位代表一个操作步骤，0表示从小杯往大杯倒水
                //1表示从大杯往小杯倒水。这里i取0到2^15，穷尽15步内的所有可能操作
                string stepString = Convert.ToString(i, 2);
                //注意对于不足15位的数，前面必须补0，不然类似0010,0000的操作步骤就被忽略了
                for (int j = 0; j < 15 - stepString.Length; j++)
                {
                    sb.Append("0");
                }
                sb.Append(stepString);
                stepString = sb.ToString();
                sb.Length = 0;
                bool isContinue = false;
                foreach (string key in steps.Keys)
                {//检查是否与已有结果重复，但这其实是不完善的，原因上面已经解释了
                    if (stepString.StartsWith(key))
                    {
                        isContinue = true;
                        break;
                    }
                }
                if (isContinue)
                {
                    continue;
                }
                cups.CupA = 3;//复位到初始状态，小杯3升水，大杯5升
                cups.CupB = 5;
                StringBuilder tmpSteps = new StringBuilder();//复位临时的操作步骤
                for (int j = 0; j < stepString.Length; j++)
                {//
                    string step = "";
                    result = pullWater3(stepString[j], cups, out step);//倒水操作
                    tmpSteps.AppendLine(step);
                    if (result)
                    {//若得到一个解
                        //获得当前操作步骤的2进制字符串表示
                        string substeps = stepString.Substring(0, j);
                        if (checkQuickest3(quickest, substeps))
                        {//如果属于最快的方法之一，加入到最终的输出结果集
                            steps.Add(substeps, tmpSteps.ToString());
                        }
                        break;//没必要走完15步，继续找下一种方法
                    }
                }
            }
            if (steps.Count > 0)
            {//如有解，输出结果
                outputSteps3(steps, quickest);
            }
        }

        private void outputSteps3(SortedList<string, string> steps, List<string> quickest)
        {//输出结果
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 2; i++)
            {//找到最快的2种方法
                if (steps.ContainsKey(quickest[i]))
                {
                    sb.Append(steps[quickest[i]]);
                    sb.AppendLine("----------------------");
                }
            }
            txtResult.Text = sb.ToString();
        }

        private bool checkQuickest3(List<string> quickest, string candidateSteps)
        {//检查是否是最快的方法之一
            bool isQuickest = false;
            for (int i = 0; i < 2; i++)
            {//只找最快的前2种，排除重复
                if (candidateSteps.Length < quickest[i].Length
                    || (candidateSteps.Length == quickest[i].Length 
                        && candidateSteps != quickest[i])
                    )
                {
                    quickest.Insert(i, candidateSteps);
                    isQuickest = true;
                    break;
                }
            }
            return isQuickest;
        }

        private bool pullWater3(char type, Cups cups, out string step)
        {//倒水操作，类似sp1234，不过考虑了从小杯倒大杯和从大杯倒小杯两种情况
            step = ""; 
            StringBuilder sb = new StringBuilder();
            int tofill = 0;
            if (cups.CupB == 4)
            {
                return true;
            }

            if (type == '0')
            {//从小杯到大杯
                if (cups.CupB == 5)
                {//大杯满
                    sb.Append(" 倒空大杯;");
                    cups.CupB = 0;
                }
                tofill = 5 - cups.CupB;
                if (cups.CupA == 0)
                {//小杯空
                    sb.Append(" 加满小杯;");
                    cups.CupA = 3;
                }
                if (cups.CupA <= 5 - cups.CupB)
                {
                    tofill = cups.CupA;
                }
                sb.Append(" 从小杯倒 " + tofill.ToString() + " 升水倒大杯;");
                cups.CupA -= tofill;
                cups.CupB += tofill;
            }
            else
            {//大杯到小杯
                if (cups.CupA == 3)
                {
                    sb.Append(" 倒空小杯;");
                    cups.CupA = 0;
                }
                tofill = 3 - cups.CupA;
                if (cups.CupB == 0)
                {
                    sb.Append(" 加满大杯;");
                    cups.CupB = 5;
                }
                if (cups.CupB <= 3 - cups.CupA)
                {
                    tofill = cups.CupB;
                }
                sb.Append(" 从大杯倒 " + tofill.ToString() + " 升水到小杯;");
                cups.CupA += tofill;
                cups.CupB -= tofill;
            }
            step = sb.ToString();
            if (cups.CupB == 4)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

#25

上面这句sb.Remove(98, 1);粘贴错了，应是sb.Remove(15,1);

#26

该回复于2012-04-24 14:08:48被版主删除

#27

引用 23 楼  的回复:

但是程序有点小问题，输出结果是：
第二题（说真话）：A = True, B = False, C = True。刚好和正确答案反了。
不过改正也很容易，都取反即可，即：
Console.WriteLine("第二题（说真话）：A={0}……

在 #18 楼我做了说明。

#28

引用 23 楼  的回复:

倒水那个问题，sp1234有几个问题没考虑到：
1.把b == 4作为递归结束条件，在有解的情况下是可以的，但如果无解，将堆栈溢出。好像难以确定这个递归的结束条件，所以我在程序里硬性规定如果步骤大于N，就认为无解，不再考虑

实际上我在#20和#21楼也做了简单说明。当时写那个程序，就是假设我们都知道这类题目可以这样机械地简单求解为前提。而只要两个杯子的容积（一个3升、一个5升）互为素数，就一定可以求解。程序中把3、5这两个数都写死了，也就无需判断是否无解了。

我在#21楼说明了一个通用的问题求解基本的搜索树结构和算法（在两种情况下会自动停止搜索）。实际上已经在一个 通用解题方法上说明了这个判断。

#29

具体地说，不是“在程序里硬性规定如果步骤大于N，就认为无解”，而是应该在发现目标状态重复时就停止深度搜索而是去回溯其它动作。

同时我其实在#21楼要表达的才是我最想分享的算法。那里可以包括你能想到的其它几种“解法”，而且用搜索树可以遍历所有解法，不是只能知道一个解。

#30

另外的方法是用递归，实际也有两种不同的写法，这里先改写一下sp1234的写法：

StringBuilder sb = new StringBuilder();
            Action<int, int, bool, int> pullWater = null;
            pullWater = (a, b, isFromSmallToBig, count) =>
            {
                if (b == 4 || count > 20) //最多试20步
                    return;
                if (isFromSmallToBig)
                {
                    if (b == 5)    //如果5升的杯子满了
                    {
                        sb.AppendLine("empty big cup;");
                        pullWater(a, 0, true, count++);
                    }
                    else if (a == 0)   //3升的杯子是空的
                    {
                        sb.AppendLine("fill up small cup;");
                        pullWater(3, b, true, count++);
                    }
                    else if (a + b <= 5)     //倒水不会溢出
                    {
                        sb.AppendLine("pull " + a.ToString() + " l water to big cup and "
                            + "big cup now has " + (a + b).ToString() + " l water;");
                        pullWater(0, a + b, true, count++);
                    }
                    else
                    {
                        sb.AppendLine("small cup has " + a.ToString() +
                            " l water and pull " + (5 - b).ToString() + " l water to big cup.");//{0}升水其中{1}升倒入5升杯子。", a, 5 - b);
                        pullWater(a + b - 5, 5, true, count++);
                    }
                }
                else
                {
                    if (a == 3)    //如果3升的杯子满了
                    {
                        sb.AppendLine("empty small cup;");
                        pullWater(0, b, false, count++);
                    }
                    else if (b == 0)   //5升的杯子是空的
                    {
                        sb.AppendLine("fill up big cup;");
                        pullWater(a, 5, false, count++);
                    }
                    else if (a + b <= 3)     //倒水不会溢出
                    {
                        sb.AppendLine("pull " + b.ToString() + " l water to small cup and "
                            + "small cup now has " + (a + b).ToString() + " l water;");
                        pullWater(a + b, 0, false, count++);
                    }
                    else
                    {
                        sb.AppendLine("big cup has " + b.ToString() +
                            " l water and pull " + (3 - a).ToString() + " l water to small cup.");//{0}升水其中{1}升倒入5升杯子。", a, 5 - b);
                        pullWater(3, a + b - 3, false, count++);
                    }
                }
            };
            pullWater(0, 0, true, 0);
            sb.AppendLine("------------------");
            pullWater(0, 0, false, 0);

#31

引用 29 楼  的回复:

具体地说，不是“在程序里硬性规定如果步骤大于N，就认为无解”，而是应该在发现目标状态重复时就停止深度搜索而是去回溯其它动作。

同时我其实在#21楼要表达的才是我最想分享的算法。那里可以包括你能想到的其它几种“解法”，而且用搜索树可以遍历所有解法，不是只能知道一个解。

目标状态重复就停止深度搜索以及用搜索树遍历，这些我也想到了。问题是对具体实现有点疑问，请指教：
1.这样意味着必须保存所有搜索状态并比较，这样效率（性能）会不会有问题？
2.搜索树的层次如何定？这个层次等于是这里所说的操作步数吧。

所以基于这个考虑，可能还是硬性规定最多搜索几步简单些。

#32

顺便骂一下csdn，ie 9.0 下回复区的工具栏（如“插入源代码”，“插入超链接”等图标）无法显示，害得我只能用opera来回复。shit!

#33

引用 32 楼  的回复:

顺便骂一下csdn，ie 9.0 下回复区的工具栏（如“插入源代码”，“插入超链接”等图标）无法显示，害得我只能用opera来回复。shit!

呵呵，这个问题我曾反馈过。不过可以点击ie9地址栏后面的兼容性视图可以解决工具栏问题。

#34

看过好多Sp1234所回的帖子，对sp1234表示由衷的钦佩。

#35

第一个数列的东东就不用多说了，其他两个用程序来实现还真有点难度

#36

第一题是斐波那契数列
int Fibonacci(int n)
{
 if( n == 1 || n == 2) // 递归结束的条件，求前两项
  return 1;
 else
  return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。
}
第二题最笨的方法是三个for循环遍历
第三题是
方法一  
1.用3升的容器接满水，倒入5升容器中。  
2.再用3升的容器接满，倒入5升容器中。此时3升容器中还剩下1升水。  
3.将5升容器中的水倒掉，将3升容器中剩下的1升水倒入5升容器。  
4.再将3升容器接满水倒入5升容器中，此时5升容器中就是4升水。  

方法二  
1.用5升的容器接满水，倒入3升容器中。此时5升容器中有2升水。  
2.将3升容器中的水倒掉，在将5升容器中剩下的水倒入3升容器中。此时3升容器中有2升水。  
3.将5升容器接满水，把水再倒入3升容器中至满。此时5升容器中剩4升水。

#37

楼上的都是高手  都是大神 膜拜ing...