Go to the hall , The kitchen , Well written code , Turn over the wall , Welcome to Rui unstoppable daily practice ！

** subject ： High speed Fibonacci Number algorithm **

Content ： Let's talk about it first. Fibonacci The sequence , It's defined as a sequence of numbers ：f1,f2....fn There are, for example, the following rules ：

Try to find a high speed solution fn Methods

My solution ： I didn't think much about it , open vs2013 And then they knocked , The problem is really very easy, Every minute is supernatural .. Mr. , If it's not right, it will be conquered ！

In fact, the recursive form of this algorithm is given in the title , So the first thing I think of is recursion , It's just that solving high-speed methods before recursion , I wrote a non recursive algorithm

#include <iostream>

using namespace std; int _tmain(int argc, _TCHAR* argv[])

{

int f(int n);

cout << f(7) << endl;

getchar();

return 0;

} int f(int n)

{

int temp = 0, f1 = 1, f2 = 1;

if (n == 1 || n == 2)

return 1;

else

{

for (int i = 1; i < (n - 1); i++)

{

temp = f1 + f2;

f2 = f1;

f1 = temp;

}

return temp;

}

}

Then I wrote a recursive algorithm

#include <iostream>

using namespace std; int _tmain(int argc, _TCHAR* argv[])

{

int f(int n);

cout << f(7) << endl;

getchar();

return 0;

} int f(int n)

{

if (n == 1|| n==2)

return 1;

if (n > 2)

return f(n - 1) + f(n - 2);

}

On the basis of recursion , Someone has come up with a sharper algorithm , I didn't think of that .. ashamed ...

This algorithm uses some skill matrices , By matrix multiplication Fibonacci Addition of , And then through me in 《 Numerical self multiplication is a non recursive solution 》 The method of using exponential binary heap multiplication by distinguishing odd and even numbers mentioned in , Reduce the number of multiplications .

ps：

Using the matrix multiplication above , In the matrix 11 The number of positions is the matrix 11 and 21 And , And with matrices 11 and 21 Express Fibonacci Of f(n-1) and f(n-2), To seek by multiplying fn.

#include <iostream>

using namespace std; int _tmain(int argc, _TCHAR* argv[])

{

int f(int n);

cout << f(7) << endl;

getchar();

return 0;

} int f(int n)

{

void matrix_power(int a, int b, int c, int d, int n, int *aa, int *bb, int *cc, int *dd);

int a, b, c, d;

if (n == 1 || n == 2)

{

return 1;

}

else

{

matrix_power(1, 1, 1, 0, n - 2, &a, &b, &c, &d);

return a + b;

}

} void matrix_power(int a, int b, int c, int d, int n, int *aa, int *bb, int *cc, int *dd)

{

int xa, xb, xc, xd;

if (n == 1)

*aa = a, *bb = b, *cc = c, *dd = d;

else if (n & 0x01 == 1)

{

matrix_power(a, b, c, d, n - 1, &xa, &xb, &xc, &xd);

*aa = a*xa + b*xc;

*bb = a*xb + b*xd;

*cc = c*xa + d*xc;

*dd = c*xb + d*xd;

}

else

{

matrix_power(a, b, c, d, n >> 1, &xa, &xb, &xc, &xd);

*aa = xa*xa + xb*xc;

*bb = xa*xb + xb*xd;

*cc = xc*xa + xd*xc;

*dd = xc*xb + xd*xd;

}

}

The experimental results of the three pieces of code are the same as, for example, the following ：

** Welcome to add a small daily practice , Hey ！**

** Practice every day , I'll see you in a long time , come on. ！**

** -End-**

References ：《c A selection of 100 language titles 》

## A little practice every day —— High speed Fibonacci More articles on arithmetic

- A little daily practice —— High speed Fibonacci Number algorithm
Go to the hall . The kitchen . Well written code , Turn over the wall , Welcome to Rui unstoppable daily practice ! subject : High speed Fibonacci Number algorithm Content : Let's talk about it first. Fibonacci The sequence , It's defined as a sequence of numbers :f1,f2....fn There are, for example, the following rules : ...

- A little practice every day ——Armstrong Count
Go to the hall . The kitchen , Well written code , Turn over the wall , Welcome to Rui unstoppable daily practice ! subject :Armstrong Count Content : In a three digit positive integer , such as abc. Some can satisfy a^3+b^3+c^3=abc Conditions , That is to say, each ...

- A little practice every day ——Eratosthenes Screening method
Go to the hall . The kitchen , Well written code . Turn over the wall , Welcome to Rui unstoppable daily practice ! subject :Eratosthenes Screening method Content : Finding prime numbers is a very common problem , Usually, it's nothing more than eliminating with numbers . Except when it's endless , A given number is a prime number . But ...

- java try Fibonacci Count
Problem B Fibonacci Count The time limit :3000 ms | Memory limit :65535 KB describe Infinite series 1,1,2,3,5,8,13,21,34,55... be called Fibonacci The sequence ...

- Daily exercise of classic algorithm problems —— Seventeen Dijkstra Algorithm
original text : Daily exercise of classic algorithm problems -- Seventeen Dijkstra Algorithm Maybe in life , We often encounter a problem , Under many restrictions , How to find an optimal solution ? Maybe you think a lot of things like “ Linear programming ”,“ Dynamic programming ” These classics ...

- High speed nearest neighbor algorithm for high dimensional data FLANN
Copyright notice : This article is an original blog article , It can't be reproduced without the permission of the blogger . https://blog.csdn.net/jinxueliu31/article/details/37768995 High speed nearest neighbor algorithm for high dimensional data FL ...

- SCAU1143 How many? Fibonacci Count -- Big Fei wave number 【 Hang Dian -HDOJ-1715】-- High precision addition --Fibonacci Count --- Big number comparison
/******* To the reader ( Ha ha, if anyone looks at it 23333) Haha, the great hero belongs to Hua Nong 19 I'm a novice in software engineering , I have little talent and little learning, but I have the words of the University Science Association “ Take the initiative to have a story ” Or bold to do a humble attempt to build a blog , After thinking about yourself, everything you learn is ...

- 【 Algorithm 】273- Every Monday And Data structure and algorithm （Tree）
This is the sixth week's exercise , I've been working overtime a lot lately . Here's the link I shared earlier : [ Algorithm ]200- Every Monday And Data structure and algorithm (Stack) [ Algorithm ]213- Every Monday And Data structure and algorithm (LinkedList) [ Algorithm ] ...

- Every Monday And Data structure and algorithm （Queue）
This is the second week's exercise , Here is a supplement , May day is coming , My plan has been arranged first , Develop an interesting thing . Here's the link I shared earlier : 1. Every Monday And Data structure and algorithm (Stack) 2. Every Monday And Data structure and ...

## Random recommendation

- Python Data type “ Sequence overview and basic sequence types (Basic Sequences)”
A sequence is an ordered queue , A focus on " Orderly ". One .Python The classification of the sequence in Python There are several types of sequences in : 3 Two basic sequence types (Basic Sequence Types):list. ...

- spring boot Pack it up jar The package is being published to the server
http://blog.csdn.net/sai739295732/article/details/49444447

- Replace all strings , obtain url Parameter values
Replace all strings : var newStr = str.replace(/null/g, ""); obtain url Parameter values <script type="text/javas ...

- IOS Code block pass value
#import <UIKit/UIKit.h> typedef void (^MyBlock)(NSString*); @interface SecondViewController : ...

- Use ExposedObject Yes Asp.net MVC Anonymous type in JsonResult Unit test
return JsonResult yes MVC Common return value types in , And the simple and convenient way is to use it with anonymous types . such as : public ActionResult PreviewEmail() { …… return J ...

- 1058 N The length of the factorial of
1058 N The length of the factorial of Base time limit :1 second Space restriction :131072 KB Input N seek N The factorial of 10 The length of the decimal representation . for example 6! = 720, The length is 3. Input Input N(1 <= N <= ...

- CSS Self study notes （8）:CSS expand （ One ）
CSS Element alignment have access to margin Attribute classes align elements horizontally When you align block elements horizontally , You can change the block element's margin Property is defined as "auto", What needs to be noted here is , It should be stated that !DOCTYPE, otherwise ...

- Super full ！ Sort out the common iOS Third party resources
One : Third party plug-ins 1: Based on the idea of responsive programming oc Address :https://github.com/ReactiveCocoa/ReactiveCocoa 2:hud Prompt box Address :https://github. ...

- Go Language type conversion
Type conversion is used to convert a variable of one data type to a variable of another type .Go The basic format of language type conversion is as follows : type_name(expression) type_name For the type ,expression Expression for . real ...

- JavaScript , js Context (this Reference to )
Context representative this The value of the variable , as well as its Refer to ; It determines how a function is called ; When a function is called as a method of an object , this Always point to The object that calls this method . ----- 1 , Situation 1 : Literally ...