首页 > 代码库 > SGU[123] The sum

SGU[123] The sum

Description

描述

The Fibonacci sequence of numbers is known: F1 = 1; F2 = 1; Fn+1 = Fn + Fn-1, for n>1. You have to find S - the sum of the first K Fibonacci numbers.

斐波那契数列广为大家所知:F= 1; F= 1; Fn+1 = F+ Fn-1(其中n > 1)。你需要求斐波那契数列前K个数的和S。

 

Input

输入

First line contains natural number K (0<K<41).

输入文件包含自然数K(0<K<41)。


Output

输出

First line should contain number S.

第一行包含整数S。


Sample Input

样例输入

5


Sample Output

样例输出

12

 

Analysis

分析

考虑到数据范围,这道题目只要模拟一下就行了。但是我还是比较喜欢使用数学方法来求解。

令Sn表示斐波那契数列的前N项和,那么我们很容易求得S= Fn+2 - 1。

 

Solution

解决方案

#include <iostream>using namespace std;const int MAX = 64;int f[MAX];int main(){	int N;	cin >> N;	f[1] = f[2] = 1;	for(int i = 3; i <= N + 2; i++)	{ f[i] = f[i - 1] + f[i - 2]; }	cout << f[N + 2] - 1 << endl;	return 0;}

 

这道题目应该是非常简单的。当然,如果你不知道斐波那契数列可以在O(n)时间内求得,那么这道题目对于你来说还是有一定难度的。

SGU[123] The sum