| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1681 人关注过本帖
标题:这“台阶”问题求解答
只看楼主 加入收藏
piggydog
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-1-22
结帖率:0
收藏
已结贴  问题点数:20 回复次数:16 
这“台阶”问题求解答
Time Limit:    1000MS    Memory Limit:    65536KB
Total Submissions:    217    Accepted:    55
Share
Description:
      校队的里小胖非常的懒,他看农大春晖桥的台阶那么小阶又那么陡,每次只上一阶,那样太费时间了,所以他每次上台阶,每步都要么上两阶,要么上三阶。现在他很好奇,每次都走不一样的走法,在农大的四年里能否走完所有的走法。所以他就去询问会编程的zhu同学。
      为了使问题更简单,现在你只需要编程计算,按小胖的走法,共有n阶的台阶可以有几种不同的走法。
Input:
输入只有一个正整数n(n<10000)。
Output:
输出一个整数,代表共有多少种不同的走法。
Sample Input:
5
Sample Output:
2
Hint:
答案可能很大,会超出__int64范围。
搜索更多相关主题的帖子: 正整数 Memory 编程 
2013-01-22 11:57
sh3792897
Rank: 1
等 级:新手上路
帖 子:2
专家分:2
注 册:2013-1-22
收藏
得分:2 
好复杂
2013-01-22 14:10
globc
Rank: 2
等 级:论坛游民
帖 子:15
专家分:12
注 册:2013-1-20
收藏
得分:2 
刚才抽空写了一个,要的话Q我。
2013-01-22 14:19
神龙赖了
Rank: 10Rank: 10Rank: 10
来 自:萨塔星
等 级:青峰侠
威 望:2
帖 子:711
专家分:1788
注 册:2012-10-13
收藏
得分:2 
楼上怎么不直接发上去啊...

I have not failed completely
2013-01-24 11:05
大米稀粥客
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:82
专家分:155
注 册:2013-1-8
收藏
得分:2 
只有看的份
2013-01-24 17:25
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:2 
fn=fn-2+fn-3
高精度计算
2013-01-24 17:44
wangjialong
Rank: 2
等 级:论坛游民
帖 子:77
专家分:95
注 册:2012-11-8
收藏
得分:2 
好复杂啊
 会的麻烦发出来

新手发言,请多指教。
2013-01-24 17:52
globc
Rank: 2
等 级:论坛游民
帖 子:15
专家分:12
注 册:2013-1-20
收藏
得分:0 
/*
注意台阶级数太大会吐核,台阶级数小于等于99才能得到准确结果;但是级数越大,误差也可能越大;
该程序由c++编写,经过gcc编译;
*/
#include<iostream>
#include<vector>
using namespace std;
typedef struct{//用来保存符合情况的组合
    int i2;//连上2级台阶的次数
    int i3;//连上3级台阶的次数
}SHL;
typedef long long int INT;
//求m到k的积
INT jiechen(int m,int k){
    if(m<=k){
        INT res=1;
        int i=m;
        for(;i<=k;i++){
            res*=i;
        }
        return res;
    }
}
//算i个2连上,j个3连上的情况下,有多少种组合
INT fa(int i,int j){
    if(0==i || 0==j) return 1;
    int n=i<j?i:j;//找出i,j中的较小值
    int m=i>j?i:j;//找出i,j中的较大值
    INT res=jiechen(m+1,i+j)/jiechen(1,n);//排列组合优化后的公式,以保证级数级数尽可能大而不吐核
    return res;
}
int main()
{
    vector<SHL> vs;
    cout<<"输入台阶数:";
    int n;
    cin>>n;
    if(n>=2){
    int i,j;
    int k2=n/2+1;
    int k3=n/3+1;
    //得到上2级和3级台阶的次数组合
    for(i=0;i<=k2;i++){
        for(j=0;j<=k3;j++){
            if(2*i+3*j==n){
                SHL shl;
                shl.i2=i;
                shl.i3=j;
                vs.push_back(shl);
            }
        }
    }
    vector<SHL>::iterator it=vs.begin();
    INT sum=0;
    while(it!=vs.end()){
        sum+=fa(it->i2,it->i3);//累加各种情况下的排列组合   
        it++;
    }
    cout<<"可以有"<<sum<<"种上台阶的方法"<<endl;
    }
    else cout<<"输入不合法!"<<endl;
    return 0;
}
2013-01-24 19:49
小俎俎
Rank: 2
等 级:论坛游民
帖 子:18
专家分:12
注 册:2012-10-6
收藏
得分:2 
我在想有没有规律呢?
2013-01-24 20:01
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:2 
这题原来没什么难点,先赞一下6楼
第n阶可以从第n-2阶上来,也可以从第n-3阶上来,所以 到达第n阶的走法数 = 到达第n-2阶的走法数 + 到达第n-3阶的走法数
公式就是 f(n) = f(n-2) + f(n-3)
如果是Javar的话,它们会直接写个递归函数,一运行死机了,然后理直气壮的告诉你,你的电脑配置太差需要升级^_^
但我们用的C/C++,我用标准C语法写一个,在gcc4.7.2(加编译参数-std=c99)下编译测试通过
程序代码:
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uintmax_t foo( unsigned n ) // n<10000 但 无符号64bits的整数只能算到160
{
    uintmax_t buf[3] = { 1, 1, 1 }; // f(2), f(3), f(4)
    for( unsigned i=5; i<=n; ++i )
        buf[(i+1)%3] += buf[(i+2)%3];

    return buf[(n+1)%3];
}

#include <stdio.h>

int main()
{
    printf( "%"PRIuMAX"\n", foo(5) );
    printf( "%"PRIuMAX"\n", foo(9) );
    printf( "%"PRIuMAX"\n", foo(160) );
    printf( "%"PRIuMAX"\n", foo(99999) );

    return 0;
}

代码简单,但仍然不符合题意,因为题目要求n<10000,而uint64_t只能算到n==160的时候,再多就溢出了。
要想完成这道题,得自己定义个长整数运行函数,用数组或链表等等来分段存储整数。这个也很简单,我下午再写
2013-01-25 10:05
快速回复:这“台阶”问题求解答
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026004 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved