C大调帕斯卡三角形

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

任务是编写一个程序来计算给定位置的值帕斯卡三角形。计算它的公式写为元素=行！ / ( 位置！* (行 - 位置)! )

我编写了一个简单的控制台程序，似乎工作正常，直到我开始测试它large数字。

当在第 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;
}

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

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

例如，假设你有row=35 and position=10。那么计算就是

element = 35! / (10! * 25!)

which is

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位进行计算。