int limit в программе перестановок (C++)

Question

Я написал простую программу на C++, которая вычисляет перестановки/факториалы в 2 разных методах. Проблема возникает, когда я пытаюсь использовать более длинный метод (p1) с 20 и 2. Предоставлено «20!» ОГРОМНОЕ число. Есть ли предел с целыми числами при вычислении факториала с использованием метода рекурсии?

#include <iostream> 
using namespace std; 

int p1(int n, int r); 
int p2(int n, int r); 
int factorial(int x); 

int main() 
{ 
    cout << p1(10, 8) << endl; 
    cout << p2(10, 8) << endl; 
    cout << p1(4, 3) << endl; 
    cout << p2(4, 3) << endl; 
    cout << p1(20, 2) << endl; // THE NUMBER PRINTS INCORRECTLY HERE 
    cout << p2(20, 2) << endl; 

    system("PAUSE"); 
    return EXIT_SUCCESS; 
} 

int p1(int n, int r) // long version, recursively calls factorial 
{ 
    return (factorial(n)/factorial(n - r)); 
} 

int factorial(int x) 
{ 
    if (x == 0) 
     return 1; 
    else if (x > 0) 
     return (x * factorial(x - 1)); 
} 

int p2(int n, int r) // shortcut, does arithmetic in for loop 
{ 
    int answer = n; 
    for (int i = 1; i < r; i++) 
    { 
     answer *= n - 1; 
     n--; 
    } 
    return answer; 
} 

Answer 1

20! является 2.4*10^18

Вы можете проверить ссылку на limits.h, чтобы увидеть, что эти пределы.

считают, что 2^32 является 4.2*10^9. long int обычно представляет собой 32-битное значение.

считают, что 2^64 - 1.8*10^19, поэтому 64-разрядное целое число проведет вас через 20!, но не более. unsigned long long int должен сделать это для вас тогда.

unsigned long long int p1(int n, int r) 
{ 
    return (factorial(n)/factorial(n - r)); 
} 

unsigned long long int factorial(unsigned long long int x) 
{ 
    if (x == 0) 
     return 1; 
    else if (x > 0) 
     return (x * factorial(x - 1)); 
} 

unsigned long long int p2(int n, int r) 
{ 
    unsigned long long int answer = n; 
    for (int i = 1; i < r; i++) 
    { 
     answer *= n - 1; 
     n--; 
    } 
    return answer; 
} 

Если вы имеете в этом назначении, рассмотреть вопрос об использовании float или double, если вам не требуется абсолютная точность, или просто нужно, чтобы добраться до 20 и сделать. Если вам нужна абсолютная точность и выполнить факториал выше 20, вам нужно будет разработать способ хранения большего целого числа в байтовом массиве, таком как состояния @ z32a7ul.

Также вы можете сохранить операцию, выполнив answer *= --n; до предварительного декремента n, прежде чем использовать его.

Answer 2

20! превышает целочисленный диапазон. Ваша функция быстрого доступа не превышает просто потому, что вы не рассчитать весь факультет, но 20 * 19

Answer 3

Если вам это действительно нужно, вы можете создать класс, который содержит массив байтов переменной длины и определить на нем операторы. В этом случае только доступная память и ваше устройство ограничивают размер номеров. Я думаю, что Scheme (диалект LIPS) делает что-то подобное.