1. Dasturiy ta’minot va uning turlari

99. Satrlarda qismiy satrlarni izlash algoritmi Rabin-Karp algoritmini keltiring
Naive algoritmi singari, Rabin-Karp algoritmi ham naqshni birma-bir siljitadi. Ammo Naive algoritmidan farqli o'laroq, Rabin Karp algoritmi naqshning xesh qiymatini matnning joriy pastki qatorining xesh qiymatiga moslashtiradi va agar xesh qiymatlari mos kelsa, u faqat individual belgilarga mos kela boshlaydi. Shunday qilib, Rabin Karp algoritmi quyidagi satrlar uchun xesh qiymatlarini hisoblashi kerak.
1) Shaklning o'zi.
2) m uzunlikdagi matnning barcha pastki qatorlari.
Matnning m oʻlchamli barcha pastki satrlari uchun xesh qiymatlarini samarali hisoblashimiz kerakligi sababli, biz quyidagi xususiyatga ega boʻlgan xesh funksiyasiga ega boʻlishimiz kerak.
Keyingi siljishdagi xesh joriy xesh qiymatidan va matndagi keyingi belgidan samarali hisoblanishi kerak yoki biz aytishimiz mumkinki, hash(txt[s+1 .. s+m]) hash(txt[s .. s) dan samarali hisoblanishi kerak. +m-1]) va txt[s+m], yaʼni hash(txt[s+1 .. s+m])= rehash(txt[s+m], hash(txt[s .. s+m-) 1])) va rehash O(1) operatsiyasi bo'lishi kerak.
Rabin va Karp tomonidan tavsiya etilgan xesh funksiyasi butun sonni hisoblaydi. Satr uchun butun son qiymati qatorning raqamli qiymatidir.


100. A[n] massivni Insert usulida saralash algoritmini yozing
Massiv deyarli tartiblangan va tartiblanmagan qismga bo'lingan. Saralanmagan qismdan qiymatlar tanlanadi va tartiblangan qismning to'g'ri joyiga joylashtiriladi.
Kiritish tartibining xususiyatlari:
Bu algoritm oddiy amalga oshirish bilan eng oddiy algoritmlardan biridir
Asosan, Insertion sort kichik ma'lumotlar qiymatlari uchun samarali
Qo'shishni saralash tabiatan moslashuvchan, ya'ni qisman saralangan ma'lumotlar to'plamlari uchun mos keladi.
Qo'shishni tartiblash algoritmining ishlashi:
Misolni ko'rib chiqing: arr[]: {12, 11, 13, 5, 6}
12 11 13 5 6
Birinchi o'tish:
Dastlab, massivning dastlabki ikki elementi kiritish tartibida solishtiriladi.
12 11 13 5 6
Bu erda 12 11 dan katta, shuning uchun ular o'sish tartibida emas va 12 o'zining to'g'ri joyida emas. Shunday qilib, 11 va 12 ni almashtiring.
Shunday qilib, hozircha 11 tartiblangan pastki qatorda saqlanadi.
11 12 13 5 6
Ikkinchi o'tish:
Endi keyingi ikkita elementga o'ting va ularni solishtiring
11 12 13 5 6
Bu erda 13 12 dan katta, shuning uchun ikkala element ham o'sish tartibida ko'rinadi, shuning uchun almashtirish sodir bo'lmaydi. 12, shuningdek, 11 bilan birga tartiblangan pastki qatorda saqlanadi

Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j >= 0 and key < arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ("% d" % arr[i]) # This code is contributed by Mohit Kumra