| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 1681 人关注过本帖
标题:这“台阶”问题求解答
只看楼主 加入收藏
TonyDeng
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:304
帖 子:25861
专家分:48889
注 册:2011-6-22
  得分:2 
.NET有大数库,但喜欢自己写也不妨。

授人以渔,不授人以鱼。
2013-01-25 10:12
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:346
帖 子:7133
专家分:41569
注 册:2011-1-18
  得分:0 
用gcc4.7.2(加编译参数-std=c99)编译通过
程序代码:
#include <stdio.h>
#include <string.h>
#include <assert.h>

struct LINT
{
    char s[1221];
};
void LINT_Add( struct LINT* a, const struct LINT* b )
{
    unsigned int carry = 0; // 进位
    for( unsigned i=0; i<sizeof(a->s)/sizeof(a->s[0]); ++i )
    {
        unsigned int t = a->s[i] + carry + b->s[i];
        a->s[i] = t%10;
        carry = t/10;
    }
    assert( !carry );
}
void LINT_print( const struct LINT a )
{
    unsigned index;
    for( index=sizeof(a.s)/sizeof(a.s[0]); index!=0 && a.s[index-1]==0; --index );
   

    for( ; index!=0; --index )
        printf( "%d", a.s[index-1] );
    printf( "\n" );
}

struct LINT foo( unsigned n ) // n<10000
{
    struct LINT buf[3];
    memset( buf, 0, sizeof(buf) );
    buf[0].s[0] = 1;
    buf[1].s[0] = 1;
    buf[2].s[0] = 1;
   

    for( unsigned i=5; i<=n; ++i )
        LINT_Add( &buf[(i+1)%3], &buf[(i+2)%3] );

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

int main()
{
    printf( "f(5)    = " ); LINT_print( foo(5) );
    printf( "f(9)    = " ); LINT_print( foo(9) );
    printf( "f(160)  = " ); LINT_print( foo(160) );
    printf( "f(9999) = " ); LINT_print( foo(9999) );

    return 0;
}
输出结果是:
f(5)    = 2
f(9)    = 5
f(160)  = 14259783588075761122
f(9999) = 532692007196403076840086044264255523113714914725252086145326949585837649390243870857959406324793592736972425612431078622475937455583346791205433629410931900797493770245279774910198229460584496988314997671042632704512024742343587220120829419877051261930541767628082507655809853242587233225386542061628556348459136090633670036641627215466003906583021299432556032462067337369377107891435277145238984081213639359946488344186946303604827609917906184642065848574653993271679319211448048568608150422454451753661350958133644615496914749572769142397010151476835399019138797806037315775221716575799617373815695867377717177479911647575592883693303948949915321227437729134435491247398565078258983042195762299575946884187468661324492277001655885133168762929052270227367508629279955407560075483653046555323940297228255122240657440108763129951404924396624995571537985494523928272785337167279084924030103801237616149132354044661946868772838710467253307015210211851491307648768246251701753894940216220435783767200686129793673346343949601237721523242757900283498087839228458702712757201526934514262828326691183606210590730486536260411030273989268755551961441198829618698017478630108071633713948107766636907226105209476954643635913541414033
没有对照,不知道是否正确。若有错误,你自己改改
2013-01-25 11:17
globc
Rank: 2
等 级:论坛游民
帖 子:15
专家分:12
注 册:2013-1-20
  得分:0 
递归对于递归次数多,情况较复杂的情况下,很耗费内存,有时效率也低,所以一般情况下我宁愿用其他的方式(如果可以),也尽量不用递归。
2013-01-25 12:27
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
  得分:2 
尝试提交这个代码

#include<stdio.h>

#define NUM_LEN    512
#define E_LIMIT    100000000
#define F_STR    "%08d"

void add(int * r, int * a, int * b)
{
    int f, i;
    for(f = i = 0; i < NUM_LEN; i++)
    {
        r[i] = a[i] + b[i] + f;
        if(r[i] >= E_LIMIT) r[i] -= E_LIMIT, f = 1; else f = 0;
    }
}

void output(int n)
{
    int a[4][NUM_LEN] = {{0}, {1}, {1}, {1}}, *f0 = a[0], *f1 = a[1], *f2 = a[2], *f3 = a[3], *t, i;
    if(n <= 0){ puts("0"); return;}
    if(n <= 4){ puts("1"); return;}
    for(i = 5; i <= n; i++)
    {
        add(f0, f2, f3);
        t = f3; f3 = f2; f2 = f1; f1 = f0; f0 = t;
    }
    for(i = NUM_LEN - 1; i >= 0 && f1[i] == 0; i--);
    for(printf("%d", f1[i--]); i >= 0; printf(F_STR, f1[i--]));
    puts("");
}

int main()
{
    int n;
    scanf("%d", &n);
    output(n);
    return 0;
}

重剑无锋,大巧不工
2013-01-25 18:21
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:346
帖 子:7133
专家分:41569
注 册:2011-1-18
  得分:0 
回复 14楼 beyondyf
你的代码 和 我的代码,除了风格不一致外,算法完全一模一样,难道是 英雄所见皆雷同^_^
还有一个小差别是,我用的是十进制,你用的是亿进制
其实我一开始也想使用十亿进制的,但想想算了,不能假定int一定大于等于4bytes
2013-01-26 09:15
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
  得分:0 
回复 15楼 rjsp
选择了递推,那无非就是这个算法,更高级的是求出通项公式,呵呵,兄弟我没有把握能找到。

至于风格,那不过是锦上添花的东西,呵呵,我也时常提醒朋友不要模仿我的风格,免得走火入魔。

我很欣赏你慎密的思维,的确我们不能确定整型变量一定是32位的。不过,变量的尺寸与处理器无关,相关的是编译器,几乎所有的OJ都会公布它的编译器是什么,所以在提交前可以确定整型变量的尺寸。而且现在32位以下的编译器已经很少见了,所以我愿意假设整型的尺寸一定不小于32位。

当然不管整型变量的尺寸是多少,也不管用的数制是多少,它们的效率差别只是线性的(这种差别我并不大关心),在算法时间复杂度上是一样的,所以我们的算法完全可以说是一样的。

兄弟不必在意这些细节。希望以后能和你多在算法层面进行交流

重剑无锋,大巧不工
2013-01-28 01:11
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:346
帖 子:7133
专家分:41569
注 册:2011-1-18
  得分:0 
回复 16楼 beyondyf
谢谢,我就是这么一说,我不是一个较真的人。
2013-01-28 08:52
快速回复:这“台阶”问题求解答
数据加载中...
 
   



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

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