(7)[Chapter12]분할정복_3_피보나치 수열(작성중)

분할정복_3_피보나치수열_이론과 코드노트.pdf

3.40MB

##꽤 어려워 했던 부분 노트 사진 :

 

##핵심 개념(작성중):

##코드 :

 

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable : 4996)
 
typedef unsigned long ULONG;
 
typedef struct _tagMatrix2x2 
{
    ULONG Data[2][2];
}Matrix2x2;
 
Matrix2x2 Matrix2x2_M(Matrix2x2 A, Matrix2x2 B)
{
    //1_ 반환용 임시 행렬 C선언;
    Matrix2x2 C;
 
    //2_ 곱셈 연산
    C.Data[0][0] = A.Data[0][0] * B.Data[0][0] + A.Data[0][1] * B.Data[1][0];
    C.Data[0][1] = A.Data[0][0] * B.Data[0][1] + A.Data[0][1] * B.Data[1][1];
    C.Data[1][0] = A.Data[1][0] * B.Data[0][0] + A.Data[1][1] * B.Data[1][0];
    C.Data[1][1] = A.Data[1][0] * B.Data[0][1] + A.Data[1][1] * B.Data[1][1];
 
    //3_ C반환
    return C;
}
 
Matrix2x2 Matrix2x2_P(Matrix2x2 A, int N)
{
    //종료 조건 : A^1
    if (N == 1) 
    {
        return A;
    }
 
    //분할 
    A = Matrix2x2_P(A, N / 2);
 
    //정복 (구현부) (쪼개진 후, 역순으로 조립 생각)
    //A^2 = A^1 X A^1 부터 생각
    A = Matrix2x2_M(A, A);
 
    if (N % 2 != 0) {//N이 홀수 라면, A^1을 한번 더 곱해야 함
        Matrix2x2 B;
 
        B.Data[0][0] = 1;
        B.Data[0][1] = 1;
        B.Data[1][0] = 1;
        B.Data[1][1] = 0;
 
        A = Matrix2x2_M(A, B);
    
    }
 
    return A;
 
}
 
//행렬 제곱 후, 01원소 || 10원소만 뽑아내기
ULONG Fibo(int N) 
{
    //행렬 A 선언 ,  초기화
    Matrix2x2 A;
 
    A.Data[0][0] = 1;
    A.Data[0][1] = 1;
    A.Data[1][0] = 1;
    A.Data[1][1] = 0;
 
 
    //행렬 A 제곱 연산
    A = Matrix2x2_P(A, N);
 
    //원소 추출, 반환
    return A.Data[0][1];
 
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    printf("F(%d) = %lu\n", N, Fibo(N));
 
    return 0;
}