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

1.2 Ilmoqsiz algoritmlar

Grey kodi ikkilik qatorlarni sanashning alternativ algoritmlaridan, masalan, leksikografik tartibda afzalliklarga ega: ketma-ket ketma-ketlikdagi ikkilik qatorni anan-1 ... a1 o’zgarishi mumkin: ai: = 1 - doimiy vaqt ichida ai. Ammo, biz ham yangilanishi kerak bo’lgan bitning pozitsiyasini hisoblashimiz kerak. Rekursiv ta’rifni (1) to’g’ridan-to’g’ri amalga oshirish O (2n) optimal umumiy ishlash vaqtiga ega algoritmga olib keladi, ya’ni sanab o’tilgan bit satrida doimiy o’rtacha vaqt.

Qattiqroq talab - har bir voris qatorini doimiy ravishda yomon vaqt ichida hisoblash. Bunday algoritm loopsiz avlod algoritmi deb ataladi. Ichaksiz sanash algoritmlari

0000000010110101111101001011100000 0111 0222 1112 1001 2120 2220

0000010010010101101111001011110001 0112 1222 1111 1000 2110 2221

0000110010000100101111011011010002 0102 1221 1110 2000 2111 2222

0000100110000100111111111011000012 0101 1220 1120 2001 2112

0001100110010100011111101001000011 0100 1210 1121 2002 2102

0001110110110100001110101001010010

0200 1211 1122 2012 2101

0001010110101100001110111001110020 0201 1212 1022 2011 2100

0001000111101100011110011001100021 0202 1202 1021 2010 2200

0011000111111100111110001000100022 0212 1201 1020 2020 2201

0011010111011100101010001000110122 0211 1200 1010 2021 2202

0011110111001101101010011000010121 0210 1100 1011 2022 2212

0011100101001101111010111000000120 0220 1101 1012 2122 2211 0010100101011101011010100110 0221 1102 1002 2121 2210