Basic Pascal Tutorial/Chapter 4/Programming Assignment/bg

│ български (bg) │ English (en) │ français (fr) │ 日本語 (ja) │ 中文（中国大陆） (zh_CN) │

4G - Programming Assignment (author: Tao Yue, state: unchanged)

Класически проблем с рекурсията, преподаван във всички уводни курсове по компютърни науки, е Кулите на Ханой. В този проблем имате три вертикални колчета. В най-левия кол има конусовидна кула, състояща се от поредица дискове с форма на поничка. Например, така изглежда четириетажната кула:

   |       |       |
   |       |       |
   *       |       |
  ***      |       |
 *****     |       |
*******    |       |

Колчетата са означени 1, 2 и 3 отляво надясно. Предизвикателството е да преместите кула (с всякаква височина) от колче 1 към колче 3. В процеса не може да се поставя голям диск върху по-малък диск и може да се премести само един диск (най-горният диск на колче) по всяко време.

Проблемът изглежда тривиален за един или два диска. За един диск просто го премествате от колче 1 в колче 3. За два диска преместете най-горния диск от колче 1 в колче 2, след това 1 в 3 и накрая преместете по-малкия диск от 2 в 3.

Проблемът се усложнява за три или повече диска. За три диска бихте преместили 1 на 3, след това 1 на 2, след това 3 на 2. Това ефективно създава двуетажна кула на колче 2. След това преместете най-големия диск: 1 на 3. Сега преместете двуетажната кула на върха на големия диск: 2 към 1, 2 до 3, 1 до 3.

Вашата задача, ако решите да я приемете - е да напишете програма, използвайки рекурсивна процедура за решаване на Кулите на Ханой за произволен брой дискове. Първо попитайте потребителя за височината на оригиналната кула. След това разпечатайте инструкции стъпка по стъпка за преместване на отделни дискове от едно колче на друго. Например проблем с три диска трябва да доведе до следния изход:

1 to 3
1 to 2
3 to 2
1 to 3
2 to 1
2 to 3
1 to 3

Както е посочено в раздела за рекурсия, рекурсията е една от най-трудните за разбиране теми. Някои хора ще разгледат този проблем и ще открият че е изключително лесен за решаване. Други ще имат много проблеми с него. Въпреки това, след като успеете да разбирете принципа на рекурсията, действителното писане на програмата е сравнително просто.

Така че ако искате да се предизвикате, спрете да четете сега. Ако имате проблеми, продължете да четете за малко подсказване.

---

Подсказка: проблемът, както всички рекурсивни проблеми, намалява, като става по-опростен с всяка стъпка. Помните ли проблема с три диска? Първо създавате двудискова кула на колче 2, което ви позволява да преместите най-долния диск на колче 1 към колче 3. След това премествате двудисковата кула върху колче 3.

Същото е и с четири диска. Първо създайте кула с три диска на щифт 2, след това преместете най-големия диск на кол 3 и преместете кулата с три диска на кол 3. Как се създава кулата с три диска? Просто. Вече знаем как да преместваме кула с три диска от колче 1 в колче 3. Този път просто се придвижвате от колче 1 към колче 2, след което когато най-голямото колче е на мястото си, вие премествате кулата от колче 2 до кол 3. В цялата тази процедура можем да действаме така, сякаш големият диск не съществува, тъй като гарантирано е по-голям от останалите и по този начин не създава проблем. Просто използвайте решението с три диска, като превключвате числата.

На добър час!