1 Проблем с Ханойската кула

Препис

2 Нека първо решим този по-прост проблем. На фиг. Дадени са възможни схеми за прехвърляне на кули от и дискове. Нека да видим как работи процесът на трансфер за кула от три диска: първо прехвърляме горните два диска на третия прът (първите три хода), след това прехвърляме долния диск на втория прът (четвърти ход), след което прехвърляме горните два диска от третия прът до втория ... Сега можем да измислим начин да пренаредим кулата от четири диска: комбинирайте мислено горните дискове в един "супердиск", прехвърлете го на третия прът (можем да направим това, вижте фигурата), прехвърлете долния диск на втория прът и след това прехвърлете третия прът на втория. Кулата от пет диска може да се измества по същия начин. Единствената разлика е, че горните 4 диска трябва да бъдат комбинирани в "супер диск". Сега можете да запишете решението на проблема. За да прехвърлите 64 диска от първия прът към втория, можете психически да комбинирате горните 6 диска в един "супердиск", да го прехвърлите на третия прът, след това да прехвърлите долния диск на втория прът и накрая да преместите "супердиска "от третия прът към втория. Това решение обаче е непълно: липсва обяснение как да се пренареди 6-дисков супердиск. Следователно за цялостно решение ще трябва да напишем 64 текста, подобни на този, даден в предишния параграф, като правим малки промени в зависимост от височината на кулата. За да не пишете (почти) едно и също нещо няколко пъти, можете да определите броя на дисковете в кулата с буквата n и да напишете този текст само веднъж. За да прехвърлите n дискове от първия прът към втория, можете психически да комбинирате горния (n) диск в един "супердиск", да го прехвърлите на третия прът, след това да прехвърлите долния диск на втория прът и накрая да изместите "супердиск" от третия прът към втория ... Трябва обаче да се внимава, когато се използва такава нотация: винаги трябва да проверявате за какви стойности на n тя „работи“. Ясно,

Фиг. 3: Схеми за оформление и дискове в кулата на Ханой

4, че текстът на предишния параграф е безсмислен за отрицателни (както и нецели числа) стойности на n: не може да има отрицателен брой дискове в кулата. Но има още едно изключение: n = 0. Наистина, за n = 0 "супердискът" ще съдържа n = диск, което е невъзможно. По този начин точната формулировка на алгоритъма е както следва. За да преместите n дискове, n, от първия прът към втория, можете психически да комбинирате горния (n) диск в един "супердиск", да го прехвърлите на третия прът, след това да прехвърлите долния диск на втория прът и накрая, преместете "супердиска" от третия прът към втория. Не е нужно да правите нищо, за да прехвърлите 0 диска. Горният алгоритъм за превключване има една важна характеристика: на една от стъпките трябва да се изпълни целият алгоритъм, но за другата n. Алгоритмите от този вид се наричат ​​рекурсивни. Недостатъкът на този алгоритъм е, че той не дава бърз отговор на въпроса „Какъв ход трябва да се направи първо?“: За да отговорите на този въпрос, трябва психически да „разширите“ n нива за влагане . Брой ходове След въпроса на теоретичната разрешимост за безкрайно време, е полезно да разберете дали е възможно да се реши проблемът за кратко време. Задача. Кой е най-малкият брой ходове, възможни за сглобяване на Ханойската кула? В лекцията ще решим само по-опростен проблем Задача 4. Колко движения ще са необходими за преместване на Ханойската кула, ако следваме алгоритъма от предходния параграф? Тези две задачи са значително различни. Представете си, че са ви помолили по най-бързия начин да стигнете от сградата на HSE на Мали Гнездниковски до метростанция Tverskaya и вие отговорихте: „Обикновено минавам през ул. м. Смоленская, оказва се около час. " 4 Повечето съвременни алгоритми за криптиране се стремят точно да гарантират, че кодът не може да бъде „разбит“ за кратко време: месец, година, две години, десет години, в зависимост от важността на информацията.

5 За да разрешите проблем от този вид, е полезно първо да познаете отговора и след това да го докажете. За да познаете отговора, е удобно първо да съставите таблица, в която едната колона е броят на дисковете, а другата е броят на ходовете. Брой дискове Брой ходове Как да изчислим броя ходове за повече дискове? Нека разгледаме нашия алгоритъм: за да преместите кула от n диска, трябва да преместите два пъти кула от n диска и да извършите още едно движение. Ако обозначим броя ходове, необходими за преместване на кулата от n дискове според нашия алгоритъм, през T n, тогава наблюдението от предишното изречение може да бъде записано по формулата: T n = T n +, n. Сега можем да продължим нашата маса по-нататък. Брой дискове Брой ходове 0 0 = 0 = 0 ++ 0 = ++ 7 = ++ 4 5 = = = ++ Разглеждайки тази таблица, можете да познаете отговора: T n = n. Тъй като тази формула за T n „се сближава“ с всички данни, с които разполагаме, можем да се опитаме да го докажем. Първо, знаем, че T = =. Второ, ако T n = n, тогава T n = T n + = (n) + = n. Остава да приложим принципа на математическата индукция. По-подробен текст за това как да направите това ще се появи на сайта около обедното време. пет