3

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

任务是编写一个程序来计算帕斯卡三角中给定位置的值。计算它的公式写成element = row!/(位置!*(行 - 位置)!)

我编写了一个简单的控制台程序,它似乎可以正常工作,直到我开始对它进行大量测试。

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

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

到目前为止,在这里找到了最好的解决方案 -你如何 printf an 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;
}
4

4 回答 4

5

阶乘变得非常大非常快(向下滚动一点查看列表)。即使是 64 位数字也只能达到20!. 因此,在开始相乘之前,您必须进行一些预处理。

大体思路是将分子和分母因式分解,并去除所有公因式。由于帕斯卡三角的结果总是整数,因此可以保证在去除所​​有公因数后分母将为 1。

例如,假设您有row=35and 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 位进行计算。

于 2015-01-21T02:51:00.393 回答
3

(我的 C 生锈了,所以这可能不是很准确)

您的阶乘函数返回一个 uint64_t,但它使用常规整数进行计算。如果您将 f 和 i 更改为 uint64_t,我认为您将避免当前的整数溢出问题。

但是,您仍然会很快遇到溢出(uint64_t 将在 21 左右溢出!)。为避免这种情况,您可以使用该算法更聪明一些。使用 row=16 和 position=3,你需要 16!/(3!* 13!)。您可以取消大部分条款(16!/13!只是 14*15*16)并最终得到 14*15*16 / (1*2*3)。这将使您的程序比第 21 行更进一步。

于 2015-01-21T01:24:35.013 回答
1

当您计算阶乘时,即使您返回一个 64 位整数,如果您使用常规 int 变量进行中间计算,它也不会产生影响。改成这样:

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

另外,请考虑如何重新排列方程,以便不必计算非常大的中间值。例如,您可以重新排列为:

元素=(阶乘(行)/阶乘(位置))/阶乘(行-位置);

这样你就不会将两个阶乘相乘并得到一个非常大的数字。

此外,当您计算阶乘(行)/阶乘(位置)时,您可以消除阶乘(行)和阶乘(位置)中的项,因此您不需要计算整个阶乘。

于 2015-01-21T01:20:45.103 回答
0

这将起作用:

#include <stdio.h>

int main()
    {
    printf ("\n");
    int n = 10;
    int i;
    int j;
    int x[n];

    for (i = 0; i < n; i++)
         x[i] = 0;

    for (i = 1; i <= n; i++)
         {
         for (j = n - 1; j >= 1; j--)
              x[j] = x[j-1] + x[j];

         x[0] = 1;

         int s = n - i;

         for (j = 0; j < s; j++)
              printf ("  ");

         for (j = 0; j < n; j++)
              {
              if (x[j] != 0)
                  printf (" %3d", x[j]);
              }

        printf ("\n");
        }

    printf ("\n");
    return 0;
    }
于 2016-08-18T17:14:54.147 回答