Google的编程习题

[oneleaf]

T( 0 ) = 1 ; T(1)=1;T(2)=2;T(n)=T(n-1)+T(n-2)+T(n-3);
用最优方式求T(n) ;

int T(int n) {
}
可以用最熟悉的语言写

[oneleaf]

代码： 全选

#!/usr/bin/python
def T(n):
    if n == 0:return 1
    elif n == 1:return 1
    elif n == 2:return 2
    else:
        i = 3
        a = 1
        b = 1
        c = 2
        while i <= n:
            d = a + b + c
            i = i + 1
            a = b
            b = c
            c = d
        return d

import sys
print T(int(sys.argv[1]))

[oneleaf]

代码： 全选

#!/usr/bin/python
x=[1,1,2]
def T(n):
    if n > len(x)-1:
       x.append(T(n-1)+T(n-2)+T(n-3))
    return x[n]

import sys
print T(int(sys.argv[1]))

[devis]

第二楼的算法要比第三楼的好的多。
第三楼的看似简单，实际上有大量重复的运算，并且三个并列的递归更是噩梦一样。

[roylez]

3楼的程序，运行不了……
这样改改应该和一楼效果一样。

代码： 全选

#!/usr/bin/env python                                                           
def T(n):                                                                       
    a = [0,1,1,2]                                                               
    if n>3:                                                                     
        for i in range(4,n+1):                                                  
            a.append(a[i-1]+a[i-2]+a[i-3])                                      
    return a[n]                                                                 
                                                                                
import sys                                                                      
print T(int(sys.argv[1])                                  

[cnsdxl]

楼上的，我想应该是这样的：

代码： 全选

#!/usr/bin/env python                                                           
def T(n):                                                                       
    a = [1,1,2,4]                                                               
    if n>3:                                                                     
        for i in range(4,n+1):                                                 
            a.append(a[i-1]+a[i-2]+a[i-3])                                     
    return a[n]
import sys                                                                     
print T(int(sys.argv[1]) )

[dongmh]

代码： 全选

#!/usr/bin/env python

def T(tarNum):
    x = [ 1 , 1 , 2 ]
    if tarNum <= 2 :
        return x[tarNum]
    else :
        i = 3
        while i <= tarNum :
            x = [x[1],x[2],x[2]+x[1]+x[0]]
            i = i + 1
        return x[2]
    
if __name__ == '__main__':
    import sys
    print T(int(sys.argv[1]))

今天刚学python
原理和oneleaf大人一样
稍微弄好看了点 就是性能下降了

[liubentailang]

二楼的算法最强，一个乘法运算都没有，完全采用加法实现，太强了！

[sandorf]

还有更好的方法，楼上的方法都是O(n)时间的，可以用矩阵相乘写出O(log(n))时间的

代码： 全选

| 7 4 2 |   | 1 1 0 |^(n-4)  | T(n)   T(n-1) T(n-2) |
| 4 2 1 | * | 1 0 1 |      = | T(n-1) T(n-2) T(n-3) |
| 2 1 1 |   | 1 0 0 |        | T(n-2) T(n-3) T(n-4) |

其中乘方可以用log(n)时间实现

代码： 全选

def mul(A,B):
    n = len(A)
    C = [[0]*n for i in range(n)]
    for i in range(n):
        for j in range(n):
            C[i][j] = sum([A[i][k]*B[k][j] for k in range(n)])
    return C

def power(A, n):
    if n == 1:
        return A
    tmp = power(A, n/2)
    
    if n%2:
        return mul(mul(tmp,tmp),A)
    else:
        return mul(tmp,tmp)
            
def T2(n):
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 2
    if n == 3: return 4
    if n == 4: return 7
    init = [[7,4,2],[4,2,1],[2,1,1]]
    unit = [[1,1,0],[1,0,1],[1,0,0]]
    return mul(init, power(unit,n-4))[0][0]

同二楼的简单比较一下：

代码： 全选

from time import time
def test(n):
    start = time()
    # linear
    a = T(n)
    end = time()
    print 'linear:\t', end - start

    #log
    start = time()
    b = T2(n)
    end = time()
    print 'log:\t', end - start

在n>800时候更快：

代码： 全选

>>> test(10)
linear: 1.81198120117e-05
log:    0.000334024429321
>>> test(100)
linear: 0.0001380443573
log:    0.000746011734009
>>> test(1000)
linear: 0.0025589466095
log:    0.00187397003174
>>> test(10000)
linear: 0.158092975616
log:    0.0290448665619
>>> test(100000)
linear: 5.38085889816
log:    0.533372163773
>>> 

[liuqinger]

python真是个神气的语言
刚看到这个的时候我觉得如果是我答我肯定会数据库把变量和函数值对应然后来查，我觉得这个因该是个增加很快的函数（数学上叫什么搞忘记了），这个如果要用C＋＋可能实现T（64）都很困难，python 居然这么这么容易算出 T（100000） ＝ 54404133415360082315984634971425177388050274950873849802495316210909387698659515262455371961122100674504792220505817813346878027860100753162566562561850872039539258590075532731998487893875201274645050441287256876359525065601071079198040276742169925840373599353489785763306780117691135007783773307192224553480310486154690036583912667798411523214897796508524700065265863599245973393512423724698248000002133882764678931546494104522150628347811959123499200625134586732413557689125856726444076727185944969898990472542742174009612131208052794944994436272072083523205577930822620389162714750364006485115459128464899416002126557544839811189951750516963266532033678005191747244888806375996127027320316626381382701111527915169246952041973675864052182569151631515923581035348769750168901638485727925305401738200437358458371789287475742105074622044188784601827506455820355365297386508612494111429114958868490618949480899071613023812477167214808757875165597114441188586543805440338384892607244693894135363987022351217177334341301150459233800188342782506005743725506216983650308870848733959546742215736336045188763332447906137377076305991281580114913792250896790376266923963417731797413757309125753877975816720087743340224336438242766593330022813236838997691398422726973832016473320420964818470147498683742729521138721607260453710955540502038524422730230374516362416545314986985322678127999978501187119589063811613782748859508236184985629249313470237864603180735369015735861645721277434651232939560544016109260457860159930566031766948969524986250496053797291316066069211859184846451949427031953916368428248227182230859029944473456951902585045380508588687911338139348236641457804794594080601533501317534573772017481063830141831527633078042060109521803956545093571729708175414278331945215459192001396645125944539676464093509500784752528137742427504452135089595300178997408905243707448425291271768633815203693005431594094950454671981334229305464697514412379010572320420119636259177665226892805567470953050411803464108832855917963022860130776903734411078319268063850028869121479492888458503403633155448431837851685640384351245633877065298084842502644123386199124146359252350787785542460442055879758889428288722737951027488320105656828690132801887767432789911431238831458097972694121872756263097316432716133679270988945866613331795667985443340482149606263952895789126675259497510858062791845832123714258280381075890376417521991052348697645116391640612251562559518809743951345450875308243404412671816601344992634465634493778343062028985650032801235035575389227153973557967063970274519751438855181156240660414133390942479600448568894229022552693303969127986627814638424007342953838891062807595342046120869336533508109173293301462621507013539361733381345830548220790295826806620567512460035157736392522823268311309888548579580968826663574108350445141842229478840090087681266091859135647471914678809928742992884006345178705239516997250868438525984302628807043847226686488755819734650083285463394902090131534002006316684931378760653907753175194098192643161780490877845902948677233414691570349775602448769584226718675637379022178920404336067912238134067823493090510424321498448883454146319281853151071423341616162005181892858729561350563862888819147581551584662417837383914392978110146292779984961747370870299422626133725485822063788484313550629278365036033611450416387188311212606521773531486423229432715257293439329633616807230291496175409115069154373742486103609380897742426815762324878493071344851717018757595067885598871673711117116994164483080432379267892790447264825387487474275578301027705490911777821840407825242300696227464724951108241581173651390550220314270610248360258375887783322188491510328076554102776554812247490184634940959823646936042021143069211049406965546422782091685657428790371628418211280018610420562128805727912039808112825389239181199364535175409445586555970191044420460571763033397015703225577384647069156657224215180865279861751623683782567358055022880573157125375974168381976510975218797317421903814710330346686067738985777245556445962618153419977811537202778022117732001268688254237397927354856083189728246656619624473997830825373172031132385040595726221545216151233733268190202733808335256542482986705179628604156755918695548422075324684916641557718634519640060692051895120501028445102729933907943719795601087445290443749529436688696051523067702327406502416858173584432405736917811501812308599426727889413302904188054928873210849330315713848282840630710608296616684368002653649737124631089076702859968290006674520624212108537700161187850176984300263055982122232687961898073516214254186113401879454991139659595698639927690146762273425597033454788004313716200834164011039138472711500752079883970929084235033481755750700711649818270444362793880327503273272511816607985443443489302937829621167229027663442554650993412832269363398979480282682839555485453731656419729091232070042760382438545003609159768951720677002834161915675479183110902563431259111059455785139063452573501451105615498814290687979254037614988872870743380657621396344628261483542466536383757044251147782161753848733885021575767549079081908821820260753083729574614823868839332713010498846643837839973377697727108802757829060307624689329196250778434692686826609922379837521482973098183667983682680346261418487213528977024670557855243106284831594244996137169102726662634854308114519260464523763026389949111816864531517474856669045512499532978919195180850978849256504456826706665489119725919887111720903411726636349350848658152572292277821309609252598234575313423127506439472043170103020797272899154070484429113002922470180323974270063746183411875803372644874676041821473950212968756129517423635594022804402283702651471823146624477364229101633181778586576274558052754325072654734497427262061055057401109531894185308769574260284837844641788781587341959535332174773651357056458846829246398970950839387829075670124471718821121727976632121941224674121818523788529061896731237343196074614050036596410717585818278313766220455115285420928612945763030441629271362491792913418888682281814339353650071440530618176926172000934220545353320054759271242482068816996370247820652110443588663641536991822131034614117206237874336118330586620897303869259816050748827127266633462606739228287439924500514747386230355282211888294746449685379213505062070855683050231624340936734259231616069951538706291687118118936395163751410311520183599176734122652186095040538486259166679612467445226777899409653183341257333400753422230945360819226105330133729404694692225523262616863557275776926749126058509461753324752742522748228554391823003010025193555735528474500104048785360133326495030441085052629839105412075142259910950833620642793196631194849824673463440211681777890980390855243472251592035558208246547999404265041889476240756005872506483266179739241860084839916740612228259287719348229735994981756814726856621324761882322903564812675506893607855141917096437628626874008506426693792852211418016221870109438986495299399254749528125007062688487652109917257811652535541697326106840454629602191270300852017982389109795075886663235255578334542257838936358856724704462086607950000349628482850465682419724575722605115946939280449341563796703161342161375192629799073573778910054879002169233477825113446947675031547718533266007016711611338334412760465354868272177054043222402717209381789448262701241415853361844595389077445233532476302506419344372819942415596335713194884294165768060202860442654086440745812067564567959731676436393986978494581957903195203373523195026347000339024935749730256074218389197973140813280695614146252032674589429319061142907294425156629901907169345059083113547643487796704771394633953966009286223680845256000349685384078372169794265035733570986290898704337034874034779566733855813814635813067844879758709944074733862288166600468508797620636805914097925308986676367836129598907839588242076360792746935380541036088845315608760563310925963964848201778035716211341296673572955809357715192786732061144061385355917995793390563406341210444170608648121559344329628793690328552105274530282344313463087480381567377712044644354692533470341723534905615406658059783238642399107796353869142068834288474504590886863531625456666767653011666695007777892842154825707860497849731233300627291131515959720212914742738762056205921069306347530876126406255133799455547339101637132374365755019064228982758458704321253244173710208864351945375116851960982851898261359804391003294333482766520599392601022211191053863351968819139908450141434931198105782748536033635792934332895464952726854204472080138496641625420877160216702000404140604045843597525633077825696313723749606566942222605272320381661123338570514367411791214350736192711937854132832285167466565831644486207547918498592359643259952457706085015109132788212705679070421070022291837961349378691861374188481650097178769885823509103849351758246995681988455344546104464013735971068695101053250252657042253589155236871520817341773286798264832253552730772409646862034361089075091665041633314068103774712656742642995278254321597995487753287982225057362204553175192718323829681954265063637206216067191239875074584162643973515133455414372009010075045733318526706108745377374949123097730522449005785401611291193722011373677974580997433016521835965952167247425397963518631932026037135406597433847998567254893058416225197779437278056658736071198684572298364342230397290177292409182412753435144442796159079457257075209820406348264277072750699532622789849232094400725148471913400890183282442374552215652267170371836250670146789661720343134209291261260152837906355157702686987453953507119574919168525919228659370878211326737670747802513504761612936931627866175941667837011941975849336894374137814609915867741542964719473878678339365654385032721545278477906930869403485828203932686010201466442507811716441605064940511482327976800603736407348024944761530982926599300699507542761069232323769328384450958416502910844105881296689668083491237369327989943498407641670948601893056225504250331570669477782025225340739842742246119465851387563449165042039380089779467449201290807727806744242930423312743586316013722784703568994912124343714161091890169616903214067788075882017357381948558495881132454321815737235630629684345850329524639608084997212046945163481322588781607543305595615128962718873948515726102512785639214778446142248492044712916781821515272543074093301441450934807176322367128159526683466302441879539873990336104926313888678743040854074338098907018654171559448738178409153724154436286738249934000404469722985309381164845511973653820554249720520640360559597504394917360223459405052746786047304867678327835227922409724307554706168711040813014887950737160001229580354252332954150100638551450893718917262990011929991492955848987513910766467924721632141906446587581903610073087399104311232920318972559733592598288352817867131078059858307821598322530083030016862484461610964940793890208242481591134818309012877684322576441989072497111335259386460673274095816429094229677829267684634776828644485409729681575904721377370284899711797815388880905888837756806499450594238851697275694620095285971616716980808556906342220572325898760460449684267463548814706656761933322226596589692069115098234402341388920806202491598001553295214043325871209123489813517796128354827655700492730061389240587043982429236859216382621614488921198516931244357610303552988903838644820474407699044829428550709494986346636260474180972190977399306347747856593516022337546545031385697745990157067510281815723260372742459912788901018932115724261796245695448437085161793580113392279403205847951620333994943765835033210849543922309066500633835743660231664195141603702151045480236414413580317817732501005786745696940375078319725676952249425992254218624134722512342179490800208482582670160652011245372521128553082313010348159664983435915464222208246459436156288761452767955785847904208384400479303919211197164569706668227211321633673680628534383820378116477090564242138414718555534573742924952093917302921807264603809099096456845021691449816347617873088164628880972378896343436847926474054341798597647182782230292906765516303938325265877509697017511434270356018076867588069267631234242962077990219168340895433756439374016714420194708808836351179013660014123097051928278427759921664873652329635379600464703674387207591419800024392031979257003029333283336034776151642932415281311364765441019656055264666280320279753028093113713191752649414719331770616332735078193951018423640549974174670485051373966379252041690121412575143421956580863141018529275269696647298803504720438164054185684398999689996785280211068784770405369372754710934595796109594756501244952140346840371902166142567784265302484644397478959155355026384452699910091086594266789147995528991261678046576004960942468963678136372171595310581899679245219797299605276555899534315438314540552514329675530425910539331370879508007748643205375748048488518148462660836601108161853404785885705202960826473726725795809170249914512310959702191267523944812138106818987911956284856636797521625799214626295688815667705605089130182806370575137052989089011922968368079565265191334341177411878125554450733206443340290647293110076703081888584281118163099564796707254294620750364544080880445070395158708071517733420913656542641102962857550810092335798059382372625747883559504840097695751252269295562551584910599759174165036648608256360782684771645602798233945828255426301888060983827112407511192947806942234175478666507866214691687680721349137325044370010002311192021621587528604294917010638246194274934507983328729299782548269922705857074192591977299802903690110504779224069686289558262195899441240433418528482194875290312624463347559097204764621849758216879712864193435660983911784065663456974722616911077687436029527195482565246634001343653954208650480106965600617565918063474646929240776577574658412268284663437142855779558174284493170550081570244143953949389698900257286839360846843096621861168511135396963240072412708955950609067200551106870916883269929951318415601224668547687137233665918542914555046952412064454655804169394732383973154330480512925415399862637246648043638391531573223227895736342388355669020336248125665296841624948324567694565447259878468811570369707764730981405436627866640130249283434540482475361114215156762437641641380004319599728618229302943685670304496338471896925753563351049249842657463789334628310621046175306485771896076271579791166621066094673047365510814531221282313056682575452365291680757606715095647024592187257469013353073554285242492278789455230590588262625463453374318736986134275108847542241066398594531863200755184300200804193290099427657619515736697082716014568451016231691901212931337430447802094921663662526055084588005353861070096255474369927436920811425184421303291740822557222790968590041269506061840951463778000357033381871389628689501138737869939494609894870580813520037290356750386126033801404210422565148635576561333856583382550202566876001817191849589655084265240490411404112580022960423706136455079632408045519161399119674268295619608892543561792420001635000115042076048662711351970157563684039353527666058713804047834939960026249393122825276048056927701134197053435263875078160664430113576170328135379564814205969886369044773527097632566867242439388785566098756263893619084526049710052012137446069051065166701724210877473695264714558761767302526797363452615193074187890839317850620276919597920370505254625526658287452602705318182192296969659683797439201864434495876908042239116634374546764809450292556725433267700721797123436578982445557762891062656203078809227080979985713635975377733506027572966752639039839613627408114290760261969017172299334233764525858448517664223249124911088120109880181822984481984527999932557420837702061769724740251432517183696555280266778014133414138168067073639111484616360241028122361152666013548084049802687148840859337561821395572193423192044599216409753680561123745054818711723310475539627058402708478908314865943272233818204226936535835091424975541505867160172735804345443458785604021010557239611792294369186182146521336810959257038289470282276354944437920723518843702930622840719596491966302487618033067749613227912838435588032890084158926813077386188734949141031068384778413910211599391066282103686001749897544075300165770539277550512062071342498751788952091757334444602780409808646817161309542403375902816678364773395363766395441378159894839285598401452831660024202194180587873065040968806046666882631244378817546775879731930438268713141180271256319494581030558230972766869169743936147915718024407283307493415538877177962726697174686294278513138499507482822963313799357171901797100568305455843851134505481335888462341344601254662155918660655266474231529495891004450864075271507243472024517923912374188179353899043576839028467508049561989933920049239274519671468225877739878841005130677997893982919888376731598975453131822165467579057689802102559028999181485760816644170682300523720400674816080868040726749630668566205027320726997342118709440600954663460909108653303630255708169327608928076354234034538105175567444057408499294903966878279471604876606171435208278773157397808835826226289940022831626152606119875165976936580754703809203038225692575219399510488186854814034153105067748560447645593173226106924001185466623773244348208731965255408825416181692932077865588263427325515754087218540121981532009569827815906109898834500990966959872691660257780691843322522034461732225847695258315847807433389774169918425374881584637798226312633961081477663136642059561005876985179243464994943868514072937268372827740179716288952494803556787570203593674779558573980293521607884629935045054466526196181921133847708648312687532235784175710181611201500345138080280368617728638430157908676745405575431899091352277505724533412475079933735331077908010957165891631107054467320234396403189214051819432126122287078844565649574946135631652922640223640129869091897460220265852516512946978990023256409327880013066560364934941363879982462471071537083349976710618090504706172502698037120143018748716501116219433348539274544653832814394097347380179100721904637489081738199445171509975186702649253122822383015343217384599676833475955804432140478338669510461253322045807206810190528238228161003236737395527119596304215959845579570901607967372059183061942597557686529646465014875500251202961559393978516127714094229616843448609547914172652307039024834365030650546207252216959794208005398663904418120808830519261322575922355407844259168187433769591622600496691301842486532098613282850335901658067908500087508140255870108304019515622831044709529447128345918000547289836430709953773676194849740169516588503008055070464237580950039843125043677750829975344418060639613700672004180154018743838302127097452223267020758772145465312052548634340518825994002330468881466741104548141182582612305571440172018631879591344482947331744626385901948455519228504991574808999906173875897376557373437206138346744618977420417704552608604349928841349051026380515086156095614471913936504475801133241959133132882277050718011059137496432977961796903817126672084588775593988846202285767726571869018410042559634015745188499480215114158024482968949136075586529794865202758858037652554740763948622701501962349294180077020280400326183392269972947303035166362445884117354851740493243472144486576466460441888430627101902030964655124655983553998968093783884325174024103251989148732176845744053587125464683096366220136928595667086620937016799073518973856151188274911733784894521902507202283651533557163216673420619724035435607057209892763075334868017444044977779309350988395903757128137695631370094016195688734250687701429211693023599982713248898409443261360726657600683827367278670098862632418650853918280546899005903681957570495606806088546535649005740296480747789129519847644510350732715146995311192291026818757037535683039057683966447314799619071923417163368226168525025093683719602432181632113977436106039979011615640639063530087867307670149357473462940212721829600734990877523281302731901754332402699675443584062438235257139598972666142615082305809656516773073931285151094259210468993567993250494961599396644180429812977526205176892920048138640195819892054057148059781809168767310523999509419481689016436007317193811382037360755530021652853535342989456053414325861729323196029079524877291616240538069841016025928822955152944937446763210538979756463393708926737141244819176580205312937141536795058501509522167852608072573063813648878892023301925017597973366591015671818057090921158124200568520079831207972177661629688531429956660612459146524343872502101262981898718748375457704267372030013052388988769321356027094993689626493440189476970273955381639089998900201047350101604435963246002981742619664359568101393920133557778346603755883821511260195453351786405411065924847963027314770426256704938148376388970908750064169471780984272891636814445183028832088602808436154613090261377829151291374899145980138584904091824781077109346895433509223628659493708147223135446677364965807839580401082646427086655278175149803706579889700378782307456408842869596621022905158610218658760132898820108092062680900904144916093451760832390490841199474779040638643358753768084221815787809992896098569404001506271377720792667970842837159432134765159811269497846336508953795820632774607526465800223583414430105858263791403235024495935030332085417016048048439090150686097324901941710235169261435306654107051317103813147225057770836123897939256280962519151880454371901978551383925410172453208326063878918737309955733206823537863747195531293452633891145331393544176342551119592892176174889539516270864069231296463598298861407219661549407001336208985853617329148158413511485227526969394549583995844556755246811719649550553667675977227895134121419998773653870952093775455314908869311470298296988913964454721012926374864575176395924854285915237247151598094880853074280500162821808361597197196925418694712719728842780047197442469289188186994102515244336294266589588477421723992814232213167690563052227206932472708871842492730113993319745346315516711848685552868864299310500403283794612109824796661105010952985811382427096883990349902451371859129062865128022617778082280498030194911500444803993458579973573762724982199545927231191751526799693653307746006754827344145625101678058073454805033757451281580418561008959646045185816783764979284679284075104816484542966314910929287423515277421501548699013503955549139184310717700986186106968550759974712724705948503116422500836262779762471497192832738654379718657031402564891021438139656373059065182991210644932895825073677831174694353685826431527787872078483298639549144929650798440177176456074063814369852331331954372503192692376576164010432903983114615711402545432696663923532350750764330642445601092932335315775326828307517389518677795211008047158992933738644935253392554364562009760288173398982014448475146725252557228799631308902156136951060206375671392510516028544688160072120965684448848555379652828699393658920571158459526959735197558875642458106874321637822691660918766310823045484846012602514934682940883534783785243128167050653709352554776237016827301014009722104669179746745004302841850756203712613749439780732331615169493689511015073685826759349474519287602398504366222827878333264056166026572997457727383296969599237716965125766561580035620385383216889271717877723745412417708180662313283972919061799977944233546340522450159588090115094161863339774437755612341469473122527232096348583569874972749763601812614599067330432482733626263767780460156711667033511253535816136077728263492614549124956789896320088275169349958800129292162167137810929782947757121062164411112625322029169176379158697465478085385131535201978776896238645156851484243837196098763358103859782728331064948529185580535195058388219550185748647878323239691903843700919445437554926776492539970464030815108388669518404937213508396190221229992441997853194863333996768106607067773148419351405908491461289811613970521189328709724830241700607312308037817169571193850280528292522623178195787538664215840718807903550531812421476692559509244750130124434363958374751481250450041808867882464747561222510701831217567229453951015062323774390381875677702027759547818362371209121697545587645841274583150823343551455550213182433094678095853016817500130732669968422964983127138001002011758725755838514835655072387106466204649868670055078758323850903001481161868731685366826906319585805955297681473825729655627377234084587993207353033444363362472475501300619224269027243623903260512136562882892901381528178176273710190238763528788881830359511427016256831663604447022833045197804610091965821151474517465980294605700962197028681164289196335509668158025133558985055849979089176635425390693229562855360527040095934954022561565218956885373852837410083108489610829464821794620847344359343665690019544500768964423234875599036797464155840016865975778242146821044562397644131125763724442197267741246913844734348504826364063441033302312937751355228282603076631680447842758798028374844382685693438412341746245164314228906396685463572014649845970092413841903389321282727487596491886006789739062944454108626044875130307417753603740595164174765647013761461118156282465716271432601746682811890918009294926318628361421022567465789559786156622240831147828923456082849681228321284158889594909898092383708188938322464749315338205323769312510209144651732947789503860770292264090076249492427266529603134741922008203892209048051097739722251862024552012477794426846407096812064138330674032948421820078570265628989908643956098288978744556902099439886261618744579982879620517977127631095498921635732261164511713009498322630545638481824881841061101566849118079640015029007765767644748618667427230324219220558380213605617465420629439889267826597869171573597211335210251051217414255936893050271728294099370690452182233537797701135511446300196275014183387425452997489110212637837017317109103660781088389793159539244332352218196415565965399681709307120647078948974550579193779642237316031354205927778073373766007648035374156360683095042407219600710686468997877316012265539604654355156908471277913226907522299049202852163285061542574739610890619605455965451743778241895461699989700657878378425213092839448307230476799413825413120891295172220255172333688803683294079634717424678087824806677269270651578414207938827677252486588882601668797214093287728587939872850766509750000304686968077693630882784657650179353418111550842082203637794320326637202866445582536427191270135220116833393810149049545619799101390014663738732439365556534812375878258508211573236430778613365574373393405235087372359982504025989314316563472123396257
天那，这个太难以置信了

[gashero]

是字符串运算？感觉还是数字运算有一些挑战。

[xiechy]

你用gmp的话一样可以。c++/c算是中级语言吧，性能至上的运算（当然，fortran和汇编除外）还是最合适的，你试试在python中计算>1000位的数字运算看看？
这题如果最简单的话应该是计算特征值吧，以前高中竞赛时讲过。但是也要算乘方，所以实现上还是线性代数的方法好些。

[deng]

不管什么语言，算法确实很重要啊！！

[freshfish]

很有意思，想知道这种习题可以从哪里找到。

[SuperWar3Fan]

erlang
-----begin-----

-module(a1).
-exports(tx/1).

tx(0)->
0;
tx(1)->
1;
tx(2)->
2;
tx(n)->
tx(n-1)+tx(n-2)+tn(n-3).

---------finish-----------
just a test