Lintcode366 Fibonacci solution 题解
发布在Lintcode题解2018年3月4日view:537
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Find the Nth number in Fibonacci sequence.

A Fibonacci sequence is defined as follow:

The first two numbers are 0 and 1.

The ith number is the sum of i-1th number and i-2th number.

The first ten numbers in Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

Notice:The Nth fibonacci number won’t exceed the max value of signed 32-bit integer in the test cases.

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指:

前2个数是 0 和 1 。

第i个数是第i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

【注】在测试用例中,斐波那契数不会超过带符号的32位整数的最大值。

【题目链接】

www.lintcode.com/en/problem/fibonacci/

【题目解析】

此题使用递归会导致TLE,因为有不少地方进行了重复计算,改为循环即可解决(迭代法)…

另外为了避免输入非法值(比如负数),输入改为了unsigned int

| 1, (n=0)

fib(n)=     | 1, (n=1)

| fib(n)+fib(n-1) (n>1, n∈N)

【参考答案】

www.jiuzhang.com/solutions/fibonacci/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏