Pascal在C中的三角形
我是一名计算机工程专业的学生，下学期我将开始C课程。 所以为了让自己做好准备，我已经开始自己学习C并偶然发现了一个有趣的任务，专为我看来，一见钟情，而不是一个非常先进的水平。
任务是编写一个程序来计算Pascal三角形中给定位置的值。 并且计算它的公式被写为element = row！ /（位置！*（行 – 位置）！）
我写了一个简单的控制台程序似乎工作正常，直到我用大数字测试它。
当使用第16行和第3行尝试此程序时，它会将值计算为0，尽管很明显不存在这样的值（实际上它应该将值计算为560），此三角形的所有单元格都应该是是整数，大于一。
我想我在存储和处理大数字时遇到了问题。 阶乘函数似乎工作正常，我使用的公式一直有效，直到我尝试大数
到目前为止，这里找到了最好的解决方案 – 如何printf unsigned long long int（unsigned long long int的格式说明符）？ 使用类型为uint64_t的inttypes.h库但它仍然没有给我我需要的结果。
#include #include #include 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! 。 所以你必须在开始乘法之前做一些预处理。
一般的想法是分解分子和分母，并删除所有的共同因素。 由于Pascal三角形的结果总是整数，所以在保留所有公因子被删除后，分母将为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
完成所有操作后，arrays结束为
array[10] = { 1, 17, 11, 1, 31, 1, 29, 14, 3, 26 }
将这些数字相乘，答案为183579396 ，整个计算可以使用32位整数执行。 通常，只要答案适合32位，就可以用32位完成计算。
（我的C生锈了，所以这可能不是很准确）
你的阶乘函数返回一个uint64_t，但它正在用常规的int进行计算。 如果您将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行更进一步。
在计算阶乘时，即使返回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; }
另外，考虑如何重新排列等式，以便不必计算非常大的中间值。 例如，你可以重新排列到这个：
element =（factorial（row）/ factorial（pos））/ factorial（row-pos）;
那么你就不会将两个因子相乘而得到一个非常大的数。
此外，当您计算阶乘（行）/阶乘（pos）时，您可以消除阶乘（行）和阶乘（pos）中的术语，因此您无需计算整个阶乘。
这将有效：
#include 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; }