您的第一个明显问题当然是您应该打印 Pascal(i,j)。你的第二个更微妙：
递归
帕斯卡三角形的全部意义在于它提供了一种计算二项式系数的方法，而无需计算阶乘。
问题是阶乘增长得非常快，而且像 Pascal(1,120) = 120!/(1!*119!} 这样的系数只等于 120，但它的分母和分母都在 10^198 的数量级上，这不可能以任何机器整数类型存储。
查看维基百科上的帕斯卡三角。重点是递归关系：
Pascal( r, n ) = Pascal( r-1, n-1 ) + Pascal( r, n-1 )
这是一个使用它的简单解决方案（这只打印 r,n 帕斯卡数）：
#include <iostream>
#include <sstream>
int pascal( int r, int n ) {
if( n == 0 )
return 1;
if( r == 0 || r == n )
return 1;
return pascal( r - 1, n - 1 ) + pascal( r, n - 1 );
}
int main( int argc, char *argv[] ) {
if( argc != 3 ) {
std::cout << "Expected exactly 3 arguments." << std::endl;
return -1;
}
int r, n;
std::stringstream ss;
ss << argv[1] << ' ' << argv[2];
ss >> r >> n;
if( ss.bad() || r < 0 || n < 0 || r > n ) {
std::cout << "Invalid argument values." << std::endl;
return -2;
}
std::cout << pascal( r, n ) << std::endl;
return 0;
}
记忆
这种方法还有第三个甚至更微妙的问题，它的复杂性比它需要的要糟糕得多。考虑计算 Pascal(3,6)：
Pascal(3,6) =
= Pascal(2,5) + Pascal(3,5) =
= (Pascal(1,4)+Pascal(2,4)) + (Pascal(2,4)+Pascal(3,4)) = ...
在最后一行中，您会注意到 Pascal(2,4) 出现两次，这意味着您的代码将计算两次。此外，Pascal(3, 5) 实际上等于 Pascal(2,5)。所以你可以计算 Pascal(2,5) 两次，这意味着计算 Pascal(2,4) 四次。这意味着随着 r 和 n 变大，程序将非常缓慢。我们想计算每个 Pascal(i,j) 一次，然后保存它的值以供其他调用使用。为此，一种简单的方法是使用将 (r,n) 对映射到 Pascal(r,n) 值的映射：std::map< std::pair, int >。这种方法称为记忆。此外，将 int 更改为 long long 以获得大数，您将获得以下算法：
#include <iostream>
#include <sstream>
#include <map>
typedef long long Integer;
typedef std::map< std::pair< Integer, Integer >, Integer > MemoMap;
typedef MemoMap::iterator MemoIter;
MemoMap memo;
Integer pascal( Integer r, Integer n ) {
// make sure r <= n/2 using the fact that pascal(r,n)==pascal(n-r,n)
if( r > n / 2LL )
r = n - r;
// base cases
if( n == 0LL || r == 0LL )
return 1LL;
// search our map for a precalculated value of pascal(r,n)
MemoIter miter = memo.find( std::make_pair( r, n ) );
// if it exists return the precalculated value
if( miter != memo.end() )
return miter->second;
// otherwise run our function as before
Integer result = pascal( r - 1LL, n - 1LL ) + pascal( r, n - 1LL );
// save the value and return it
memo.insert( std::make_pair( std::make_pair( r, n ), result ) );
return result;
}
int main( int argc, char *argv[] ) {
if( argc != 3 ) {
std::cout << "Expected exactly 3 arguments." << std::endl;
return -1;
}
Integer r, n;
std::stringstream ss;
ss << argv[ 1 ] << ' ' << argv[ 2 ];
ss >> r >> n;
if( ss.bad() || r < 0LL || n < 0LL || r > n ) {
std::cout << "Invalid argument values." << std::endl;
return -2;
}
std::cout << pascal( r, n ) << std::endl;
return 0;
}
以前，Pascal(5,100) 永远不会终止。现在它在我的电脑上立即完成。将此代码集成到您的代码中，您将成为一只快乐的熊猫。
自下而上
记忆是自上而下的动态编程，即您首先想到最难的问题，然后将其划分为更简单的重叠问题，同时保存结果。自下而上的解决方案将从帕斯卡三角形的第一行开始并继续计算后续行 - 这在速度和内存方面都更有效（仅存储两个数组）。然而，自上而下的方法更容易实现（您不必考虑需要什么值，只需保存所有内容），它允许您在独立的 pascal() 调用之间保存中间结果。在您的情况下，由于您试图通过多次独立调用 pascal 来打印 Pascal 的三角形，因此这是合适的方法。如果您同时打印和计算，自下而上是迄今为止最有效的方法：
#include <iostream>
#include <sstream>
#include <vector>
typedef long long Integer;
void print_pascal( Integer maxn ) {
std::vector< Integer > prevRow, currentRow;
prevRow.resize( maxn + 1 );
currentRow.resize( maxn + 1);
prevRow[ 0 ] = 1;
// print first row.
std::cout << 1 << std::endl;
for( Integer currentN = 1 ; currentN <= maxn ; ++ currentN ) {
// compute & print current row
currentRow[ 0 ] = currentRow[ currentN ] = 1;
std::cout << 1;
for( Integer r = 1 ; r < currentN ; ++ r ) {
currentRow[ r ] = prevRow[ r - 1 ] + prevRow[ r ];
std::cout << ' ' << currentRow[ r ];
}
std::cout << ' ' << 1 << std::endl;
// constant time because swap() only swaps internal ptrs.
currentRow.swap( prevRow );
}
}
int main( int argc, char *argv[] ) {
if( argc != 2 ) {
std::cout << "Expected exactly 1 argument." << std::endl;
return -1;
}
Integer maxn;
std::stringstream ss;
ss << argv[ 1 ]; ss >> maxn;
if( ss.bad() || maxn < 0LL ) {
std::cout << "Invalid argument values." << std::endl;
return -2;
}
print_pascal( maxn );
return 0;
}