¿µÀç±³À°¿ø ¼öÇÐÀϱâ6

±Û¾´ÀÌ »õ¾Ï

µî·ÏÀÏ 2009-05-27 09:58

Á¶È¸¼ö 10,366

´ñ±Û 2

±ÛÀÚÈ®´ë ±ÛÀÚÃà¼Ò
Ä«Ä«¿ÀÅå Ä«Ä«¿À½ºÅ丮 ºí·Î±× ³×À̹ö¹êµå ÆäÀ̽ººÏ Æ®À§ÅÍ

À̹ø ½Ã°£¿¡ ¹è¿î °ÍÀº ±× À¯¸íÇÑ ÇǺ¸³ªÄ¡ ¼ö¿­À̾ú´Ù. ±×·±µ¥ ÀÏ¹Ý Çпø °°Àº °÷¿¡¼­ ¹è¿ì´Â °Í°ú´Â ´Þ¶ó¼­ Àç¹ÌÀÖ¾ú´Ù.

º¸Åë Çпø °°Àº °÷¿¡¼­´Â A¶ó´Â ¹®Á¦¸¦ Ç® ¶§ ±× ´äÀÌ ÇǺ¸³ªÄ¡ ¼ö¿­·Î ³ª¿À¸é ¡®ÀÌ ´äÀº ÀÌ·± ÀÌ·± ±ÔÄ¢À» °¡Áø ÇǺ¸³ªÄ¡ ¼ö¿­ÀÌ´Ù. ±×·¯¹Ç·Î ´ÙÀ½ ´äÀº ÀÌ°ÍÀÌ´Ù.¡¯ ÀÌ·± ½ÄÀ¸·Î ¹è¿î´Ù. ÇÏÁö¸¸ ¿µÀç±³À°¿ø¿¡¼­´Â ¸ðµç ÇлýÀÌ ±× »ç½ÇÀ» ¾È´Ù´Â ÀüÁ¦°¡ ±ò·È±â ¶§¹®¿¡ ¿Ö ±× ¹®Á¦ÀÇ ´äÀÌ ÇǺ¸³ªÄ¡ ¼ö¿­·Î ³ª¿À´ÂÁö¸¦ ¹è¿î´Ù. ÀÌ´Â ³»°Ô »ö´Ù¸¥ °æÇèÀÌ µÇ ÁÖ¾ú´Ù. ¾î´À Á¤µµ ÇÏ´Ù º¸´Ï±î ÀÌÁ¦´Â ¾î´À Á¤µµ ¿ä·ÉÀÌ »ý°å´Ù. ¿¹¸¦ µé¾î º¸°Ú´Ù. 1°ú 0À» ¹èÄ¡ÇÑ´Ù. ±×·¯³ª 1°ú 1ÀÌ ºÙ¾î¼­´Â ¾È µÈ´Ù. ±×·¸°Ô µÇ¸é

1°³ÀÇ ¼ö- 1, 0 2°¡Áö

2°³ÀÇ ¼ö- 00, 10, 01 3°¡Áö

3°³ÀÇ ¼ö- 000, 100, 010, 001, 101 5°¡Áö

ÀÌ·¸°Ô µÈ´Ù. ¿©±â¼­ 2, 3, 5´Â ÇǺ¸³ªÄ¡ ¼ö¿­ÀÌ´Ù. ÇǺ¸³ªÄ¡ ¼ö¿­ÀÇ ±ÔÄ¢Àº f(n)=f(n-1)+f(n-2)ÀÌ´Ù. ¿©±â¼­ ÀÌ ¹®Á¦°¡ ÇǺ¸³ªÄ¡ ¼ö¿­ÀÌ µÇ´Â ÀÌÀ¯´Â 1°³ÀÇ ¼ö¿¡ ÀÖ´Â ¼ö¿¡ 01À» ºÙÀÎ 2°¡Áö¿Í 2°³ÀÇ ¼ö¿¡ ÀÖ´Â ¼ö¿¡ 0À» ºÙÀÎ 3°¡Áö °æ¿ì°¡ ÇÕÃÄÁ®¼­ ¾ÕÀÇ °ø½ÄÀ» ¸¸Á·Çϱ⠶§¹®ÀÌ´Ù.

¶Ç ÇǺ¸³ªÄ¡ÀÇ È®Àå°ø½Äµµ ¹è¿ü´Ù. ¿¹¸¦ µéÀÚ¸é f(n)-1=f(n-2)+f(n-3)+...+f(1)+f(0)ÀÌ´Ù. ÀÌ´Â f(n)=f(n-2)+f(n-1)=f(n-2)+f(n-3)+f(n-2)=f(n-2)+f(n-3)+...+f(1)+f(0)+f(1)À̱⠶§¹®ÀÌ´Ù.(f(1)Àº 1À̹ǷΠÀÌÇ×ÇÏ¸é µÊ.)

À̹ø ¼ö¾÷Àº ÀϹÝÀûÀ¸·Îµµ À¯¸íÇÑ ÇǺ¸³ªÄ¡ ¼ö¿­À» ¹è¿üÀ½¿¡µµ ´Ù¸¥ ¹æ¹ýÀ¸·Î Ç߱⠶§¹®¿¡ ±²ÀåÈ÷ Àç¹ÌÀÖ¾ú´Ù. ÇǺ¸³ªÄ¡ ¼ö¿­ÀÇ ´Ù¸¥ È®Àåµéµµ ´õ ¾Ë¾Æº¸°í ½Í¾îÁ³´Ù.

´ä±Û ¸ñ·Ï ±Û¾²±â
·Î±×ÀÎ ÈÄ µ¡±ÛÀ» ³²°ÜÁÖ¼¼¿ä

Æ÷¹Ìºñ¾Ø¿¥