黑马程序员技术交流社区

标题: 关于递归和循环的两道题 [打印本页]

---

作者: 郑绪梅    时间: 2013-5-7 16:59
标题: 关于递归和循环的两道题


1，不使用递归计算 1,1,2,3,5,8,13...n 输入n 输出第n个数的值
2，不使用循环计算1-2+3+4+5+...+n 输入结果

---

作者: 曾大鹏    时间: 2013-5-7 17:02


第一题 可以定义一个数组 f
初始化使得f[1]=1; f[2]=1;
我们可以得出递推公式
f[n]=f[n-1]  + f [n-2]    ,n>=3

然后直接循环遍历到n就行了


第二题
2*n+1 ,n>=0
输入一个N 直接输出2*N+1

---

作者: 郑绪梅    时间: 2013-5-7 17:28

曾大鹏 发表于 2013-5-7 17:02
第一题 可以定义一个数组 f
初始化使得f[1]=1; f[2]=1;
我们可以得出递推公式

第一题的要求是不使用递归。。这样还是用到递归了。

---

作者: 一直在路上    时间: 2013-5-7 17:30
import java.util.ArrayList;
import java.util.List;


public class Test1 {
       
        public int count(int num){
                List<Integer> list = new ArrayList<Integer>();
                list.add(1);
                list.add(1);
                if(num>=3){
                        list.add(list.get(num-2)+list.get(num-3));
                        return list.get(num-1);
                }else{
                        return 1;
                }
        }
       
        public int  count2(int num){
                return (2*num)+1;
        }
        public static void main(String[] args) {
                Test1 test = new Test1();
                System.out.println(test.count(1));;
                System.out.println(test.count(2));;
                System.out.println(test.count(3));;
                System.out.println(test.count2(1));;
                System.out.println(test.count2(2));;
                System.out.println(test.count2(5));;
        }
}

---

作者: 曾大鹏    时间: 2013-5-7 17:41

郑绪梅 发表于 2013-5-7 17:28
第一题的要求是不使用递归。。这样还是用到递归了。

这个又不算递归  我这只是循环而已啊 。。

---

作者: 王宝生    时间: 2013-5-8 12:57
第一个是斐波那契，这个之所以使用数组是因为速度要优于使用递归，代码如下：
        public static int sum(int n)
        {
            int[]list=new int[n];
            list[0] = 1;
            for (int i = 1; i <n; i++)
                list[i] = i;
            int result = 1;
            for(int i=0;i<n;i++)
                result+=list[i];
            return result;
        }
也可以把两个循环合并到一起。

第二个代码如下：

        public static int sum(int n)
        {
            if (n == 1)
                return 1;
            return n + sum(n - 1);
        }

直接复制，能够运行！！！！

---

作者: zms2100    时间: 2013-5-8 16:02
LZ这第一道题挺坑人的，O(∩_∩)O~............LS让我学习了，原来这东西叫斐波那契数列啊，不过LS们的第一题代码结果都是错的，沙发童鞋(太邪恶了，直接贴斐波那契数列的公式就上来，不过思路是对，O(∩_∩)O~，不过LS们的思路都是差不多的) 【第一题代码见最下面，先贴第二题】
可能LS，那符号打错了，第一个数学符号打的是减号来的（应该是加号吧），另外沙发童鞋的第二题也是错的，这第二题是递增数列来的，公式应该是num = n(n+1)/2，这个这么简单的公式应该很好实现，篇幅有限，不贴代码了。(假如n=100,那么按沙发的公式，总数num 应该是等于201，但是答案应该是5050才对啊)。
————————————第一题代码——————————————————————————————
package hehe;
import java.util.ArrayList;
class MathDemo
{
        public static void main(String[] args)
        {
                sum(8);
        }
        public static void sum(int n)
        {
                int[] i = new int[n];
                i[0] = 1;
                i[1] = 1;
                for(int x =2;x<n;x++)
                {
                        i[x] = i[x-1] + i[x-2];
                }
                for(int x : i)
                {
                        System.out.println(x);
                }
        }
}

---

作者: zms2100    时间: 2013-5-8 16:07

zms2100 发表于 2013-5-8 16:02
LZ这第一道题挺坑人的，O(∩_∩)O~............LS让我学习了，原来这东西叫斐波那契数列啊，不过LS们的第一 ...

这个跟递归其实是差不多的，毕竟都是这样运算，不过递归的定义是要调用本方法嘛.........
注意: 因为是定义为int型，所以不建议输入的数值超过46，因为int型是8位字节，容易出现错乱成负数。

---

作者: 王宝生    时间: 2013-5-8 19:41
哈哈， 多谢楼上提醒，多谢多谢！！！我的那个int result=1 改为int result=0就好了。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2