1-мавзу. Алгоритмик масалани ечиш асослари 4соат

1.1-машқ 
1. Номидан “алгоритм” сўзи келиб чиққан инсон – Ал-Хоразмий асарлари билан танишиб 
олингнг, хусусан, "алгоритм" ва "алгебра" сўзларидаги умумийликни билиб олинг. 
2. Маълумки, АҚШ патентлик тизим фаолиятининг асосий мақсади “амалий санъатга” 
кўмаклашиш ҳисобланади. Сиз қандай ўйлайсиз, алгоритмни бу давлатда патентлаштирса 
бўладими? 
3. а) Сизнинг институтдан уйга қайтишингизнинг батафсил кўрсатмасини (бу алгоритмнинг 
тавсифида қилинганидек) тузинг. 
б) Сизнинг севимли таомингизни тайёрланишининг батафсил рецептини (бу алгоритмнинг 
тавсифида қилинганидек) тузинг. 
4. а) Евклид алгоритми ёрдамида ged (31415,14142) функциянинг қийматини топинг. 
б) Евклид алгоритми ёрдамида ged (31415,14142) функциянинг қиймати min {m, n} қийматдан 
ged (m, n) қийматгача юқоридан пастга сонларни кетма-кет саралаш алгоритмига қараганда неча 
марта тез ҳисобланишини баҳоланг. 
5. Исталган иккита m ва n мусбат сонлар учун ged (m, n) = gcd (m, n)=gcd (m mod n) тенглик 
бажарилишини исботланг. 
6. Агар Евклид алгоритми ишлатилганида биринчи сон иккинчисидан кичик бўлса нима 
бўлиб ўтади? Бундай кириш маълумотлари қўйилганида алгоритмнинг максимал бажарилиши 
вақти қандай бўлади? 
7. а) m ва n кириш параметрларининг қайси қийматларида Евклид алгоритмида 1 ≤ m, n ≤ 10 
шартда бўлиш операцияларининг минимал сони бажарилади? 
б) m ва n кириш параметрларининг қайси қийматларида Евклид алгоритмида 1 ≤ m, n ≤ 10 
шартда бўлиш операцияларининг максимал сони бажарилади? 

---

8. а) Евклид ўз асарида бутун сонли бўлиш операциялари ўрнига айириш операциялари 
ишлатиладиган ЭКУБни қидириш алгоритмини тавсифлаган. Евклид алгоритмининг бу вариантини 
псевдокодда ёзинг. 
б) Евклид ўйини [20]. Доскада иккита тенг бўлмаган мусбат сонларни ёзинг, ўйинда икки киши 
иштирок этади. Иштирокчилар навбати билан доскада олдиндан ёзилган иккита сонларнинг 
фарқига тенг бўлган мусбат сонни ёзади. Чунончи бу сон янги бўлиши, яъни у доскада ёзилган 
бўлмаслиги керак. янги сонни ёза олмаган иштирокчи ютқазган ҳисобланади. Сизнинг фикрингизча 
қайси биринчи ёки иккинчи иштирокчи устунликка эга бўлади? 
9. {
√𝑛 } функцияни ҳисоблаш алгоритмини ўйлаб топинг. 
10. Евклид такомиллаштирилган алгоритмида нафақат иккита m ва n мусбат сонларга 
ЭКУБ (уни d орқали белгилаймиз), балки шундай иккита х ва у сонлари ҳам (мусбат бўлиши шарт 
эмас) аниқланадики, бунда m·x + n·y = d тенглик бажарилади. 
а) 
Евклид такомиллаштирилган алгоритмини топинг ([[65]. 28]) ва уни ўзингиз 
ёқтирган дастурлаштириш тилидага дастур кўринишида ишлатинг. 
б) 
Дастурнинг кўринишини шундай ўзгартирингки, у исталган а, b ва с бутун 
коэффициентлар учун а·х + b·y= с диофант тенгламанинг бутун сонли ечимини топа олсин. 
(ҳисобга олинки, коэффициентларнинг айрим комбинациялари учун тенглама ечимга эга 
бўлмаслиги мумкин 
Алгоритмик масалаларни ечиш асослари 
Бу бўлимни бу бобга киришда амалга оширилган муҳим хулосани такрорлаш билан 
бошлаймиз: 
Алгоритмларни масалаларни жараёнли ечилиши деб ҳисоблаш мумкин. 
Чунончи бу ечим жавобларни олиш учун кўрсатмалар орқали қанчалик яққол аниқлайдиган 
шунчалик жавоблар ҳисобланмайди. Айнан конструктив процедураларнинг аниқланиши 
аниқлигига урғу бериш информатикани бошқа фанлардан, хусусан, ечимнинг мавжудлигини 
исботлаш ва (баъзан) ечимнинг характеристикаларини тадқиқ қилиш билан чекланадиган назарий 
математикадан ажратиб туради. 
Энди эса алгоритмларни лойиҳалаштириш ва таҳлил қилиш босқичларини санаб ўтамиз ва 
қисқача тавсифлаймиз (1.2-расм).