Вычислите факториал произвольно большого количества, показав все цифры
Меня недавно попросили, в интервью, описать метод для вычисления факториала любого произвольно большого количества; метод, в котором мы получаем все цифры ответа.
Я искал различные места и спросил на нескольких форумах. Но я хотел бы знать, существует ли какой-либо способ выполнить это, не пользуясь библиотеками как GMP.
Спасибо.
5 ответов
GNU Multiprecision Library - хорошая библиотека! Но так как вы говорите, что использование внешних библиотек запрещено, то я считаю, что это возможно только путем взятия массива 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' - это всего лишь целочисленный массив, а факториал - это простая функция, которая умножает заданное число на 'большое число'.
Надеюсь, это решит ваш вопрос...
Хорошее решение от Шриватсана Айера и мое предложение :
Его все же можно сделать более эффективным с точки зрения экономии памяти, используя беззнаковый char-массив, а не массив int для хранения цифр. Для лучшей оптимизации памяти, мы также можем использовать один байт для представления 2-х цифр. Так как для представления любой цифры от 0 до 9 достаточно 4 бит. Таким образом, мы можем упаковывать две цифры в один байт, используя битовые операции. Потребуется 12.5% необходимой памяти для массива int.
Класс BigInteger решит вашу проблему, а приведенная выше реализация на языке C даст вам представление о том, как будет реализован BigInt, за исключением того, что код оптимизирован под скорость и приспособлен только к вычислениям факториала.
.Ну, вы должны написать свои собственные математические процедуры с использованием массивов. Это очень просто для сложения, умножение немного сложнее, но все же возможно.
EDIT: Хотел поместить пример, но пример Шриватсана Айера просто отличный.
.Поскольку все проголосовали за Шриватсана, у меня просто есть сомнения, связанные с этой проблемой. Вам нужно хранить все цифры? Если да, то решение Шриватсана в порядке. Если нет, то почему бы просто не вывести цифры на экран, как вы вычисляете факториал? Я не форматирую вывод правильно, но это может послужить цели.
int factorial(int num)
{
if (num <= 0)
return 1;
else
{
std::cout << num << std::endl;
return num * factorial(num - 1);
}
}
UPDATE
Для всех нижних знаков, хотя это сообщение 5-летней давности, и вывод для факториала(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.
Я думал, что это то, о чем я спрашивал.
.