C언어 팩토리얼 배열 - ceon-eo paegtolieol baeyeol

일기장처럼 쓰이지만, 블로그인 일기장

목차 Show

일기장처럼 쓰이지만, 블로그인 일기장
'프로그래밍/C'의 다른글

프로그래밍

프로그래밍/C

일단개그하다 2015. 5. 24. 00:27

저작자표시 비영리 변경금지

Tag

100!, C, C언어, factorial, 팩토리얼

'프로그래밍/C'의 다른글

이전글[C language] 텍스트 파일 글자 수 세기(연결 리스트)
현재글[C language] 배열을 사용한 100 팩토리얼 구하기
다음글[C language] 삼항 연산자(조건 연산자)

[C language] 기본적인 동적 할당 예제 (malloc) 2015.05.24
[C language] 단일 연결 리스트 2015.05.24
[C language] 삼항 연산자(조건 연산자) 2015.05.24
[C language] 텍스트 파일 글자 수 세기(연결 리스트) 2014.07.20

비밀글

이전 포스트에서 배열을 사용하여 제법 큰 수에 대한 팩토리얼 값을 구해봤습니다. 오늘은 그 원리에 대해서 다뤄보도록 하겠습니다. 그리고 응용하여 아주 큰 수(100만이상)에 대한 팩토리얼값도 구해보도록 하죠.

void fact2(int n, char *str)

함수 원형에 대해서 살펴보면 리턴값이 없고 두개의 인수를 가지는 void형 함수입니다. 첫번째 인수n은 구하고자하는 수이고, 두번째 인수 *str은 팩토리얼의 결과값을 담을 그릇 즉 문자형 배열의 주소입니다. 왜 숫자를 저장할 배열인데 문자형 배열을 사용했을까요?

저번 소수를 구하는 프로그램에서도 문자형 배열을 사용해서 소수를 구했던 적이 있지요? 그 처럼 숫자를 한자리씩 나누어 저장 할 거니까 문자형 배열을 사용해도 충분하기에 문자형 배열을 사용하였습니다.

10! = 3628800;입니다.

이 숫자를 한자리씩 잘라서 배열에 저장하여 표현 하면

0 0 8 8 2 6 3 즉 str[0] = 0, str[1] = 0, str[2] = 8,......str[5] = 6, str[6] = 3

위와 같이 배열에 저장 할 수 있습니다.

저장은 저렇게 한다지만 계산은?
직접 하나씩 계산을 하면서 어떻게 가능한지 알아보도록 하죠.

str[0] = 1;
함수안의 내용을 보면 먼저 위와같이 배열의 첫번째에 1을 저장하였습니다.

다음에 2부터 n까지 곱해줘서 팩토리얼값을 구합니다.

str[0] * 2 = 2;

r = 0으로 초기화 되었으니,

r = 2 + 0 = 2;

str[j] = str[0] = 2 % 10 = 2;

r = 2 / 10 = 0;

자릿수를 나타내는 cnt는 1이니 한번만에 for문을 빠져나옵니다.

while(r) = while(0) 거짓이니 아무일도 하지않고 빠져나옵니다.

여전히 cnt = 1;

이제 i값이 1증가해서 3;

r = str[0] * i + 0 = 2 * 3 = 6

str[j] = str[0] = r % 10 = 6 % 10 = 6

r = r /10 = 0;

i값이 1증가해서 4;

r = str[0] * i + 0 = 6 * 4 = 24

str[j] = str[0] = r % 10 = 24 % 10 = 4

r = r /10 = 24 / 10 = 2;

while(r) = while(2)로 참

str[cnt++] = str[1] = r % 10 = 2 % 10 = 2, cnt = 2;

r = r /10 = 2 / 10 = 0

자릿수가 하나 증가해 2가 되었습니다.

i값이 1증가해서 5;

r = str[0] * i + 0 = 4 * 5 = 20

str[j] = str[0] = r % 10 = 20 % 10 = 0

r = r /10 = 20 / 10 = 2;

cnt가 2로 증가했으니

r = str[1] * i + r = 2 * 5 + 2 = 12

str[j] = str[1] = r % 10 = 12 % 10 = 2

r = r /10 = 12 / 10 = 1;

while(r) = while(1)로 참

str[cnt++] = str[2] = r % 10 = 1 % 10 = 1, cnt = 3;

r = r /10 = 1 / 10 = 0

자릿수가 하나 증가해 3이 되었습니다.

이런식으로 쭉 해나가면 큰 수에 대한 팩토리얼값도 구할수 있게 됩니다.

        while(r)
        {
            str[cnt++] = r % DX;
            r /= DX;
        }
이 부분에서 if(r)이 아닌 while(r)을 사용한 이유는 자릿수가 100이상 1000단위로 넘어가면 10으로 나눈 몫이 두자리수가 넘어 갑니다. 그래서 if(r)이 아닌 while(r)을 사용하였습니다.

void fact2(int n, char *str)
{
str[0] = 1;
int i, j, r, cnt = 1;

    for(i = 2; i <= n; i++)
    {
        j = 0;
        while(!str[j]) j++; <==  이곳은 사실 처음부터 생각했던건 아니고 결과를 보고서 넣게된 경우입니다.

나중에 테스트해 보시면 알겠지만 5이상부터는 0으로 끝나고, 큰 수의 팩토리얼값들은 끝에 0이 상상 이상으로 많이 나옵니다. 값이 0이면 일일이 계산해서 확인해보지 않아도 0이므로 끝에 0은 스킵해주기 위한 겁니다. 큰 수의 팩토리얼 계산할때 시간이 아주 약간 세이브가 됩니다. 모든 0을 걸러내면 안됩니다. 중간의 0은 r값이 0이 아닐 수 있기 때문입니다.

배열에 계산 결과를 저장했으면 출력을 해야 되겠지요.

printf("자릿수 = %d, %d! = ", cnt, n); 큰 수의 팩토리얼값은 커서 자릿수를 표시해주는게 좋습니다.

    for(i = cnt - 1; i >= 0; i--)
    {
        printf("%d",str[i]);
    }
반복문을 사용해서 거꾸로 출력을 해주면 온전한 숫자가 출력이 됩니다.

그럼 위와 같은 간단한 방법으로 100만정도 되는 큰 수의 팩토리얼값을 구할수 있을까요? 아래 그림은 1500!값의 결과입니다. 자릿수가 4115자리로 우리가 배열로 준 5000에 육박하네요. 이정도 배열 크기로는 택도 없습니다.

그렇다고 배열의 크기를 무한정으로 크게 할 수도 없습니다. 그렇다면 어떻게 하면 가능할까요? 백터를 사용하거나 아니면 사용자정의 자료형을 만들어 사용하면 됩니다.

다음은 벡터를 적용해서 작성된 코드입니다.

#include <stdio.h>
#include <time.h>
#include <vector>
#include <algorithm>

using namespace std;

#define DX 10

void fact2(int n)
{
int i, j, r, cnt;
time_t t1, t2;

vector<char> vc;
vector<char>::iterator it;

t1 = clock();
vc.push_back(1);

    for(i = 2; i <= n; i++)
    {
        j = 0;
        while(!vc[j]) j++;

        for(r = 0; j < vc.size(); j++)
        {
            r += vc[j] * i;
            vc[j] = r % DX;
            r /= DX;
        }
        while(r)
        {
            vc.push_back(r % DX);
            r /= DX;
        }
    }
    t2 = clock();

printf("계산시간 = %.3fsec\n", (t2 - t1)/1000.);
printf("자릿수 = %d, %d! = ", vc.size(), n);

    cnt = vc.size();
    int N = 0;
    for (i = cnt - 1; i >= 0; i--)
    {
        printf("%d",vc[i]);
        if(++N > 100) break;
    }
    printf("\n");
}

int main()
{

//for(int i = 20; i <= 100; i++) fact2(i, fNum);
fact2(10000);
}

이정도 코드로만 해도 10만 100만 팩토리얼값을 구할 수는 있지만 시간이 많이걸립니다. 효율이 많이 떨어진다는겁니다.

10만 팩토리얼 결과입니다. 자릿수가 너무 많아서 100자리까지만 출력해봤습니다. 엄청나지요.

점심 먹으면서 100만 팩토리얼을 실행시켜놨는데... 점심식사가 끝났는데 아직 결과가 안나왔습니다. 언제나 나오려나.. 나오긴 하려나.... 기다려 보지요.
결과 나오면 수정으로 첨부하겠습니다.

드디어 결과가 나왔습니다. 한번 보시죠

자릿수는 무려 556만이 넘고, 계산시간은 1시간 반이 훌쩍 넘네요. 계산은 가능한데 시간이 너무 많이걸려서 효율적이지 못합니다.

전에 제가 작성했던 프로그램으로는 11분이 체 안걸렸네요.

정확한 결과값을 알기위해서는 파일로 저장을 하면 됩니다. 다음번 포스트에서는 효율 개선과 파일 출력에 대해서 알아보도록 하지요.