[Fibonacci series]

---

1. Basic introduction

The Fibonacci sequence refers to a sequence that looks like this 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368
Tips ： This sequence starts at number one 3 A start , Each of these terms is equal to the sum of the first two terms .

---

2. Recursive implementation

#include<stdio.h>
int Fib(int n)
{
    
    if (n <= 2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}
int main()
{
    
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    return 0;
}

Running results

Time complexity ：O(2^n)

Spatial complexity :O(n)

Tips ： Space can be reused , Not cumulative ; Time is gone forever , Cumulative

---

3. Non recursive implementation

Iterative implementation

Tips ： Time complexity ：O(n) ; Spatial complexity O(1)

#include<stdio.h>

int Fib(int n)
{
    
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
    
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
    
	int n = 0;
	scanf("%d", &n);
	int ret = Fib(n);
	printf("%d\n", ret);
	return 0;
}

Running results

---

Array implementation

Tips ： Time complexity ：O(n) ; Spatial complexity O(n)

#include<stdio.h>
#include<stdlib.h>
long long Fibonacci(unsigned int n)
{
    
	if (n == 0)
		return 0;
	long long ret=0;
	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	if (fibArray == NULL)
	{
    
		printf(" Space development failed ");
		
	}
	else
	{
    
		fibArray[1] = 1;
		fibArray[2] = 1;
		for (long long i = 3; i <= n; i++)
		{
    
			fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
		}
		ret = fibArray[n];
		free(fibArray);
		fibArray = NULL;
		
	}
	return ret;
}
int main()
{
    
	unsigned int n = 0;
	scanf("%d", &n);
	long long ret = Fibonacci(n);
	printf("%lld\n", ret);
	return 0;
}

---

The above is the whole content of this article , If there are mistakes in the article or something you don't understand , Communicate more with meow bloggers . Learn from each other and make progress . If this article helps you , Can give meow bloggers a concern , Your support is my biggest motivation .