100! Одним числом

[noskovgleb]

Есть такой код, который вычисляет факториал 100, очень хотелось бы разобраться как он работает, вот собственно сам код:

#include<iostream.h>
#include<conio.h>
void main()
{  int i,k,n=200,A[200];
   clrscr();
   for(i=0; i<n; i++)
      A[i]=0;
   A[0]=1;
   for(k=0; k<100; k++)
   {  for(i=0; i<n; i++)
         A[i]*=(k+1);
      for(i=0; i<n; i++)
      {  A[i+2]+=(A[i]/100);
         A[i+1]+=(A[i]%100/10);
         A[i]%=10;
      }
   }
   for(i=0; i<n; i++)
      cout<<A[n-i-1];
   cout<<endl;
   getch();
}

[Granus]

Делается обычная длинная арифметика. A - массив десятичных чисел числа.
Число = A[0] + 10 * A[1] + 100 * A[2] + ...
Изначально число в A - 1. Потом оно последовательно умножается на все числа до 100. Для этого мы сначала каждый элемент массива умножаем на k, после чего обрабатываем переполнение (случаи, когда A[i] >= 10, мы все-таки цифры в них храним). Собственно, вот этот код

for(i=0; i<n; i++)
      {  A[i+2]+=(A[i]/100);
         A[i+1]+=(A[i]%100/10);
         A[i]%=10;
      }

и избавляет от переполнения.

[noskovgleb]

а можно по подробнее, как будто если бы вы чайнику объясняли?
как работает особенно эта конструкция:

for(i=0; i<n; i++)
         A[i]*=(k+1);
      for(i=0; i<n; i++)
      {  A[i+2]+=(A[i]/100);
         A[i+1]+=(A[i]%100/10);
         A[i]%=10;
      }

[Granus]

Для начала, чуть-чуть подправлю, чтобы было понятнее

for(k=1; k<=100; k++)
   {  for(i=0; i<n; i++)
         A[i]*=k;
      for(i=0; i<n; i++)
      {  A[i+2]+=(A[i]/100);
         A[i+1]+=(A[i]%100/10);
         A[i]%=10;
      }
   }

Этот кусок кода - умножение длинного числа на k (хотя, думаю, Вы догадались).
Напомню, в массиве A мы храним десятичные цифры нашего числа. X = A[0] + 10 * A[1] + 100 * A[2] + ... + 10^199 * A[199];
Из этого представления видно, что чтобы умножить число на k (где k - "короткое" число, помещающееся в базовые типы данных), мы можем каждую цифру умножить на k:

for(i=0; i<n; i++)
         A[i]*=k;

Но здесь возникает проблема: в массиве будут уже не цифры, а числа (причем числа <= 900: изначально там цифры <= 9, k <= 100 значит результат умножения <= 900).
Приведенное выше разложение все еще будет работать, но вот нам дальше работать с этим числом трудновато (все операции считают, что в массиве только цифры). Поэтому мы боремся с переполнением:

for(i=0; i<n; i++)
      {  A[i+2]+=(A[i]/100);
         A[i+1]+=(A[i]%100/10);
         A[i]%=10;
      }

Как мы с ним боремся? Мы знаем, что получившиеся в массиве числа у нас <= 900, то есть лишних цифр в нем не более двух (сотни A[i]/100 и десятки A[i]%100/10). Поэтому в следующую ячейку мы прибавляем число десятков, через одну - число сотен, после чего в данной ячейке оставляем только одну цифру - число единиц. От этого могли еще увеличиться значения дальше, но их переполнение цикл обработает позже, поэтому все сработает.

[noskovgleb]

вроде бы все понятно. Гранусу большое спасибо за ответ.
Очень помог.

[Karmadon]

У меня подобный пример но переписан под вектор
Но работает только на коротких числах (до 26!)
а потом только конец цифры

#include<iostream.h>
#include <vector.h>

int main()
{   
    int factor(5);
    int i(0);
    int k(0);
    vector<int> A(0);
    
    A.push_back(1);
    A[0]=1;
    
    for(k=0; k<factor; k++)
        {
            A.push_back(0);
        
        for(i=0; i<A.capacity(); i++)
            {
                A[i]*=(k+1);
            }
        
            for(i=0; i<A.capacity(); i++)
                {  
                    A[i+2]+=(A[i]/100);
                    A[i+1]+=(A[i]%100/10);
                    A[i]%=10;
                }
        }
    for(i=0; i<A.size(); i++)
        {
            cout<<A[A.size()-i-1];
        }
    
   cout<<endl;
    return 1;
}

Что не так?

[Karmadon]

Вот работающий варинат (может пригодится)

#include    <iostream.h>
#include    <vector.h>

int main()
{   
    bool nulic(true);
    int factor(1000);
    int i(0);
    int k(0);
    vector<int> A(0);
    
    A.push_back(1);
    A[0]=1;
    
    
    for(k=0; k<factor; k++)
        {
        A.push_back(0);
        
        for(i=0; i<A.size(); i++)
            {
            A[i]*=(k+1);
            }
        A.push_back(0);
        A.push_back(0);
        for(i=0; i<A.size(); i++)
            {  
                A[i+2]+=(A[i]/100);
                A[i+1]+=(A[i]%100/10);
                A[i]%=10;
            }
        }
    
    
    for (i=A.size(); i>=0; i--) 
        {
        
        if (A[i]==0) 
            {
            if (!nulic) 
                { 
                    cout<<A[i];
                }
            }
        else
            {
                cout<<A[i];
                nulic=false;
            }

        }
   
    cout<<endl;

    return 1;
}