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

6-karrauchunikkilikGreykodva 4-karlikuchunuchlikGreykod.

1. 
   n = 6 (kvadrat) disklar bilan. Hanoy algoritmini ishga tushirishda ushbu rasmdagi konfiguratsiya 110011 bitli satr bilan birga sodir bo’ladi. (Disklarning pozitsiyalari va bu bitli satr o’rtasidagi munosabatlar to’g’ridan-to’g’ri emas, qarang.) Keyingi ko’chirish uchun disk - D1; u P0 qozig’iga soat yo’nalishi bo’yicha harakat qiladi va oxirgi bit to’ldiriladi. Grey kodining davomchisi 110010 qatoridir. Shundan so’ng D1 bir qadamni to’xtatadi, D3 disk esa yana soat yo’nalishi bo’yicha P1 dan P2 gacha harakat qiladi va o’ngdan uchinchi bit to’ldirilib 110110 qatoriga olib keladi. Turli xil kombinatoriya tuzilmalari uchun Erlich [3] tomonidan kashf etilgan va Grey kodlari uchun turli xil halqasiz algoritmlar ma’lum, qarang Bitner, Ehrlich va Reingold [1] va Knut [10, Algoritmlar 7.2.1.1.L va 7.2.1.1.H] . Ushbu algoritmlar qo’shimcha ko’rsatkichlarni saqlash orqali doimiy ishlash vaqtiga erishadilar. Xanoy minorasi Xanoy minorasi - bu rekursiv algoritmlar printsipini tasvirlash uchun standart darslik namunasi. Uning ortib boruvchi radiusi n D1, D2, ..., Dn disklari va uchta P0, P1, P2 qoziqlari bor, 2-rasmga qarang. Maqsad - barcha disklarni dastlab dam olgan P0 qozig’idan boshqa qoziqqa o’tkazish. , quyidagi qoidalarga muvofiq:
   

1. Bir vaqtning o’zida faqat bitta diskni ko’chirish mumkin: bitta qoziqdagi eng yuqori diskni boshqa qoziqning disklari ustiga siljitish mumkin 2.Disk hech qachon kichikroq diskning tepasida yotolmaydi.

N balandlikdagi minorani harakatlantirish uchun Dn diskni bir nuqtada harakatlantirish kerak. Ammo Dn diskini A qoziqdan B ga o’tkazmasdan oldin Dn ustida joylashgan D1, ..., Dn-1 disklarini uchinchi qoziqqa ko’chirish kerak. Dn ni B ga o’tkazgandan so’ng, ushbu disklarni uchinchi qoziqdan B ga ko’chirish kerak, bu n balandlikdagi minora uchun muammoni n - 1 balandlikdagi ikkita minoraga kamaytiradi va quyidagi rekursiv protseduraga olib keladi.

move_tower (k, A, B): (k eng kichik D1 ... Dk disklarni A qoziqdan B qoziqqa o’tkazing) agar k-0 bo’lsa: qaytish

yordamchi: = 3 - A - B; (yordamchi uchinchi qoziq, A va B dan farq qiladi) move_tower (k - 1, A, yordamchi) Dk diskni A dan B ga ko’chirish

move_tower (k - 1, yordamchi, B)

1.4 Xanoy minorasi va Grey kodlari orasidagi bog’lanish

Grey kodining delta ketma-ketligi - yangilangan bit pozitsiyalarining 1,2,1,3,1,2,1,4,1,2,1, ... ketma-ketligi. (Odatdagi konvensiyadan farqli o’laroq, biz bitlarni 1 dan boshlaymiz.) Ushbu ketma-ketlik (1) dan kelib chiqadigan aniq rekursiv tuzilishga ega. Shuningdek, u ikkilik hisoblashda i dan i + 1 gacha oshirilganda o’zgargan bitlar sonini tavsiflaydi. Bundan tashqari, xuddi shu ketma-ketlik yuqorida joylashgan move_tower rekursiv algoritmi bilan harakatlanadigan disklarni ham tasvirlashini kuzatish oson. Shunday qilib, Gn kulrang kodi yordamida Xanoy minorasi jumboqini echishda foydalanish mumkin, qarang. Gardner [4]. Boshqa yo’nalishda Xanoy minorasi jumboqidan Gn kulrang kodini yaratish uchun foydalanish mumkin, qarang Buneman va Levi [2].

Xanoy minorasi uchun navbatdagi harakatni hisoblashning bir nechta halqasiz usullari ma’lum va ular to’g’ridan-to’g’ri Grey kodining halqasiz algoritmlariga olib keladi. Biz shunday algoritmlardan birini tasvirlaymiz.1.5 Xanoyning ilmoqsiz minorasi va ikkilik Grey kodi

Move_tower rekursiv algoritmidan quyidagi faktni topish qiyin emas.

I Taklif 1. Agar minora P0 dan P1 ga ko’chirilishi kerak bo’lsa va n g’alati bo’lsa yoki minora P0 dan P2 ga va n juft bo’lsa, toq sonli disklarning harakatlari doimo oldinga qarab harakatlanadi ("soat yo’nalishi bo’yicha ”) Dumaloq yo’nalish: P0 → P1 → P2 → P0, va juft disklar har doim teskari dumaloq yo’nalishda davom etadi: P0 → P2 → P1 → P0.

Boshqa holatda, taxmin mavjud bo’lmaganda, ko’rsatmalar oddiygina almashtiriladi. Biz minorani ma’lum bir qoziqqa ko’chirishga emas, balki Grey kodini yaratishga qiziqish bildirganimiz sababli, biz aytilgan taklifga sodiq qolamiz.