C language jump step problem solution
- 2020-04-01 23:46:17
- OfStack
There are n steps in total. If you can jump 1 step at a time, you can also jump 2 steps. Find the total number of jumping methods, and analyze the time complexity of the algorithm.
Answer: a function f(n) is used to represent the total jump of n steps.
1. If there is only one step, f(1) = 1;
2. If there are 2 steps, f(2) = 2;
3, when there are n steps, if the first jump 1 level, there are f(n-1) jumping method, if the first jump 2 levels, there are f(n-2) jumping method, that is, f(n) = f(n-1) + f(n-2).
Is the Fibonacci sequence.
The operation interface is as follows:
Answer: a function f(n) is used to represent the total jump of n steps.
1. If there is only one step, f(1) = 1;
2. If there are 2 steps, f(2) = 2;
3, when there are n steps, if the first jump 1 level, there are f(n-1) jumping method, if the first jump 2 levels, there are f(n-2) jumping method, that is, f(n) = f(n-1) + f(n-2).
Is the Fibonacci sequence.
#include "stdafx.h"
#include <iostream>
using namespace std;
//cycle
int TotalStep(int n)
{
if (n <= 0)
{
return 0;
}
else if (1 == n || 2 == n)
{
return n;
}
int first = 1;
int second = 2;
int total = 0;
for (int i = 3; i <= n; i++)
{
total = first + second;
first = second;
second = total;
}
return total;
}
//recursive
int RecurTotalStep(int n)
{
if (n <= 0)
{
return 0;
}
else if (n == 1 || n == 2)
{
return n;
}
else
{
return RecurTotalStep(n - 1) + RecurTotalStep(n - 2);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cout<<TotalStep(20)<<endl;
cout<<RecurTotalStep(20)<<endl;
return 0;
}
The operation interface is as follows:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/201305240925052.jpg ">