问题描述
我是计算机工程专业的学生，下学期我将开始C语言课程.因此，为了有所准备，我开始自己学习C，偶然发现了一个有趣的任务，旨在让我对它一见钟情，而不是非常高级的水平.
I'm a computer engineering student and next semester I am going to start C course. So in order to prepare myself a bit, I have started learning C by myself and stumbled across an interesting task, designed for, how it seemed to me at first sight, not a very advanced level.
任务是编写一个程序来计算帕斯卡三角形"中给定位置的值.给出的计算公式写为 element = row！/(position！*(row-position)！)
The task is to write a program to compute the value of a given position in Pascal's Triangle. And the formula given to compute it is written as element = row! / ( position! * (row - position)! )
我编写了一个似乎可以正常工作的简单控制台程序，直到使用大数字进行测试为止.
I've written a simple console program that seems to work okay, until I get to testing it with large numbers.
尝试使用第16行和第3位的程序时，它会将值计算为0，尽管很显然不可能有这样的值(实际上，它应该将值计算为560)，但是该三角形的所有单元格应该是整数并且大于1.
When trying this program with row 16 and position 3, it calculates the value as 0, although it's obvious that there can't be such a value (in fact it should compute the value as 560), all cells of this triangle are supposed to be integers and be greater than one.
我想我在存储和处理大量数字时遇到问题.阶乘函数似乎还可以，并且我使用的公式一直有效，直到我尝试大数为止.
I suppose I'm experiencing a problem with storing and processing large numbers. The factorial function seems to work okay, and the formula I used works until I get to trying large numbers
到目前为止，这里找到了最好的解决方案-如何做您是否使用类型为uint64_t的inttypes.h库打印了一个无符号的long long int(无符号的long long int的格式说明符)?
So far the best solution was found here - How do you printf an unsigned long long int(the format specifier for unsigned long long int)? using inttypes.h library with type uint64_t but it still doesn't give me the result I need.
#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;
}
推荐答案
框架获得确实很大非常快(向下滚动以查看列表).直到20!，即使是64位数字也只能使用.因此，在开始乘法之前，您必须做一些预处理.
Factorials get really big really fast (scroll down a little to see the list). Even a 64-bit number is only good up to 20!. So you have to do a little preprocessing before you start multiplying.
通常的想法是分解分子和分母，并消除所有公因子.由于Pascal的Triangle的结果始终是整数，因此可以保证在除去所有公因子后，分母将为1.
The general idea is to factor the numerator and the denominator, and remove all of the common factors. Since the results of Pascal's Triangle are always integers, you are guaranteed that the denominator will be 1 after all common factors have been removed.
例如，假设您有row=35和position=10.那么计算是
For example let's say you have row=35 and position=10. Then the calculation is
element = 35! / 10! * 25!
是
35 * 34 * 33 * ... * 26 * 25 * 24 * ... * 3 * 2 * 1
---------------------------------------------------
10! * 25 * 24 * ... * 3 * 2 * 1
因此，第一个简化是分母中较大的阶乘会抵消分子的所有较小项.留下
So the first simplification is that the larger factorial in the denominator cancels all of the smaller terms of the numerator. Which leaves
35 * 34 * 33 * ... * 26
-----------------------
10 * 9 * 8 * ... * 1
现在，我们需要删除分子和分母中剩余的公因子.这有助于将分子的所有数字放入数组中.然后，对于分母中的每个数字，计算最大公约数(gcd)并将分子和分母除以gcd.
Now we need to remove the remaining common factors in the numerator and denominator. It helps to put all the number of the numerator in an array. Then, for each number in the denominator, compute the greatest common divisor (gcd) and divide the numerator and denominator by the gcd.
以下代码演示了该技术.
The following code demonstrates the technique.
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;
}
}
这是代码逐步执行的操作
Here's what the code does step by step
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
说完所有内容后，数组最终显示为
When all is said and done the array ends up as
array[10] = { 1, 17, 11, 1, 31, 1, 29, 14, 3, 26 }
将这些数字相乘，答案为183579396，整个计算可以使用32位整数进行.通常，只要答案适合32位，就可以使用32位进行计算.
Multiply those numbers together and the answer is 183579396, and the entire calculation could be performed using 32-bit ints. In general, as long as the answer fits into 32-bits, the calculations can be done with 32-bits.
这篇关于帕斯卡三角形C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！