次の手続きはAckermann関数という数学関数を計算する.
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
次の式の値は何か.
(A 1 10) (A 2 4) (A 3 3)Aを上で定義した手続きとして, 次の手続きを考える.
(define (f n) (A 0 n)) (define (g n) (A 1 n)) (define (h n) (A 2 n)) (define (k n) (* 5 n n))正の整数nに対して手続きf, gおよびhが計算する関数の簡潔な数学的定義を述べよ. 例えば(k n)は5n2を計算する.
Ackermann関数を定義します.
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
問題文の例を計算してみます.
ようこそ DrRacket, バージョン 6.1 [3m]. 言語: Pretty Big; memory limit: 2048 MB. > (A 1 10) 1024 > (A 2 4) 65536 > (A 3 3) 65536 >
次の手続きf, g, hが計算する関数の簡潔な数学的定義を考えます.
まず, 手続きを定義します.
(define (f n) (A 0 n)) (define (g n) (A 1 n)) (define (h n) (A 2 n))
手続きを使っていくつかの例を計算して結果を観察します.
見通しを良くするために, ２章で扱う手続きを使ってズルをします.
ようこそ DrRacket, バージョン 6.1 [3m]. 言語: Pretty Big; memory limit: 2048 MB. > (map f '(1 2 3 4 5 6 7 8)) (2 4 6 8 10 12 14 16) > (map g '(1 2 3 4 5 6 7 8)) (2 4 8 16 32 64 128 256) > (map h '(1 2 3 4)) (2 4 16 65536) >
計算結果とAckermann関数の定義から, 次のような関係がありそうです.
関数の表記を一般的な表記で書きます.
f(n) = A(0, n)
= 2 * n
Ackermann関数の引数xが0の場合に相当するため, 引数yの値を2倍した結果を返します.
このことから, f(n)=2nといえます.
Ackermann関数の定義とf(n)の結果から, g(n)は次のように変形できます.
g(n) = A(1, n)
= A(0, A(1, (n - 1)))
= 2 * A(1, (n - 1))
= 2 * A(0, A(1, (n - 2)))
= 2 * 2 * A(1, (n - 2))
= 2 * 2 * ・・・・・ * 2 * A(1, 1)
= 2 * 2 * ・・・・・ * 2 * 2
この結果から, g(n)は2をn回掛けています.
このことから, g(n)=2nといえます.
Ackermann関数の定義とg(n)の結果から, h(n)は次のように変形できます.
ここでは, 2nを2^nと記述しています.
h(n) = A(2, n)
= A(1, A(2, (n - 1)))
= 2 ^ A(2, (n - 1))
= 2 ^ A(1, A(2, (n - 2)))
= 2 ^ 2 - A(1, (n - 2))
= 2 ^ 2 ^ ・・・・・ ^ 2 ^ A(2, 1)
= 2 ^ 2 ^ ・・・・・ ^ 2 ^ 2
この結果から, h(n)は2の2乗の2乗の・・・・をn回繰り返したものです.
例えば, h(5)は上で求めたh(4)の結果を使うと次のようになります.
h(5) = A(2, 5)
= A(1, 65536)
= 2 ^ 65536
つまり, 265536を計算することになります.
実際に計算してみた結果は次のとおりです.
ようこそ DrRacket, バージョン 6.1 [3m]. 言語: Pretty Big; memory limit: 2048 MB. > (A 2 5) 2003529930406846464979072351560255750447825475569751419265016973710894 0595563114530895061308809333481010382343429072631818229493821188126688 6950636476154702916504187191635158796634721944293092798208430910485599 0570159318959639524863372367203002916969592156108764948889254090805911 4570376752085002066715637023661263597471448071117748158809141357427209 6719015183628256061809145885269982614142503012339110827360384376787644 9043205960379124490905707560314035076162562476031863793126484703743782 9549756137709816046144133086921181024859591523801953310302921628001605 6867010565164675056803874152946384224484529253736144253361437372908830 3794601274724958414864915930647252015155693922628180691650796381064132 2753072671439981585088112926289011342377827055674210800700652839633221 5507783121428855167555407334510721311242739956298271976915005488390522 3804357045848197956393157853510018992000024141963706813559840464039472 1940160695176901561197269823378900176415171900511334663068981402193834 8143542638730653955296969138802415816185956110064036211979610185953480 2787167200122604642492385111393400464351623867567078745259464670903886 5477434832178970127644555294090920219595857516229733335761595523948852 9757995402847194352991354376370598692891375715374000198639433246489005 2543106629669165243419174691389632476560289415199775477703138064781342 3095961909606545913008901888875880847336259560654448885014473357060588 1709016210849971452956834406197969056546981363116205357936979140323632 8496233046421066136200220175787851857409162050489711781820400187282939 9434461862243280098373237649318147898481194527130074402207656809103762 0399920349202390662626449190916798546151577883906039772075927937885224 1294301017458086862263369284725851403039615558564330385450688652213114 8136384083847782637904596071868767285097634712719888906804782432303947 1865052566097815072986114143030581692792497140916105941718535227588750 4477592218301158780701975535722241400019548102005661773589781499532325 2085897534635470077866904064290167638081617405504051176700936732028045 4933902799249186730653993164072049223847481528061916690093380573212081 6350707634351669869625020969023162859350071874190579161241536897514808 2619048479465717366010058924766554458408383347905441448176842553272073 1558634934760513741977952519036503219802010876473836868253102518337753 3908861426184800374008082238104076468878471647552945326947661700424461 0633112380211345886945322001165640763270230742924260515828110703870183 4532456763562595143003203743274078087905628366340696503084422585596703 9271869461158513793386475699748568670079823960604393478850861649260304 9450617434123658283521448067266768418070837548622114082365798029612000 2744132443843240233125740354501935242877643088023285085588608996277445 8164680857875115807014743763867976955049991643998284357290415378143438 8473034842619033888414940313661398542576355771053355802066221855770600 8255128889333222643628198483861323957067619140963853383237434375883085 9233722284644287996245605476932428998432652677378373173288063210753211 2386806046747084280511664887090847702912081611049125555983223662448685 5665140268464120969498259056551921618810434122683899628307165486852553 6914850299539675503954938371853405900096187489473992880432496373165753 8036735867101757839948184717984982469480605320819960661834340124760966 3951977802144119975254670408060849934417825628509272652370989865153946 2193004607364507926212975917698293892367015170992091531567814439791248 4757062378046000099182933213068805700465914583872080880168874458355579 2625846512476308714856631352893416611749061752667149267217612833084527 3936469244582892571388877839056300482483799839692029222215486145902373 4782226825216399574408017271441461795592261750838890200741699262383002 8228624928418267124340575142418856999427233160699871298688277182061721 4453142574944015066139463169197629181506579745526236191224848063890033 6690743659892263495641146655030629659601997206362026035219177767406687 7746354937531889958786628212546979710206574723272137291814466665942187 2003474508942830911535189271114287108376159222380276605327823351661555 1493693757784666701457179719012271178127804502400263847587883393968179 6295069079881712169068692953824852983002347606845411417813911064856023 6549754227497231007615131870024053910510913817843721791422528587432098 5249578780346837033378184214440171386881242499844186181292711985333153 8256732187042153063119774853521467095533462633661086466733229240987984 9256691109516143618601548909740241913509623043612196128165950518666022 0307156136847323646608689050142639139065150639081993788523183650598972 9912540447944342516677429965981184923315155527288327402835268844240875 2811283289980625912673699546247341543333500147231430612750390307397135 2520693381738433229507010490618675394331307847980156551303847581556852 3621801041965025559618193498631591323303609646190599023611268119602344 1843363334594927631946101716652913823717182394299216272538461776065694 5422978770713831988170369645886898118632109769003557358846244648357062 9145305275710127887202796536447972402540544813274839179412882642383517 1949197209797145936887537198729130831738033911016128547415377377715951 7280841116275971863849242228023734419254699919836721921312870355853079 6694271341639103388275431861364349010094319740904733101447629986172542 4423355612237435715825933382804986243892498222780715951762757847109475 1190334822414120251826887137281931042534781961284401764795315050571107 2297431456991522345164312184865757578652819756484350895838472292353455 9464521215831657751471298708225909292655638836651120681943836904116252 6687100445602437042006637090019411855571604720446436969328500600469281 4050711906926139399390273553454556747031490388602202463994826050176243 1969305640666366626090207048887438898907498152865444381862917382901051 8208699363826618683039152732645812867828066013375000965933646251460917 2318031293034787742123467911845479131110989779464821692250562939995679 3483801699157439700537542134485874586856047286751065423341893839099110 5864655951136460610551568385412174598018071331636125730796111683438637 6766730735458349478978831633012924080083635682593915711313097803051644 1716682518346573675934198084958947940983292500086389778563494693212473 4261030627137450772861569225966285738579055332406418490184513282846327 0926975383086730840914224765947443997334813081098639941737978965701068 7026734161967196591599588537834822988270125605842365589539690306474965 5841479813109971575420432563957760704851008815782914082507777385597901 2912940730946278594450585941227319481275322515232480150346651904822896 1406646890305102510916237770448486230229488966711380555607956620732449 3733740278367673002030116152270089218435156521213792157482068593569207 9021450227713309998772945959695281704458218195608096581170279806266989 1205061560742325686842271306295009864421853470810407128917646906550836 1299166947780238225027896678434891994096573617045867862425540069425166 9397929262471452494540885842272615375526007190433632919637577750217600 5195800693847635789586878489536872122898557806826518192703632099480155 8744555751753127364714212955364940843855866152080121150790750685533444 8925869328385965301327204697069457154695935365857178889486233329246520 2735853188533370948455403336565356988172582528918056635488363743793348 4118455801683318276768346462919956055134700391478768086403226296166415 6066750815371064672310846196424753749055374480531822600271021640098058 4497526023035640038083472053149941172965736785066421400842696497103241 9191821212132069397691439233683747092282677387081322366800869247034915 8684099115309831541206356612318750430546753698323082796645741762080659 3177265685841681837966106144963432544111706941700222657817358351259821 0807691019610522292638797450490192543119006205619065774524161919131875 3398404934397682331029846589331837301580959252282920682086223033258528 0119266496314441316442773003237792274712330696417149945532261035475145 6312906688543454268697884477429817774937101176146516241836166802548152 9633530849084994300676365480610294009469375060984558855804397048591444 9584445079978497045583550685408745163316464118083123079704389849190506 5875864258107384224205911919416741824904527002882639830579500573417114 8703118714283418449915345670291528010448514517605530697144176136858238 4102787659324662689978418319620312262421177391477208004883578333569204 5339359532545648970285585897355057512351295365405028420810227852487766 0357424636667314868027948605244578267362623085297826505711462484659591 4210278122788941448163994973881884622768244851622051817076722169863265 7016543169197426512300417573299044735376725368457927543654128265535818 5804684006936771860502007054724754840080553042495185449526724726134731 8174742180078574693465447136036975884118029408039616746946288540679172 1386012254195038197045384172680063988206563287928395827085109199588394 4829777564715202613287108952616341770715164289948795356485455355314875 4978134009964854498635824847690590033116961303766127923464323129706628 4113074270462020320133683503854253603136367635752126047074253112092334 0283748294945310472741896928727557202761527226828337674139342565265328 3068469997597097750005560889932685025049212884068274139881631540456490 3507758716800740556857240217586854390532281337707074158307562696283169 5568742406052772648585305061135638485196591896864959633556821697543762 1430778665934730450164822432964891270709898076676625671517269062058815 5496663825738292741820822789606844882229833948166709840390242835143068 1376725346012600726926296946867275079434619043999661897961192875051944 2356402644303271737341591281496056168353988188569484045342311424613559 9252723300648816274667235237512343118934421188850850793581638489944875 4475633168921386967557430273795378526254232902488104718193903722066689 4702204258836895840939998453560948869946833852579675161882159410981624 9187418133647269651239806775619479125579574464714278686240537505761042 0426714936608498023827468057598259133100691994190465190653117190892607 7949119217946407355129633864523035673345588033313197080365457184791550 4326548995597058628882868666066180218822486021449999731221641381706534 8017551043840662441282280361664890425737764095632648282525840766904560 8439490325290526337532316509087681336614242398309530806549661879381949 1200339194894940651323988166420800883955549422370967348400726427057011 6508907519615537018626479745638118785617545711340047381076276301495330 9735174180655479112660938034311378532532883533352024934365979129341284 8549709468263290758301930726653377825593143311109638480539408592839889 0779621047984791968687653998747709591278872747587443980677982496827827 2200926449944559380414608770641941810440758269805688038949654616587983 9046605876453418102899071942930217745199761044950431968415034555140448 2092893337865736305283061999007774872692299860827905317169187657886090 8941817057993404890218441559791092676862796597583952483926734883634745 6516870161662406424242412289611180106156823425393921800524834547237792 1991122859591419187749179382334001007812832650671028178139602912091472 0100947878752551263372884222353869490067927664511634758101193875319657 2421214760382847747745717045786104173857479113019085838778901523343430 1300528279703858035981518292960030568261209195094373732545417105638388 7047528950563961029843641360935641632589408137981511693338619797339821 6707610046079800960160248230969430438069566201232136501405495862506152 8258803302290838581247846931572032323360189946943764772672187937682643 1828382603564520699468630216048874528424363593558622333506235945002890 5585816112753417837504559361261308526408280512138731774902002495527387 3458595640516083058305377073253397155262044470542957353836111367752316 9972740292941674204423248113875075631319078272188864053374694213842169 9288629404796353051505607881263662064972312575790195988730411956262273 4372890051656111109411174527796548279047125058199907749806382155937688 5546498822938985408291325129076478386322494781016753491693489288104203 0156102833861438273781609463413353835783407653143214171506558775478202 5245478065730134227747061674424196895261316427410469547462148375628829 9771804186785084546965619150908695874251184435837306590951460980451247 4094113738999278224929833677960110153870961297497055663016373072027507 3475992294379239382442742118615823616131788639255309511718842129850830 7238259729144142251579403883011359083331651858234967221259621812507058 1137594955250227472746743698871319266707692991990844671612287388584575 8462272657333075373557282395161696417519867501268174542932373829414382 4814377139861906716657572945807804820559511881687188075212971832636442 1553367877512747669407901170575098195750845635652173895441798750745238 5445520013357203333237989507439390531291821225525983379090946363020218 5353848854825062897715616963860712382771725621313460549401770413581731 9317633701363322528191275471914434509207118488383668181742633429496118 7009150304916533946476371776643912079834749462739782217150209067019030 2469762151278521956142070806461631373236517853976292092025500288962012 9701413796400380557349492690735351459612086747965477336929587736286356 6014376796403843079686413856344780132826128458918489852804804884418082 1639423974014362903481665458114454366460032490618763039502356402044530 7482102413668951966442213392007574791286838051751506346625693919377402 8351207566626082989049187728783385217852279204577184696585527879044756 2192663992008409302075673925363735628390829817577902153202106409617373 2835984940666521411981838108845154597728951645721318977979074919410131 4836854463961690460703010759681893374121757598816512700076126278916951 0406315857637534787420070222051070891257612361658026806815858499852631 4658780866168007332646768302063916972030648944056281954061906852420030 5346315662189132730906968735318164109451428803660599522024824888671155 4429104721929134248346438705368508648749099178812670565665387191049721 8200423714927401644609434598453925367061322106165330856620211889682340 0575267548610147699368873820958455221157192347968688816085363161586288 0150395949418529489227074410828207169303387818084936204018255222271010 9856534448172074707560192459155994310729495781978785905789400525401228 6751714251118435643718405356302418122547326609330271039796809106493927 2722683035410467632591355279683837705019855234621222858410557119921731 7179698043393177077507556270560478317798444476375602546370333692471142 2081551997369137197516324130274871219986340454824852457011855334267526 4715978310731245663429805221455494156252724028915333354349341217862037 0072603152798707718724912344944771479095207347613854254853115527733010 3034247683586549609372232400715451812973269208105842409055772564580368 1462234493189708138897143299831347617799679712453782310703739151473878 6921191875667003193212818968033226965944592862106074388274169194651622 6763254066507088107103039417886056489376981673415902592519461182364294 5652669372203155504700213598846292758012527715422016629954863130324912 3110296279237238997664168034971412265279319076363261368141455163766565 5983978848938173308266877990196288693229659737995193162118721545528739 4170243669885593888793316744533363119541518404088283815193421234122820 0309503133410507047601599879854725291906652224793197154403317948368373 7322082188577334162385644138070054191353024594391350255453188645479625 2260251762928374330465102361057583514550739443339610216229675461415781 1271970017386114942795014112532806212547758105129720884652631580948066 3368767014731073354071771087661593585681409821296773075919738297344144 5256688770855324570888958320993823432102718224114763732791357568615421 2528496579033350931527769255058456440105521926445053120737562877449981 6364633283581614033017581396735942732769044892036188038675495575180689 0058532927201493923500525845146706982628548257883267398735220457228239 2902071448222198855871028969919358730742778151597576207640239512438602 0203259659625021257834995771008562638611823381331850901468657706401067 6278617583772772895892746039403930337271873850536912957126715066896688 4938808851429436099620129667590792250822753138128498515269029317002631 3632894209579757795932763553116206675348865131732387243874806351331451 2644889967589828812925480076425186586490241111127301357197181381602583 1785069322440079986566353715440884548663931817083957357807990597308390 9488180406093595919090747396090441015051632174968141210076571917748376 7355751000733616922386537429079457803200042337452807566153042929014495 7806296341383835517835997647088513490048569736979652386958459945955920 9070905895689145114141268450546211794502661175016692826025095077077821 1950432617383223562437601776799362796099368975191394965033358507155418 4364568526166742436889203710374953284259271316105378349807407391586338 1796765842525803673720646935124865223848134166380806150570482905989069 6451936440018597120425723007316410009916987524260377362177763430621616 7448849308109299010095179745415642512048220867145868492551324442667771 2786372821133153622430109182439124338021404624222334915355951689081628 8487989988273630445372432174280215755777967021666317047969728172483392 8410156422745072717792693999297403080727703950135815451424940490265361 0582540937311465310494338248437971860693721444460082679800247122948940 5761853892203425608302697052876621377373594394224114707074072902725461 3073585417456914194464876243576823970657031841684675407334663462936739 8362000404140071405427763248013274220268539369886978760700959004868465 0626771363070979821006557285101306601010780633743344773073478653881742 6812307437660666433127753564665786037151929227684404582732832438082128 4121877613204246046490080105473142674926082692215563740548624171703102 7919996942645620955619816454547662045022411449404749349832206807191352 7679867478134582038595704134661779372285349400316315995440936840895725 3343870298671782977037333280680176463950209002394193149911500910527682 1119510999063166150311585582835582607179410052528583611369961303442790 1738117874120612881820620232638498615156564512300477929675636183457681 0504334176954306753804111392855379252924134733948105053202570872818630 7291158911335942014761872664291564036371927602306283840650425441742335 4645499870553187268879264241021473636986254637471597443549434438997300 5174252511087735788639094681209667342815258591992485764048805507132981 4299359911463239919113959926752576359007446572810191805841807342227734 7213977232182317717169164001088261125490933611867805757223910181861685 4910850088527227437421208652485237245624869766224538481929867112945294 5515497030585919307198497105414181636968976131126744027009648667545934 5670599369954645005589216280479763656861333165639073957032720343891754 1526750091501119885687270884819553167693168127289214303137681801644547 7367518353497857924276463354162433601125960252109501612264110346083465 6482355979342740568688492244587454937767521203247038030354911575448312 9527589193989368087632768543876955769488142284431199859570072752139317 6837831770339130423060958999137314684569010422095161967070506420256733 8734461156552761759927271518776600102389447605397895169457088027287362 2512107622409181006670088347473760515628553394356584375627124124445765 1663064085939507947550920463932245202535463634444791755661725962187199 2791865754908578529500128402290350615149373101070094461510116137124237 6142672254173205595920278212932572594714641722497732131638184532655527 9604270541871496236585252458648933254145062642337885651464670604298564 7819684615936632889542997807225422647904006160197519750074605451500602 9180663827149701611098795133663377137843441619405312144529185518013657 5558667615019373029691932076120009255065081583275508499340768797252369 9870235679310268041367457189566414318526790547171699629903630155456450 9004480278905570196832831363071899769915316667920895876857229060091547 2919636381673596673959975710326015571920237348580521128117458610065152 5988838431145118948805521291457756991465775300413847171245779650481758 56395072895337539755822087777506072339445587895905719156736 >
何も準備せずにこういう計算をできるので, Schemeは便利＼(^o^)／
0 件のコメント:
コメントを投稿