Рассчитать факториал произвольно большого числа, показывая все цифры
Недавно в одном из интервью меня попросили описать метод вычисления факториала любого произвольно большого числа; метод, в котором мы получаем все цифры ответа.
Я искал разные места и спрашивал на нескольких форумах. Но я хотел бы знать, есть ли способ сделать это без использования таких библиотек, как GMP.
Спасибо.
11 ответов
Библиотека GNU Multiprecision хороша! Но поскольку вы говорите, что использование внешних библиотек недопустимо, я полагаю, что это возможно только путем взятия массива типа int, а затем умножения чисел, как вы делаете это пером на бумаге!
Вот код, который я написал некоторое время назад..
#include<iostream>
#include<cstring>
int max = 5000;
void display(int arr[]){
int ctr = 0;
for (int i=0; i<max; i++){
if (!ctr && arr[i]) ctr = 1;
if(ctr)
std::cout<<arr[i];
}
}
void factorial(int arr[], int n){
if (!n) return;
int carry = 0;
for (int i=max-1; i>=0; --i){
arr[i] = (arr[i] * n) + carry;
carry = arr[i]/10;
arr[i] %= 10;
}
factorial(arr,n-1);
}
int main(){
int *arr = new int[max];
std::memset(arr,0,max*sizeof(int));
arr[max-1] = 1;
int num;
std::cout<<"Enter the number: ";
std::cin>>num;
std::cout<<"factorial of "<<num<<"is :\n";
factorial(arr,num);
display(arr);
delete[] arr;
return 0;
}
'arr' - это просто целочисленный массив, а factorial - простая функция, которая умножает данное число на "большое число".
Надеюсь, что это решает ваш запрос..
Принятый ответ хорошо, но это C++; мы можем сделать лучше Давайте начнем наш собственный Bignum класс, с абсолютно неограниченным количеством цифр.
Для достижения максимальной эффективности мы будем работать с чистыми двоичными числами, упаковывая каждый элемент массива в столько битов, сколько мы можем эффективно обработать. Более простой подход - хранить одну десятичную цифру в каждом элементе. Здесь я пошел на компромисс, сохраняя 9 десятичных цифр в каждой uint32_t элемент.
Данные хранятся с прямым порядком байтов, так как гораздо проще vector в конце, когда нам нужны элементы более высокого порядка.
Когда у нас есть этот класс, факториальная функция сама является простотой.
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <stdint.h>
#include <vector>
class Bignum
{
public:
Bignum(int value)
{
assert(value >= 0 && value <= 999999999);
parts.push_back(value);
}
Bignum& operator*=(int rhs)
{
assert(rhs >= 0 && rhs <= 999999999);
uint32_t carry = 0;
for (size_t i = 0; i < parts.size(); i++)
{
uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry;
parts[i] = (uint32_t)(product % 1000000000LL);
carry = (uint32_t)(product / 1000000000LL);
}
if (carry != 0)
parts.push_back(carry);
return *this;
}
friend std::ostream & operator<<(std::ostream& stream, const Bignum& num);
private:
std::vector<uint32_t> parts;
};
inline std::ostream& operator<<(std::ostream& stream, const Bignum& num)
{
char oldfill = stream.fill('0');
for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++)
stream << *it << std::setw(9);
stream.fill(oldfill);
stream.width(0);
return stream;
}
Bignum factorial(int n)
{
Bignum fac = 1;
for (int i = 2; i <= n; i++)
fac *= i;
return fac;
}
int main(int argc, char* argv[])
{
for (int n = 0; n <= 52; n++)
std::cout << factorial(n) << std::endl;
return 0;
}
Хорошее решение от Srivatsan Iyer и мое предложение:
Это все еще можно сделать более эффективным с помощью памяти, используя массив unsigned char вместо использования массива int для хранения цифр. Это займет всего 25% памяти, необходимой для массива int.
Для лучшей оптимизации памяти мы также можем использовать один байт для представления двух цифр. Поскольку для представления любой цифры от 0 до 9 достаточно только 4 бита. Таким образом, мы можем упаковать две цифры в один байт, используя побитовые операции. Это займет 12,5% памяти, необходимой для массива int.
Ну, вы должны написать свои собственные математические процедуры с использованием массивов. Это очень просто для сложения, умножение немного сложнее, но все же возможно.
РЕДАКТИРОВАТЬ: хотел опубликовать пример, но пример Шриватсана Айера просто отлично.
У меня есть решение для расчета факториала, который отлично работает по крайней мере для n<=15000. Факториал 10000 можно рассчитать менее чем за 1 секунду, а для расчета факториала требуется менее 2 секунд. (Конечно, ваш вопрос ничего не говорит о временных ограничениях, и эти сроки полностью зависят от машины). В любом случае, концепция довольно проста. Я использую массив символов. Первый символ массива - "1". Младшие биты хранятся в индексе, начиная с 0. Переменная (m согласно моей программе) отслеживает факториальную длину. Конечное значение m - это количество цифр в факториале, а (m-1) -й элемент массива char - это MSB факториала. Когда цикл повторяется, символы добавляются в правой части массива. Переменная 'c' отслеживает перенос.
Недостатки использования массива - это остатки неиспользуемых байтов. Кроме того, вы не можете зарезервировать пространство для массива. Кроме того, массивы имеют тенденцию работать медленно.
Вы можете проверить мою программу на ideone: http://ideone.com/K410n7
Я считаю, что мое решение все еще можно оптимизировать. Пожалуйста, предложите как.
include<stdio.h>
char res[200000];
inline int fact(int n)
{
int i,j;
register int m,c;
m=1;
res[0]='1';
for(i=2;i<=n;i++)
{
c=0;
for(j=0; j< m; j++){
c =((res[j]-48)*i)+c;
res[j]=(c%10)+48;
c=c/10;
}
while(c>0){
res[m]=(c%10)+48;
c=c/10;
m++;
}
}
return m;
}
int main() {
int n,i,d;
scanf("%d",&n);
d=fact(n);
for(i=d-1;i>=0;i--)
printf("%c",res[i]);
return 0;
}
Класс BigInteger решит вашу проблему, а реализация C выше дает вам представление о том, как будет реализован BigInt, за исключением того, что код оптимизирован для скорости и предназначен только для вычисления факториала.
#include <iostream>
using namespace std;
int main ()
{
int i,n,p=1;
cout<<"Enter a number: ";
cin>>n;
cout<<endl;
for (i=1;i<=n; i++)
{
cout<<i<<" X ";
p=p*i;
}
cout<<endl<<endl<<p<<" factorial of "<<n;
return 0;
}
Код показан ниже:
#include<bits/stdc++.h>
using namespace std;
#define MAX 5000
void factorial(int n)
{
int carry , res_size = 1, res[MAX];
res[0] = 1;
for(int x=2; x<=n; x++)
{
carry = 0;
for(int i=0; i<res_size; i++)
{
int prod = res[i]*x + carry;
res[i] = prod % 10;
carry = prod/10;
}
while (carry)
{
res[res_size++] = carry%10;
carry = carry/10;
}
}
for(int i=res_size-1; i >= 0; i--)
{
cout<<res[i];
}
}
int main()
{
int n;
cin>>n;
factorial(n);
cout<<endl;
return 0;
}
Это на самом деле довольно легко. Вот два способа. Один является точным, а другой является приближенным. Для точных цифр любое число свыше 10000 будет рассчитываться за несколько секунд. Приблизительно это займет микросекунды, пока вы не попадете в миллионы. Это приближение Стерлинга, если кому-то интересно.
Факториал 10 000 000 - это приблизительно 1.2024234127436e+65657059 Это заняло 5,9 секунды. Нахождение точной суммы заняло бы 34 дня.
<?php
$test= 3579;
echo 'Factorial of '.$test.'<br><br>';
$tm= microtime( true);
echo 'Exact '.( $f= factorialexact( $test)).' e+'.(strlen( $f)-1).' missing decimal place after first digit<br>';
echo ( microtime( true) - $tm). ' seconds<br><br>';
$tm= microtime( true);
echo 'Aprox '.factorialapprox( $test).'<br>';
echo ( microtime( true) - $tm). ' seconds<br><br>';
function factorialexact( $n){
$f= '1';
for ( $i=$n; $i>1; $i--){
$f= JL_bcmul( $f, (''.$i));
}
return $f;
}
function factorialapprox( $n){
// Stirling's factorial approximation
// aprox factorial n = sqrt( 2 * pi * n) * n^n / e^n
// store in t the easy part, calc the first term easily
$t= sqrt( 2 * 3.14159265358979 * $n);
// things get tough from here because for large n
// n^n can blow away floating point pachages
// declare exponent of the number
$e= 0;
// the remaining terms are n^n / e^n
// both n and e (natural log) are raised to the same power
// that is n, just negative of each other
for ( $i=0; $i<$n; $i++){
// loop to
// mulitply by n and divide by e for each iteration
$t= $t * $n / 2.71828182845904;
// exponents are going to get away from us
// so reduce or increase t
while ( $t>1000){
$t= $t/1000;
$e= $e+3;
}
while ( $t<0.001){
$t= $t*1000;
$e= $e-3;
}
}
// garentee the base number is between 1 and 10
while ( $t>=10){
$t= $t/10;
$e= $e+1;
}
while ( $t<1){
$t= $t*10;
$e= $e-1;
}
// return at a floating string.
// do not use parseFloat() or floatval()
// $v= explode( 'e', $result); $floatvalue= $v[0] * pow( 10, $v[1]);
// won't work either. $v[1] is way too large
// the exponent can easily be in the tens of thousands
$p= '-';
if ( $e>=0){ $p= '+'; }
return $t.'e'.$p.$e;
}
function JL_bcmul( $a, $b){
if ( function_exists( 'bcmul')){
return bcmul( ( ''.$a), (''.$b));
}
$s= array();
for ($i=0; $i < count( $a) + count( $b); $i++){ $s[$i]= '0'; }
$t= 0;
for ($i=0; $i < strlen( $b); $i++){
for ($j=0; $j < strlen( $a); $j++){
$t= $s[$i+$j] + intval( $a[strlen( $a) - $j - 1]) * intval( $b[ strlen( $b) - $i - 1]);
$s[$i+$j]= $t % 10;
$s[$i+$j+1]= $s[$i+$j+1] + floor( $t / 10);
}
}
$s= array_reverse( $s);
return trim( trim(( implode( '', $s).'_'), '0'), '_');
}
#include<stdio.h>
#include<string.h>
char f[10000];
char factorial[1010][10000];
void multiply(int k){
int ci,sum,i;
int len = strlen(f);
ci=0;
i=0;
while(i<len){
sum=ci+(f[i] - '0') * k;
f[i] = (sum % 10) + '0';
i++;
ci = sum/10;
}
while(ci>0){
f[i++] = (ci%10) + '0';
ci/=10;
}
f[i]='\0';
for(int j=0;j<i;j++)factorial[k][j]=f[j];
factorial[k][i]='\0';
}
void fac(){
int k;
strcpy(f,"1");
for(k=2;k<=1000;k++)multiply(k);
}
void print(int n){
int i;
int len = strlen(factorial[n]);
printf("%d!\n",n);
for(i=len-1;i>=0;i--){
printf("%c",factorial[n][i]);
}
printf("\n");
}
int main()
{
int n;
factorial[0][0]='1';
factorial[1][0]='1';
fac();
while(scanf("%d",&n)==1){
print(n);
}
return 0;
}
Поскольку все голосовали за Шриватсан, у меня просто есть сомнения, связанные с этой проблемой. Вам нужно хранить все цифры? Если да, то решение Шриватсана в порядке. Если нет, то почему бы просто не отобразить числа, когда вы вычисляете факториал? Я неправильно форматирую вывод, но это может послужить цели.
int factorial(int num)
{
if (num <= 0)
return 1;
else
{
std::cout << num << std::endl;
return num * factorial(num - 1);
}
}
ОБНОВЛЕНИЕ Для всех downvoters, хотя это 5-летний пост, и выход для factorial(3);
3
2
1
6 // this is the result of the factorial and the digits above are the ones all the digits in the calculation.
Я думал, что это то, что спросил.