pascal的Triangle实现 [英] pascal's Triangle implementation

问题描述

我正在尝试为帕斯卡的三角形编写程序，该公式用于计算 nth 行中的 rth 值是 n！/ r！（nr）！

I am trying to make a program for pascal's triangle,the formaula to calculate the rth value in nth row is n!/r!(n-r)!

我一直想像这样实现它：

I've been tring to implement it like this:

          #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;         
             }

但我不知何故获得了以下输出：

but somehow I am getting this output:

                   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

有人可以指导我我要去哪里了吗？

Could someone guide me where am I going wrong?

推荐答案

您的第一个显而易见的问题当然是您应该打印Pascal（i，j）。您的第二个更微妙：

Your first, obvious problem is of course that you should be printing Pascal(i,j). Your second is more subtle:

Pascal三角形的全部要点是它提供了一种

The whole point of Pascal's Triangle is that it gives a way of computing binomial coefficients without needing to compute the factorials.

问题是阶乘确实增长很快，并且诸如Pascal（1,120）= 120！/（1！* 119）的系数！}仅等于120，但是其分母和分母约为10 ^ 198，无法存储在任何机器整数类型中。

The problem is factorials grow really quickly and a coefficient such as Pascal(1,120) = 120!/(1!*119!}, is equal only to 120, but its nominator and denominator are on the order of 10^198 which could not be stored in any machine integer type.

Wikipedia 上的Pascal三角形。整点是递归关系：

Check out Pascal's Triangle on Wikipedia. The whole point is the recursive relation:

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

这里有一个简单的解决方案（仅打印r，n帕斯卡数）：

Here's a simple solution making use of that (this only prints the r,n pascal number):

#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）：

Memoization

There is a third and even more subtle problem with this method, its complexity is much worse than it needs to be. Think about computing 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>。此方法称为记忆。同样，将整数更改为大整数的long long，您将获得以下算法：

In that last line you'll notice Pascal(2,4) appears twice which means your code will compute it twice. Futhermore Pascal( 3, 5 ) is actually equal to Pascal(2,5). So your could is computing Pascal(2,5) twice, which means computing Pascal(2,4) four times. This means as r and n grow large the program will be very slow. We would like to compute each Pascal(i,j) a single time and then save its value to be used by other calls. To do this, a simple way is to use a map which maps (r,n) pairs to Pascal(r,n) values: std::map< std::pair, int >. This method is called memoization. Also, changing ints to long long for big numbers, you get the following algorithm:

#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）永远不会终止。现在，它可以立即在我的计算机上完成。将此代码集成到您的代码中，您将成为快乐的熊猫。

Before, Pascal(5,100) would never terminate. Now it finishes instantly on my computer. Integrate this code into yours and you'll be a happy panda.

记忆力是最高的向下动态编程，即您首先想到最困难的问题，然后将其划分为更简单的重叠问题，同时一路保存结果。自下而上的解决方案将从Pascal Triangle的第一行开始，并继续计算随后的行-这在速度和内存（仅存储两个数组）方面都更加有效。
自上而下的方法更易于实现（您不必考虑只需要保存所有内容就需要什么值），并且它允许您保存独立的pascal（）调用之间的中间结果。对于您而言，由于您要尝试通过多次独立调用pascal来打印Pascal的Triangle，因此这是一种合适的方法。如果您同时打印和计算，则自下而上是迄今为止最有效的方法：

Memoization is top-down dynamic programming i.e. you first think of the hardest problem and then divide it into simpler, overlapping problems while saving the results along the way. A bottom up solution would start with the first row of the Pascal Triangle and keep computing following rows - this is more efficient, both in speed and memory (storing only two arrays). The top-down method however is easier to implement (you don't have to think about what values you're going to need you just save everything) and it allows you to save intermediate results between independent pascal() calls. In your case, since you're trying to print Pascal's Triangle by calling pascal independently many times, this is the appropriate method. If you print and compute at the same time, bottom up is by far the most efficient way of doing it:

#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;
}

这篇关于pascal的Triangle实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！