Layer7_20160323수업_2의2000제곱(2의 2000승)

<2의 2000제곱>

알고리즘 설명 : 

전제조건_1 : 배열 한칸한칸마다 숫자 한자리씩 넣는다. 필자는

result[0]==일의자리수, result[1]==십의자리수, result[2]==백의자리수 ...

이렇게 되는것 보단

result[700]==일의 자리수, result[699]==십의자리수, ...

이렇게 되는게 더 이해하기 편해서 배열을 역으로 돌렸다.

전제조건_2 : 나중에 출력할 때는 0을 정리해서 출력하기 때문에 결과값에는 상관이 없다.

코드 : 

 
#include <stdio.h>
int main() {
    int i, j, k, a = 0;
    int result[701] = { 0 }, result_sub[701] = { 0 };
    result[700] = 2;
 
    for (i = 1; i < 2000; i++) { //2000번 반복
        for (k = 700; k >= 1; k--) {
            if ((result[k] * 2) < 10) {//해당 자릿수(result[k])에 들어있는 값에 X2를 해서 10이 넘어가지 않는다면 그냥 그 수에 X2를 해서 그 자리에 집어넣는다.
                result[k] = result[k] * 2;
            }
 
            else if ((result[k] * 2) >= 10) {//result[k]에 들어있는 값에 X2를 해서 10이 넘어갈 경우 바로 윗자릿수(result_sub[k-1])에 +1을 하고 그 자리에는 X2한 값의 일의자리 수를 집어넣는다.
                result[k] = (result[k] * 2) % 10;
                result_sub[k - 1] += 1;
            }
        }
        for (a = 700; a >= 1; a--) {//result_sub[a]에 있던 +1들을 result[a]에 합쳐준다.
            if (result_sub[a] == 1) {
                result[a] += 1;
                result_sub[a] = 0;
                if (result[a] >= 10) {//이 과정에서 또 10이 넘어가면 그 윗자리수에 +1을 하고 그 자리에는 %10한 값을 남긴다.
                    result[a] = result[a] % 10;
                    result[a - 1] += 1;
                }
            }
        }
    }
    i = 0;//i를 재활용 하기 위해서 0으로 정리.
    for (j = 0; j < 700; j++){//i, j 재활용, 출력값 앞에 있는 0 정리
        if (result[j] != 0)
            break;
        else{
            ++i;
        }
    }
    for (j = i; j <= 700; j++) {//출력값 앞에 있는 0 정리 후 출력.
        printf("%d", result[j]);
    }
    return 0;
}

일차원 배열과 이중for문만 알고 있다면 누구나 할 수 있다!~