Мне сложно понять, почему
#include <iostream>
using namespace std;
int fib(int x) {
if (x == 1) {
return 1;
} else {
return fib(x-1)+fib(x-2);
}
}
int main() {
cout << fib(5) << endl;
}
приводит к ошибке сегментации. Как только x опустится до 1, он не должен в конечном итоге вернуться?
Когда x==2 вы вызываете fib(1) и fib(0):
return fib(2-1)+fib(2-2);
Рассмотрим, что произойдет, когда fib(0) будет оценено...
Причина в том, что последовательность Фибоначчи начинается с двух известных объектов: 0 и 1. Ваш код проверяет только один из них (один).
Измените свой код на
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2);
}
Чтобы включить как 0, так и 1.
Почему бы не использовать итерационный алгоритм?
int fib(int n)
{
int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
По определению первые два числа в последовательности Фибоначчи равны 1 и 1, или 0 и 1. Следовательно, вы должны справиться с этим.
#include <iostream>
using namespace std;
int Fibonacci(int);
int main(void) {
int number;
cout << "Please enter a positive integer: ";
cin >> number;
if (number < 0)
cout << "That is not a positive integer.\n";
else
cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}
int Fibonacci(int x)
{
if (x < 2){
return x;
}
return (Fibonacci (x - 1) + Fibonacci (x - 2));
}
Я думаю, что это решение короткое и выглядит неплохо:
long long fib(int n){
return n<=2?1:fib(n-1)+fib(n-2);
}
Изменить: как упомянуто jweyrich, истинно рекурсивная функция должна быть:
long long fib(int n){
return n<2?n:fib(n-1)+fib(n-2);
}
(поскольку fib (0) = 0. но основываясь на вышерекурсивной формуле, fib (0) будет 1)
Чтобы понять алгоритм рекурсии, вы должны обратить внимание на свою бумагу, и самое главное: "Думайте нормально, как часто".
int fib(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
в последовательности фибоначчи первые 2 числа всегда продолжаются до 1, и каждый раз, когда значение становится 1 или 2, оно должно возвращать 1
int fib(int x)
{
if (x == 0)
return 0;
else if (x == 1 || x == 2)
return 1;
else
return (fib(x - 1) + fib(x - 2));
}
Это мое решение проблемы фибоначчи с рекурсией.
#include <iostream>
using namespace std;
int fibonacci(int n){
if(n<=0)
return 0;
else if(n==1 || n==2)
return 1;
else
return (fibonacci(n-1)+fibonacci(n-2));
}
int main() {
cout << fibonacci(8);
return 0;
}
int fib(int x)
{
if (x < 2)
return x;
else
return (fib(x - 1) + fib(x - 2));
}
if(n==1 || n==0){
return n;
}else{
return fib(n-1) + fib(n-2);
}
Однако использование рекурсии для получения числа фибоначчи - это плохая практика, потому что функция вызывается примерно в 8,5 раз по сравнению с полученным числом. Например. для получения числа фибоначчи 30 (1346269) - функция называется 7049122 раз!
Мое решение:
#include <iostream>
int fib(int number);
void call_fib(void);
int main()
{
call_fib();
return 0;
}
void call_fib(void)
{
int input;
std::cout<<"enter a number\t";
std::cin>> input;
if (input <0)
{
input=0;
std::cout<<"that is not a valid input\n" ;
call_fib();
}
else
{
std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
}
}
int fib(int x)
{
if (x==0){return 0;}
else if (x==2 || x==1)
{
return 1;
}
else if (x>0)
{
return fib(x-1)+fib(x-2);
}
else
return -1;
}
он возвращает fib (0) = 0 и ошибку, если отрицательный
Я думаю, что это лучшее решение для фибоначчи, использующее рекурсию.
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
ull FIBO[100005];
using namespace std;
ull fibo(ull n)
{
if(n==1||n==0)
return n;
if(FIBO[n]!=0)
return FIBO[n];
FIBO[n] = (fibo(n-1)+fibo(n-2));
return FIBO[n];
}
int main()
{
for(long long i =34;i<=60;i++)
cout<<fibo(i)<<" " ;
return 0;
}