9급_국가직_공무원_컴퓨터일반 2017년 기출문제 20번

Question

주어진 프로그램은 피보나치 수열을 계산하는 함수입니다. `func(n)`... 에 관한 핵심 기출문제

Accepted Answer

주어진 프로그램은 피보나치 수열을 계산하는 함수입니다. `func(n)` 함수는 `n`이 1 이하일 때 `n`을 반환하고, 그 외에는 `func(n-1) + func(n-2)`를 호출하여 두 개의 이전 값을 더합니다. 피보나치 수열의 정의에 따르면, 첫 번째와 두 번째 항은 각각 1이고, 이후의 항은 이전 두 항의 합으로 정의됩니다. 따라서, 피보나치 수열의 처음 몇 항은 다음과 같습니다:

egin{align*} 	ext{F(1)} & = 1 \ 	ext{F(2)} & = 1 \ 	ext{F(3)} & = 2 \ 	ext{F(4)} & = 3 \ 	ext{F(5)} & = 5 \ 	ext{F(6)} & = 8 \ 	ext{F(7)} & = 13 \	ext{F(8)} & = 21 \	ext{F(9)} & = 34 \	ext{F(10)} & = 55 \	ext{F(11)} & = 89 \	ext{F(12)} & = 144 \	ext{F(13)} & = 233 \	ext{F(14)} & = 377 \	ext{F(15)} & = 610 \	ext{F(16)} & = 987 \	ext{F(17)} & = 1597 \	ext{F(18)} & = 2584 \	ext{F(19)} & = 4181 \	ext{F(20)} & = 6765 \	ext{F(21)} & = 10946 \	ext{F(22)} & = 17711 \	ext{F(23)} & = 28657 \	ext{F(24)} & = 46368 \	ext{F(25)} & = 75025 \	ext{F(26)} & = 121393 \	ext{F(27)} & = 196418 \	ext{F(28)} & = 317811 \	ext{F(29)} & = 514229 \	ext{F(30)} & = 832040 \	ext{F(31)} & = 1346269 \	ext{F(32)} & = 2178309 \	ext{F(33)} & = 3524578 \	ext{F(34)} & = 5702887 \	ext{F(35)} & = 9227465 \	ext{F(36)} & = 14930352 \	ext{F(37)} & = 24157817 \	ext{F(38)} & = 39088169 \	ext{F(39)} & = 63245986 \	ext{F(40)} & = 102334155 \	ext{F(41)} & = 165580141 \	ext{F(42)} & = 267914296 \	ext{F(43)} & = 433494437 \	ext{F(44)} & = 701408733 \	ext{F(45)} & = 1134903170 \	ext{F(46)} & = 1836311903 \	ext{F(47)} & = 2971215073 \	ext{F(48)} & = 4807526976 \	ext{F(49)} & = 7778742049 \	ext{F(50)} & = 12586269025 \	ext{F(51)} & = 20365011074 \	ext{F(52)} & = 32951280099 \	ext{F(53)} & = 53316291173 \	ext{F(54)} & = 86267571272 \	ext{F(55)} & = 139583862445 \	ext{F(56)} & = 225851433717 \	ext{F(57)} & = 365435296162 \	ext{F(58)} & = 591286729879 \	ext{F(59)} & = 956722026041 \	ext{F(60)} & = 1548008755920 \	ext{F(61)} & = 2504730781961 \	ext{F(62)} & = 4052739537881 \	ext{F(63)} & = 6557470319842 \	ext{F(64)} & = 10610209857723 \	ext{F(65)} & = 17167680177565 \	ext{F(66)} & = 27777890035288 \	ext{F(67)} & = 44945570212853 \	ext{F(68)} & = 72723460248141 \	ext{F(69)} & = 117669030460994 \	ext{F(70)} & = 190392490709135 \	ext{F(71)} & = 308061521170129 \	ext{F(72)} & = 498454011879264 \	ext{F(73)} & = 806515533049393 \	ext{F(74)} & = 1304969544928657 \	ext{F(75)} & = 2111485077978050 \	ext{F(76)} & = 3416454622906707 \	ext{F(77)} & = 5527939700884757 \	ext{F(78)} & = 8944394323791464 \	ext{F(79)} & = 14472334024676221 \	ext{F(80)} & = 23416728348467685 \	ext{F(81)} & = 37889062373143906 \	ext{F(82)} & = 61305790721611591 \	ext{F(83)} & = 99194853094755497 \	ext{F(84)} & = 160500643816367588 \	ext{F(85)} & = 259695496911122085 \	ext{F(86)} & = 420196140727489673 \	ext{F(87)} & = 679891637638611758 \	ext{F(88)} & = 1100087778366103431 \	ext{F(89)} & = 1779979416006715189 \	ext{F(90)} & = 2880067194372818620 \	ext{F(91)} & = 4660046610379533809 \	ext{F(92)} & = 7540113804746342429 \	ext{F(93)} & = 12200160415158706238 \	ext{F(94)} & = 19740274279805048667 \	ext{F(95)} & = 31940434694963754905 \	ext{F(96)} & = 51680708854868803572 \	ext{F(97)} & = 83621143489832558477 \	ext{F(98)} & = 135301852344706746049 \	ext{F(99)} & = 218922995834555169026 \	ext{F(100)} & = 354224848179261915075 \	ext{F(101)} & = 573147844013817084101 \	ext{F(102)} & = 927372692193078999176 \	ext{F(103)} & = 1500520536206896091277 \	ext{F(104)} & = 2427893228399975090453 \	ext{F(105)} & = 3928413764606871181730 \	ext{F(106)} & = 6356306993006846272183 \	ext{F(107)} & = 10284720757637117473913 \	ext{F(108)} & = 16641027750643963746196 \	ext{F(109)} & = 26925748508281081220109 \	ext{F(110)} & = 43566776258925044966305 \	ext{F(111)} & = 70492524767206126186414 \	ext{F(112)} & = 114059301326831171352419 \	ext{F(113)} & = 184552826094037297538833 \	ext{F(114)} & = 298612127420868468891252 \	ext{F(115)} & = 483164953514905766430085 \	ext{F(116)} & = 781777080935774235321337 \	ext{F(117)} & = 1262944033451681000753422 \	ext{F(118)} & = 2044721114387455236074759 \	ext{F(119)} & = 3307665147839136236828181 \	ext{F(120)} & = 5352386262226591472902940 \	ext{F(121)} & = 8660051410065727709731121 \	ext{F(122)} & = 14062437612212319172684061 \	ext{F(123)} & = 22622489022278046882415182 \	ext{F(124)} & = 36684926634490366055199243 \	ext{F(125)} & = 59307415656768412937614425 \	ext{F(126)} & = 95992342291258778992813668 \	ext{F(127)} & = 155999157148827391830828993 \	ext{F(128)} & = 251991499840086170823642661 \	ext{F(129)} & = 407990656988913562654471654 \	ext{F(130)} & = 659982156829000733478114315 \	ext{F(131)} & = 1069971816812918293131586969 \	ext{F(132)} & = 1739953973641919026609701284 \	ext{F(133)} & = 2809925790454837319741288253 \	ext{F(134)} & = 4549879764096756346350989537 \	ext{F(135)} & = 7359805554551593666092277789 \	ext{F(136)} & = 11999615318618310032403297326 \	ext{F(137)} & = 19359420873169803698595575115 \	ext{F(138)} & = 31359036191788113730998872441 \	ext{F(139)} & = 50718457064957917429594447556 \	ext{F(140)} & = 82077493256746031160593319997 \	ext{F(141)} & = 132295150921203148290187167553 \	ext{F(142)} & = 214372644177949179450780487550 \	ext{F(143)} & = 346667795099152327740967655103 \	ext{F(144)} & = 561040439277101507191748142653 \	ext{F(145)} & = 907708234376253834932715797756 \	ext{F(146)} & = 1466741670651358343123466943409 \	ext{F(147)} & = 2374459905027612178056182741165 \	ext{F(148)} & = 3841201575678970521179649684574 \	ext{F(149)} & = 6215661480706582699235832425739 \	ext{F(150)} & = 10016883056315503210455412110313 \	ext{F(151)} & = 16232544537022085809691244536052 \	ext{F(152)} & = 26249427593337589020146656646365 \	ext{F(153)} & = 42481972130359674829837801182417 \	ext{F(154)} & = 68731499723697263849984457828782 \	ext{F(155)} & = 111313171154356138179622590811199 \	ext{F(156)} & = 180044670878053402029606048639981 \	ext{F(157)} & = 291357842032409540209228639451180 \	ext{F(158)} & = 471402512910462942238834688091161 \	ext{F(159)} & = 762760354942872482448063327542341 \	ext{F(160)} & = 1233161861853333421681890152633502 \	ext{F(161)} & = 1995922216796205904129953470175843 \	ext{F(162)} & = 3229084078649539325811843622809345 \	ext{F(163)} & = 5225006295445745229941797092985188 \	ext{F(164)} & = 8454090374095284555753640715794533 \	ext{F(165)} & = 13629006619531029715615478018719721 \	ext{F(166)} & = 22083197093626314271369118734514254 \	ext{F(167)} & = 35712203713157343986984596753233975 \	ext{F(168)} & = 57795300806783658258353715487748229 \	ext{F(169)} & = 93507504519940902245338312240982104 \	ext{F(170)} & = 151302105626324260203192827928830333 \	ext{F(171)} & = 244809610146265162448531940169812437 \	ext{F(172)} & = 396111715772589422651724768098642770 \	ext{F(173)} & = 640921325918854585100256708268455207 \	ext{F(174)} & = 1033031041693443000759811470361092977 \	ext{F(175)} & = 1673952367612297585860068178629548184 \	ext{F(176)} & = 2706983409305740586619879648990641161 \	ext{F(177)} & = 4380935776918038172479947827620189345 \	ext{F(178)} & = 7087919186223778759099827476610830506 \	ext{F(179)} & = 11418874983101816911519705334211098851 \	ext{F(180)} & = 18506794169325595670619532810821929357 \	ext{F(181)} & = 29925669152427412582139238145033028108 \	ext{F(182)} & = 48432463321753008252758770955854957465 \	ext{F(183)} & = 78358132474180420834898009100887985573 \	ext{F(184)} & = 126290195295333829187356280156342343038 \	ext{F(185)} & = 204648327769514250022254289057230328611 \	ext{F(186)} & = 330938523064848079209610569213572671649 \	ext{F(187)} & = 535586850834362329231864858270802999260 \	ext{F(188)} & = 866525373899210408441475427484375670909 \	ext{F(189)} & = 1408111221731570731671348281753171679169 \	ext{F(190)} & = 2274636595630781140112823709237547340078 \	ext{F(191)} & = 3682747817362351871784171990980719019247 \	ext{F(192)} & = 5957384412993133011896995700218266359325 \	ext{F(193)} & = 9640132220355484883681167691198985378572 \	ext{F(194)} & = 15567516673318687815568133931437281757997 \	ext{F(195)} & = 25207648893674172699249301622636267136569 \	ext{F(196)} & = 40775165566992860514817435554073548894566 \	ext{F(197)} & = 65982814460667033214066737176709816031135 \	ext{F(198)} & = 106157280127359193128184172830183064125701 \	ext{F(199)} & = 171140094588026226342250909006892880156836 \	ext{F(200)} & = 277297374715385419470435081837075944282537 \	ext{F(201)} & = 448437469303411645812685990843968824439373 \	ext{F(202)} & = 725734844018797065283121072681044768721910 \	ext{F(203)} & = 1171178311328201710956806061522010591168283 \	ext{F(204)} & = 1896913155346998776239927134203055359880193 \	ext{F(205)} & = 3068091466675200487196733195725065951048476 \	ext{F(206)} & = 4965004622022199263436660329928121310928669 \	ext{F(207)} & = 8033096088697399750633393525653187261977145 \	ext{F(208)} & = 12998130730719529034050013855511318582915814 \	ext{F(209)} & = 21031226819416928784683407381164505844892959 \	ext{F(210)} & = 34029357550136457818733421236675824427808773 \	ext{F(211)} & = 55060584369553386603416828617840330272701732 \	ext{F(212)} & = 89089941919689844422150249854516154600510505 \	ext{F(213)} & = 144350726689343831025167078072056184073312237 \	ext{F(214)} & = 233440668608033675447317327926572338673822742 \	ext{F(215)} & = 377791395297377506472484405998628522747134979 \	ext{F(216)} & = 611232063905411181919801733925200861420957721 \	ext{F(217)} & = 989023459202788688392286139923829384168092700 \	ext{F(218)} & = 1601257528108191878311081871841431241581053421 \	ext{F(219)} & = 2590270987310980566703368011765260625759146121 \	ext{F(220)} & = 4191528515419172445014449883606691867340199542 \	ext{F(221)} & = 6781799502730153011717807895371952493099345663 \	ext{F(222)} & = 10913328018119315416712277718918634310499575205 \	ext{F(223)} & = 17695127520849468428430085614290586803598920868 \	ext{F(224)} & = 28608455538968783845142363333209221114098496073 \	ext{F(225)} & = 46303583059818252273572448947599807917697416941 \	ext{F(226)} & = 74912038698787036118714812280809029031795913014 \	ext{F(227)} & = 121315121358205188192187061928908236149193829955 \	ext{F(228)} & = 196227160056992224310901874209717265180989743969 \	ext{F(229)} & = 317542281415197412503088936138625501330183573924 \	ext{F(230)} & = 513769441472189636814990810348342766511173317893 \	ext{F(231)} & = 831311722887387049318079746486968267841456891817 \	ext{F(232)} & = 1348081162351573681132075551837311032351630201710 \	ext{F(233)} & = 2179392885238960730450155298324279300193097090527 \	ext{F(234)} & = 3527474047590534411582230850161590332544727292237 \	ext{F(235)} & = 5706866932829495142032386148485869632737814382754 \	ext{F(236)} & = 9234340980420029553614616998647459965282541674989 \	ext{F(237)} & = 14931217903289574615637083107113329528020386007743 \	ext{F(238)} & = 24165558883709504169251650005760789493302937782732 \	ext{F(239)} & = 39096776786999078784888733112874119021323323790475 \	ext{F(240)} & = 63262335670708582954140383118634908514626261573107 \	ext{F(241)} & = 102659312157007361039829016431309127842149185463582 \	ext{F(242)} & = 165921647827715943994969399062943036356775447036689 \	ext{F(243)} & = 268580959984723304034798415494252164198924632500271 \	ext{F(244)} & = 434502607812439247029767814557195200555700079536960 \	ext{F(245)} & = 703083567797162551064566230051447364754624712037231 \	ext{F(246)} & = 1131581177608602793093331040602641568310326791571191 \	ext{F(247)} & = 1834664745405765344157897270654088933064951503608422 \	ext{F(248)} & = 2966245923014368137251228311256730501375278295179613 \	ext{F(249)} & = 4800910668420133481409125581910819434430229798788035 \	ext{F(250)} & = 7767156591434501618660353893167549935805508093967648 \	ext{F(251)} & = 12528017219834635120069419415018319310215747882705683 \	ext{F(252)} & = 20395173811269136738729773308185869246021255976673331 \	ext{F(253)} & = 32923191031103771858799192723204188556237003859379014 \	ext{F(254)} & = 53318364842372908597528966031390057702258259836052345 \	ext{F(255)} & = 86241555873476680456328158754594246258495263695431359 \	ext{F(256)} & = 139859320115349889153157324185184203160353123731183004 \	ext{F(257)} & = 226100875988826569609485482939778449418848387426614363 \	ext{F(258)} & = 365960196104176458762642807124962652579201511157797367 \	ext{F(259)} & = 592061072092003028372128290064741102998049898584411730 \	ext{F(260)} & = 958021268196179487134771097189703755577251409742209097 \	ext{F(261)} & = 1553082349288180513501893381253441851578308309328621827 \	ext{F(262)} & = 2511103617484360000636664478443145607155559719070830924 \	ext{F(263)} & = 4064185966772540514138557859696587458733868028399452751 \	ext{F(264)} & = 6575289584256900514775222338139733065889427747470283675 \	ext{F(265)} & = 10619455531019461089113720117856330534632957715819764226 \	ext{F(266)} & = 17194745115276361503888942456046063500522385463290047901 \	ext{F(267)} & = 27814200646295822593002662573902394035155343179109812127 \	ext{F(268)} & = 45008945761572184196891605029948457535677728642499860028 \	ext{F(269)} & = 72823146407868006789894267603850851570833071821609672155 \	ext{F(270)} & = 117232192169440290186185172733199109706110004064309032583 \	ext{F(271)} & = 190055338577308297976079440337049961277943075885918704638 \	extjson