|
O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti
|
| bet | 108/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi t1-misol.
Binar qidiruv usulidan foydalanib massiv elementlari orasida belgilangan elementni qidirish dasturi quyida keltirilgan:
1-usul.
#include
#include
int Binsearch(int a[], int N, int key, int *t)
{
int l=0, r=N-1, mid=(l+r)/2;
while (l<=r)
{ *t+=1;
if (a[mid]==key) return mid;
if (a[mid]>key) r=mid-1;
else l=mid+1;
mid=(l+r)/2;
}
a[N]=key;
return N;
} main ()
{
int i, N, mas[1000], key, P, t=0;
cout<cin>>N;
cout<<"Massiv elementlarini kiriting!"<for (i=0; icin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<cin>>key;
P=Binsearch(mas,N,key, &t);
if (P==N) cout<<"Bunday elementni massivga qo'shis lozim"<<"
"<
"<
getch();
return 0;
}
2-usul.
#include
#include
int InSeqsearch(int realArray[], int N, int kind[2][1000],int m,int key, int *t)
{
int i=0,
low = 0,
hi = 0;
while ((i
{
i++;
(*t)++;
}
(*t)++;
if (i==0)
low=0;
else
low=kind[1][i-1];
if (i==m)
hi=N;
else
hi=kind[1][i]-1;
for (int j=low; j<=hi; j++)
{
(*t)++;
if( key==realArray[j] )
{
return j;
}
}
return -1;
}
main ()
{
int i = 0 ,
N = 0,
mas[1000] = {0},
kind[2][1000] = {0},
key = 0,
P = 0,
index = 0,
kindIndex = 0,
t = 0;
cout<cin>>N;
cout<<"Massiv elementlarini kiriting!"<for (i=0; icin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<cin>>key;
cout<<"Boshlangich qadamni kiriting! "<cin>>P;
i = P-1;
while(i{
kind[0][kindIndex] = mas[i];
kind[1][kindIndex++] = i;
i += P;
}
index = InSeqsearch(mas,N,kind,kindIndex,key, &t);
if (index == -1)
cout<<"Bunday element massivda yuq "<< index <<" "<else
cout<<"Bunday element bor"<<" "<getch();
return 0;
}
3-usul.
#include
#include
#include
#include
struct TNode {
int value;
TNode* pnext;
};
//Ro'yhatga element qo'shish
void add2list(TNode **pphead, int val) {
TNode **pp = pphead, *pnew;
pnew = new TNode;
pnew->value=val;
pnew->pnext = *pp;
*pp = pnew;
}
//Ro'yhat elementlarini ekranga chiqarish
void print(TNode *phead)
{
TNode* p = phead;
while(p) {
cout <<" "<< p->value<<"-> ";
p = p->pnext;
}
cout << endl;
}
// Ro'yhatda element qidirish, C++
TNode* Find(TNode *phead, int x)
{
TNode *p=phead;
while(p)
if (p->value==x) return p;
else p = p->pnext;
return 0;
}
//Ro'yhat elementini o'chirish
void deleteList(TNode *phead) {
if(phead) {
deleteList(phead->pnext);
if(phead)
delete phead;
}
}
//Asosiy qism
int main() {int mas[1000], N, key; TNode* T;
clrscr();
TNode *phead = 0;
cout<<"Ro’yhat uzunligini kirit"<cin>>N;
cout<<"Elementlarni kirit!"<for(int j=0; jcin>>mas[j];
for(int i = 0; i < N; ++i)
add2list(&phead,mas[i]);
cout<<"Qidiruv elementni kiriting!"<cin>>key;
cout << "Elements of the list:" << endl;
print(phead);
T=Find(phead,key);
if (T==0) cout <<"Bunday element yoq"<else cout <<"Bunday element bor"<<" "<value<<" "<//deleteList(phead);
getch();
return 0;
}
4-usul.
#include
#include
int search(int a[], int N, int key, int *t)
{
int i=0;
while (i!=N)
{*t+=1;
if (a[i]==key) return i;
else i++;
}
//a[N]=key;
return -1;
}
main ()
{
int i, N, mas[1000], key, P, t=0;
cout<cin>>N;
cout<<"Massiv elementlarini kiriting!"<for (i=0; icin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<cin>>key;
P=search(mas,N,key,&t);
if (P==-1) cout<<"Bunday elementni massivga qo'shis lozim"<<"
"<
else cout<<"Bunday element bor"<<" "<
getch();
return 0;
}
Topshiriqlar
Ketma-ket qidiruv usulidan foydalanib, A massiv eng kichik elementini toping.
Ketma-ket qidiruv usulidan foydalanib, A massiv elementlari orasidan 3 (3,6,9, ...) ga karralilarini ekranga chiqaring.
Binar qidiruvdan foydalanib elementlarni tasodifiy ravishda toping.
Mashina raqamlari ro’yxati berilgan: 345, 368, 876, 945, 564, 387, 230. Binar qidiruvdan foydalanib berilgan raqamli mashina qaysi joyda turganini toping.
Butun sonlar massivi berilgan. Boshiga qo’yish va transpozisiya usuliga prosedura tuzilsin. Berilgan masalani yeching va masalada har ikkala usulda topilgan elementni ro’yxat boshiga joylashtiring.
Adabiyotlar
1.I.A.Karimov “O’zbekiston mustaqillikka erishish ostonasida”,Toshkent 2011y.
2.Adam Drozdek .Data structures and algorithms in C++. Second edition.2001 by Brooks/Cole.
3.N.A.Litvinenko. Texnologiya programmirovaniya.”BXV Peterburg” Sankt-Peterburg.2005g.
4. Alfred V. Axo., Djon E. Xopkroft, Djefri D. Ulman. Struktura dannыx i algoritmы//Ucheb.pos., M. : Izd.dom: "Vilyams", 2000, - 384 s.
5. Baknell Djulian M. Fundamentalnыye algoritmы i strukturы dannыx v Delphi//SPb: OOO «DiaSoftYuP», 2003. 560s.
6. Robert Sedjvik. Fundamentalnыye algoritmы na C++. Analiz, Strukturы dannыx, Sortirovka, Poisk//K.: Izd. «DiaSoft», 2001.- 688 s.
7. Knuth, D. E. (1968). The Art of Computer Programming Vol. I: Fundamental Algorithms, Addison – Wesley, Reading, Mass. (Russkiy perevod: Knut D. Iskusstvo programmirovaniya dlya EVM. Tom 1: Osnovnыye algoritmы. – M., «Mir», 1976. Russkiy perevod pererabotannogo izdaniya: Knut D. Iskusstvo programmirovaniya. Tom 1: Osnovnыye algoritmы. – M., Izdatelskiy dom «Vilyams», 2000.)
8. Xudoyberdiyev M.X., Akbaraliyev B.B. “Ma‟lumotlat tuzilmasi va algoritmlar” fanidan amaliy mashg„ulotlar uchun topshiriqlar (uslubiy ko„rsatmalari bilan). Toshklent, 2013 y.
|
| |
