[C language] Fibonacci sequence and frog jumping steps (the most detailed elementary frog jumping steps)

Catalog

• The solution of recursive Fibonacci number
• Iterative solution to Fibonacci number
• A detailed explanation of the frog jumping on the steps

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... This sequence starts at number one 3 A start , Each of these terms is equal to the sum of the first two terms . This series is also called golden section series .

Raise questions ： How to use C Language solution No n A Fibonacci number ？

programme 1： recursive

Ideas ： When n <= 2 when , Direct output 1;

            When n > 2 when , Use the formula f(n) = f(n-1) + f(n-2) Realize recursive operation .

#define _CRT_SECURE_NO_WARNINGS 1  

#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", ret);

	return 0;
}

shortcoming ： A great deal of repetition has been done ！ When n When a large , The operation time is greatly prolonged , The efficiency is greatly reduced ！

programme 2： iteration

Ideas ： From to later , Shilling a = 1,b = 1,c = 1.

          When n <= 2 when , Direct output c;

          When n > 2 when ,c = a + b, So we get the third number , Then make a = b, b = c, Count again c = a + b, So we get the fourth number ...

int fib(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);
	
	printf("%d", fib(n));

	return 0;
}

advantage ： Avoid a lot of repeated calculations , Greatly improve the operation efficiency ！

The problem of frog jumping on the steps

The rules ： Frogs can jump one or two steps at a time

problem ： Frog jumps n How many options are there for each step ？

analysis 1：1 A stair - There is a plan ;

analysis 2：2 A stair - There are two options ;

analysis 3：3 A stair - The first step is to jump 1 individual , And then there were 2 individual ; The first step is to jump 2 individual , And then there were 1 individual ; Number of schemes = jump 2 Number of projects + jump 1 Number of projects ;

analysis 4：4 A stair - The first step is to jump 1 individual , And then there were 3 individual ; The first step is to jump 2 individual , And then there were 2 individual ; Number of schemes = jump 3 Number of projects + jump 2 Number of projects ;

analysis 5：5 A stair - The first step is to jump 1 individual , And then there were 4 individual ; The first step is to jump 2 individual , And then there were 3 individual ; Number of schemes = jump 4 Number of projects + jump 3 Number of projects ;

...

analysis n：n A stair - Number of schemes = jump n-1 Number of projects + jump n-2 Number of projects .

summary ： This is a Fibonacci sequence problem , There are also two solutions ： Recursion and iteration

#include <stdio.h>

// recursive 
int solve1(int n)
{
	switch (n)
	{
	case 1:
		return 1;
	case 2:
		return 2;
	default:
		return solve1(n - 1) + solve1(n - 2);
	}
}

// iteration 
int solve2(int n)
{
	int a = 1;
	int b = 2;
	int c = 0;
	
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}

	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);

	printf(" Recursive results ：%d\n", solve1(n));
	printf(" Iteration results ：%d\n", solve2(n));

	return 0;
}

tips： The frog jumping steps is a little different from the Fibonacci sequence when n = 2 When the results are different , So there are differences in some codes , But the big idea remains the same .