18.A - Factorial
Time Limit: 1s Memory Limit: 128MB
DESCRIPTION
10.9절에서 소개된 BigInteger 클래스를 이용하면 큰 숫자에 대한 팩토리얼을 구할 수 있다 (이를테면, 100!). 팩토리얼 함수를 재귀호출을 이용해서 구현하시오. (그러나, 단순 재귀 호출로는 fail. 메모화를 활용)
Using the BigInteger class introduced in Section 10.9, you can find the factorial for a large number (e.g., 100!). Implement the factorial method using recursion. Write a program that prompts the user to enter an integer and displays its factorial.
INPUT
* Line 1 : 테스트 케이스 T (1~10)
* Line 2 ~ T+1 : n (1~10000)
OUTPUT
* 1~T : n!
SAMPLE CODE
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
input.nextLine();
for(int i=0; i<T; i++){
String numberString = input.nextLine();
BigInteger bigNumber = new BigInteger(numberString);
System.out.println(factorial(bigNumber));
}
}
YOUR_CODE
}
SAMPLE INPUT
3 982 1545 6215
SAMPLE OUTPUT
469334317148140749406216870023560953789663822582271786299082889560691696445697736463821802727779314513374790647293188217378707774562420864093777845401759818042912689948164964965995287226497726220071245527064879140348338375599217212380324258834313929901107986429302630808956042118313325315001764013959815219122259665863945336494074249282300466718302998900231276347656536940354217005805841560061199723456138056217059972902654750275093419369145780426261563747423944125447207001852418310116482841716472049404993455323879061996844384482163973453328875145175175828673242223055553083128205142506556761591161703380354266996133570370455764379981525291662707763457956839134829681191257375699147694255944136333556337688982770495144778355408823751312515977384385838176470285722114989109587562075217818758072839993809127937431593362578071758228050785841944337650209819856288052980765171609046124534746883534293354732607995850174590148759941498532551648137953064189066965669809578687751794669681425760676619196653370063406147828637124532652849161554887146427359166851098603214466843092837349084782609389958692942742935511665596677304967968948852525771020356172041830534631985565843936616746389029853784839463051273299778608137072645564377416853947286086004921617751894535081393895594242648748377360869658851466759476809418457989016444441885480409097871637092484831224722379522218568104986531090024756343963080505537926908574224751880431743969593685650121402395829216589540588767031722800156650816793054478128935323157771034868255256968906202160019828177697993102847702977562246570386643204145997951843434766395367992026522219190849841438075992353680649253993883553363282744843231360881003422640043976538588382690846225686000185484163260675151356457418229864589253499218145376640126850816974398767134971510630899128320567231809590890081562010430596997228832398634482504368631792690477895513164004547039775617047324383362411865085658659889361543004097754433808531919944082619735934646391531879752232712074362412039396208972419949902958482421062347219435719674847788108002254791523069424007929462617592730724638222228045572209501867447271795330690912572107972385102431352086804240832150290450574543195707122716957539051835525444324769999798764167163313910943552253493490492249610983047168000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 8000377334273947734117443819851025921792659710000122064176440286787261948640171562194018750653137957677543860591065069093955258074072090240945991175066525076352651851733230477022578878263163053006959554620820234426877244678049274479262665752274333734737304850462693658221404837312737627840500493719509929502716556775833280687551715827451691900233061635492146196401105908781161718491701470043622081021519770122212391661579750188761829071472026586182770686819086918018920477221334012491570802824439976845027826375179950201488045636463565501026490193965395139784126299994516474118161976152989531591838801855275539193173054374236300790330945635400585336638734380292286308189401326715175414999973547424014631524480822126398550112872185507898738249051103102228029050283038657984965514779081392234128854409055457852914009960799682755083775358949394596643822966410584191376978557049619380273254868271075608413781577734500549886834536644725361209427042406747989607871349750915886607260855431839973563262895547464107283149943309419912487226538995575277008047494337447786699166926689048137317788477265067797975177143636398059651982868355465009826272055466963136756469203718906431556639338974186790959848446969731613956163456453246056403229981926739629612609461050137814351115988484663672535136882964032734659175553571174899213309957700548579804994733801049001941998859928045598019682260332349901979816150153633300298635598208774490564022651420355129307863079829467599100626933068312404366407565341237875454648832943075781483199555071013853154799864675788738760181509543440865660991431543727520466396393581877293862854456951546571294154402464841305683670886491786336081229532448025622790043046694867988300737665032452204611617199353764397814839903626529870225507318000067048463455439777657249566442981221581266659636356682788764575346868759404577119975541835833877290165822488305184571124426415006279994240155941501339098031580054612496610680617269878322277157415592704132007475386472809107361656113837146135435927582773394170236927310622009529061839730734051324383653091095332224872404786932421403803753147130901972879825453316203140379555479900267956153257698875415711670245231540284260231056074830693626462689782729839596292156337906432941513715088567034977263979622900543502913454082971494142466430115373982620421058516069368576544144379587433823436446749912800712223427189503511486510482205383995975256819702776978119964112916029729683276203109606192988572757899498196383826303978852848583612500093285171850939819201684317174713464677126237807051826359159029994704631877980530115517147813781213536290681996448462227377652904919960297935365397466918079990634644892603454187759423708935415817918331579527159093129612515714491068746996823521722404021629298950168925332138811026918030112127176918270724069407762578417168676463194074657257956893915130547387777058254292454406889591310225450970646929568908282673514789865707027366559757530359729839241277332382756816831202400593893172360527345939702844808180938450296199686661546751886356448230434702179712037984265840419487924692460952670325149413655080262348529379641258750004062373902668452067156390593087844340186724206028089128037855599882273234354990412720160762665461846499039216769391887329862825189036910840430514341906940550334290946631202028527986597929638394126912540070186227617422442459242104652736888452913953433345395441490012841816059294646327692696769561146854564575004169978797860057013807754777335949935118802015427175514595003900726519820463660837399134606155792485422184248744007050299226679579712362203453003519504139154909082384611417520803841463131324610129599721360929308411704537674400552354720392435499541113765932779691859585016108640351936856125672506439839560761558341288872199291218216127304267232973462129205469217169968070254520968978182456146658772668085302367433816333170840685125952907549586023776256000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 246747494413438651961798341410478513165728687971840842388909092631184889108601402676169553822473219007299445101085491909419365767583476642631765506136463451860112267675889818239818584010453666386807194464528157286193473158663676107952249721933068902272872598723307111539919284922421247357755181764916834494680197749384642929042191885992150353969862801935171914830855803940225143615500608386742367088295659939535550026605997907364850575475472607861048344079050482491955450292123719561179479371607112471245382546732798455398315291266811033888054458127224190881787601187871866239038549572434764568521652354211989839149263119479829256212103879118637371075662672712842043977113856252071612140224590297359066578281203043158136273854691096463258555656828120464908296466407923194486666530374691908060729814632917317740633111395914636375315429548643779010565239793773312409896673934944512343246375413158588643436911989505170419436045587706462340768754488248006140427226102065074852898209767502750902168968648613365154749773060487820136680998613755440770976128773921394075324776454571307658694061872036398104435713217005507495525875575626722523507968055518613360437258769513812731416480384918730921320723885058866686226457928715624885698310607076010590698729593422646210621753482753375764617990733813343893902190541127721608015820623284127121422340913407521994239408466304155024822906471595803460709687823521468740643273934389802569318889206319470008854111382092568138728735939204776035566811996214145317994137322336806280152760003471992299600092671207585194854932454765275363603497853465034681642520694881555790364893648560994677639618041718511373337396448800595464905862595906019418938283238143790308709491629084520999652708092396889846650549892426543976496869638584891640527795852862664836921412228521095124862857722030363200488969752802632433904571586966470839577507877672332380418261586138303296494577057059974685975463762900421637823825048708964340409177090786312555348235237950465996748714386038744315531500516637204208600979198906079598404702651829800447364491032814922069931495846624416853511795253562024395542666106795787605060224822661354267813418316354795023696301638498241106774694458630505093238989546613716445287987693293565164093669988341251676448504782854466691241042348739868259255855708444191395732728509866470732269511478638415535504233455876148984663903827193056327958796676395631432176409260586653231393383459378155478314477678529066856496172295009237200680358431759149334491296929561226119864715511739770143502161518256370389085401695204902134520452546023519046104150309442144943454605193352071698109702149843809737247341963865179553557487269751946708347984864344931027259394884614248078834648982249104371690852938826194909061886316996610656619542947122060975867747217280746130112573544562742038408541382364725319254373084852171331363477303428517515449305631881518565187765292299822862750153588198299425524480979631393387167108644854298632954336535586653752692211219203320225951977127946314045796695982792743383024997921187154795073667812279200427062740354835034703348780671757981563476425749553589390380215344596487287579105402002673264168680179260573759688889185942840281610486078059678773675476215341435126259093422608948641590071482750893796214013293586223137982890055750091137761756814401135650898249683901419578334732927864164281943997434052649801244199405098962596251195665782376313886260667394481770747475780553162081670804414150628604169707204108179469786991873618294049073696891435172063613407332568830977884422112264140485704382048013461767199122976827946382984448661789476701921347098685169590502292649586524149866342656531423859904957584686861727159738983127276042241479299537891603746447596858999013102023170648049975308381187962910463469629840666723448751281037710798059202780519914530004840403496200404389599297237670991292518027708698830020855704063324644922633985794558276110664737669558379836774382072968499338615577639909532747787222891046760143626051764196505851251328765512181402126752419118607246553410959253945766125826604761887862114256390401734419474810254091163859995690250510827984621991895590708783763697584000301126629632018037854520483959933975165969293136063631787598471793166838563415309127187348281963692728105572390907296218895512369754964463207223997189601087949336706165224758355742064443686152773289965711818610231670299780668996406868228020122744588677837394464587858871253084605832118033386466174239798091211632308422831480890860013318269344924430196181231571330022168177853667937936421783858375099089984122965598972415307207977801679052278332066695899811812755984311700373975507456822177605910927226234198313740712099635971165219606707755924198256960374671538912861983034213435717717893978834574348018218725889435095687385939187678505714006119580755018877938549199159156047058304248854618202153919332876717146921568482829638077826574307878081091234893210699717483841828438336715375356283541483205901404963568672902334238498234181516594497004311552393987907777250704027858054765525925587329977513459105062272898583194717984345267837270273952155222075322198946932996233128714809468084248532372137469106099102015108535347718824266025528061214147009217300034977281027713250817664137048278077263710737223670098136471170368157436152951957886047233988761992286067904869510237097806736915710568301348116069214511275382441063661313054644640017014874383743465747922184479105948018948384231074769117502242006349673823143371160800324108578608267727212148342793583904254420991235840570424529442617148516738383194709199372432685189682073032691288621259553539379020348490732860417859712244433051229739674587147896247392395709774537389833598577295713765326498149329858422691677909727508229986928125456900299711803773392720073449778183511480764478281467131119812117103165945084390583038806116121492663874439139474965781102429761766964378659275878944076931110774653806392885917176784614487960499900626816304203776405345068898675580902906690398272954749942399596064932730484528484575738498520925551297633085203159832712808307062115638960280747380720564357292712574357089599046258499615442824599238784483892626546270414517630421746413754341037372986464201316505435400681802308183989704949148723943373245817455291660783215882671848883368216603666600403379826747457304800395232479762938390221587261265854942544856141691635576775405646818755217519262009294136678580218482657806375231873525807110487277158675877690706626977492360302116573443154062520396986546930805658080978619568577906964815194269749685813871845943417434958412604296030904171771927414214940245533969815333842616755792670166942007931512671375826067549601674178213288864205831740890288295747098665196812047790653990925115777192075917761420023051805086304047895758039943890964006928409006250278247795842563744792653420153044735446844482874614966775779116417798369208860871383901159289854921882029869877997985626375159426706173352222335157529399818594913416833152522829108199462919527222662245799944899600410318556171129427343467848373646436825340137082098853137486315585814204905438381988182083638840780347456361636739783452016050850774507187322923743958636751065329384556259284651117491622754517740396614480537076694262255893995182826105604458645117299409013455234278133627325942373552993361094008535773890252445590430108525206988211668348360446829353293935663766321316125980829288428969400838915959049389041130751914374980374378144114207630384801354875021298031117363272257616385644300085989430119600255589241215373639451272149177758077320016950405773000258485138810293128251572635322288468237431549999239134372135778081562778956597265678372229904369036350046146259569946798744286646537745669398272646564602132960540051748815073045916974919964569011395629761041355195698511934562414015875738807985138245604340823986008465177205434972437451499685533319087579163854739825581909928899240153872197811247792595862588873121872910090704138934668849768792330927147654126429793287414868675502131801864955213267189749917229301235368347420533835617106820562946142491976525856955533204354213193037160195504398863502091377723354140938400296718880845220728984712267761490281023549669185720995836144767839735793145382537990361772534008756141704822525004262898844453050775942956020916298085420840165814854930928174275401734292576717192481233524717197022260777717068513699712315248411689938736826068119072362880757094910955518550319266125932014354378037414029642394482392813388198889571598260196111343921532794693240955614566345760238295527564903824180712130709672070459187467900212342707706715613610405250745635289150176882885774901699056886321549796484878977241172890773331231907889403529015632905344812450810419253532522474338046041821635806606827563164913547161066815925880623375565694419958427150663963774504267081081592309328268944832870684439459181647645203786879697639865796356434681258141564029749944094997141038299752580084454198447756130626558942808673259712335150209623482026882059125209212895504150413414579408174610139409295754444715073134590191765948976305268809021424689168884465318805040553058918469493957488463298318781240279359589496807092109137146386065288636816614743256098332133337167578404184504379896954397540818983371513011929561493442288605518951663566842515043382438402081476218149435180473740838551198021670866039144734762633730406336670364945130781208348169433499775650865956103436677459135521334131409206657474911237469954139991850730488452319124698701611842553492040415116793731928046927131342710999225957894921397716163391409118127684505643453768847084801493577464003530931066743337441879368335577527856940892126394116709021282892537688797674976077461130688586077345219274017832867889877191303659435099195775264679283073026742779669485410417210348822587742955890113521910183438518765375809146458033605116630822800997644632788112303493271570477507773426689659047243800924714315192205665934355658969637107561700154048844309827129541768508720456512225053038576365808910062733397614978909338751754130700740805382143396069627175990343548780555305789500828061275699879603587089063332959032448424438988494172229566961158671645957661526654519584341042383280824010947565615087620141842506554394261808938968641487437021677017207952876524728335677683743234148246069012523987370227568523408771703392951055403594954279864257831255840563201199396934313909648724325398177278196991361771274445162291453967343844835313314956802499703765418560116538186194534894209996630906533086448410459160400794117046588648080356208699064939398417415762943997900249900414275984966889511555745649803790385784816377061097460323455512437398292535786064834329368255059557379614943689694162723104672730715945157592659076014742017211096089446176627828622754726709154789928520340386307976890236087730377483356344481444186784218469669657213811070091102806885814995707522673696777975858228889058998533616545726250823842194465515088314848587331259126199332573931995725012124596660599072096349430180275021667671598432964357253395664275680150106846807147749319144450906225988842850790093868231796356977759012726032728143960589865197426497600606377288271396599819936520165769556795912445382689995249094743643267762929787973976034778467633824852037838977617480113559236770026659521385721319454162105976235684884970438213194028448000601089417157903309683089162583875647411825125103055913811679815537174750487002909530171510511396646426229745614121359479227055560587397039257059961790829906613504135231460437418009105562812532608642995856766973007146101800600545414025837791734480707778145480084004250299818082524364796548869527650189195465867529552175498671467783511760521382930098919707248206149792609519381460179231220352946433875154110275282319871496655768141924104763720017863096240292553215715148182734702934304323044518905450813982664435462734727892442185064250846188632870039970319168521336720869675884841310701149797817595487508446765748246703722282061395605680602503734653728237954203885378430448838686543651440008004903014366666093517819396821806918596829625312190740913001982464302859480294363658356258985986493144613362473380786947170717328024871459276271664166164869304445100051330859959362471232393832804876537267083098772564763624651238325036886458217433458369055519432305388509978106781118787149020637224865844768674780191104918802796711554591544214587667035979551663167202287490133271395906728382150851184321367387460466140485060487679413625902012143252088024285429795050953300140125214804363573321661205160782282161366190470818670414115449349385898486722664095270954856343601619578855840625132274978616740941538125955852766867210211713762291350497245347705502777643053492075151773185318904776324661979463298509083685138745357294751069359365194722179045030596134825227885648823400304178259361966100403774186757332831610871569450891992090260881906708879587355134738290939425570855150468430878377023050108615665579673867500900966659436777554367236399493531073084496691747537064816170732035791574467067954298668894541458493052930472253953751435807687839004530238202221997521886589750634396589955239691729917392119029082516040894063837696223399464534445797765136120602182207123458624657802810209729757079317517328644845810250796959234884023175569891066973905014425226904895423718218507551360124949405477013954608556346732232273153617211960803578229502872160918577463803170069981518528412452715268469763409959375524302065542520060107727964096724179335843876684318855345440370300442378786278316178016020953147003099858154870675770681276034736842851806247240984156778569559685979371020919540348487491613072059714597135263180865915954193646312408959644530665619427575723337265748557798061028870435400010139865903933010491828970997078059423779795637227276313232094927639684407497391489967177851588892295610354858813627243628832687576649702578515190149341264258775936793347746072267113908341706766236238348147466962156754096666846871257342883918992665559433275939647081530779189607790452155320706248253322452070315967579567783155654970970937077066068367779592178861844130538470263660758669017497349275449495138081820387700076375412719121737931983184397827645848337879450329423760230850785337944499700323863654722391796324255027316353942333574552526601066276050046580909540146564747193688340261157573199185934668109395157495598873316010675718651807935321807099565814807094307457913588884743432046369693217591162922971812725074264770063481503205752326866221869471116223039849418940318061005077396737077888840857774298899978286453706114441352071465775315110041633528131919449766657956719199611329617404223887618937016024120556603925397233323482691666855376793091207553423011641906966494822217855245542925950401689288681419247976172538248445861482659543986822559921928816783263815808122310989609907499716040789055259435790101205439910370997949836362114094839335345486954106959137670401352135415960478929594116367602594678699447109324062809300315844721267870033024567157843485244414315352892237029175315697368290577119216813783571993421906516181978930607829285160868296228897307272051902187660975919974085945140339167549945595113618469419041782284039463784149273014737821355255357950597929643438605958401308680623735815016673680542628798176959572715570357386884994038258320526787092889611313511774035001860350489181301744888678902664844695321650809100659913707230706904533196127231668401334480244319119460390668480757970685152413673873308844940782643088217031933928307860326359215963028010072234894705181220437640112591208011565412722810292027198766582193182249054747982954260512920888763616017221804591032191802203116479257678902536826211512226750875122061460577311189192542714169360836155501489618287722225640805754919731878972678828781821342517436039735873989067390420619260137527048173208760338883698582112734835111315133513344808590896514514486938494543795841533987935351642812356286132552711621560129612440348462367250780976515342753923443377878874287508017955480962620786559033214763723950196192048279182135488535753423600569872958359281170095431364997299998730390703734401976926067589017602383810912359298742393634532796660821464490949563216602381789391813187369166522747692689881880105125464256550669962817252964430968405689586767778718705032799419275724213941438192566866970216516635470780839144840667271726952864277226197872393787315989573241161271537273814771762547745381894987921332707682863347273893943423694149968852057216903210826140578639084179316682675094869155361135731369230618486134495909095050831369648771733550248385894789134710236738242233009712517297172001661036744347672229768575861109256410877237112564386072880554870898966774149037962661293557931376357667948173383716019748791785974291339864075891898250096805001992960658103473194647832425225639198886216726721211081907648444834083117891796523728138676375489626058516081610784180547932318928471395001583533088763895515441854274797297370694132331013416799269362427873545359645495458225617461069102786276865012014223970650260479191274604374183374141153498121727519468865150548552274722696206007634229809512222382861843817280279736234377482527335392984754717934469793352771362737146490981846260565375952488303841047694695001756796509013977156145101059003200750358230758395725765667088226462576457551169281580468621743027417435949358627186967241598472067042733183151140289099367940092084675896651503974470032353804611986969327220158651383851299647421752188514083209318664285774469271920170072241996937011002825613173216702151649999611341233407641361623399027409663516081284302893203967901643524287963046236763679840464906336460820092771576608949179490369560959172023803762121604537367480484454904813020571465575742167621771758297285588855780348124532628504375656267081524502076034450462453363957711423588564462359410967926129108254423738403169442962275313525090211150193152351753655320647462240059975524421967593395775474556909282436434768819792715421583046680529614081456106525995079634683099418509035139178267219932185253244635431462290992591538746689988757498385171283396181200109164354671626081737459054748676909257343535143447845914178339935485987786968424023853665499904458871096528510206968688488554809003023302634934661995576384412984644186040584904620134000331905339769671133648655782066212730857176672035329284056747345917084944700530653194430502696091705976574066958778759621388225888548018846210163747019389980467612464592848597117248618695639829210276569429620795957818158689306812335402128430790675507463182721856549198214754989116154033533659598310552791290593882800988094702448992894438801808070307049851850195267989691130483421110802879839277281985323874241668806764859225125410161803132306235945509452724402664282015328117123610009898983664646040344412148439748875511366459409227928226655799221851754434885674148486582518655637878205448377951277968732829875601637289704005258417834787847555648483819757359335789498323477968006653253642075967192018158060615413447524554116788891801582755182791156670714173012487803497754979736256055276809697876269405745078990359671824842557889850621222947751607946274060795438648599347917652671137920384914890476689089020665918436326492744007539167248829401443587333471435766378509883316985180911390828045034472612356238423369823751490637151629629084171459536151406052483342515069864981892600158973342676957874342712338983617062702048870400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
input.nextLine();
for(int i=0; i<T; i++){
String numberString = input.nextLine();
BigInteger bigNumber = new BigInteger(numberString);
System.out.println(factorial(bigNumber));
}
}
public static BigInteger factorial(BigInteger b){
if(b.equals(BigInteger.ONE))
return BigInteger.ONE;
return b.multiply(factorial(b.subtract(BigInteger.ONE)));
}
}
18.B - Fibonacci numbers
Time Limit: 1s Memory Limit: 128MB
DESCRIPTION
(피보나치 숫자들) 반복문을 이용하여 18.2에 나열된 메소드를 다시 작성하시오. 즉, 반복문을 이용하여 피보나치 수열을 구하시오.
(Fibonacci numbers) Rewrite the fib method in Listing 18.2 using iterations.
INPUT
* Line 1 : 테스트 케이스 T (1~1,000)
* Line 2 ~ T+1 : n (1~20)
OUTPUT
* Line 1 ~ T : fib(n)
SAMPLE INPUT
3 2 9 18
SAMPLE OUTPUT
1 34 2584
HINT
힌트 : 재귀호출 없이 fib(n)를 계산하려면, fib(n-2)와 fib(n-1)을 먼저 계산하여야 한다. f0과 f1을 전전항과 전항의 피보나치 숫자라고 하자. 구하고자 하는 피보나치 숫자는 f0 + f1이 될 것이다. 알고리즘은 다음과 같이 표현될 수 있다:
Hint: To compute fib(n) without recursion, you need to obtain fib(n - 2) and fib(n - 1) first. Let f0 and f1 denote the two previous Fibonacci numbers. The current Fibonacci number would then be f0 + f1. The algorithm can be described as follows:
f0 = 0; // For fib(0)
f1 = 1; // For fib(1)
for (int i = 1; i <= n; i++) {
currentFib = f0 + f1;
f0 = f1;
f1 = currentFib;
}
// After the loop, currentFib is fib(n)사용자 입력을 받아 피보나치 숫자를 출력하는 프로그램을 작성하시오.
Write a test program that prompts the user to enter an index and displays its
Fibonacci number.
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
input.nextLine();
for(int i=0; i<T; i++){
int n = input.nextInt();
BigInteger f0 = BigInteger.ZERO;
BigInteger f1 = BigInteger.ONE;
BigInteger fn = BigInteger.ZERO;
for(int j = 0; j < n - 1; j++){
fn = f0.add(f1);
f0 = f1;
f1 = fn;
}
if(n == 1)
fn = BigInteger.ONE;
System.out.println(fn);
}
}
}
Wrong Answer0
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
input.nextLine();
for(int i=0; i<T; i++){
int n = input.nextInt();
BigInteger f0 = BigInteger.ZERO;
BigInteger f1 = BigInteger.ONE;
BigInteger fn = BigInteger.ZERO;
for(int j = 0; j < n - 1; j++){
fn = f0.add(f1);
f0 = f1;
f1 = fn;
}
System.out.println(fn);
}
}
}
18.C - Tower of Hanoi
Time Limit: 1s Memory Limit: 128MB
DESCRIPTION
(하노이의 탑) 18.8의 TowerOfHanoi.java를 수정하여, n개 원판들이 A탑에서 B탑으로 이동하는 횟수를 구하시오.
(힌트 : 정적 변수를 사용하여, 함수가 호출될 때마다 증가시키시오.)
(힌트2 : 하노이의 탑 원본은 3개의 탑에 대한 문제입니다.)
(Tower of Hanoi) Modify Listing 18.8, TowerOfHanoi.java, so that the program finds the number of moves needed to move n disks from tower A to tower B.
(Hint: Use a static variable and increment it every time the method is called.)
(Hint2 : Original Tower of Hanoi problem is question about 3 tower)
INPUT
* Line 1 : 테스트 케이스 T (1~1,000)
* Line 2 ~ T+1 : n (1~20)
OUTPUT
* Line 1 ~ T : n개 원판들의 이동 횟수
SAMPLE INPUT
3 9 20 7
SAMPLE OUTPUT
117 116515 31
import java.util.*;
public class Main {
static int c = 0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
for(int i = 0; i < n; i++){
int m = input.nextInt();
move(m, 'A', 'B', 'C');
System.out.println(c);
c = 0;
}
}
public static void move(int n, char fT, char tT, char aT) {
if(fT == 'A' && tT == 'B') c++;
if (n == 1)
return;
else {
move(n - 1, fT, aT, tT);
move(n - 1, aT, tT, fT);
}
}
}
18.D - 문자열 순열
Time Limit: 1s Memory Limit: 128MB
DESCRIPTION
(String permutation) Write a recursive method to print all the permutations of a string. For example, for the string abc, the permuation is
입력된 문자열의 모든 순서를 출력하는 프로그램을 recursive method 로 작성하시오.
예를들어, abc 문자열이 입력되면
abc, acb, bac, bca, cab, cba
을 출력해야한다.
INPUT
Line 1 : 랜덤한 길이의 문자열
OUTPUT
Line 1 ~ 길이! : 각 문자열 순열
SAMPLE INPUTABCD SAMPLE OUTPUTABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
import java.util.*;
public class Main {
static int c = 0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.nextLine();
int n = 1;
for(int i = 1; i <= s.length(); i++)
n *= i;
String ans[] = new String[n];
print(ans, s, 0, s.length() - 1);
Arrays.sort(ans);
for(int i = 0; i < ans.length; i++)
System.out.println(ans[i]);
}
public static void print(String ans[], String s, int f, int l){
if(f == l)
ans[c++] = s;
else{
for(int i = f; i <= l; i++){
s = swap(s, f, i);
print(ans, s, f + 1, l);
s = swap(s, f, i);
}
}
}
public static String swap(String s, int i, int j) {
char temp = s.charAt(i);
s = s.substring(0, i) + s.charAt(j) + s.substring(i + 1, s.length());
s = s.substring(0, j) + temp + s.substring(j + 1, s.length());
return s;
}
}
Wrong Answer0
import java.util.*;
public class Main {
static int c = 0;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.nextLine();
print(s, 0, s.length() - 1);
}
public static void print(String s, int f, int l){
if(f == l)
System.out.println(s);
else{
for(int i = f; i <= l; i++){
s = swap(s, f, i);
print(s, f + 1, l);
s = swap(s, f, i);
}
}
}
public static String swap(String s, int i, int j) {
char temp = s.charAt(i);
s = s.substring(0, i) + s.charAt(j) + s.substring(i + 1, s.length());
s = s.substring(0, j) + temp + s.substring(j + 1, s.length());
return s;
}
}'학부공부 > Java_Basic' 카테고리의 다른 글
| Chapter 19. Generics[Java Basic] (1) | 2021.11.06 |
|---|---|
| Chapter 18. Recursion(2)[Java Basic] (0) | 2021.11.06 |
| Chapter 13. Abstract Classes and Interfaces[Java Basic] (0) | 2021.11.06 |
| Chapter 12. Exception Handling and Text I/O[Java Basic] (0) | 2021.11.06 |
| Chapter 11. Inheritance and Polymorphism[Java Basic] (0) | 2021.11.06 |
댓글