Abdujalil baxromovning

24-labaratoriya mashg’uloti Mavzusi: Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi.

Esingizda bo’lsa bu masalani xasislik algoritmlari orqali yechgandik. Xasislik algoritmlarining xususiyatlaridan kelib chiqib, biz o’shanda 3000 natijasini olgandik. Chunki xasislik algoritmi har doim ham optimal yechimni bermaydi, balki, u yechimni tezkorlik bilan topishga yordam beradi. Yechim yetarlicha bo’ladi, lekin optimal bo’lmasligi mumkin. Masala uchun Xasislik algoritmida algoritm murakkabligi bahosi O(n) ga teng.
Dinamik dasturlashda esa, masalaning optimal yechimi topiladi. Bunda masala qism masalalarga ajratilib keyin umumlashtirilgani uchun yechimni olishda xasislik algoritmidan biroz ko’proq vaqt sarflanadi. Yechim esa optimal bo’ladi. Masala uchun Dinamik dasturlashda algoritm murakkabligi bahosi O(n^2) ga teng.
Amaliy qism
1-misol. Shunday uch xonali son topingki, uni 11 ga bo’lganda bo’linma uning raqamlari yig’indisiga teng bo’lsin.
Program L23;
uses Crt;
var
a, n, p, s : integer;
begin
a := 100;
writeln(' 11 ga bo’lganda bo’linma uning raqamlari yig’indisiga teng ’);
write(‘bo’lgan uch xonali son ');
repeat
n := a; s := 0;
repeat
p := n mod 10;
s := s + p*p;
n := n div 10
until n = 0;
if (a mod 11 = 0) and (s = a div 11) then write(a, '; ');
a := a + 1
until a = 1000;
end.
2- misol. n soning barcha bo’luvchilarini aniqlovchi dastur tuzilsin.
Bunday masala berilganda talabalar ko’pincha quyidagi yechish usulini taklif etishadi.
1 dan to n gacha bo’lgan barcha natural sonlarni ko’rib chiqish kerak, agar ulardan birontasi n soninig bo’luvchisi bo’lsa, uni ekranga chiqarish kerak. Masalan 36 soni uchun tekshirish maqsadida 1, 2, 3, ..., 36 sonlarini olamiz va ulardan 36 ning bo’luvchilarini tanlab olamiz. Bo’luvchilar quyidagilardir: 1, 2, 3, 4, 6, 9, 12, 18 va 36. Bunday usuldan foydalanish mumkin. Lekin, diqqat bilan 36 ning bo’luvchilariga qarab chiqsangiz, bularning barchasi 1 dan to 18 gacha, ya’ni 36 ning yarmigacha bo’lgan oraliqda joylashganligini ko’rasiz, faqatgina oxirgi bo’luvchi - sonning o’zidir. 
Mantiqan o’ylaganda ham, shunga amin bo’lamizki, bo’luvchilar aynan: 1 dan n/2 gacha bo’lgan oraliqda joylashadi.
Agar sonning yarmidan ham katta bo’luvchi bor degan fikr tug’ilsa, uni 2 ga ko’paytirib berilgan sondan katta son hosil qilamiz. Shunday qilib, sonning o’zidan tashqari barcha bo’luvchilari 1 dan n/2 gacha bo’lgan oraliqda joylashishi ayon bo’ladi, demak sonning bo’luvchilarini aynan shu oraliqdan tekshirish kerak. Bu yerdan dasturni tuzish rejasi kelib chiqadi: 1 dan n/2 gacha bo’lgan sikl tashkil etish; agar nson ushbu oraliqdagi biror-bir songa bo’linsa, u holda ushbu bo’luvchi ekranga chiqarilsin; sikl davom ettirilsin; ekranga sonning o’zi chiqarilsin.