c++ - 帕斯卡的三角形实现

Question

我正在尝试为帕斯卡三角形编写程序，计算 nth 行中的 rth 值的公式是 n!/r!(n-r) !

我一直想像这样实现它:

          #include <iostream>     // std::cout, std::endl
          #include <iomanip>      // std::setw
          int Pascal(int ,int );
          int Factorial( int);
          int main () 
          {
           int n=0;//Number of rows in the triangle
           for(int i=12;i>0;i--)
            {
              std::cout << std::setw(i)<<std::endl;
              for (int j=1;j<12-i;j++)
               {
                int r=0; //rth element initialized for each row
                int P= Pascal(r,n);
                std::cout << P ;
                std::cout <<std::setw(2);
                r=r+1;
               }

              n=n+1;

           }
               std::cout<<std::endl;
                   return 0;
           }
           int Pascal(int r,int n)
           {
               int d = n-r; ///Difference of n with r
               int f1; ///factorial of n
               int f2; ///factorial of r
               int f3; ///factorial of (n-r)

               f1=Factorial(n);
               f2=Factorial(r);
               f3=Factorial(d);
               return f1/(f2*f3);

           }
           int Factorial( int begin )
           {
                   int F;
                   if ( begin == 0 )
                   {
                    return 1; 
                   }
                   else
                   {
                     F= begin*Factorial(begin-1);
                   }
              return F;         
             }

但不知何故我得到了这个输出:

                   1
                  1 1
                 1 1 1
                1 1 1 1
               1 1 1 1 1
              1 1 1 1 1 1
             1 1 1 1 1 1 1
            1 1 1 1 1 1 1 1
           1 1 1 1 1 1 1 1 1
          1 1 1 1 1 1 1 1 1 112

有人可以指导我哪里出错了吗？

Answer 1

您的第一个明显问题当然是您应该打印 Pascal(i,j)。你的第二个更微妙:

递归

帕斯卡三角的全部意义在于它提供了一种无需计算阶乘即可计算二项式系数的方法。

问题是阶乘增长得非常快，像 Pascal(1,120) = 120!/(1!*119!} 这样的系数只等于 120，但它的分母和分母大约是 10^198它不能存储在任何机器整数类型中。

在 Wikipedia 上查看帕斯卡三角形.重点是递归关系:

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) 永远不会终止。现在它在我的电脑上立即完成。将此代码集成到您的代码中，您将成为一只快乐的 Pandas 。

自下而上

记忆化是自上而下的动态规划，即您首先想到最难的问题，然后将其分解为更简单、重叠的问题，同时保存结果。自下而上的解决方案将从 Pascal 三角形的第一行开始并继续计算后续行 - 这在速度和内存方面都更有效(仅存储两个数组)。然而，自上而下的方法更容易实现(您不必考虑需要什么值，只需保存所有内容)，并且它允许您保存独立的 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;
}