|
key kalitga mos elementni izlash chegaralarini aniqlab olamiz. Dastlab u
[0,n]
| | bet | 39/47 | | Sana | 15.11.2023 | | Hajmi | 490,46 Kb. | | #99136 |
key kalitga mos elementni izlash chegaralarini aniqlab olamiz. Dastlab u
[0,n] oralig„ida, ya‟ni low=0,hi=n.
-
Agar low<=hi bo„lsa, oraliq o„rtasini hisoblaymiz. mid=(low+hi)/2
-
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.
-
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.
-
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.
-
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(){
struct Guruh{
string fio,adres;
}talaba[n];
for(int i=0;i
cout<fio=";cin>>talaba[i].fio; cout<<"adres=";cin>>talaba[i].adres;
}
//jadval binar qidiruv olib boriladigan maydoni bo‘yicha tartiblangan
//bo‘lishi kerak
for(int i=0;i for(int j=i+1;j
if(talaba[i].adres>talaba[j].adres){ Guruh h=talaba[i]; talaba[i]=talaba[j];
talaba[j]=h;
}
for(int i=0;i
cout< "< cout<
int low = 0,hi = n-1,search=-1,q=0; string key="TTJ";
while(low<=hi){
int mid = (low + hi) / 2; q++;
if (key == talaba[mid].adres){ search = mid;
break;
}
if (key < talaba[mid].adres) hi = mid - 1;
else low = mid + 1;
}
if(search!=-1) cout<<"qidirilayotgan el "< – o‘rinda
turibdi va "< ta solishtirishda topildi"<
else {cout< system("PAUSE");
return EXIT_SUCCESS;
}
while(talaba[search-1].adres==key) search--; while(talaba[search].adres==key) {
cout< "<
search++; } system("pause");
}
Dastur natijasi:
n=5
-
talabaning fio=fam1 adres=Toshkent
-
talabaning fio=fam2 adres=TTJ
-
talabaning fio=fam3 adres=ijarada
-
talabaning fio=fam4 adres=uchastkada
-
talabaning fio=fam5 adres=TTJ
fam2 TTJ fam5 TTJ
fam3 ijarada fam4 uchastkada
qidirilayotgan el 1-orinda turubdi va 2 ta solishtirishda topildi fam2 TTJ
fam5 TTJ
Nazorat savollari -
Qanday qidiruv algoritmlarini bilasiz?
-
Qidiruv jarayonining tezligi nimalarga bog‟liq?
-
Statik tuzilmadan birorta elementni izlashning qanday usullari mavjud?
-
Ro‟yhat tuzilmasidan elementlarni izlab topish tezligini oshirish uchun qanday algoritmlar mavjud?
-
Binar qidiruvni ro‟yhat tuzilmasiga qo‟llab bo‟ladimi? Sababini asoslang.
Variantlar:
-
Ketma-ket qidiruv usulidan foydalanib, ro„yhat eng kichik elementini toping.
-
Ketma-ket qidiruv usulidan foydalanib, ro„yhatda berilgan kalitdan katta elementlarni toping.
-
Ketma-ket qidiruv usulidan foydalanib, ro„yhat eng kichik elementini toping.
-
Ketma-ket va binar qidiruv usulidan foydalanib, A massivdan elementni va taqqoslashlar sonini toping.
-
Binar qidiruvdan foydalanib elementlarni tasodifiy ravishda toping.
-
Mashina raqamlari ro„yhati berilgan: 345, 368, 876, 945, 564, 387, 230. Binar qidiruvdan foydalanib berilgan raqamli mashina qaysi joyda turganini toping.
-
Ketma-ket qidiruv usulidan foydalanib ro„yhatda har ikkinchi elementni qidiring va taqqoslashlar sonini aniqlang.
-
Binar qidiruvdan foydalanib massivdan berilgan kalitga karrali kalitli elementni va solishtirishlar sonini toping.
-
Boshiga qo„yish va transpozitsiya usulidan foydalanib massiv eng katta elementi topilsin.
-
Boshiga qo„yish usulidan foydalanib ro„yhatda 11 ga butun bo„linuvchi eng katta sonni toping (agar bunday sonlar ko„p bo„lsa, u holda ularning eng kattasini toping; agar bunday son mavjud bo„lmasa – shunga mos ma‟lumot chiqaring).
-
Transpozitsiya usulidan foydalanib ro„yhatda 11 ga butun bo„linuvchi eng katta sonni toping (agar bunday sonlar ko„p bo„lsa, u holda ularning eng kichigini toping; agar bunday son mavjud bo„lmasa – shunga mos ma‟lumot chiqaring).
-
Boshiga qo„yish usulidan foydalanib ro„yhatda qo„shni elementlari ayrimasi 72 dan kichik bo„lgan elementni toping. Agar bunday elementlar ko„p bo„lsa, u holda ularning eng kattasini toping; agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Transpozitsiya usulidan foydalanib ro„yhatda qo„shni elementlari bo„linmasi juft son bo„lgan elementni toping. Agar bunday elementlar ko„p bo„lsa, u holda ularning eng kattasi yoki eng kichigini toping; agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Boshiga qo„yish usulidan foydalanib ro„yhatda qo„shni elementlar ayrimasi juft bo„lgan elementni toping. Agar bunday elementlar ko„p bo„lsa, u holda ularning eng kattasi yoki eng kichigini toping; agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Transpozitsiya usulidan foydalanib ro„yhatda kerakli elementgacha bo„lgan elementlarning o„rta arifmetigi 12 ga teng bo„lgan element topilsin. Agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Boshiga qo„yish usulidan foydalanib ro„yhatda 10 ga bo„linuvchi maksimal elementni toping. Agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Boshiga qo„yish va transpozitsiya usulidan foydalanib massiv eng kichik
-
Transpozitsiya usulidan foydalanib ro„yhatda qo„shni elementlari ayirmasi juft va 3 ga bo„linadigan elementni toping. Agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Boshiga qo„yish usulidan foydalanib ro„yhatda kerakli elementdan keyingi elementlarning o„rtacha kvadratik qiymati 10 dan kichik bo„lgan elementni toping. Agar bunday elementlar ko„p bo„lsa, u holda ularning eng kattasini toping; agar bunday element mavjud bo„lmasa – shunga mos ma‟lumot chiqaring.
-
Transpozitsiya usulidan foydalanib har bir x element uchun tg(x) qiymatini aniqlang va eng katta qiymatga ega bo„lgan elementni 1-o„ringa qo„ying.
-
Berilgan ro„yhatda qidirilayotgan element transpozitsiya usuli bilan qancha murojaatda ro„yhat boshiga kelishini aniqlash dasturini tuzing.
-
Massivdan boshiga qo„yish usuli yordamida key kalitli elementni izlash dasturini tuzing.
-
Binar qidiruv usuli yordamida massivga yangi elementni kiriting.
-
Binar qidiruv usuli yordamida massivning key kalitli elementini o„chiring.
-
Ro„yhatda transpozitsiya usuli yordamida toq elementlarni topish dasturini tuzing.
-
Berilgan massivda key kalitli elementni ketma-ket va binar qidiruv usullari yordamida izlang va qaysi usul ushbu qidiruv holatida samara berganligini aniqlash dasturini keltiring.
-
Talabalar ismi va umumiy ballaridan iborat jadvaldan ketma-ket qidiruv usuli bilan balli maksimal bo„lgan talabani toping.
-
Talabalar ismi va umumiy ballaridan iborat jadvaldan binar qidiruv usuli yordamida so„ralgan talabaning umumiy balini chiqarish dasturini tuzing.
-
Boshiga qo„yish usuli yordamida talabalar ismlaridan iborat massiv elementlariga ko„p marta murojaat qilib massivni qayta tartiblang.
-
Transpozisiya usuli yordamida talabalar ismlaridan iborat ro„yhat elementlariga ko„p marta murojaat qilib massivni qayta tartiblang.
-
|
| |
