帕斯卡的三角实施

Question

我正在尝试为pascal的三角形制作一个程序,用于计算行中rth值的格式nthn!/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三角形的全部意义在于它提供了一种计算二项式系数的方法,而无需计算因子.

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

在维基百科上查看Pascal的三角形.整点是递归关系:

Pascal( r, n ) = Pascal( r-1, n-1 ) + Pascal( r, n-1 )

这是一个使用它的简单解决方案(这只打印r,n pascal数字):

#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)出现两次,这意味着您的代码将计算两次.Futhermore 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>.这种方法称为memoization.此外,对于大数字,将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 Triangle的第一行开始,并继续计算以下行 - 这在速度和内存(仅存储两个数组)方面更有效.然而,自上而下的方法更容易实现(您不必考虑您只需要保存所有内容所需的值),并且它允许您在独立的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;
}