前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >斐波拉契数列

斐波拉契数列

作者头像
悠扬前奏
发布2019-05-28 20:41:20
4260
发布2019-05-28 20:41:20
举报
文章被收录于专栏:悠扬前奏的博客

Python

用Python写斐波拉契数列。斐波拉契(Fibonacci)数列,除第一个和第二个数以外,后面的数字由前面两个数相加得到。

1. 简单输出

代码语言:javascript
复制
def fab(n):
    i, a, b = 0, 0, 1
    while i < n:
        print(b)
        a, b = b, a + b
        i += 1

2. 显然,上面的程序只能打印,复用性很差,返回一个List会好一点:

代码语言:javascript
复制
def fab(n):
    i, a, b = 0, 0, 1
    l = []
    while i < n:
        l.append(b)
        a, b = b, a + b
        i += 1
    return l

然后打印:

代码语言:javascript
复制
for n in fab(5):
    print(n)

3. 2中生成List的方法,空间复杂度为O(n),考虑用迭代器实现(iterable),空间复杂度会是O(1)。

通过__iter__()方法可以将类变成可迭代的类,而迭代器用__next()__实现

代码语言:javascript
复制
class Fab(object):
    def __init__(self, n):
        self.n = n
        self.i, self.a, self.b = 0, 0, 1

    def __iter__(self):
        return self

    def __next__(self):
        if self.i < self.n:
            r = self.b
            self.a, self.b = self.b, self.a + self.b
            self.i += 1
            return r
        raise StopIteration()

for循环中会自动调用next方法,返回下一个数。

4. 用yield关键字可以简化3中的代码

yield关键字可以把一个函数变成一个生成器(generator),对函数执行到yield时,会返回一个迭代值,下次之迭代时,代码从yield下一行继续执行,函数的内部变量和上次中断前一样。 由于函数被生成了generator,该对象也具有next()方法

代码语言:javascript
复制
def fab(n):
    i, a, b = 0, 0, 1
    while i < n:
        yield b
        a, b = b, a + b
        i += 1

Java

1. 普通

最基础的。

代码语言:javascript
复制
    public static void showFab(int n) {
        int a = 0, b = 1;
        for (int i = 1; i <= n; i++) {
            System.out.println(b);
            b = a + b;
            a = b - a;
        }
    }

2.递归

用上递归

代码语言:javascript
复制
    public static int showFab(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return showFab(n-1)+showFab(n-2);
        }
    }

3. 迭代器实现

考虑到上面两种方法要输出很多位的话都很占内存,用迭代器写一个不怎么占内存的。

代码语言:javascript
复制
public class FibonacciTest implements Iterator<BigDecimal> {
    private BigDecimal a = BigDecimal.ZERO;
    private BigDecimal b = BigDecimal.ONE;
    private int n, i = 0;

    public FibonacciTest(int n){
        this.n = n;
    }

    @Override
    public boolean hasNext() {
        return i < n;
    }

    @Override
    public BigDecimal next() {
        BigDecimal temp = a.add(b);
        b = a.add(b);
        a = b.subtract(a);
        this.i++;
        return temp;
    }

    public static void main(String[] args) {
        FibonacciTest f = new FibonacciTest(1000);
        while(f.hasNext()){
            System.out.println(f.next());
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.07.03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Python
    • 1. 简单输出
      • 2. 显然,上面的程序只能打印,复用性很差,返回一个List会好一点:
        • 3. 2中生成List的方法,空间复杂度为O(n),考虑用迭代器实现(iterable),空间复杂度会是O(1)。
          • 4. 用yield关键字可以简化3中的代码
          • Java
            • 1. 普通
              • 2.递归
                • 3. 迭代器实现
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档