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

  1. 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 : ...

  2. 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 ...

  3. 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 ...

  4. 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 ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. 【 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 ] ...

  9. 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

  1. 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. ...

  2. spring boot Pack it up jar The package is being published to the server

    http://blog.csdn.net/sai739295732/article/details/49444447

  3. Replace all strings , obtain url Parameter values

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

  4. IOS Code block pass value

    #import <UIKit/UIKit.h> typedef void (^MyBlock)(NSString*); @interface SecondViewController : ...

  5. 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 ...

  6. 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 <= ...

  7. 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 ...

  8. 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. ...

  9. 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 ...

  10. 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 ...