|
Raqamli texnologiyalar vazirligi muhammad al xorazmiy nomidagi toshkent axborot texnologiyalari universiteti
|
| bet | 2/6 | | Sana | 17.11.2023 | | Hajmi | 1,86 Mb. | | #100479 |
Bog'liq Маълумотлар тузилмаси ва алгоритми 1 deadline 1, 2, 3 erkinova2Amaliy bajarish uchun
Massivdagi x elementiningjoylashganindeksinianiqlovchidasturalgoritminituzing.
``python
massiv = [5, 7, 12, 3, 10, 8]
x = 3
indeks = massiv.index(x)
print(f"{x} elementining indeksi: {indeks}")
2 – Amaliymashg‘ulot: Ma’lumotlarniqidirishalgoritmlarivadasturlariniishlabchiqish, Ma’lumotlartuzilmalarinixeshlashalgoritmlariyordamidahosilqilish. Ma’lumotlarnisaralashalgoritmlarivadasturlariniishlabchiqish, Chiziqlima’lumotlartuzilmalariniqaytaishlashalgoritmlarivadasturlarinituzish.
Ishdanmaqsad:Ushbuamaliyotishiningmaqsaditalabalarqandayqidirishusullarivaalgoritmlarimavjudliginivaularningsamaradorliklarinibaholashnio‘rganishlarikerak. Shu asosdaqidirishusullariniqiyosiytahlilqilishlari, C++ dasturlashtilidaqidirishbilanislashnivaulargaoiddasturlartuzishnio‘zlashtirishlarikerak.
Qo‘yilgan masala:Talabalartopshiriqvariantigamosqidirishusuliyordamidamasalaniyechishdasturiniyaratishko‘nikmasigaegabo‘lishlarikerak.
Ish tartibi:
1.Tajribaishinazariyma’lumotlarinio‘rganish;
2.Berilgantopshiriqningalgoritminiishlabchiqish;
3. C++ dasturlashmuhitidadasturniyaratish;
4. Natijalarnitekshirish;
5.Hisobotnitayyorlashvatopshirish.
Aytaylikbizgamassivberilgan:a[]={15, 23, 7, 45, 87, 16};
Bizgaushbumassivdabironbir element boryokiyo‘qliginitekshiraoladigandasturtuzishshartiqo‘yilgan. Ushbumasalaniyechishdaengbirinchixayolgakeladiganusul - bumassivniketma-ketharbirelementinisolishtiribchiqishvabuusul:
Chiziqliqidiruv - Linear Search deb ataladi, vabuusulkodiquyidagiko‘rinishda:
#include
usingnamespace std;
int linearSearch(int array[], int size, int searchValue)
{ for(int i =0; i< size; i++)
{ if(searchValue == array[i])
{ returni; }}
return-1;
} int main()
{ int a[]={15, 23, 7, 45, 87, 16};
int userValue;
cout<<"Enter an integer: "<
cin>>userValue;
int result = linearSearch(a, 6, userValue);
if(result >=0)
{ cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result <
} else {
cout<<"The number "<
Ko‘ribturganingizdek, funksiyamiz 2 ta parametrqabulqiladi, birinchisimassivnio‘zi, ikkinchisiesa biz qidirayotgan element. Agar unitopaolmasak, “-1”qiymatniqaytaramiz.
Endi bundan optimal bo‘lganusul–binary (ikkilik)qidiruvniko‘ribchiqsak. Bu usulda ham funksiyaga 2 ta parametr, birinchisimassivo‘zikeyinesa biz qidirayotganelementniparametrsifatidaberiladi. Qidiruvesaquyidagicha: Dastlab biz massivboshivaoxirinio‘zimizuchuno‘zgaruvchilardabelgilabolamiz, meningkodimdabu left va right o‘zgaruvchilaridir:
left := 0 right := len(a)
so‘ngraquyidagishartbajarilganholda
left< right
quyidagiketma-ketoperatsiyalarniamalgaoshiramiz
left va right index larimarkazidagielementnitopamiz (left + right) / 2
topilganelementimiz biz qidirayotganelementgatengbo‘lsaunda mid elementnijavobsifatidaqaytaramiz
agar a[mid] elementimiz biz qidirayotganelementdankichkinabo‘lsa biz left = mid deb belgilaymizvashunda a[mid:right] bo‘lagidaqidiruvdavometadi.
agar a[mid] elementimiz biz qidirayotganelementdankattabo‘lsademak right = mid deb belgilaymizshundaqidiruv a[left:mid] bo‘lagidaqidiruvdavometadi.
Shu zayldaqidiruv left < right shartbajarilmagunichadavometadi, agar bujarayonda biz qidirgan element topilmasa u xolda -1 javobqaytariladi, quyidadasturkodikeltirilgan:
#include
Using namespace std;
int binarySearch(int array[], int size, int searchValue)
{ int low =0;
int high = size -1;
int mid;
while(low <= high)
{ mid =(low + high)/2;
if(searchValue == array[mid])
{ return mid;
} elseif(searchValue> array[mid])
{ low = mid +1; }
else
{ high = mid -1; } }
return-1; }
int main()
{ int a[]={12, 22, 34, 47, 55, 67, 82, 98};
int userValue;
cout<<"Enter an integer: "<
cin>>userValue;
int result = binarySearch(a, 8, userValue);
if(result >=0)
{ cout<<"The number "<< a[result]<<" was found at the"
" element with index "<< result <
} else { cout<<"The number "<
Bu usulbinarqidiruvniiterativusulideyiladi, shuningdekbualgoritmnirekursiyausulida ham yozishmumkin, rekursivusulnierinmasangizo‘zingizyozibko‘ring. Bitta urinishdako‘pchilikdasturchilarbunarsanito‘g‘riyozaolishmaydivabu normal holat, chunkixatoborjoydao‘zustidaishlashuchunimkoniyatbo‘ladi.
Endi buqidiruvusullariniayrimjihatlarinikeltiribo‘tamiz:
funksiyagaberilayotganmassiv Binar qidiruvuchunalbattao‘sishtartibidabo‘lishi talab qilinadi, chiziqliqidiruvuchunesaberilayotganmassivqaytartibdabo‘lishiniahamiyatiyo‘q
chiziqliqidiruvdaelementlarnibittalabharbirinitekshiriladi, binardaesaalgoritmidankelibchiqibchiziqliganisbatananchakamsolishtirishamalibajariladi, chiziqliqidiruvningishlashvaqtiko‘pibilan O(n) vabinarqidiruvnikiko‘pibilan O(log n)
|
| |
