Как посчитать факториал большого числа? К примеру 400!. Я так понимаю, что в стандартные типы такое число не влезет, как это обойти? Если можно пример или сам алгоритм.
6 ответов
Что-то на длинные числа народ потянуло... Зачёты близко?
#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
-
Количество нулей совпало: [400/5]+[400/25]+400/125]=80+16+3=99 2 дек 2015 в 17:16
Например, такое. А вообще, такие числа в обиходе не встречаются. Например, я когда-то писал факториал на С++, и мне хватало значений вплоть до 137! (тип long long int).
UPD В крайнем можно все писать в тип string
или char*
а затем применять функции упрощения, если таковые допускаются. Например, здесь рассматривается формула Стирлинга.
UPD2 И Википедия в помощь. Только это приближенное вычисление.
Использовать инструменты для арифметики большой точности. Например, в Java это классы BigInteger
и BigDecimal
.
Ну или в учебных целях писать эти классы/функции самому.
BigInteger думаю поможет тут.
-
2добро пожаловать на Stack Overflow на русском! Ссылки на внешние ресурсы — это прекрасно, но оставьте вместе со ссылкой описание, чтобы другие пользователи имели представление о её содержимом. Всегда цитируйте самую необходимую информацию, которую вы взяли из указанного источника, на случай если он недоступен или навсегда закрыт.. дополнить ответ можно, нажав править 22 янв 2021 в 11:30
unsigned long double
.
Также я помню, в одной олимпиаде рассматривался пример с массивом из integer
(на fpc).
type newType: array[0..10000] of integer.
{использовалось для нахождения чисел Фибоначчи}
-
При использовании чисел с плавающей точкой будут потери точности. При этом чем больше операций и чем более разные по порядку числа будут в выражениях - тем больше будут потери– gecube8 окт 2011 в 15:47
-
-
Насчет потери точности, то такое никто проверять не будет=) Зато нагрузка на саму систему увеличится в разы при огромном к-ве операций . Хотя всунуть факториал 400 в double, пусть и long))... 8 окт 2011 в 16:11