Маъруза – Алгоритмлаш асослари Режа

7. Ичма-ич жойлашган циклик алгоритмлар




Баъзан, такрорланувчи алгоритмлар бир нечта параметрларга боғлиқ бўлади. Одатда бундай алгоритмларни ичма-ич жойлашган алгортмлар деб аталади.
Мисол сифати берилган nxm ўлчовли a_ij –матрица элементларининг йиғиндисини ҳисоблаш масаласини қарайлик.
1-мисол. Бу ерда i- матрицанинг сатри номери, j-эса устун номерини ифодалайди. Юқоридаги йиғинди ифодагига мос равишда, сатр элементлари йиғиндисини кетма-кет ҳисоблаш зарур бўлади. Юқоридаги блок-схемада шу алгоритм ифодаланган.

2

мисол. Бу йиғинди ҳисоблаш учун, i нинг ҳар бир қийматида j бўйича кўпайтмани ҳисоблаб, аввал йиғинди устига кетма-кет қўшиб бориш керак бўлади. Бу жараён қуйидаги блок–схемада акс эттирилган. Бу ерда i-ташқи цикл - йиғинди учун, j-эса ички цикл-кўпайтмани ҳосил қилиш учун фойдаланилган.
Мустақил бажариш учун топшириқлар.

1. 
   4 хонали сонлар орасидан аввалги иккита рақамли йиғиндиси, кейинги 2 рақамли йиғиндисига тенг бўлган сонлар чоп этилсин ва миқдори аниқлансин.
   
2. 
   Берилган a_ij nxn ўлчовли матрицанинг сатр элементларининг йиғиндиси чоп этилсин.
   
3. 
   nxm ўлчовли a_ij матрицанинг элементларининг энг катта ва кичик элементлари топилсин.
   

8. Рекуррент алгоритмлар.

Ҳисоблаш жараёнида баъзи бир алгоритмларнинг ўзига қайта мурожаат қилишга тўғри келади. Ўзига–ўзи мурожаат қиладиган алгоритмларга реккурент алгоритмлар ёки рекурсия деб аталади.

Бундай алгоритмга мисол сифатида Фибоначчи сонларини келтириш мумкин. Маълумки, Фибоначчи сонлари қуйидагича аниқланган.

1-мисол. а₀=а₁=1, а_i=а_i-1+а_i-2 i= 2,3,4,

Бу реккурент ифода алгоритмига мос келувчи блок-схема юқорида келтирилган. Эслатиб, ўтамиз формуладаги i-индексга ҳожат йўқ, агар Фибоначчи сонининг номерини ҳам аниқлаш зарур бўлса, бирорта параметр-калит киритиш керак бўлади.
2

-мисол.
Бу ифода i нинг ҳар бир қийматида факториални ва йиғиндини ҳисоблашни тақозо этади. Шунинг учун аввал факториални ҳисоблашни алоҳида кўриб чиқамиз. Қуйидаги реккурент ифода факториални кам амал сарфлаб қулай усулда ҳисоблаш имконини беради.
Р=1
Р=Р*2i*(2i+1)
Ҳақиқатан ҳам, i=1 да 3! ни, i=2 да Р=3!*4*5=5! ни ва ҳакозо тарзда (2i1)! ни юқоридаги реккурент формула ёрдамида ҳисоблаш мумкин бўлади. Бу мисолга мос келувчи блок-схема қуйида келтирилган.

Мустақил бажариш учун топшириқлар

1. ҳисоблансин.
2. ҳисоблансин.