Tower of Hanoi

 

ÇϳëÀÌ(º£Æ®³²ÀÇ µµ½Ã)ž¿¡ °üÇÑ ¹®Á¦ÀÇ °í¾ÈÀÚ·Î Lucas (ÇÁ¶û½ºÀÎ, 1842³â) ¶ó´Â ¼öÇÐÀÚ°¡ ¾Ë·ÁÁ® ÀÖ´Ù. 1883³â Claus ¶ó´Â À̸§¾Æ·¡ ÀÌ ÇϳëÀÌ Å¾ ¹®Á¦°¡ óÀ½ ³ªÅ¸³µ´Ù. °¡¸¸È÷ »ìÆ캸¸é, Claus ¶ó´Â À̸§Àº Lucas ¶ó´Â À̸§ÀÇ Ã¶ÀÚ¸¦ µÚ¹Ù²ã ³õÀº °ÍÀÓÀ» ¾Ë ¼ö ÀÖ´Ù. ±×°¡ ¾´ ¼öÇаÔÀÓ¿¡ °üÇÑ Ã¥ Récréations mathématiques (1882-94) Àº °íÀüÀÌ µÇ¾î ÀÖ´Ù.

Àü¼³ÀÇ ³»¿ë

º£³ª·¹½º¿¡´Â ¼¼°èÀÇ Áß½ÉÀÌ ÀÖ°í, ±× °÷¿¡´Â ¾ÆÁÖ Å« »ç¿øÀÌ ÀÖ´Ù. ÀÌ »ç¿ø¿¡´Â ³ôÀÌ 50cm Á¤µµ µÇ´Â ´ÙÀ̾Ƹóµå ¸·´ë 3 °³°¡ ÀÖ´Ù. ±× Áß ÇÑ ¸·´ë¿¡´Â õÁö âÁ¶ ¶§¿¡ ½ÅÀÌ ±¸¸ÛÀ» ¶Õ¸° 64 ÀåÀÇ ¼ø±ÝÀ¸·Î µÈ ¿øÆÇÀ» Å©±â°¡ Å« °ÍºÎÅÍ ¾Æ·¡¿¡ ³õÀ̵µ·Ï Çϸ鼭 Â÷·Ê·Î ½×¾Æ ³õ¾Ò´Ù. ±×¸®°í ½ÅÀº ½Â·Áµé¿¡°Ô ¹ã³·À¸·Î ½¬Áö ¾Ê°í ÇÑ À徿 ¿øÆÇÀ» ¿Å±â¾î ºó ´ÙÀ̾Ƹóµå ¸·´ë Áß ¾î´À °÷À¸·Î ¸ðµÎ ¿Å°Ü ³õµµ·Ï ¸í·ÉÇÏ¿´´Ù. ¿øÆÇÀº ÇÑ ¹ø¿¡ ÇÑ °³¾¿ ¿Å°Ü¾ß ÇÏ°í, Àý´ë·Î ÀÛÀº ¿øÆÇ À§¿¡ Å« ¿øÆÇÀ» ¿Ã·Á ³õÀ» ¼ö ¾ø´Ù. 64°³ÀÇ ¿øÆÇÀÌ º»·¡ÀÇ ÀÚ¸®¸¦ ¶°³ª ´Ù¸¥ ÇÑ ¸·´ë·Î ¸ðµÎ ¿Å°ÜÁ³À» ¶§¿¡´Â ž°ú »ç¿ø, ½Â·ÁµéÀº ¸ðµÎ ¸ÕÁö°¡ µÇ¾î »ç¶óÁö¸é¼­ ¼¼»óÀÇ Á¾¸»ÀÌ ¿Â´Ù.  

À§ÀÇ °æ¿ì´Â ¿øÆÇÀÇ °³¼ö°¡ 2ÀÌ´Ù. ÀÌ ±×¸²¿¡¼­ º¸¸éÀº ÃÖ¼ÒÇÑ 3¹ø À̵¿Çϸé, ´Ù¸¥ ¿øÆÇÀ¸·Î ¿Å°ÜÁüÀ» ¾Ë ¼ö°¡ ÀÖ´Ù. ±×¸®°í, ¿øÆÇÀÇ °³¼ö°¡ 3À̸é, ÃÖ¼ÒÀ̵¿ ¼ö´Â 7¹øÀÌ µÊÀ» ¾Ë ¼ö°¡ ÀÖ´Ù.

´Ù½Ã Á¤¸®Çϸé, ¿øÆÇÀÇ °³¼ö¸¦ n À̶ó ÇÏ°í, ÃÖ¼ÒÀ̵¿¼ö¸¦ M À̶ó Çϸé, n = 2 À϶§ M = ,   n = 3 À϶§ M = ÀÌ·¯ÇÑ ½ÄÀ¸·ÎºÎÅÍ ÃßÃøÀ» Çϸé, 64 °³ÀÇ ¿øÆÇÀ» ¿Å±â´Â µ¥´Â ¹øÀ̶ó´Â °ÍÀ» ¾Ë ¼ö°¡ ÀÖ´Ù.

Àü¼³¿¡¼­Ã³·³ 64 °³¸¦ ¿Å±æ ¶§, ÇÑ ¹ø ¿Å±â´Â ½Ã°£À» 1ÃÊ °É¸°´Ù°í °¡Á¤ Çϸé 64 °³¸¦ ¿Å±â´Â µ¥´Â ÃÊ°¡ °É¸°´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ°í, À̸¦ ³âÀ¸·Î ȯ»êÇϸé, ´ë·« 5833 ¾ï³â Á¤µµ¶ó°í ÇÑ´Ù.

žç°ú Áö±¸¿¡ °üÇÑ ¾Æ·¡ÀÇ Á¤º¸´Â ¾Æ·¡¿Í °°´Ù.

žçÀº 46¾ï³â µ¿¾È È°µ¿ÇØ¿Â °ÍÀ¸·Î º¸À̸ç 50¾ï³âÀº ´õ ÅÂ¿ï ¿¬·á°¡ ³²¾ÆÀÖ´Ù. ¸»±âÀÇ Å¾çÀº Çï·ýÀ» ´õ¿í ¹«°Å¿î ¿ø¼Ò·Î À¶ÇÕÇÏ´Â ¹ÝÀÀÀÌ ÀϾ°í ºÎÇ®¾î ¿À¸£´Âµ¥, Áö±¸¸¦ »ïų Á¤µµ±îÁö ±Øµµ·Î Ä¿Áø´Ù. ±× ÈÄ 10¾ï³âÀº Àû»ö°Å¼º(red giant)À¸·Î »ýÈ°Çϸç, À̳» °©Àڱ⠼öÃàÇÏ¿© ¹é»ö¿Ö¼º(white dwarf) ÀÌ µÈ´Ù -- ¿ì¸®ÀÇ Å¾ç°ú °°Àº º°ÀÇ Á¾¸»Àº ÀÌ¿Í °°´Ù. ¿ÏÀüÈ÷ ½ÄÀ¸·Á¸é ¾Æ¸¶ 1Á¶³â Á¤µµÀÇ ½Ã°£ÀÌ °É¸± °ÍÀÌ´Ù

µû¶ó¼­, 50¾ï³â ÈÄ¿¡ žçÀÌ Àû»ö°Å¼ºÀÌ µÇ¸é, Áö±¸°¡ »ý¸íü°¡ µÉ ¼ö ¾ø´Â »óÅ°¡ µÇ¹Ç·Î Á¾¸»À̶ó°í º¼ ¼ö ÀÖ°í, ÇϳëÀÌ Å¾À» ¿Å±â´Â µ¥, 5833¾ï³â Á¤µµ´Â °É¸®¹Ç·Î ±× ¾È¿¡ ¸ðµç Áö±¸ÀÇ ¸ðµç °ÍÀÌ ³¡³­´Ù´Â °ÍÀº °úÇÐÀûÀ¸·Î Ÿ´ç¼ºÀÌ ÀÖ´Ù.

ÀÚ ±×·¯¸é, À̸¦ ¼öÇÐÀûÀ¸·Î Á¤¸®¸¦ Çغ¸ÀÚ.

n À» ¿øÆÇÀÇ °³¼ö¶ó°í ÇÏ°í, ÀÌ ¶§ À̵¿È½¼ö¸¦ ¶ó°íÇÏÀÚ. n °³ÀÇ ¿øÆÇÀ» ¿Å±â·Á¸é À§ÂÊ¿¡ ÀÖ´Â (n-1) °³ÀÇ ¿øÆÇÀ» ¸ðµÎ ´Ù¸¥ ¸·´ë·Î ¿Å±ä ÈÄ¿¡ ¸Ç ¾Æ·¡ ¿øÆÇÀ» ºó ¸·´ë·Î ¿Å±â°í, ´Ù½Ã ±× À§¿¡ (n-1) °³ÀÇ ¿øÆÇÀ» ¿Å°Ü ³õÀ¸¸é, µÈ´Ù.

°ð, n°³ÀÇ ¿øÆÇÀ» À̵¿ÇÏ´Â ¹æ¹ýÀ» ´ÙÀ½°ú °°´Ù.

{A¡æB·Î (n-1)°³ À̵¿} + {A¡æC·Î 1°³ À̵¿} + {B¡æC·Î (n-1)°³ À̵¿}

ÀÌ°ÍÀ» ½ÄÀ¸·Î ³ªÅ¸³»¸é, ÀÌ ½ÄÀº °íµîÇб³ 2ÇгâÀÌ»ó ¼öÁØÀ̸é, ÀÏ ¹ÝÇ×À» ±¸ÇÒ ¼ö ÀÖ´Ù.

À§ÀÇ ½Ä¿¡¼­, ÀϹÝÇ× À̶ó°í Çϸé, ÀÌ µÊÀ» ¾Ë ¼ö ÀÖ´Ù.

term :

ÇϳëÀÌž (Tower of Hanoi)    ¼öÇÐ (Mathematics)    ÀΰøÁö´É (Artificial Intelligence)

site :

Hanoi Tower : ÀüºÏ´ë ¹Ú¼øö ±³¼ö´Ô µ¿¿µ»ó

ÇϳëÀÌ Å¾ ¼ÓÀÇ ¼öÇÐ ¿ø¸® : ÀÎÅÍ³Ý ½ºÄð : 6 °³ÀÇ ¿øÆÇÀ» ¿Å±â´Â °æ¿ìÀÇ applet demo

Tower of Hanoi     

Tower of Hanoi : Java Puzzle : Disc(¿øÆÇ) ¸¦ 12 °³±îÁö Á¶ÀýÇÏ°í Speed ¸¦ Á¶ÀýÇÏ¸ç ¿òÁ÷ÀÓ(Move)ÀÇ ¼ö¸¦ ¼¿ ¼ö ÀÖ´Ù.

video :

°ÅµìÁ¦°öÀÇ À§·Â : ¼öÇÐÀ¸·Î Ǫ´Â ¼¼»óÀÇ ºñ¹Ð - YTN »çÀ̾𽺠: ¹Ú°æ¹Ì È«ÀÍ´ë±³¼ö, 2014/02/12

 

... À§ÀÇ µ¿¿µ»ó 15ºÐºÎÅÍ ÇϳëÀÌž ¼³¸íÇÕ´Ï´Ù. ...