0votos

Escalera en Haskell

por josejuan hace 6 años

Como N es menor de 10.000, entonces, está claro que al restar cualquier valor (válido) a N, vamos a tener un elemento de entre 10.000 y sólo de entre esos 10.000. Así, es obvio que memoizando una función de recurrencia tendremos una eficiencia muy buena (máximo habrá que calcular N * k veces esa función). Ésto no quita, que buscando alguna propiedad pueda mejorarse...

Describe el numero de combinaciones que tiene la rana para subir una escalera (C)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import Data.Function.Memoize 
 
escalera :: Integer -> Integer -> Integer 
escalera n k = g n 
  where g = memoize f 
        f 0 = 1 
        f x = sum [g (x - y) | y <- [1..if x < k then x else k]] 
 
{-- 
 
Por ejemplo, para N=10.000 y k=100, en apenas un segundo y 21 Mbytes de RAM en un Phenom a 2,7 Ghz tenemos el valor 
 
9975315584403791924418710774461765266075288774128190682721068891837650748940202587941855920580511886227666327879656284219771577901792667944479996207852073663867839115222800706261779809248842580014905237222635842242798988783861456125604466287109986700802237146997002527668754557244003114361429211256272915745265862604877688640050611960497515922768656939814136301507867852994798423697560562077739116247636099428858948601705495179284151805149399837722640784038341513855755706517294102150733286363370434827278620599116015578773058948315860174444997924167798499733527850500225170652594131712626189943069075611216453065489096546524988793378846471542294859587135917216305857638856658857762544129836266255564231952664568507149466860007290900668493449058857613059271973418041081295210110159153266424123099889788877119198672836058947726608845584229300640697221608725393792946523069859379665840409071122918103816316122378672404264850111804309229134617454065603598863994484474758213181541948836734169036117237741451313923466855746837652487829331899365372060231044286067841806066796703612250751915208089544028090589739183350235861307964611973482588340629527622592873586012169126781911797109029138653352504959436424081063692357870751832345162106002188834707982632662650721911769170431901514271302228054571484896711153483993937244333520214360650110142243772731929016463015653537646365134139716530702089760712595747942614771339751982383060496742015456720041525345566694352518607920833591246867341670828876314286848405065778059635176562164133683596382219551068294172689170605178339015577947876809934616637996761400817095289467619871829356426757779210656208297910042958879521600479931320056392709274125847282545668666978935811173967116417786830071006598481203416895219005129045468147882792738627995881281069191794281063419430138374533068151600651560610621495173525560766021582819530230890960563106345014639335950153553204244706392923891421116483738482388751375947972680743310917976623704536020785585405204708017030800961261223500322892718225135106990070904414034779779029604957897275483086335143910794750703137338385939538496272110358652923854731074075480402278783340293193566455902533727470602085318061958430821499033663228207216254965386325482582688273358145994283550455449112374546639221631386804393572644243818095756181494568173510569755697631675495723715541216747190779567610388798759373909809666204171680587319877239010495830516601578006708730477017123675096487748567654495026159035160516936831001616398769934803409389489626304431048670530893796264719550177277316353017614626098872635263096515444091464385454203692265775940425178084398122018510833854027440081959269447993965811287374480284273419762304872787637911435971010249713041726141626807170011294361239069695107688922853472422608179237499965358860029069638769591731514392996122544108423388434627673404054000923503184546553751753587768523020864437947466674572221022663726425824680178513406058098411602532212702526927668610670761410984749909397416711466735868271656761 
 
El coste real aquí es de operar con precisión variable, pues las restas que hay que hacer tienen cada vez más y más dígitos. 
 
Así, al coste cuadrático indicado de O(N*k) habría que añadir el de la longitud de los números intermedios (por lo que la complejidad real es difícil de calcular). 
 
No obstante, incluso multiplicando ambos valores por cuatro (N=40.000, k=400) sólo le lleva 42 segundos y 253 Mbytes de RAM. 
 
79213018628653934002986807558217389692925280874965542152044632085818482885614443722591610774817450203648205899510693649841734796907014870116214238503630660461995990415742768698082753201747479908631178799405570631065336967786813242916027742996029441462373712424855071059696378661730983798572898633502226024938431044230597866643430912391186095315521603204753738614349232792841073479795430062481437939390138745630717341932582883402616309722937819962877816457931753736724784950324589730283019967337232865697443755030225971396016766395135531043196528609876693347187073939227052383995613550649468744305756939730074068704631643501047411265116158958025256004884307596687174625792598537487276946319154486891096743540909037905681590046414933113525230213572722123931892071124627649406540733293739378435653567130982634498767974079591400383751777723706190232008857665459821151694947745588926573351298925336918963810208191523845911991749508568715446369979303006329925100419785841130475318719125725948708909537791196844522781628258240569306387409982221554634602567099461918510139886292325652762897274294775885601767077592687836789186755290684045845126395246467037773334142160616555321141634665133749603808434557973252065767107979403163061886358115411601584348477843879231141119184320845933958061236446218290006957456258147133325819189761031245818939798696575825768037369125567976887042855298220530732923489052471939802551985717259124734905109671992563285738162400947223146845962100427749151930638814217342192062024073470913462944384612707630289207399163806750163901486087743643792876433872905400075365152718615051123064374737153258991404451555573947427076116913147273250941570622229474000929192209930410726291067481442782813342213289246243431765156015005914276852253938340677265288767214513530872742428407598982715603937542524281831531732259371865913786513240277730008923680373885354272557898311850056059879914240187291660542910425000494381607326208241947328493773320465203437863012090118916485762455315441687361180724134871244308897920081367535197289768153338259911918917154661399235700285878990713586880565607208966589325800139615206672913172074322703964092782685864694134103596261208272161710827263609271018067621850522071804601658789740486576267195144640596209070821315566167106151452943332065061993947966394341913335614909972863779461084010193777522264797431454627861452682444388879835787005955485066756581538750567350483131594118211523008570570864286601678618080561142546307582384976921308777127007946975768367110072764463160315651026113754691264594630181223932865374263631632173253007782167140771691781273686668347544994668921213395989936560896013432527383115409157348875985925226935869562635145226033848416276634227117562869857986278557301233600774296094542823883260242883819115386666546088979948997412521044202836231837175564100139046778026371458156114640084037376501328319357323996519693983104614666802966805886332061446275949451694771587565855819978867376214120115414822547685064038555435820284495004956366591298155389266423892562888281961761796216878446108998165826411332411334205350285109652711533981409424721270506080593635075090690975877551411219709222017801600927555909060327000719393107723389066513097201845920532393665884488053953072990885616641500457355526290463600483335524654213203622841460750315800332826803318900787469621938964495254047063330988450764536806531872728495015732994534960095488495123074701205140691223116823778375379306113713280243943366929586952747107563032593187984338345451740091963242591426370301101737440392865356956115606163466901939202334145650866219964354733539533104278462947360334829378783720664479414772615649170983469177687817814141670017093941545645496158788182541335529229185670487683253479190422764481703258710595211523515101625031150809755114803920750188453592148963989399484163451310228322370901909649767049538353424889365939320918030165923860546765918298168539059170969337101203137366138042953220340132369376475435398985960417286672895389795376369353999626455199361865347217273028023388365655955457268417670770759502739277599781171287894691761511783989816962889278534930465917571858106000776549143154910029925044728840378283610323426805162202637842204996720313056529180490733181892412224572336185806726351502170543745083315013629560291593101464025260537464589485940961466879233876614776898841073657633098971775845043025609024226859199154374693366015061372476016911647107708889488535955029540282587828290607559717919399780734878362677806515208438037099896653625923504391363337249674162361106888138672816353763155640184638599411339990362761079244160710249940239903011920279634096000756394933351727531893489796356716123259211240987849296123131390264845651526306487652199698603679090087015812612198435100519819128508299112032439840940977979086387619700556705205953648404415713881949452639023616725460657168147416762066394275245513670869688064310128880558317761311256838283780859614960343314648853471158477442707929629646773073810523397083493348892270892035572993234551415830949827246779393214775083178162328809263255728328446861599413844817479536370819615843688921781826711679532882815356059342483745483671330820057713013219899052922652012332476897799823886060568367147758590293000895665730706096877240427757960471794838472357795113364956601908749856271788814834652364925727655802809621197427707203211813212449037806314767536351164200855478989898088586546085706698504271504626425549664799979167503263392399001834008033288729996124542092596735606062537238867534837343586048180620344592591501599037125565664593200846812389426855768470862516809336730799713639948725917490045177219599795380356949641540346891526698241807859959433636309011273296367823241248720078273529391855863050590126646655782715150430136970656201438061059716726275055210800580221822187621829439216420399502270672751432812442524935494448987364911867691241495607811523122437826723364858180403933254649030484877311899810207746165841851786516924217154851344108235871082761768474588977191543051858760937830192982029093879882967784333093087396446403391603703003538997366433984513735545944488439366759480927811694533147974808111776117916374806391958910825584487321492658062652420802391591537011026508368304664567842248088450256387535090950475143398457819829171784620363911146700000009978111140824012278016096113546383350179566751159461169555028764933592583760006789890231408309926146304827124030593814678789573724398508618453899927708231733723839856591087524706689705490164988898156513929004970594509561469163286690151947570041375030983905719065980366714997850024153628193055903890643508944647740927038895341929173047600274508738689657191344795895400277145954301571770340119117576396046813994656082281494943811296417011532180499640981088869838107009107081508428335540539918044138527067589436296385207697915386757492741173450083890465370990393654265845386812402513055956902923307929970580395892568159434339337307893465322622504104546512488843794785296516609796496679763371912811159729030473559633109857883659144763590860535029101712261476491267861924894099810746113185448085802814291049345489752274936760998139139458720528445401807448278108359483434394116974977497902330884035028978488082985703935682932330182286658879972814811624505911956953579419311519627313611360710220245606710619589060993025676205213982972191775468157510331693325636727317052042103673359300081819946531134569141405565793895036002622883626804719916590699354337641992501303695909840755094094153795339576083034185836347011867006159455391647220795368105957602088237310235282782520612052744844415838248462216929065218990587864090908620012510338306110671223640557248115692999393396524378318567569694582565199921853754211220117398512470492994989670224205454489680074737066540090068542475196610441882432375498414945167600528278224358148486305750989690698138385596560526807127561398751704550919809781361321837507006007730181596663495400165403328600176277226365795381479324069715813717593192747312410717459898260945707192186286397684577658371115043360946502405689292548314099478645961859604080670089702027273347031206407932795602393654954593100413380425888236611518161958188620221855333837741971313284156385182943754252403268965158243873940733967293695290438470414709885942276590846273958434892955194559066665850677448414848049197508438660734825739578224370948193162346394088133809932927928684451969265047591143448295821287757316174936053761094541355310327859947695910951320944981459738854412420986894380698717194062584273421355577134659829288865032314393599082618642115396305760141467712177717645162061690000204651123746354983945422021926891673095221731704305838374111870849307060028497708052841978094818931857265575175112284709342368832445967969621601967500154195499839120073234444108894571782739579202604241892159500783688155422697917614515562920719340084702039985761584487931905538607725674102171223682398278980612166948377682692348424277564545974506920401493344103499166107287479757034960301095408348033099428508182511309177578364035374275089084636895250534544754951325868770410617845666830376176779254824978322070393907881943007339686419448922002424899634179465026471679875162270442774680318341702366305878597614443080764279008111985236441732430064657380446518405907345778316617402912233095063291250137976375478914185686094403102296923242027856076576351633345381803614176559595107898213242068279225239934330837484303165310711486033834297703642111478008314085533631330237744307201021535259576415707615865768215424717670311600423220814217919744451892597050568492525489746878402447354112503759705352020741607765510378529828342252152730890092704925808047255543592478296066390344198038607559704315752364574334145846310778846085828319193987889581545195318708250067133414797345130609259051265985042344493817485967018346760708285765092210791769989283229403152233368849224678989726742954633783894727254060664260851639472920058639665856826320123145130628227842763580618403375907396563801774486845447734034011194597775741575790034927927760280510585914102436480188519574979042516866225996872705467058601975999347273348020228814482907139016795358019887855281714378970084183848393275283726302592936506026651816220658805532808813267996854724107663342393051167624409951019527825063253182830949898935360516504879654671443250866580871410504527593812320760256891253537304890490520672133855080838276813644817013573588818780637898558416807045578664294843693166220396526509783201594238610591840431371634211753177354546621683052557428004358981419823774072901645365918237904343314901259442254419767172692229582449985678755244774780062092980010831712865009823127674257194329575074478797716079449804908036244529098939876104206170050686797050058981640793137408517681611642148982129254272618756514655414098973120449936275708933602497166586787718721353456450249613788687718014628250489915299210577011234533531255568315211140829443476992778994100415935200490539895898032780936729270657063587159040206690266416754112234530801801557317365975215609419706272642038755493869078744604654760260045306203742799471777335066836728435396963455228308992627257838781654029801989226952565801941393173310821800971625273591923745370993475611295196307069069264453366889857472899005555469001916315384437040311137157783724411907063052327991102661230378698201937095539465500678326711727597467123313783409417092006300126849375526375760249014311149607016052288186725692652660589824110004503903440323412204126883419165562088625282654494010118615804488324522341398705419067378703265791122997458216432411802830104975079798303962150451427665129272883944508338938670875119101361305364502489999081117826193432437780624067883519810641470705072701998703740973607818600525254409379122936216432362584402548410558719922842893646753329054526201777412629918977967673528140751263618925264848060827886681674277068682039224102271129037001362823231502333286065141388283483922680317603365104264782577381315681491428758396505622818885847955113707849077295601557217396223092629895129215450151321947811383671480838330161443818613482000824812444114223104 
 
--} 
2 comentarios
0votos

Escrito por Raul GM hace 6 años

No entiendo nada de Haskell, llebabas unos días sin enviar y pensaba dónde está josejuan? xD

¿Oye podrías currarte esta Kata en C razonada? ¡Te pondré votaco!
0votos

Escrito por josejuan hace 6 años

La única dificultad de hacerlo en C es que no disponemos de aritmética en precisión variable, por lo que la suma (sin usar un API, claro) debe hacerse "a mano" (tampoco es especialmente difícil) como en mi solución de Emulando a Dik T Winter, por lo demás es inmediato.

El algoritmo interesante es darse cuenta de la memoización.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.