MyException - 我的异常网
当前位置:我的异常网» ASP.NET »  简单的递归算法

简单的递归算法

www.MyException.Cn  网友分享于:2013-04-25  浏览:15次
求助 简单的递归算法
一组数的规则如下:1、1、2、3、5、8、13、21、34.....,求第30位数是多少?用递归方式实现

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

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

------解决方案--------------------
第一题是斐波那契数列
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升水。
------解决方案--------------------
一组数的规则如下:1、1、2、3、5、8、13、21、34.....,求第30位数是多少?用递归方式实现

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

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

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

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

------解决方案--------------------
菲波拉切数列,稍微知识面广一点的中学生都应该知道。

这个数列有一个有趣的性质,就是前一项/后一项逼近0.618黄金分割。
------解决方案--------------------
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编个程序,请高人教我,谢谢!

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

C# code

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;
        }

文章评论

亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Java程序员必看电影
Java程序员必看电影
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
中美印日四国程序员比较
中美印日四国程序员比较
程序员都该阅读的书
程序员都该阅读的书
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
代码女神横空出世
代码女神横空出世
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
鲜为人知的编程真相
鲜为人知的编程真相
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
一个程序员的时间管理
一个程序员的时间管理
旅行,写作,编程
旅行,写作,编程
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
每天工作4小时的程序员
每天工作4小时的程序员
程序员的鄙视链
程序员的鄙视链
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员应该关注的一些事儿
程序员应该关注的一些事儿
我的丈夫是个程序员
我的丈夫是个程序员
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
老程序员的下场
老程序员的下场
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
 程序员的样子
程序员的样子
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
如何成为一名黑客
如何成为一名黑客
为什么程序员都是夜猫子
为什么程序员都是夜猫子
我是如何打败拖延症的
我是如何打败拖延症的
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员和编码员之间的区别
程序员和编码员之间的区别
编程语言是女人
编程语言是女人
漫画:程序员的工作
漫画:程序员的工作
10个调试和排错的小建议
10个调试和排错的小建议
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
那些争议最大的编程观点
那些争议最大的编程观点
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有