Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari samarqand filiali

MUSTAQIL ISH


FANNING NOMI: “MA’LUMOTLAR TUZILMASI VA UNING ALGORITMLAR,,


MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI SAMARQAND FILIALI

MAVZU

1. 
   Binar qidiruvdan foydalanib massivdan berilgankalitga karrali kalitli elementlar sonini toping?
   
2. 
   Kolleziyalar muammosinihal qilishning muqobil usuli haqida ma’lumot bering, o’zingizni F.I.SH ni hesh qiymatini qaytaruvchi dastur tuzing?
   

Binar qidiruv
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng yomon ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha. Talabalar ma‟lumotlaridan – FIO va adresdan iborat jadval berilgan. Binar qidiruvdan foydalanib TTJ da yashaydigan talabalar ro„yhatini hosil qiling. Algoritm 1. Jadvalga n ta talaba FIO va adreslarini kiritamiz. 2. Binar qidiruvni jadvalning birorta maydonida amalga oshirish uchun jadvalni shu maydoni bo„yicha tartiblab olish kerak. Shuning uchun masalaning qo„yilishida adresi TTJ bo„lgan talabalarni topish kerakligi sababli jadval ma‟lumotlarini adres maydoni bo„yicha saralab olamiz. Masalani yechishda to„g„ridan-to„g„ri tanlash orqali saralashdan foydalanilgan. 3. key kalitga mos elementni izlash chegaralarini aniqlab olamiz. Dastlab u [0,n] oralig„ida, ya‟ni low=0,hi=n. 4. Agar low<=hi bo„lsa, oraliq o„rtasini hisoblaymiz. mid=(low+hi)/2 5. Agar mid o’rnida turgan talaba adresi TTJ bo„lsa, element topildi, search=mid va 7-qadamga o„tiladi, aks holda keyingi qadamga o„tiladi. 6. Agar “TTJ” so„zi alifbo bo„yicha mid o„rnida turgan talaba adresi qiymatidan kichik bo„lsa, izlash quyi chegarasi o„zgaradi, ya‟ni mid o„rnida turgan elementdan bitta oldingi elementgacha olinadi, ya‟ni hi=mid-1. Aks holda, yuqori chegara o„zgaradi – mid dan keyingi elementdan to oxirgi elementlar oralig„i olinadi, ya‟ni low=mid+1. 4-qadamga o„tiladi. 7. Agar topilgan elementdan oldin turgan elementning (mid-1) ham adres maydoni TTJ bo„lsa, search--, ya‟ni bitta oldingi elementga o„tamiz va shu qadamni boshidan bajaramiz. Aks holda keyingi qadamga o„tiladi. 8. Joriy (search ko„rsatayotgan) elementdan boshlab adresi “TTJ” ga teng bo„lgan talaba ma‟lumotlarini ekranga chiqaramiz. Agar adresi “TTJ” dan farq qiladigan talaba chiqib qolsa, algoritm tugallanadi. Dastur kodi #include using namespace std; int main(){ int n;cout<<"n=";cin>>n; 105 struct Guruh{ string fio,adres; }talaba[n]; for(int i=0;i<Masalan:

3. 
   Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
   
4. 
   1. x ni o'rtadagi element bilan solishtiramiz.
   
5. 
   2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
   
6. 
   3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
   
7. 
   4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.