/* * remember the 100-steps ladder at the university of my graduation. * it's an unforgotable place. * these steps in hurry to another classroom, * sometimes one by one step, sometimes three into two steps and even one step. * nerver thoungh of the process thought the ladder. How may ways to pass * throught the amazing place. * what a pity! * today is the time to make up for these hurry-missing steps. * * 11/19/2012 14:11:40 * */
#include <stdio.h>#include <string.h>#define N 100
/* * result[i] 记录 i 步阶梯的走法数 * */unsigned long long result[N+1];
/* * n步阶梯，有三种走法： * 1、先是跨一步，剩下n-1步，设剩下n-1步，有f(n-1)中走法； * 2、是跨两步，剩下n-2步，设剩下n-2步，有f(n-2)中走法； * 3、先是跨三步，剩下n-3步，设剩下n-3步，有f(n-3)中走法； * n步阶梯总的走法f(n) = f(n-1) + f(n-2) + f(n-3); * * 剩下的阶梯，递归这个过程。 * */unsigned long long howmany_ways_for_nsteps(int n){ if (n <= 1) return 1; if (n <= 2) return 2; // 1,1; 2 if (n <= 3) return 4; // 1,1,1; 1,2; 2,1; 3
if (result[n]) return result[n];
result[n] = howmany_ways_for_nsteps(n-1) + howmany_ways_for_nsteps(n-2) + howmany_ways_for_nsteps(n-3);
return result[n];}unsigned long long howmany_ways_to_pass_through_100Steps( void ){ memset(result, 0, sizeof result);
return howmany_ways_for_nsteps(N);}
int main( int argc, char* argv[] ){ printf("%llu", howmany_ways_to_pass_through_100Steps() );
return 0;}
// 2229828423
转载于:https://www.cnblogs.com/prajna/p/3442501.html
