C 中的帕斯卡三角形
Pascal's Triangle in C
我是一名计算机工程专业的学生，下学期我将开始学习C课程。因此，为了让自己稍微做好准备，我开始自学 C 并偶然发现了一项有趣的任务，专为乍一看似乎不是很高级的水平而设计。
任务是编写一个程序来计算帕斯卡三角中给定位置的值。计算它的公式写成 element = row! /（位置！*（行-位置）！）
我已经编写了一个简单的控制台程序，在我开始使用 large 数字对其进行测试之前，它似乎工作正常。
当用第 16 行和位置 3 尝试这个程序时，它计算的值为 0，虽然很明显不可能有这样的值（实际上它应该计算为 560），所有单元格这个三角形应该是整数并且大于一。
我想我遇到了存储和处理大量数字的问题。阶乘函数似乎工作正常，我使用的公式一直有效，直到我开始尝试大数
到目前为止，这里找到了最好的解决方案 - How do you printf an unsigned long long int(the format specifier for 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 位整数，如果您使用常规 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;
}
另外，考虑一下如何重新排列方程式，这样就不必计算非常大的中间值。例如，您可以重新排列为：
元素=（阶乘（行）/阶乘（位置））/阶乘（行-位置）；
这样你就不会将两个阶乘相乘并得到一个非常大的数。
此外，当您计算阶乘(row) / 阶乘(pos) 时，您可以消除同时出现在阶乘(row) 和阶乘(pos) 中的项，因此您不需要计算整个阶乘。
（我的 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 行走得更远。
阶乘得到 really big really fast（稍微向下滚动以查看列表）。即使是 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
现在我们需要去掉分子和分母中剩下的公因数。它有助于将分子的所有数字放入数组中。然后，对于分母中的每个数字，计算 greatest common divisor (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位计算。
这会起作用：
#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;
}
我是一名计算机工程专业的学生，下学期我将开始学习C课程。因此，为了让自己稍微做好准备，我开始自学 C 并偶然发现了一项有趣的任务，专为乍一看似乎不是很高级的水平而设计。
任务是编写一个程序来计算帕斯卡三角中给定位置的值。计算它的公式写成 element = row! /（位置！*（行-位置）！）
我已经编写了一个简单的控制台程序，在我开始使用 large 数字对其进行测试之前，它似乎工作正常。
当用第 16 行和位置 3 尝试这个程序时，它计算的值为 0，虽然很明显不可能有这样的值（实际上它应该计算为 560），所有单元格这个三角形应该是整数并且大于一。
我想我遇到了存储和处理大量数字的问题。阶乘函数似乎工作正常，我使用的公式一直有效，直到我开始尝试大数
到目前为止，这里找到了最好的解决方案 - How do you printf an unsigned long long int(the format specifier for 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 位整数，如果您使用常规 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;
}
另外，考虑一下如何重新排列方程式，这样就不必计算非常大的中间值。例如，您可以重新排列为：
元素=（阶乘（行）/阶乘（位置））/阶乘（行-位置）；
这样你就不会将两个阶乘相乘并得到一个非常大的数。
此外，当您计算阶乘(row) / 阶乘(pos) 时，您可以消除同时出现在阶乘(row) 和阶乘(pos) 中的项，因此您不需要计算整个阶乘。
（我的 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 行走得更远。
阶乘得到 really big really fast（稍微向下滚动以查看列表）。即使是 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
现在我们需要去掉分子和分母中剩下的公因数。它有助于将分子的所有数字放入数组中。然后，对于分母中的每个数字，计算 greatest common divisor (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位计算。
这会起作用：
#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;
}