又来求教了，这次是一个图形的算法问题！题目如下 - 编程论坛

#2

w5277050902012-12-09 18:14

算法才是编程的精华之所在啊。。。
不懂之好帮顶了

#3

rjsp2012-12-10 09:23

真变态呀，一张图片不直接贴出来，却先贴到M$ office中，真是脱裤子放屁，你自己不觉得麻烦，看得人也会觉得麻烦呀

“只能往上、往右、往右上”
--- 可以得出，到(a,b)的走法数 = 到(a-1,b)的走法数 + 到(a-1,b-1)的走法数 + 到(a,b-1)的走法数
因此，递归算法就是

程序代码：

unsigned f( int a, int b )
{
    if( a <  b )
        return 0;

    if( b == 0 )
        return 1;

    return f(a-1,b) + f(a-1,b-1) + f(a,b-1);
}

#include <iostream>

int main()
{
    std::cout << f(2,2) << std::endl;

    return 0;
}

多么简单呀

但一般而言，只有SB才用递归算法（只是一般而言，不代表全部），因此将递归算法反过来，一层层的累加

程序代码：

typedef unsigned int U32T;
U32T f( unsigned n )
{
    U32T* p_ = new U32T[n+2];
    p_[0] = 0;
    U32T* p = p_ + 1;
    for( U32T i=0; i<n+1; ++i )
        p[i] = 1;

    for( U32T i=1; i<=n; ++i )
    {
        for( U32T j=0; j<=n-i; ++j )
        {
            p[j] = p[j-1] + p[j] + p[j+1];
        }
    }

    U32T r = p[0];
    delete[] p_;
    return r;
}

#include <iostream>

int main()
{
    for( unsigned i=1; i<=15; ++i )
        std::cout << i << " = " << f(i) << std::endl;

    return 0;
}

输出为
1 = 2
2 = 6
3 = 22
4 = 90
5 = 394
6 = 1806
7 = 8558
8 = 41586
9 = 206098
10 = 1037718
11 = 5293446
12 = 27297738
13 = 142078746
14 = 745387038
15 = 3937603038

#4

mmmmmmmmmmmm2012-12-10 09:31

顶版主学习一下