«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan kurs ishi

Xanoy algaritimi Ikkilik Grey kodining halqasiz algoritmi.

Boshlang: Barcha disklarni P0-ga qo’ying.

D1 soat yo’nalishi bo’yicha harakatlantiring.

Dk D1 ko’tarmaydigan ikkita qoziqdagi eng yuqori disklardan kichikroq bo’lsin.

Agar bunday disk bo’lmasa, tugating.

Agar k toq bo’lsa, Dk-ni soat yo’nalishi bo’yicha harakatlantiring; aks holda, uni soat sohasi farqli ravishda harakatlantiring.

Grey kodini olish uchun biz shunchaki Dk diskini harakatga keltirganda ak: = 1 - ak ni o’rnatamiz [2]. Jarayonning surati uchun 2-rasmga qarang.

Bizga Dk uchun soat yo’nalishi bo’yicha / soat sohasi farqli o’laroq qoidalar kerak bo’lmaydi: chunki Dk ni D1 ustiga qo’ymasligimiz kerak, shuning uchun uni qaerga ko’chirishni tanlash imkoniyati yo’q [2]. Biz yuqoridagi formulani tanladik, chunki u umumlashtirish uchun yaxshiroqdir.

Umumiy ma’lumot Ushbu maqolaning qolgan qismida biz ushbu ulanishlarni katta radiuslar (alifbo o’lchamlari) uchun Grey kodlari bilan umumlashtiramiz. 2-bo’lim uchlamchi Grey kodlari va ularning Buxarest minoralari deb nomlangan aloqalariga bag’ishlangan. Umumiy radiusli Grey kodlarini aniqlagandan so’ng, biz uchlamchi algoritmni 2-bo’limdan 4-bo’limdagi ixtiyoriy toq radiuslarga m ga, hattoki aralash (toq) radiuslarga (6-bo’lim) kengaytiramiz. 5-bo’limda biz 1.5-bo’limning ikkilik Grey kod algoritmini o’zboshimchalik bilan hatto m ga umumlashtiramiz. Va nihoyat, 8-bo’limda biz amortizatsiya qilingan ish vaqtini eng yomon chegaralarga aylantirish bilan bog’liq bo’lgan "oldinda ishlash" degan mutlaqo boshqacha g’oyaga asoslanib loopsiz algoritmlarni ishlab chiqamiz.