2

Как посчитать факториал большого числа? К примеру 400!. Я так понимаю, что в стандартные типы такое число не влезет, как это обойти? Если можно пример или сам алгоритм.

6 ответов 6

4

Что-то на длинные числа народ потянуло... Зачёты близко?

#include <iostream>
#include <sstream>
#include <gmpxx.h>
using namespace std;
int main (int argc, char *argv[]) {
    int n;
    stringstream s;
    mpz_class f = 1;
    s.str(argv[1]);
    s >> n;
    for(int i=0; i < n; ) f *= ++i;
    cout << f << endl;
}

В результате будет

alex@alex-desktop:~$ ./fact 400

640345228466238952623479703195030058507025830260029594586844 459428023971691868314362784786474632646762943505750358568108 482981628835174352289619886468029979373416541508381624264619 423523070462443250151144486708906627739149181173319559964407 095496713452904770203224349112107975932807951015453726672516 278778900093497637657103263503315339653498683868313393520243 737881577867915063118587026182701698197400629830253085912983 461622723045583395207596115053022360868104332972551948526744 322324386699484224042325998055516106359423769613992319171340 638589965379701478272066063202173794720103213566246138090779 423045973606995675958360961587151299138222865785795493616176 544804532220078258184008484364155912294542753848035583745180 226759000613995601455952061272111929181050324910080000000000 000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000

1
  • Количество нулей совпало: [400/5]+[400/25]+400/125]=80+16+3=99 2 дек 2015 в 17:16
1

Например, такое. А вообще, такие числа в обиходе не встречаются. Например, я когда-то писал факториал на С++, и мне хватало значений вплоть до 137! (тип long long int).

UPD В крайнем можно все писать в тип string или char* а затем применять функции упрощения, если таковые допускаются. Например, здесь рассматривается формула Стирлинга.

UPD2 И Википедия в помощь. Только это приближенное вычисление.

1

Вот примерчик на си: длинная арифметика.

0

Использовать инструменты для арифметики большой точности. Например, в Java это классы BigInteger и BigDecimal.

Ну или в учебных целях писать эти классы/функции самому.

-2

unsigned long double.
Также я помню, в одной олимпиаде рассматривался пример с массивом из integer (на fpc).

type newType: array[0..10000] of integer.  
{использовалось для нахождения чисел Фибоначчи}
3
  • При использовании чисел с плавающей точкой будут потери точности. При этом чем больше операций и чем более разные по порядку числа будут в выражениях - тем больше будут потери
    – gecube
    8 окт 2011 в 15:47
  • What is usigned long double? 400 факториал в double?)
    – ivkremer
    8 окт 2011 в 16:04
  • Насчет потери точности, то такое никто проверять не будет=) Зато нагрузка на саму систему увеличится в разы при огромном к-ве операций . Хотя всунуть факториал 400 в double, пусть и long))...
    – 3JIoi_Hy6
    8 окт 2011 в 16:11

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.