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

 
Алгоритм
 
Ҳисоблаш қурилмаси
 
Кириш 
маълумотлари
 
Чиқиш 
маълумотлари
 

---

Қуйида биз кўриб чиққан алгоритмнинг янада тизимлаштирилган тавсифи келтирилади. 
Евклид алгоритми бўйича m ва n сонларга ЭКУБ ҳисоблаш: 
1-қадам Агар n = 0 бўлса, m ни жавоб сифатида қайтариш ва ишлашни тугатиш; акс ҳолда 
иккинчи қадамга ўтиш. 
2-қадам m ва n сонларга бутун бўлиш ва колдиқ қийматига r ўзгарувчини бериш. 
3-қадам n қийматга m ўзгарувчини бериш, r қийматга эса n ўзарувчини бериш. 1-қадамга 
ўтиш. 
Муқобил сифатда ўша бир алгоритмни псевдокод кўринишида ёзамиз: 
// Евклид алгоритми gcd (m, n) функциянинг қийматини ҳисоблайди 
// Кириш маълумотлари: бир вақтда нолга тенг бўлиши мумкин
иккита номанфий бутун m ва n сонлар 
// Чиқиш маълумотлари: m ва n сонларининг энг катта умумий
бўлувчиси 
While n≠0 do 
r←m 
m←n 
n←r 
rеturn m 
Пировардида, биз Евклид алгоритмининг тугашига ишонч ҳосил қилишимиз мумкинми? Бу 
қуйидаги далилни қайд этишдан келиб чиқади: итерациянинг ҳар бир қадамида жуфтлик иккинчи 
сонинг (n) қиймати камаяди, чунончи у аниқланиши бўйича нолдан кичик бўлмаслиги керак. 
Аслини олганда, навбатдаги итерацияда (m mod n) ифодани ҳисоблаш натижасида олинадиган n 
сонинг янги қиймати олдинги n сонинг қийматидан ҳар доим кичик бўлади. Натижада, эртами-
кечми жуфтлик иккинчи сонинг қиймати 0 га тенг бўлади ва алгоритмнинг бажарилиши 
тугайди. 
Кўплаб бошқа масалаларни ечилишидаги каби ЭКУБни ҳисоблашнинг бир неча алгоритмлари 
мавжуд. Келинг, бу масалани ечилишининг бошқа иккита усулларини кўриб чиқамиз. Улардан 
биринчиси m ва n сонлар унги қолдиқсиз бўлиниши учун энг катта бунни соннинг танланишига 
асосланган. Равшанки, умумий бўлувчи жуфтлик сонларнинг энг кичигидан катта бўлмаслиги, 
уни t = min {m, n} сифатида ёзиш мумкин. Шунинг учун алгоритмнинг бажарилишини m ва n сонлар 
t сонига қолдиқсиз бўлинишини текширишдан бошлаш мумкин. Агар бу шундай бўлса, t сони 
жавоб ҳисобланади. Агар бўндай бўлмаса, t сонининг қийматини бирга камайтириш ва 
текширишни яна бажариши керак. (Пировардида, биз жараённинг тугашига ишонч ҳосил 
қилишимиз мумкинми?). масалан, юқорида кўриб чиқилган (60,24) жуфтлик сонлари учун 
алгоритмнинг бажарилиши 24 сонини текширишдан бошланади, кейин 23 сонини ва t сони 12 
сонига тенг тенг бўлмагунча текширади, бундан кейин алгоритм ўз ишини тугатиши керак. 
Кетма-кет танлаб кўриш бўйича m ва n сонларга ЭКУБ ҳисоблаш: 
1-қадам min {m, n} функция қийматига t ўзгарувчини бериш. 
2-қадам m сонини t сонига бўлиш. Агар қолдиқ 0 га тенг бўлса, 3-қадамга ўтиш; акс ҳолда 4-
қадамга ўтиш. 
3-қадам n сонини га бўлиш. Агар қолдиқ 0 га тенг бўлса, t сонини жавоб сифатида қайтариш 
ва ишни тугатиш; акс ҳолда 4-қадамга ўтиш. 
4-қадам t сонидан 1 сонини айириш. 2-қадамга ўтиш. 
Эътибор берингки, Евклид алгоритмидан фарқли равишда биз кўриб чиққан ЭКУБни қидириш 
алгоритм, агар камида унинг кириш параметрларидан бири нолга тенг бўлса, юқорида 
тавсифланган шаклда тўғри ишламайди. Шундай қилиб, бу мисол алгоритмнинг кириш 
параметрларининг йўл қўйиладиган қийматлари диапазонларини яққол аниқлаш муҳимлигини 
кўрсатишга имкон беради. 
ЭКУБни қидиришнинг учинчи усули сизга ўрта мактаб фанидан таниш бўлиши керак. 
Кетма-кет танлаб кўриш бўйича иккита m ва n сонларга ЭКУБ ҳисоблаш: 
1-қадам m сонини оддий кўпҳадларга ёйиш. 
2-қадам n сонини оддий кўпҳадларга ёйиш. 
3-қадам 1- ва 2-қадамларда аниқланган m ва n сонларининг оддий кўпҳадлари учун уларнинг 
умумий бўлучиларини ажратиш. (Агар р сони m ва n сонларининг умумий бўлувчиси ҳисобланса ва 

---

уларнинг оддий кўпҳадларга ёйилишида мос равишда Рm ва Рn марта учраса, у ҳолда ажратишда 
буни mill { Рm, Рn} марта такрорлаш керак. 
4-қадам барча ажратилган бўлувчиларнинг кўпайтмасини ҳисоблаш ва уникўрсатилган 
иккита сонларга ЭКУБни қидириш натижаси сифатида қайтариш.
Шундай қилиб, юқорида кўриб чиқилган (60,24) жуфтлик сонлар учун қуйидагини оламиз: 
60 = 2·2·3·5 
24 = 2·2·2·3 
gcd (60, 24) = 2·2·3 = 12 
Мактаб йиллари бўйича соғиниш бизга хулоса қилишга ҳалал бермаслиги керакки, кўриб 
чиқилган ЭКУБни қидириш усулларидан охиргиси Евклид алгоритмига қараганда анча мураккаб ва 
секин. Лекин ҳатто унинг паст самарадорлигини эътиборга олмаганда, мактабда ўрганиладиган 
ЭКУБни аниқлаш усулини қонуний алгоритм деб ҳисоблаш мумкин эмас (камида бу ерда тақдим 
этилган кўринишда). Сиз нимага деб сўрайсиз? Бутун иш шундан иборатки, оддий кўпҳадларга 
ёйиш босқичлари бир хил аниқланмаган. Уларнинг бажарилиши учун оддий сонларнинг рўйхати 
талаб қилинади, мен эса негадир аминманки, мактаб ўқитувчиси бундай рўйхатни қандай тузишни 
тушунтирмаган. Сиз, албатта, бу бундай асоссиз айблаш учун сабаб бўлмайди деб эътиз 
билдиришингиз мумкин. Лекин бу момент аниқлаштириб олинмагунча, биз, масалан. бу 
алгоритмни ишлатадиган қандайдир дастурлаштириш тилларида ёза олмаймиз. (Айтгандай, бу 
нуқтаи назардан 3-қадам ҳам етарлича яққол аниқланмаган. Лекин унинг ноаниқлигини оддий 
кўпҳадларга ёйиш босқичига қараганда анча ойдинлаштириш мумкин ва яна сиз иккита 
рўйхатлардан умумий элементларни қандай ажратиб олиш ниятидасиз?). 
Демак, ихтиёрий берилган n бутун сондан ошмайдиган унча мураккаб бўлмаган оддий сонлар 
кетма-кетликларини генерацияланиши алгоритмини кўриб чиқиш вақти келди. Эҳтимол, қадимги 
Юнонистонда ўйлаб топилган ва Эратосфен решети (тахминан эрамизгача 200 йил) дейилади.