C中的帕斯卡三角形

Question

我是一名计算机工程专业的学生，​​下学期我将开始 C 课程。因此，为了让自己做好准备，我开始自学 C 并偶然发现了一项有趣的任务，该任务旨在让我乍一看似乎不是一个非常高级的水平。

任务是编写一个程序来计算Pascal's Triangle 中给定位置的值。计算它的公式写为element = row! /（位置！*（行 - 位置）！）

我已经编写了一个简单的控制台程序，它似乎可以正常工作，直到我开始使用大量数字对其进行测试。

当用第 16 行和位置 3 尝试这个程序时，它计算出的值为 0，虽然很明显不可能有这样的值（实际上它应该计算值为 560），但这个三角形的所有单元格都应该是整数并且大于一。

我想我在存储和处理大数时遇到了问题。阶乘函数似乎可以正常工作，并且我使用的公式可以正常工作，直到我开始尝试大数字

到目前为止，这里找到了最好的解决方案 -如何打印一个 unsigned long long int（unsigned long long int 的格式说明符）？ 使用类型为 uint64_t 的 inttypes.h 库，但它仍然没有给我我需要的结果。

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

void clear_input(void);
uint64_t factorial(int x);

int main()
{
    // Printing
    printf("This program computes the value of a given position in Pascal's Triangle.\n");
    printf("You will be asked for row and position of the value.\n");
    printf("Note that the rows and positions starts from 0.\n");
    printf("\n");
    printf("     1          * 0 \n");
    printf("    1 1         * 1 \n");
    printf("   1 2 1        * 2 \n");
    printf("  1 3 3 1       * 3 \n");
    printf(" 1 4 6 4 1      * 4 \n");
    printf(" ****************   \n");
    printf(" 0 1 2 3 4          \n");
    printf("\n");

    // Initializing
    int row, pos;

    // Input Row
    printf("Enter the row: ");
    scanf("%d", &row);
    clear_input();

    // Input Position
    printf("Enter the position in the row: ");
    scanf("%d", &pos);
    clear_input();

    // Initializing
    uint64_t element, element_1, element_2, element_3, element_4;

    // Previously written as -> element = ( factorial(row) ) / ( factorial(pos) * factorial(row - pos) );
    // Doesn't fix the problem
    element_1 = factorial(row);
    element_2 = factorial(pos);
    element_3 = factorial(row - pos);
    element_4 = element_2 * element_3;

    element = element_1 / element_4;

    // Print result
    printf("\n");
    printf("%"PRIu64"\n", element_1);   // Temporary output
    printf("%"PRIu64"\n", element_2);   // Temporary output
    printf("%"PRIu64"\n", element_3);   // Temporary output
    printf("%"PRIu64"\n", element_4);   // Temporary output
    printf("\n");
    printf("The element is %"PRIu64"", element);
    printf("\n");

    return 0;
}

void clear_input(void)                                          // Temporary function to clean input from the keyboard
{
  while(getchar() != '\n');
}

uint64_t factorial(int x)                                       // Function to calculate factorial
{
    int f = 1, i = x;
    if (x == 0) {
        return 1;
    }
    while (i != 1) {
        f = f * i;
        i = i - 1;
    }
    return f;
}

Answer 1

因子变得非常大非常快（向下滚动一点以查看列表）。即使是 64 位数字也只能达到20!. 所以你必须在开始乘法之前做一些预处理。

一般的想法是对分子和分母进行因式分解，并去除所有公因数。由于帕斯卡三角形的结果始终是整数，因此可以保证在删除所有公因数后分母将为 1。

例如，假设您有row=35和position=10。然后计算是

element = 35! / 10! * 25!

这是

35 * 34 * 33 * ... * 26 * 25 * 24 * ... * 3 * 2 * 1
---------------------------------------------------
     10!                * 25 * 24 * ... * 3 * 2 * 1   

所以第一个简化是分母中较大的阶乘抵消了分子的所有较小项。哪个叶子

35 * 34 * 33 * ... * 26 
-----------------------
 10 * 9 * 8 * ... * 1     

现在我们需要去除分子和分母中剩余的公因数。它有助于将分子的所有数字放入数组中。然后，对于分母中的每个数字，计算最大公约数(gcd) 并将分子和分母除以 gcd。

以下代码演示了该技术。

array[10] = { 35, 34, 33, 32, 31, 30, 29, 28, 27, 26 };  

for ( d = 10; d >= 2; d-- )
{ 
    temp = d;
    for ( i = 0; i < 10 && temp > 1; i++ )
    {
        common = gcd( array[i], temp );
        array[i] /= common;
        temp /= common;
    }
}

下面是代码一步一步的作用

d=10   i=0   temp=10   array[0]=35  ==>  gcd(35,10)=5, so array[0]=35/5=7  and temp=10/5=2
d=10   i=1   temp=2    array[1]=34  ==>  gcd(34, 2)=2, so array[1]=34/2=17 and temp=2/2=1
inner loop breaks because temp==1
d=9    i=0   temp=9    array[0]=7   ==>  gcd(7,9)=1,  so nothing changes
d=9    i=1   temp=9    array[1]=17  ==>  gcd(17,9)=1, so nothing changes
d=9    i=2   temp=9    array[2]=33  ==>  gcd(33,9)=3, so array[2]=11 and temp=3
d=9    i=3                          ==>  gcd(32,3)=1
d=9    i=4                          ==>  gcd(31,3)=1
d=9    i=5   temp=3    array[5]=30  ==>  gcd(30,3)=3, so array[5]=10 and temp=1
inner loop breaks

当一切都说完并完成后，数组最终为

array[10] = { 1, 17, 11, 1, 31, 1, 29,  14, 3, 26 }

将这些数字相乘，答案是183579396，整个计算可以使用 32 位整数执行。一般来说，只要答案适合 32 位，就可以用 32 位进行计算。