История изменений

Исправление ~~qulinxao~~, 08.10.15 02:15 (текущая версия) :

#include <stdio.h>
 
void multiply(int F[2][2], int M[2][2]);
 
void power(int F[2][2], int n);
 
int fib(int n){
  if (n == 0)
    return 0;
  int F[2][2] = {{1,0},{0,1}};
  power(F, n);
  return F[0][0];
}

int E[2][2] = {{1,1},{1,0}};

void power(int F[2][2], int n){
  if( n == 0)
      return;
  
  if( n > 1){
      power(F, n/2);
      multiply(F, F);
  }
  
  if( n%2 )
     multiply(F, E);
}
 
void multiply(int F[2][2], int M[2][2]){
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
int main(){
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}

Исправление ~~qulinxao~~, 08.10.15 02:11:

#include <stdio.h>
 
void multiply(int F[2][2], int M[2][2]);
 
void power(int F[2][2], int n);
 
int fib(int n){
  if (n == 0)
    return 0;
  int F[2][2] = {{1,0},{0,1}};
  power(F, n);
  return F[0][0];
}

int E[2][2] = {{1,1},{1,0}};

void power(int F[2][2], int n){
  if( n == 0)
      return;
  power(F, n/2);
  multiply(F, F);
  if( n%2)
     multiply(F, E);
}
 
void multiply(int F[2][2], int M[2][2]){
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
int main(){
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}

Исходная версия ~~qulinxao~~, 08.10.15 02:10:

с просторов интернета:

#include <stdio.h>
 
void multiply(int F[2][2], int M[2][2]);
 
void power(int F[2][2], int n);
 
int fib(int n){
  if (n == 0)
    return 0;
  int F[2][2] = {{1,1},{1,0}};
  power(F, n-1);
  return F[0][0];
}

int E[2][2] = {{1,1},{1,0}};

void power(int F[2][2], int n){
  if( n == 0)
      return;
  power(F, n/2);
  multiply(F, F);
  if( n%2)
     multiply(F, E);
}
 
void multiply(int F[2][2], int M[2][2]){
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
int main(){
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}