|
2-tajriba ishi. Qidiruv usullarini tadqiq qilish
|
| Sana | 14.11.2023 | | Hajmi | 164.75 Kb. | | #98640 |
Bog'liq 2-amaliy xudo xoxlasa tushadi99%, 3-labarotoriya ishi Saralash usul va algoritmlarini tadqiq qilis, cmd buyruqlari, Incremental model nima, 1matematik, word sAM 1 savol, Документ Microsoft Word (4), Ma\'ruzalar (2), ЛАБОРАТОРНАЯ РАБОТА N1, Dasturlash 2, Ariza, Qalandarova Gulshoda, 1648631455, 1650692784, 1651669892 (2)
Toshkent axborot texnologiyalari
Unveristeti
Dasturiy injinering fakulteti
. 317—22 guruh talabasi . Azimov Murodjonning . Malumotlar tuzilmasi va algoritmlar . fanidan 2- amaliy topshiriq . yechimlari
Fan o`qituchisi : Nurdullayev Alisher . Niyatillayevich
2-tajriba ishi. QIDIRUV USULLARINI TADQIQ QILISH
Ishdan maqsad: talabalar berilgan tuzilmaning shakliga qarab biror kalitga mos elementni qidirishning optimal usulini qo’llashni o’rganishlari va qidiruv usullarining samaradorligini taqqoslashlari kerak.
Qo’yilgan masala: topshiriq variantidagi masalani so’ralayotgan qidiruv usuli yordamida yechishning C++ tilidagi dasturini yaratish ko’nikmasiga ega bo’lish.
Ish tartibi:
Laboratoriya ishi nazariy ma’lumotlarini o’rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Ishni bajarish boyicha tartib raqam 4.
1-topshiriq yechilishi :
Ketma-ket va binar qidiruv usulidan foydalanib, A massivdan elementni va taqqoslashlar sonini toping.
Ishni bajarish uchun avval binar qidiruv usuli qanday ishlashini tushinib olishga harakat qildib yani germaniya bayrog`i algoritmi
Bizda mavjud bolgan massivni o`rtasini toppish va keyin taqqoslashni amalga oshirish uchun def kalit so`zi bilan funksiya hosil qildim .va binar qidirishni amalga oshirdim.
def binar_qidiruv(arr, x):
left = 0
right = len(arr) – 1
comparisons = 0
while left <= right:
mid = (left + right) // 2
comparisons += 1
if arr[mid] == x:
return arr[mid], comparisons
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return None, comparisons
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k=int(input("k--"))
element, comparisons = binar_qidiruv(A, k)
print("Element: ", element)
print("Taqqoslashlar soni: ", comparisons)
bizning massivda birinchi navbatda element borligi aniqlab u chop etadi keyin esa 5 o`rtadagi elementdan ajratib olib taqqoslaydi.va 1,2,3,4 ga yetganda 9 ga keladi va bu uning 4 taqqoslashi hisoblanadi.
Kod python dasturlash tilida yozildi robotics lab ochiq manbalaridan foydalanildi.
Kod ish vaziatidagi screenshot:
2-topshiriq yechilishi :
Binar qidiruv usulida bu misol uchun ham algoritm yaratib olamiz .biz qidirayotgan har bitta elementni alohida qidirib taqqoslashlar soni bilan chop etamiz.
def binar_qidiruv(arr, x):
left = 0
right = len(arr) - 1
comparisons = 0
while left <= right:
mid = (left + right) // 2
comparisons += 1
if arr[mid] == x:
return arr[mid], comparisons
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return None, comparisons
# Massivni o'rnating
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Qidiriladigan elementlar
qidiriladigan_elementlar = [4, 8, 12]
for element in qidiriladigan_elementlar:
found_element, comparisons = binar_qidiruv(A, element)
if found_element is None:
print(f"{element} topilmadi")
else:
print(f"{element} topildi: {found_element}")
print(f"Taqqoslashlar soni: {comparisons}")
print()
Bu kodda binar_qidiruv funksiyasiga comparisons deb nomlangan o'zgaruvchi qo'shilgan. Bu o'zgaruvchi har qanday qidiruv jarayonida taqqoslashlar sonini saqlaydi. Dastur natijasida har bir qidiriladigan element uchun topilgan element va taqqoslashlar soni chiqadi.
Kod ishlash jarayonidan screenshot:
python dasturlash tilida qilindi .barcha funcsiya va methodlar coplier tomonidan genratsiya qilinadi .
|
| |
