Kombinatorika algoritmlari. O’rin almashtirish algoritmini loyihalash MUNDARIJA I Bob. Kambinatorika algoritmlari nazariy asoslari. ....................................... 3 1.1.Kombinatorika algoritmlari. ................................................................ 3 1.2 Kombinatsiya tushunchasi. .................................................................. 4 1.3 Kombinatsiya uchun vaqt murakkabligi. ............................................. 5 II Bob. O’rin almashtirish algoritmi. ............................................................... 8 2.1. O’rin almashtirish algoritmini realizatsiya qilish. .............................. 8 2.2. Ikki nusxadagi kombinatsiyalar tushunchasi. ................................... 10 2.3. Dublikat tushunchasi. ....................................................................... 14 ILOVALAR ................................................................................................... 20 1-ILOVA. ................................................................................................ 20 2-ILOVA ................................................................................................. 20

KIRISH Dastlab algoritm tushunchasi haqida batafsil ma’lumotga ega bo’lib olamiz. IX asrlarda yashab ijod etgan buyuk bobokalonimiz Muhammad al-Xorazmiy nomi bilan uzviy bog’liqligini tushuntirish lozim. Algoritm so’zi al-Xorazmiyning arifmetikaga bag’ishlangan asarining dastlabki betidagi “Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Shundan so’ng al-Xorazmiyning sanoq sistemasini takomillashtirishga qo’shgan hissasi, uning asarlari algoritm tushunchasining kiritilishiga sabab bo’lganligi ta’kidlab o’tiladi. Algoritm bu asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda to’liq tizimi tushuniladi. Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta umumiy bo'luvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular o'zlarining rasmiy, izchil aksiomalar tizimi doirasida yechib bo'lmaydigan muammolar mavjudligini ko'rsatdi. Kombinatsiya – bu kombinatorikaning asosiy tushunchasidir. Bu tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalarning o‘rin almashtirishlar, o‘rinlashtirishlar va guruhlashlar deb ataluvchi asosiy ko‘rinishlari o‘rganiladi.

I Bob. Kambinatorika algoritmlari nazariy asoslari. 1.1.Kombinatorika algoritmlari. Dastlab kombinatorikaning asosiy amallaridan biri hisoblangan, o’rin almashtirish nima ekanligni tushunib olishimiz kerak bo’ladi. Uning asosiy mazmunini quyidagi misol orqali tushunib olishimiz mumkin. 4,7,9 raqamlaridan ularni takrorlamasdan nechta 3 xonali son tuzish mumkin? Bu kabi masalalarni maktabning matematika darsliklarida ko’plab ishlaganmiz. 1-o‘rinda berilgan 3 ta sondan ixtiyoriy bittasi turadi, ya’ni imkoniyatlar soni 3 ta. 2- o‘rinda qolgan 2 ta raqamdan ixtiyoriy bittasi bo‘ladi, ya’ni 2- o‘rinni egallash imkoniyati 2 ta. Nihoyat, 3- o‘rinda qolgan bitta raqam turadi. Demak, shu 3 ta raqamdan tuzilishi mumkin bo‘lgan 3 xonali sonlar soni 3 • 2 • 1 = 3! = 6 ta ekan. Shu 6 ta sonni yozaylik: 479, 497, 749, 794, 947, 974. Hosil bo‘lgan 6 ta sonning tarkibi bir xil — ular berilgan 3 ta raqamdan tuzilgan, ammo ular bir-biridan raqamlarining tartibi bilan farqlanadi: 1, 2, 3 deb nomerlangan 3 ta o‘ringa 3 ta raqam turli tartibda joylashtirilgan. Bunday tartiblash (joylashtirish) o‘rin almashtirish deyiladi. n ta: 1-, 2-, n- o‘ringa n ta a1, a2, ... , an elementlarni bir o‘ringa bittadan qilib joylashtirish a1, a2, ... , an elementlardan tuzilgan o‘rin almashtirish deyiladi. n ta elementdan tuzilgan o‘rin almashtirishlar soni Pn bilan belgilanadi. Yuqoridagi misolda elementlar soni 3 ta edi, n = 3 va P3= 3 • 2 • 1 = 3! ekanini ko‘rdik. Umuman, Pn = n • (n-1) ... 2 • 1 = n! Yana bir misol bilan ko’rib chiqamiz. 4 ta a, b, c, d elementdan (predmetdan) 2 tadan olib tuzilgan har xil guruhlar soni nechta? 2 elementli guruhlarni tuzamiz: {a, b}; {a, c}; {a, d}; {b, c}; {b, d}; {c, d}; — ularning soni 6 ta. Javob: 6 ta. Umuman, n ta elementdan k tadan olib tuzilgan barcha guruhlar soni de b belgilanadi va bu son ga teng: . son n ta elementdan k tadan olib tuzilgan guruhlar soni deb o‘qiladi. Bizning misolda n = 4, k =2 edi. Demak, ekanini ko‘rsatish oson. Haqiqatan ham, .

Masalan, . Shu bilan birga, . belgining yuqori indeksidagi 2 soni kasrning suratida 2ta ko‘paytuvchi bo‘lishini bildiradi. Bu ko‘paytuvchilar: belgining quyi indeksidagi 5 va undan bitta kam bo‘lgan son 4 dir. Kasrning maxrajida esa yuqori indeksidagi son 2 gacha bo‘lgan natural sonlar ko‘paytmasi yoziladi: 2! = 1 • 2. Endigi navbatda yuqoridagi jarayonlarni algoritmni ifodalash usullari yordamida sinab ko’ramiz. 1.2 Kombinatsiya tushunchasi. Kombinatsiya nima? Kombinatsiya - bu berilgan ob'ektlarning bir turi. Matematik nuqtai nazardan, Kombinatsiya - bu elementlar/ob'ektlarning noyob to'plamidan elementlarni tanlash/tanlash. Bu yerda elementlarning tartibi muhim emas. U hodisaning umumiy natijasini hisoblash usuli sifatida ham tanilgan, bunda natija tartibi muhim emas. Masalan, sizga 5 xil rangdagi sumka beriladi va istalgan 3 rangdan naqsh yaratish so'raladi. Shuningdek, siz 4 ta rangdan istalgan 3 ta rangni tanlashingiz mumkin, keyin ularni turli tartibda joylashtirishingiz mumkin. Faraz qilaylik, ranglar RGYBI (R= Qizil, G= Yashil, Y= Sariq, B= Moviy, I= Indigo). Shunday qilib, mumkin bo'lgan naqsh RGB, RGY va boshqalar bo'lishi mumkin. Keling, quyidagi rasmni ko'rib chiqaylik: 1-rasm. Kombinatsiyaga misol keltirilgan.

Tushuntirish: 5 ta rangdan 4 tasini oling va ularni ro'yxatga kiriting 4 ta rangning har bir blokidan istalgan 3 ta rangni tanlang va barchasini sanab o'ting. Misol uchun, biz rasmda faqat "RGBI" ni tanladik va 4 ta kombinatsiyani ko'rsatdik. Buning ortida biz yaratishimiz mumkin bo'lgan kombinatsiyalar sonini hisoblash uchun nazariya mavjud. n dan r elementning kombinatsiyasi matematik jihatdan quyidagicha ifodalanishi mumkin: Kombinatsiya formulasi “!” belgisi faktorialni bildiradi . Masalan, N! = N * (N-1) * (N-2) * … * 3 * 2 * 1 Ayting, 5! = 5*4*3*2*1 = 120 Shunday qilib, yuqoridagi muammomiz uchun bizda n = 5 ma'nosini anglatuvchi 5 ta rang bor va istalgan vaqtda biz istalgan 3 ni tanlashimiz kerak. Demak, r = 3. Hisoblab bo'lgach, biz quyidagilarni olamiz: Yuqoridagi stsenariy uchun jami 10 ta rang kombinatsiyasi mumkin. 1.3 Kombinatsiya uchun vaqt murakkabligi. Kombinatsiya uchun vaqt murakkabligi tahlili. Endi deylik, n o‘lchamli massiv berilgan bo‘lsa, bizdan massivdan r elementni olib, r elementning kombinatsiyasini bajarish so‘raladi. Agar n o‘lchamli massiv berilgan bo‘lsa, u O(n2) ni oladi ) vaqt kerak bo'ladi. Bundan tashqari, agar biz takroriy yozuvni olib tashlamoqchi bo'lsak, u holda, Biz quyidagi amallarni bajarishimiz kerak: 1-qadam) Kirish massivi ma'lumotlarini o'sish bo'yicha tartiblang. Saralashning vaqt murakkabligi O(n*log(n)). 2-qadam) Berilgan vaqtinchalik massiv ma'lumotlaridan noyob elementni o'z ichiga olgan boshqa massiv yarating. 3-qadam) Keyin kombinatsiya funktsiyasini bajaring. Shunday qilib, umumiy vaqt murakkabligi = O(n 2 ) + O(nLog(n)) ga aylanadi. Biz uni O(n 2 ) deb hisoblashimiz mumkin, chunki n 2 n*log(n) dan ancha katta.