Алгоритмларни лойиҳалашга кириш. Алгоритмларни вақт ва ҳажм бўйича баҳолаш. Кўпҳадлар қийматларини ҳисоблашда

"greatest common divisor"
билан белгилаймиз 
(чунончи, m ва n сонлар бир вақтда нолга тенг бўлиши мумкин). 
Аниқланиши бўйича бу функция ҳам m га, ҳам n га қолдиқсиз бўлинадиган 
энг катта бутун сонни топиши керак. Александриялик қадимги юнон 
математиги Евклид (эрамизгача III аср) шу билан шухрат қозонганки, у 
биринчи марта геометрия фанини тизимли тавсифлади, ўзининг ишларидан 
бири бўлган Бошланиш дейиладиган асарида бу масалани ечилишининг 
алгоритмини тавсифлади. Замонавйи тилди айтганда, Евклид алгоритми 
қуйидаги тенгсизликни рекуррент ҳисоблашга асосланган:
gcd (m, n) = gcd (m mod n ) 
Бу ерда (m mod n ) ифода m ва n га бўлишдан қолдиқ ҳисобланади. 
Алгоритмнинг бажарилиши (m mod n ) ифода нолга тенг бўлганида тугайди. 
Бинобарин, ged (m, 0) = (негалиги тушунарли?), охирги олинган m қиймат 
ҳам дастлабки m ва n сонларга ЭКУБ ҳисобланади.
Масалан, (60, 24) жуфт сонларга ЭКУБни ҳисоблаш қуйидаги тарзда 
бажарилиши мумкин: gcd (60, 24) = gcd (24, 12) = gcd (12, 0) = 12. (агар бу 
алгоритм сизда таасурот қолдирмаган бўлса, масалан, 1.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 

---