C++中的斐波那契数列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19718677/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fibonacci series in C++
提问by user2943407
#include <iostream>
using namespace std;
int main()
{
int num1 = 0;
int num2 = 1;
int num_temp;
int num_next = 1;
int n;
cin >> n;
for (int i = 0; i < n; i++){
cout << num_next << " ";
num_next = num1 + num2;
num1 = num2;
num_temp = num2;
num2 = num_next - num1;
num1 = num_temp;
}
return 0;
}
I have to output the first "n" fibonacci numbers however I think there is some problem in logic.. I can't find out what am I doing wrong. The first 3 or 4 elements are correct but then a problem occurs...
我必须输出第一个“n”斐波那契数字，但是我认为逻辑上存在一些问题..我不知道我做错了什么。前 3 或 4 个元素是正确的，但随后出现问题...
EXPECTED:
For n=9
预期：
对于n=9
0, 1, 1, 2, 3, 5, 8, 13, 21
0, 1, 1, 2, 3, 5, 8, 13, 21
Actual:
实际的：
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
回答by hasan
#include <iostream>
using namespace std;
int main()
{
int num1 = 0;
int num2 = 1;
int num_temp;
int num_next = 1;
int n;
cin >> n;
if (n>=1)
cout << 0 << " ";
if (n>=2)
cout << 1 << " ";
for (int i = 0; i < n-2; i++){
num_next = num1 + num2;
cout << num_next << " ";
num1 = num2;
num2 = num_next;
}
cout << endl;
return 0;
}
回答by Brian
Try this instead. It's a bit of a different take but will get you there just the same.
试试这个。这有点不同，但会让你到达那里。
#include <iostream>
using namespace std;
int main()
{
int input(0), Alpha(0), Beta(1), Total(1);
cout << "Please input a top number: ";
cin >> input;
for(int i = 0; i <= input; i++)
{
cout << Total << endl;
Total = Alpha + Beta;
Alpha = Beta;
Beta = Total;
}
}
回答by Zac Howland
The Fibonacci Sequence is {0, 1, 1, 2, 3, ... N - 1, N, 2N - 1}.
斐波那契数列是 {0, 1, 1, 2, 3, ... N - 1, N, 2N - 1}。
In order to implement it, you need to have a N - 2variable, and an N - 1variable so that you can calculate N = (N - 2) + (N - 1):
为了实现它，您需要有一个N - 2变量和一个N - 1变量，以便您可以计算N = (N - 2) + (N - 1)：
unsigned int count = 0;
std::cin >> count;
// assume count >= 2
unsigned int prev2 = 0;
unsigned int prev1 = 1;
std::cout << prev2 << " " << prev1 << " ";
for (unsigned int i = 2; i < count; ++i)
{
unsigned int current = prev2 + prev1;
prev2 = prev1;
std::cout << current << " ";
prev1 = current;
}
std::cout << std::endl;
回答by Tony
This is my version.
这是我的版本。
It's more or less same as previous samples, but I wanted to show the use of ring buffer.
它或多或少与之前的示例相同，但我想展示环形缓冲区的使用。
// Study for algorithm that counts n:th fibonacci number
// Fibonacci[1] == 1 and Fibonacci[2] == 1 (and Fibonacci[0] == 0)
// Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2]
#include <cstdio>
#include <iostream>
#include <cstdlib>
int main(int argc, const char* argv[])
{
// not counting trivial Fibonacci[0]
if(argc != 2 || atoi(argv[1]) < 1){
std::cout << "You must provide one argument. Integer > 0" << std::endl;
return EXIT_SUCCESS;
}
// ring buffer to store previous two fibonacci numbers, index it with [i%2]
// seeded with Fibonacci[1] and Fibonacci[2]
// if you want to count really big fibonacci numbers, you have to make your own type for
// buffer variable
// this type overflows after [93] with my macbook
unsigned long long int buffer[2]={ 1, 1 };
// n:th Fibonacci
unsigned int fn = atoi(argv[1]);
// count loop is used if seeked fibonacci number is gt 2
if(fn > 2){
for(unsigned int i = 2; i < fn; ++i){
buffer[i%2] = buffer[(i-1)%2] + buffer[(i-2)%2];
}
}
// Result will be send to cout
std::cout << "Fibonacci[" << fn << "] is " << buffer[(fn-1)%2] << std::endl;
return EXIT_SUCCESS;
}
回答by user2773143
#include <iostream>
using std::cout; using std::cin;
int main()
{
unsigned int a=0u, b=1u, n;//assuming n is a positive number.
//otherwise make it int instead of unsigned
//and check if it's negative
cin >> n;
if(n==0)
{return 0;}
if(n==1)
{cout << a; return 0;}
cout << a << " " << b << " ";
for(unsigned int i=2u ; i<n; i++)
{
b = a + b;
a = b - a;
cout << b << " ";
}
return 0;
}
It puts the next value in 'b' by adding the last two values together. 'a' then gets the previous b value. assume a = 3 and b = 5. Then the new b will become 8, and 'a' will become 5. This is because it always sums the last two numbers to get the result of the next number. The next operation will sum 5 (current a) and 8(current b) and so on...
它通过将最后两个值相加来将下一个值放入 'b' 中。'a' 然后获取之前的 b 值。假设 a = 3 且 b = 5。那么新的 b 将变为 8，而 'a' 将变为 5。这是因为它总是将最后两个数字相加以获得下一个数字的结果。下一个操作将求和 5（当前 a）和 8（当前 b），依此类推...
回答by jasmine sharma
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int arr[50],n,i;
cout<<"Enter the no. of elements to be printed in fibonacci series : ";
cin>>n;
arr[0]=0;arr[1]=1;
for(i=2;i<n;i++)
{
arr[i]=arr[i-1]+arr[i-2];
}
cout<<"\nThe fibonacii series is : "<<endl;
for(i=0;i<n;i++)
{
cout<<arr[i]<<"\t";
}
getch();
}
回答by jasmine sharma
Stack overflow is, of course, a limitation of the recursive version. If that is not a problem, you may also wish to consider a templated version of recursive Fibonacci.
当然，堆栈溢出是递归版本的一个限制。如果这不是问题，您可能还希望考虑递归斐波那契的模板版本。
#include <iostream>
template <int N> int Fib(){ return Fib<N-1>() + Fib<N-2>(); }
template <> int Fib<1>() { return 1; }
template <> int Fib<0>() { return 1; }
using namespace std;
int main()
{
// For the 10th Fibbonacci number...
cout << Fib<10>() << endl;
return 0;
}
回答by wally
Concise version:
精简版：
int n, a{0}, b{1};
std::cin >> n;
while (n-- > 0) {
std::cout << a << " ";
std::tie(a, b) = std::make_tuple(b, a + b);
}
回答by ShimonD
You can write a code generating a Fibonacci series avoiding the if-else statement that prints zero and one, avoiding printing them outside the loop and avoiding the 'temp' integer. You can do it by initializing the 'first' and 'second' variables with -1 and 1, so the sum between them will give you 0, which is the first organ of the series, and the loop will do the rest of the job.
您可以编写生成斐波那契数列的代码，避免打印零和一的 if-else 语句，避免在循环外打印它们并避免使用 'temp' 整数。您可以通过使用 -1 和 1 初始化 'first' 和 'second' 变量来实现，因此它们之间的总和将为您提供 0，这是该系列的第一个器官，循环将完成剩下的工作.
#include <iostream>
using namespace std;
int main()
{
int num, a = -1, b = 1;
cout << "enter a number:" << endl;
cin >> num;
for (int i = 0 ; i <= num ; i++ )
{
b += a;
cout << b << " ";
a = b - a;
}
cout << endl;
return 0;
}
回答by Zohaib
Well I have been looking for some recursive solution to do the same task, Mostly what people do is, they write a recursive function for finding nth Fibonacci number, and then in the main program, they run a loop n times, and call this recursive function with values 1 to n to get all the n Fibonacci numbers and print them, which is a big overhead.
好吧，我一直在寻找一些递归解决方案来完成相同的任务，大多数人所做的是，他们编写一个递归函数来查找第 n 个斐波那契数，然后在主程序中，他们运行 n 次循环，并将其称为递归使用值为 1 到 n 的函数来获取所有 n Fibonacci 数并打印它们，这是一个很大的开销。
Here is a solution which does the same task but it calls recursive function only once for getting all up to n Fibonacci numbers, and stores them in an array, and then prints. Which is ((n-1)*(recursive call's overhead)) times faster than the one I mentioned earlier. Thumbs up if you find it helping :)
这是一个执行相同任务的解决方案，但它只调用一次递归函数来获取最多 n 个斐波那契数，并将它们存储在一个数组中，然后打印。这比我之前提到的要快 ((n-1)*(递归调用的开销)) 倍。如果你觉得它有帮助，请竖起大拇指:)
#include<iostream>
using namespace std;
int *arr;
int iter = 0;
int len;
int returnValue;
void exist(int num, int arr[] ) /* this function checks if the Fibonacci number that recursive function have calcuated is already in the array or not, mean if it is already calculated by some other recursive call*/
{
bool checkExistance = false; /* if this is true, means this Fibonacci number is already calculated and saved in array, so do not save it again*/
returnValue = num;
for (int i = 0; i< len; i++)
{
if(arr[i]==num)
{
checkExistance = true;
break;
}
}
if(!checkExistance)
{
arr[iter]=num;
iter++;
}
}
int fibonacci(int n)
{
if (n==1)
{
exist(1,arr);
return 1;
}
else if (n==2)
{
exist(1,arr);
return 1;
}
else
{
exist((fibonacci(n-1)+fibonacci(n-2)),arr);
return returnValue;
}
}
int main()
{
int n;
cout<<"Enter the number of Fibonacci you want to print: ";
cin>>n;
len = n;
arr = new int[n];
fibonacci(n);
arr[n-1] = 1;
cout<<"1:\t"<<arr[n-1]<<endl;
for (int i = 0; i< len-1; i++)
{
cout<<i+2<<":\t"<<arr[i]<<endl;
}
return 0;
}
