Ханойские башни на Scheme

1 February, 2008 (21:02) | Задачи

Отвлечемся немного от решения упражнений (пятница, все же) и решим красивую задачку, которой в упражнениях к SICP нет (по крайней мере, пока не встретилось).

Задача о Ханойских башнях является классической алгоритмической задачей. Формулируется она следующим образом.

На одном из трех алмазных шпилей надето 64 круглых золотых диска. Диски имеют разные радиусы и расположены на шпиле в порядке убывания радиусов от основания к вершине. Требуется перенести диски с первого шпиля на второй, используя при необходимости и третий шпиль. При этом неукоснительно должны соблюдаться следующие правила:

  1. за один раз можно перемещать только один диск;
  2. больший диск нельзя располагать на меньшем диске;
  3. снятый диск необходимо надеть на какой-либо шпиль перед тем, как будет снят другой диск.

Переносом дисков занимаются буддийские монахи и, по легенде, когда они закончат эту работу, наступит конец света (случится это, впрочем, не скоро).

Итак, составим для монахов план, в соответствии с которым им нужно осуществлять перенос дисков. План состоит из последовательности операций по переносу одного диска с одного шпиля на другой. Перенос задается начальным и конечным шпилями.

Обозначим шпили буквами a, b и c. Отметим, что для того, чтобы перенести n дисков со шпиля a на шпиль b, используя шпиль c как вспомогательный, нам достаточно выполнить следующие действия:

  1. перенести n-1 диск со шпиля a на шпиль c, используя b как вспомогательный;
  2. перенести единственный оставшийся на шпиле a самый большой диск на шпиль b;
  3. перенести n-1 диск со шпиля c на шпиль b, используя a как вспомогательный.

Таким образом мы свели решение задачи для n дисков к решению двух задач для n-1 дисков, а значит можем применить древовидную рекурсию.

Обозначая перенос диска со шпиля a на шпиль b как список из двух элементов (a b) и формируя план переноса дисков как список таких двухэлементных списков, можем записать элегантное и простое решение программы на языке Scheme:

(define (hanoi n src dest inter) 
  (if (= n 0) 
      null 
      (append (hanoi (- n 1) src inter dest) 
              (list (list src dest)) 
              (hanoi (- n 1) inter dest src))))

Для того, чтобы получить план переноса 64 дисков, достаточно будет сделать вызов (hanoi 64 1 2 3), где 1,2 и 3 – это просто номера шпилей (вместо номеров можно задавать произвольные идентификаторы шпилей).

Comments

Pingback from SICP по-русски » Blog Archive » Решение упражнения 2.42 из SICP
Date: February 3, 2008, 12:47 pm

[…] SICP по-русски Структура и интерпретация компьютерных программ: заметки и решения « Ханойские башни на Scheme […]

Comment from psv
Date: December 7, 2008, 12:06 am

мда а легенду о алмазных дисках и конце света не читали? и вместо null лучше ‘() писать.

Comment from Charlesprala
Date: January 6, 2020, 12:44 am

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://clck.ru/LhWeg
https://clck.ru/LhYTK
https://clck.ru/LhZBS
https://clck.ru/LhW99
https://clck.ru/LhVbN
https://clck.ru/LhWBZ
https://clck.ru/LhVgP
https://clck.ru/LhXNj
https://clck.ru/LhW3K
https://clck.ru/LhUpk
https://clck.ru/LhVBL
https://clck.ru/LhVfJ
https://clck.ru/LhXCT
https://clck.ru/LhX45
https://clck.ru/LhWAA

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 6, 2020, 7:21 am

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://clck.ru/LhVhL
http://bit.ly/2FolF06
https://clck.ru/LhWcr
https://clck.ru/LhVEq
https://clck.ru/LhUZM
https://clck.ru/LhV9S
https://clck.ru/LhXCK
https://clck.ru/LhXgR
https://clck.ru/LhY6Y
https://clck.ru/LhZ72
https://clck.ru/LhWfm
https://clck.ru/LhVWR
https://clck.ru/LhVpM
https://clck.ru/LhVm4
https://clck.ru/LhV9N

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 9, 2020, 9:35 pm

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://sosudyinfo.ru/gemorroj/sredstva/geparinovaya-maz-pri-gemorroe.html?unapproved=9194&moderation-hash=411eb6ec22ca8f2b6a68fe6e5dba185a#comment-9194
https://brandwrites.law/use-or-no-use-that-is-the-question/?unapproved=1549&moderation-hash=9153fe8436b4b0cfeb921837a7b78b9b#comment-1549
http://ronlevyphotography.com/Blog/snowboarding-photo-shoot-at-snow-summit/?unapproved=14383&moderation-hash=2c4dc8c748eb7bd0f54eaa7849355a4f#comment-14383
http://ginnitea.com/2017/08/12/1667/?unapproved=39271&moderation-hash=15632d3068de6550ec4ad36e2f819751#comment-39271
http://www.heavymedia.org/resuscitating-my-blog/?unapproved=38466&moderation-hash=7906b9a1d2800d2cd2552704327d8ea9#comment-38466
http://www.reflex317.info/2014/11/03/eleifend-eget-interdum/?unapproved=1003&moderation-hash=b668a9da7b67e695dd913a6ddaacec2f#comment-1003
http://franchisebce.com/2014/09/25/chance-win-free-leads/?unapproved=260939&moderation-hash=20cd86937fb54b22edffd42ed59b0166#comment-260939
https://www.camillaarnholdphotography.com/lusty-glaze-beach-wedding-sarah-stuart/?unapproved=24104&moderation-hash=e9c5a9153e42b86a05085aad5b6c38f4#comment-24104
http://dionis.zp.ua/nachalo-sezona-2019/?unapproved=34759&moderation-hash=60d46b6ba280ae9ae9317c9e4f9a0513#comment-34759
https://flippengroup.com/founder-of-flippen-group-joins-board-of-advisors-for-the-drucker-institute/?unapproved=65143&moderation-hash=cdbd8ed245384bfc19646b66b3583455#comment-65143
http://www.end-of-tenancycleaning.com/?unapproved=56570&moderation-hash=8008fb64f92670164aee2997314ab5c4#comment-56570
https://garciniacambogia.org/7-day-diet-meal-plans/?unapproved=56470&moderation-hash=3d1dd0388548952e9052a680d688e5a8#comment-56470
https://pridigital.com/the-continued-relevance-of-email-marketing/?unapproved=29771&moderation-hash=bfd3535afd01b0570f3e44a1a2fca538#comment-29771
https://nyangnyang.com.ua/2015/09/23/delivery/?unapproved=4342&moderation-hash=28f7c99d38010d341899f5b79c45075a#comment-4342
http://rikonria.com/kyougisyo.html?unapproved=257191&moderation-hash=f6ca5f15f502b71fcc9e45e36706a8e6#comment-257191

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 10, 2020, 4:10 am

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://resumeuncle.com/blog/how-to-write-a-letter-of-recommendation/?unapproved=868&moderation-hash=f90072cf531a5175e04daa1e6d32d2a5#comment-868
http://www.crimsonartists.com/portfolio/iron-man-review/?unapproved=30386&moderation-hash=bc369a6c6e3e60eeb453b8472f564961#comment-30386
http://forum.finddex.com/showthread.php?tid=11
https://www.itsnotasitseems.com/hello-world/?unapproved=30484&moderation-hash=026f464a40cd34b7f292a8fa419291f2#comment-30484
http://mirexcel.ru/?p=193&unapproved=354332&moderation-hash=945112392e94abcf50860a06b02260e8#comment-354332
http://hsli.org/midwestmla2013/2013/10/03/construction-on-i-55/?unapproved=41365&moderation-hash=6437124f7eefc21434986e6e30ccce9e#comment-41365
https://www.sicherheit-forum.de/ergebnisse-der-grossen-sicherheitsumfrage/?unapproved=365&moderation-hash=41985798e0b195ecbf1d5d51e1998e9d#comment-365
http://simonfuhrmann.dk/afhandling-evagrios-vej-til-apatheia/?unapproved=61102&moderation-hash=6817c987350f11721c3f76af598ceeda#comment-61102
https://develop-tom.blog.ss-blog.jp/2012-03-25-3?comment_success=2020-01-06T16:36:19&time=1578296179
http://beckerswcd.org/portfolio-view/bejou-lake-access-improvement/?unapproved=81949&moderation-hash=d850efb5aad30b2d33dcba44b10dc43d#comment-81949
http://forum.trupak.ru/viewtopic.php?pid=32#p32
http://richardhanmerweddings.co.uk/2016/11/01/hello-world/?unapproved=43732&moderation-hash=3a3d6b847928538657114d0618c073a1#comment-43732
http://www.lawatt.com/post-hole-digger-machine.html?unapproved=81279&moderation-hash=c57969c971148c543500900a9e187147#comment-81279
http://geciktiricispreyler.com/sisli-delay-sprey-krem/?unapproved=47078&moderation-hash=79a8745698e861d3c2c9990e21cf80d6#comment-47078
https://kumig.it/CharlesAngex/charlesangex

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 10, 2020, 11:49 pm

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://www.answerone.biz/deciding-solutions-escan-spy-reviews-com/?unapproved=14614&moderation-hash=0b24eb0632adadf303c10de5d204b508#comment-14614
http://sex.telebrudarna.com/gratis-telesex-2/?unapproved=52572&moderation-hash=1920d877f9718ef7c25042657f1a0e11#comment-52572
http://xn—35-eddbmdenoh3a9av3ak0m1a.xn--p1ai/%d1%83%d1%81%d0%bb%d1%83%d0%b3%d0%b0-%d1%82%d1%80%d0%b5%d0%b7%d0%b2%d1%8b%d0%b9-%d0%b2%d0%be%d0%b4%d0%b8%d1%82%d0%b5%d0%bb%d1%8c-%d0%b2%d0%be%d0%bb%d0%be%d0%b3%d0%b4%d0%b0/?unapproved=625&moderation-hash=6ed8373da284bfea235016c9d13d7944#comment-625
http://howcam.com/author/charlesoptof/
https://ok-arenda.ru/arenda-zhilogo-pomescheniya-v-moskve/?unapproved=144&moderation-hash=89ed844a8951ed786691a1031c62b556#comment-144
http://www.peugeot-207-club.ru/forum/showthread.php?p=1335155&posted=1#post1335155
http://vidpochyvaj.com.ua/72/?unapproved=46903&moderation-hash=848084384688bb4a15c8d9ccc07f87a0#comment-46903
https://cornerstonedigital.ca/blog/what-does-tls-ssl-and-set-mean-to-your-e-commerce-business/comment-page-1/?unapproved=7928&moderation-hash=b0dd7b9cf872814d4dd32e2a2de41dff#comment-7928
https://www.penflip.com/Penflip/alpha/discussions/1140
https://www.carclassifiedxchange.com/author/charlestwish/
http://klm-hrm.sch.b-edu.ru/?page_id=3416&unapproved=20340&moderation-hash=366565dfc74b4f59c1326f05a611509d#comment-20340
http://www.genas.net/forums/topic/%d1%85%d0%be%d1%80%d0%be%d1%88%d0%be-%d1%81%d0%bc%d0%be%d1%82%d1%80%d0%b8%d1%82%d1%81%d1%8f-%d1%80%d0%b5%d0%ba%d0%bb%d0%b0%d0%bc%d0%b0-3/
https://www.trangtinnamtannhang.com/cach-chua-tri-tan-nhang-hieu-qua.html?unapproved=48435&moderation-hash=855309167f3c06f5182fdd3f74b8679b#comment-48435
http://g10vrn.ru/2018/04/03/%d0%b7%d0%b0%d0%bf%d0%be%d0%b2%d0%b5%d0%b4%d0%bd%d0%b8%d0%ba/?unapproved=4784&moderation-hash=cd0f9395f67cd376ed6a21346d4cf887#comment-4784
https://www.therobbygroup.com/5-fives-ways-to-make-bookkeeping-quick-and-fun/?unapproved=48805&moderation-hash=909073daa01c1c64bf0aea0a0d5162a9#comment-48805

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 12, 2020, 8:36 am

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://concreteinsulationsystem.com/hello-world/?unapproved=21848&moderation-hash=935868dac652d0808419dae15f66a003#comment-21848
http://tecnociencia-sociedad.com/aterrizaje-en-marte-made-in-spain/?unapproved=18923&moderation-hash=5914e615d252f98657cf25a43a949754#comment-18923
https://www.succeedandshine.com/norwex-gives-back-to-texas/?unapproved=50153&moderation-hash=fe3e699837c4fd7a26b1a98e3ca7a55f#comment-50153
http://www.mytechpages.com/11-2/?unapproved=12607&moderation-hash=70ef700199cd841ee98891fd65c3eb1d#comment-12607
http://www.miguelcopon.es/hola/?unapproved=45382&moderation-hash=1d4e89801456176c8b629005c708ba02#comment-45382
https://www.ebuddyblog.com/winsetup-usb-create-bootable-usb-many-windows/?unapproved=113413&moderation-hash=8ed97f33878a1a3d694ae20608c25780#comment-113413
http://gmduo.com/home.php?mod=space&uid=46239
http://www.reboni.co.za/product/chalk-boards/?unapproved=1260&moderation-hash=3d9f04af1ae5fd24dc3ce74484f2adeb#comment-1260
http://forum.finddex.com/showthread.php?tid=11
http://spectralight.se/2016/10/01/oktober-ar-har/?unapproved=61097&moderation-hash=2daadf73b0a27b96fda7d522acc33dc2#comment-61097
http://www.tuttoinfamiglia.it/forum/suggestion-box/323344#323021
https://emergency.sandiegocountyplumber.com/privacy-policy/?unapproved=37990&moderation-hash=2be08799a3cbebc945b8e8513be1e9af#comment-37990
https://shiatsu.no/kontakt/?unapproved=8006&moderation-hash=0a113825bb060e7cde430850f5e1ddf4#comment-8006
http://autemwswiat.bloggg.pl/2016/07/20/kiedy-trzeba-wynajac-auto/?unapproved=12969&moderation-hash=751caab102c7d99eacab03e8b4c2fe91#comment-12969
http://peerlessphotography.com/uncategorized/1920s-themed-nashville-destination-wedding/?unapproved=218&moderation-hash=a3e3a800c8451a3e83c9d11c3ffde7e0#comment-218

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 14, 2020, 4:55 am

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://www.kdcavia.spr-kazan.ru/forum/messages/forum13/message25557/595-xxl_massamuscular1pt.eu9mass_extreme.html/?result=reply#message25557
https://kumig.it/CharlesAngex/charlesangex
https://allgardens.ru/zhivaya-izgorod/?unapproved=129&moderation-hash=b409d19d85aa624da67b478e9fca50c7#comment-129
https://sa-sams.co.za/2019/01/20/18-2-0/?unapproved=165&moderation-hash=ffbc99346ccdbc43211364a77bd94640#comment-165
http://apsto.ic.cz/2015/08/23/apartmany-u-stoiberu/?unapproved=52641&moderation-hash=708db5f313ac728fad71462aec3ee5a7#comment-52641
http://support-fr.org/dim/2015/05/18/batch-user-add/?unapproved=94644&moderation-hash=51a3c1b89763b3c678daaffd92c50056#comment-94644
http://www.pressticargo.co.id/sample-page/?unapproved=31756&moderation-hash=272124d7d4f4f9686950aa1f6116e16a#comment-31756
http://www.bullitour.eu/general/concert-du-bulli-tour-europa/?unapproved=78209&moderation-hash=3bd2c05bcd61decb26906637cc00f905#comment-78209
https://millybitcoin.com/?p=591&unapproved=2134&moderation-hash=3af45d9c7d02ab405e995a778db36e45#comment-2134
https://urbania.pe/blog/decoracion-y-acabados/dale-una-pincelada-de-arte-tu-hogar/?unapproved=703470&moderation-hash=e8db17a3a9770bbda62287c883f05498#comment-703470
https://fujikocafe.blog.ss-blog.jp/2015-11-29-1?comment_success=2020-01-06T16:36:18&time=1578296178
http://remirough.com/488-public-provocations-at-colab-gallery/?unapproved=34616&moderation-hash=62a1ae3d7e8b5e42782fae63e4dbf66f#comment-34616
http://skupka-pro.ru/shop/product-category/samsung-galaxy-s7-32-black/?unapproved=39575&moderation-hash=bbde153af1ec8378a83951e13605c7a4#comment-39575
http://mgl-dvv.sch.b-edu.ru/?p=743&unapproved=38418&moderation-hash=45e220adeec01a9273d987f50e423a6c#comment-38418
http://ak47.we5t.de/viewtopic.php?f=19&t=17&p=110#p110

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 14, 2020, 1:27 pm

Хорошо смотрится реклама, где максимально используется окружающее пространство
https://www.airhotel.lt/atidarymas/?unapproved=38721&moderation-hash=788bb7bfd417e4a32a0cef46f2856ac6#comment-38721
http://maysolutionsuk.com/blog/2015/01/06/got-employed/?unapproved=77881&moderation-hash=f4eb17aa452d889a503317bf05670610#comment-77881
http://www.ironlaw.ee/uncategorized/6061/?unapproved=88259&moderation-hash=f5eea3d7f6da42c55b9e2ad14857f194#comment-88259
http://unc-1.sch.b-edu.ru/2013/06/10/9/?unapproved=10702&moderation-hash=b21ecdc4634648baf97635bdc431ad2e#comment-10702
http://www.brzydkaplec.pl/polskie-marki-linie-meskie/?unapproved=54406&moderation-hash=1be7746d4a465aa49dfdc2d5ec2c63fb#comment-54406
https://travelgreecetraveleurope.com/2016/10/07/13-things-i-learned-in-paris-in-7-days/?unapproved=21553&moderation-hash=f05ce4e5a39b7394d73fe5a64c590091#comment-21553
http://hellechristensenhjort.com/en-sommar-svischade-forbi/?unapproved=103100&moderation-hash=b196ae06b003cdf8c5a68221b05e6bfc#comment-103100
https://www.doctorrocamora.com/2017/02/10/preoperatorio-para-la-laparoscopia/?unapproved=26682&moderation-hash=e8493972b3887db37b5775dfe42ba173#comment-26682
http://internet-invest.com.ua/viewtopic.php?f=81&t=108441
http://www.hdfilmizlesem.org/hizli-ve-ofkeli-7-furious-7-2015-turkce-dublaj-izle.html?unapproved=410234&moderation-hash=650074ea4a31c9ec9524e670ad29848d#comment-410234
https://www.wasdzone.com/fortniteta-eslestirme-bolgemi-nasil-degistirebilirim/?unapproved=2189&moderation-hash=8c4100ae35a0d3b9bb220b3784a52232#comment-2189
https://www.horizonhealthcare.org/newwoonsocketclinic/?unapproved=166840&moderation-hash=1816e845a8575a08acdf74461866faf0#comment-166840
https://ok-arenda.ru/arenda-zhilogo-pomescheniya-v-moskve/?unapproved=143&moderation-hash=cb1c471a9441ea572d241b2bada8f75f#comment-143
http://www.1960beads.com/events/super-duo-bracelet?unapproved=133261&moderation-hash=f6401bd6142852f01728ce31b94feb3a#comment-133261
https://thedailylark.com/pure-pr/dell-investor-relation-blog/comment-page-1/?unapproved=135191&moderation-hash=afd50d6f9adbcde978ed074e66ac805c#comment-135191

Thank you for your comment, it has been added to the moderation queue!

Comment from Charlesprala
Date: January 14, 2020, 9:20 pm

Хорошо смотрится реклама, где максимально используется окружающее пространство
http://drhaque4happykids.com/how-to-increase-breast-milk-production/?unapproved=16357&moderation-hash=83aa63ae2f1ac9dd84eed9af0ba9999d#comment-16357
http://lungsuan.chumporn.police.go.th/board/index.php?topic=289877.0
https://www.thetrustenfield.org.uk/case-study-chris-kandu/?unapproved=28853&moderation-hash=ed7b3ad7fd6f352c54b241ecffec79b8#comment-28853
http://mcduffgoldman.com/gallery-image-2/?unapproved=80371&moderation-hash=348ecb5a66d56f0f990fd5bae7aa5734#comment-80371
http://ecolia.com/blog/2019/06/01/bonjour-tout-le-monde/?unapproved=374&moderation-hash=7e7fbcfe654992929e3a5b70fd702957#comment-374
http://asoprem.com/2018/02/03/hello-world/?unapproved=33157&moderation-hash=99b23624755a43413f48308cda998a83#comment-33157
https://fujienviromax.co.uk/blog/why-consumers-are-buying-fuji-enviromax/?unapproved=5490&moderation-hash=4104592e0fdba62ec33fa1fbf01ae0e2#comment-5490
http://www.yohann-paysage.com/?unapproved=92360&moderation-hash=20034be325d3cdf8660cc1fea269feac#comment-92360
http://mahkety.ru/2017/06/29/%d1%84%d0%be%d1%80%d1%83%d0%bc-%d1%82%d0%b0%d0%b2%d1%80%d0%b8%d0%b4%d0%b0-%d0%b2%d0%bd%d0%be%d0%b2%d1%8c-%d1%81%d0%be%d0%b1%d0%b5%d1%80%d0%b5%d1%82-%d0%bd%d0%b0-%d0%ba%d1%80%d1%8b%d0%bc/?unapproved=2501&moderation-hash=3e4e33500ebefd758049d848a97aa27a#comment-2501
http://ticucinoio.com/Ricette/la-maionese/?unapproved=3639&moderation-hash=4257f908e2709cee12cb54c56b098f24#comment-3639
https://wp-theme.net/blog/2019/03/29/hello-world/?unapproved=185&moderation-hash=6ac7606ffaa8ac5e85a32cbf8a9c618c#comment-185
https://www.centerforhealingneurology.com/2019/11/17/blog-cci-surgery-a-neurologists-perspective/?unapproved=5419&moderation-hash=4a3c7380e57ee6e1582b9d8d074e6af8#comment-5419
https://www.entrepreneursuccess.ie/blog/time-management-self-management-problem/?unapproved=25933&moderation-hash=d3505e58b95d154f27046a099c5012f3#comment-25933
http://americans4hire.com/forum/viewtopic.php?f=4&t=1427148
http://resellerblog.livedrive.com/2012/08/5-top-business-backup-facts/?unapproved=231500&moderation-hash=b904ec901a2260e35d05e52d15237d99#comment-231500

Thank you for your comment, it has been added to the moderation queue!

Write a comment