算法设计中的台阶问题

daly88

其实就是把你程序的尾递归改成循环而已，本质是一样的。

ypxing

要是这样的话,就这个题目本身来说,
dp就没有什么优势了

原帖由 daly88 于 2007-8-24 11:28 发表
其实就是把你程序的尾递归改成循环而已，本质是一样的。

[ 本帖最后由 ypxing 于 2007-8-24 11:31 编辑 ]

ivhb

原帖由 daly88 于 2007-8-24 11:28 发表
其实就是把你程序的尾递归改成循环而已，本质是一样的。

这个尾递归改的？怎么个尾法？麻烦你给讲讲。
我知道的是这样
如果一个递归函数，递归的调用自己不止一次，就是个发散的序列。仅仅用一个循环是不可能的。因为你没有办法得到它的路径。

cjaizss

a(1)=1
a(2)=3
a(3)=4
n>3,
a(n)=a(n-1)+a(n-2)+a(n-3)

tyc611

原帖由 cjaizss 于 2007-8-24 13:05 发表
a(1)=1
a(2)=3
a(3)=4
n>3,
a(n)=a(n-1)+a(n-2)+a(n-3)

a(2)=2

fertiland

整数和数分解变形
#include<stdio.h>
#undef N
#define N 5
void  rd(int i,int *b, int  k){   
        int j = 0;
        int t = 0;
        for(j=i;j>=1;j--)      
                if(j<=3)               /*题目要求*/
                {      
                        b[k]=j;      
                        if(j==i)      
                        {
                                printf("%d=%d",N, b[1]);  
                                for(t=2;t<=k;t++)
                                        printf("+%d", b[t]);
                                printf("\n");
                        }   
                        else      
                                rd(i-j, b, k+1);     //继续分解的数是i-j,分解出第k+1个和数      
                }      
}  
int   main(int   argc,   char*   argv[])   
{   
        int b[N+1];
        b[0]=N;
        rd(N, b, 1);
        return   0;   
}

erduo100

daly88算法是对的 不过说得不是很清楚
问题的关键在于走上第n(n>=4)个台阶的最后一步.最后一步可能是走1个台阶,2个台阶或者3个台阶
对应停留在第n-1个台阶,第n-2个台阶,第n-3个台阶
三者是互斥的,故f(n)由三者对应的走法相加即可
走上第n-1个台阶有f(n-1)个上法,走上第n-2个台阶有f(n-2)个上法,走上第n-3个台阶有f(n-3)个上法
所以f(n)=f(n-1)+f(n-2)+(fn-3)

epegasus

让我想想起了这个帖子
http://bbs.chinaunix.net/viewthread.php?tid=779799

[ 本帖最后由 epegasus 于 2007-10-28 21:45 编辑 ]

halve

原帖由 ivhb 于 2007-8-24 12:55 发表

这个尾递归改的？怎么个尾法？麻烦你给讲讲。
我知道的是这样
如果一个递归函数，递归的调用自己不止一次，就是个发散的序列。仅仅用一个循环是不可能的。因为你没有办法得到它的路径。

这个问题的递归过程并不是无限发散的
假如有4层楼
第1步走(1,1)的效果跟(2) 的效果一样
那么(1,1)跟(2)之后可以分享同一个计算过程，如果利用这点可以避免很多重复的递归运算
这只是个大概，具体的可以去看下算法导论里面的动态规划那章，那个讲得明白