编辑

【递归】001 N-th Tribonacci Number

2019-07-05 2019-11-16 58 2 ---【递归】 Hoji Pan

一、题目

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.


二、解法

规律:Tn = Tn-1 + Tn-2 + Tn-3

(1) 递归解法(超时)

public int tribonacci(int n) {
  if(n <= 0)  return 0;
    
  if(n == 1 || n == 2)  return 1;
    
  return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);
}

(2) 非递归

序列是前3项和是第4项的值,非递归的话,就要人为地构造

public int tribonacci(int n) {
    if(n <= 0)  return 0;
    if(n == 1 || n == 2)  return 1;
    int t0 = 0, t1 = 1, t2 = 1;
    int sum = 0;
    for(int i = 4; i < n+2; i++) {
      sum = t0+t1+t2;
      t0 = t1;
      t1 = t2;
      t2 = sum;
    }
    return t2;
}

解释:(1)为什么 i < n+2 ?(2)为什么 return t2

(1)因为一次循环,变化的是前3项,也就是当序列为 0, 1, 1, 2 时,一次循环后,序列变为 1,1,2,2,可以发现第四项没有变化,故返回第四项,必须进行2次循环。

(2)t2 是当前循环的 t0+t1+t2 的和,故它代表最后要求的项。


Hoji的CSDN(在这里随意任性地创作,一首诗、一幅画、一篇文章.... 在这里你可以get到但不仅限算法、Spring, SpringBoot等后端技术、MySql,Oracle数据库探索....,其中更不乏各种框架教程、学习方法..)
博客地址:https://blog.csdn.net/qq_43539599

倘若小文于你有益,欢迎
  • 如果您的提问博主没能及时回复,通过分享文章获得援助,何尝不是一种查缺补漏的好做法
  • 版权声明:本文为博主原创文章,遵循CC 4.0 BY版权协议
  • 文章转载:请在文末添加原文章地址,这也是尊重他人劳动成果的一点体现,谢谢您的配合!
  • 评论信息 (注:评论收到回复后,会以邮箱的方式提醒您;您的邮箱不会显示到页面中)

    验证码信息 看不清?点击图片进行切换!
    精彩随处可见 更多精彩内容
    作者: 浏览 61 评论 1 赞 1 2020-01-15
    作者: 浏览 62 评论 1 赞 1 2019-11-29
    作者: 浏览 83 评论 1 赞 1 2019-11-29
    作者: 浏览 54 评论 1 赞 1 2019-11-29
    作者: 浏览 52 评论 1 赞 1 2019-11-29
    目录