首页 > ACM题库 > 九度OJ > 剑指offer(15)-跳台阶[递推]
2014
02-13

剑指offer(15)-跳台阶[递推]

题目来自九度剑指offer系列:九度-1388-二叉树的深度

题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
输入:
输入可能包含多个测试样例,对于每个测试案例,输入包括一个整数n(1<=n<=70)。

输出:
对应每个测试案例,输出该青蛙跳上一个n级的台阶总共有多少种跳法。

样例输入:
5
样例输出:
8

简单的递推关系,其实就是斐波那契数列。

#include<stdio.h>

int main(){
    int i,n;
    long long a[72];
    a[0]=1;
    a[1]=2;
    for(i=2;i<=70;i++)
        a[i]=a[i-1]+a[i-2];
    while(scanf("%d",&n)!=EOF){
        printf("%lld\n",a[n-1]);
    }
    return 0;
}

/**************************************************************
	Problem: 1388
	User: 从此醉
	Language: C
	Result: Accepted
	Time:0 ms
	Memory:912 kb
****************************************************************/

 


  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.