큰 수 처리 문서

1. 100 ! 혹은 2 ¹⁰⁰류의 큰 계산하기

큰 수를 처리하는 방법 중 한 가지를 알아보자. 이 알고리즘은 번거로운 문자처리 없이 정수 배열로 처리가 가능하다.
(2^100 , 100 ! 를 구하는데 적당한 알고리즘.... 9 * 승수가 정수 범위를 초과하지 않는 문제)

예를 들어보면

289 * 12 는

(9 + 80 + 200) * 12

• 0 ... last-1 까지
  12 를 곱한 후 나머지는 남기고 몫은 위 자리로 올림.

• last 부터 ~
  몫이 영이 될때 까지 나머지는 남기고 몫은 위로.

#include < stdio.h >

int main()
{
   int fact[10]={9,8,2};
   int i,last = 3;
   int mok;

   mok = 0;
   for( i = 0 ; i < last ;i++){
      fact[i] = fact[i]*12 + mok;
      mok = fact[i] / 10;
      fact[i] = fact[i] % 10;
   }

   for( ; mok != 0 ; last++ ){
      fact[last] = mok % 10;
      mok /= 10;
   }

}

n ! 소스

초기치를 1 로 하고 last 를 1 로 한 후 1 부터 n 까지 반복.

#include < stdio.h >


int fact[100000]={1};

int main()
{
   int i,f,last = 1;
   int mok,n;
   
   scanf("%d",&n);

   for( f = 1 ; f <= n; f++){
      mok = 0;
      for( i = 0 ; i < last ;i++){
         fact[i] = fact[i]*f + mok;
         mok = fact[i] / 10;
         fact[i] = fact[i] % 10;
      }
      
      for( ; mok != 0 ; last++ ){
         fact[last] = mok % 10;
         mok /= 10;
      }
   }


   for( i = last -1 ; i >= 0 ; i--){
      printf("%d",fact[i]);
   }

   printf("\n");
   
}