호너의 법칙, 진법 변환 (feat. Honer's method)

Honer’s method

 

호너의 법칙은 다항식을 푸는데 있어 계산량을 줄여준다.

프로그래밍에서 n진법을 10진법으로 바꿀 때 유용하게 사용할 수 있다.

예를들어,

1101 이라는 2진수가 있다.

우리가 10진수로 바꿀 때, 아래와 같이 8+4+1 = 13 으로 변환을 했다.

 

이를 수식으로 표현해보면 다음과 같다.

 

로 볼 수 있다.

여기에 x = 2를 대입(2진법 이기에)하여 계산해 보면, 우리가 위에서 계산한 방법과 똑같이

 나오는 것을 확인 할 수 있다.

여기서, 

 

를 다음과 같이 생각할 수 있다.

일반화하면 다음과 같다.

이렇게 하면 좋은 점은, 계산량을 최소화할 수 있고,

첫 번째 오는 숫자가 몇 째 자리의 수 인지 계산하지 않고 순차적으로 계산할 수 있기때문이다. 

이는 programming 할 때 부담을 줄여준다.

아래는 위 내용을 코드로 구현한 것이다.

#include <stdio.h>
 
char input[100];
int x;
 
long long honer(int x)
{
    long long sum = 0;
 
    for (int i = 0; input[i] != '\0'; i++) {
        if (input[i] >= 'A' && input[i] <= 'Z') 
            sum = sum * x + (input[i] - 'A' + 10);
        else 
            sum = sum * x + (input[i] - '0');
    }
 
    return sum;    
}
 
int main()
{
    scanf("%s", input); //string으로 변환하고자 하는 숫자를 입력받는다
    scanf("%d", &x); //몇 진법 숫자인지 입력받는다
 
    printf("result : %lld \n", honer(x));
 
    return 0;
}