帕斯卡三角形失败超过第 14 行

Question

我必须编写一个程序，为计算机科学类输出Pascal三角形，并且输出的所有内容都是正确的，直到它通过第14行，在那里它开始输出奇数无理数。这是我的代码

#include <iostream>
#include "myFunctions.h"

using namespace std;
int main() {
int rows;
cout << "Please Enter The Number of Rows: ";
cin >> rows;
cout << rows << endl;
for (int i = 0; i < rows; i++) {
for (int j = 1; j < (rows - i + 1); j++) {
cout << " ";
}
for (int k = 0; k <= i; k++) {
if (k == 0) {
cout << "1" << " ";
} else {
cout << combination(i, k) << " ";
}
}
cout << "n";
}
return 0;
}

这是我的函数文件：

#ifndef MYFUNCTIONS_CPP_INCLUDED
#define MYFUNCTIONS_CPP_INCLUDED
#include "myFunctions.h"

double factorial (int n) {
assert(n >= 0);
int v = 1;
while (n > 0) {
v *= n;
n--;
}
return v;
}
double combination (int a, int b) {
return (factorial(a) / (factorial(a - b) * factorial(b)));
}

#endif // MYFUNCTIONS_CPP_INCLUDED

最后，这是我的头文件。

#ifndef MYFUNCTIONS_H_INCLUDED
#define MYFUNCTIONS_H_INCLUDED
#include <iostream>
#include <cassert>

//*******************************************************
// description: finds factorial of value                *
// return: double                                       *
// precondition: that the value is valid and an integer *
// postcondition: returns the factorial of value        *
//*******************************************************
double factorial( int n );

//********************************************************
// description: finds combination of value               *
// return: double                                        *
// precondition: both values are integers and valid      *
// postcondition: returns the  combination of two values *
//********************************************************
double combination( int a, int b );

#endif // MYFUNCTIONS_H_INCLUDED

我假设我对函数中的方程做得不正确，或者当它达到14时，主要发生了一些特定的事情。感谢您的帮助。

Answer 1

发生了什么

C++中的int具有最大大小。正如评论中提到的，这取决于您的平台，但为了这个问题，我假设它是2^31-1，它对应于一个32位有符号整数，也是我最常见的。

当你谈到阶乘时，问题就来了。它们长得很快。14=87178291200，这比32位CCD_。对于任意n，没有可行的方法将整个阶乘保持在内存中！因为它们可以变大。

这并不是说你的代码被破坏了，它只是与计算的物理边界背道而驰。

我们该怎么解决

首先，你可以消去阶乘。基本上，由于我们可以保证a>b、 我们知道那是一个/b就是把a和b之间的数字相乘。我们可以用循环来做。那么这只是一个除以(a-b(的问题！，我们已经知道该怎么做了。这看起来像

int combination(int a, int b)
{
int tmp = 1;
for(int ii = b;ii<=a;ii++)
tmp*=ii;
tmp /= factorial(b);
return tmp;
}

更有效的是，我们可以切换到不同的算法。维基百科建议对帕斯卡尔三角形使用迭代方法。也就是说，每个元素都可以从上面一行的两个元素中计算出来。正如@Damien在评论中提到的，如果你正在寻找第n行的第k个元素，那么你可以通过来计算

int Combination(int n,int k)
{
if (k == 0 or k>n or n <= 1)
return 1;
return Combination(n-1,k) + Combination(n-1,k-1);
}