А. А. Медатов, М. З. Носиров, М. К

2. Тармоқ фармойиши ёрдамида циклли алгоритмларга дастурлар тузиш.
1мисол. Икки хонали, барча 4 га каррали бўлган сонлар рекуррент боғланиши ва шу сонлар йиғиндисини ҳисоблаш алгоритми тузилсин.
a) икки хонали 4 га каррали сонларнинг энг кичиги 12, кейингилари 16, 20, … 96. Демак, биринчи ҳади 12 га қолганлари эса ўзидан аввалги сонга 4 ни қўшиш ёрдамида ҳосил бўлади. Шунинг учун рекуррент боғланишни қуйидагича ёзиш мумкин. Биринчи ҳад i=12; иккинчи ҳад i=12+4, уни ўзидан аввалги ҳад билан боғласак, i=i+4; учинчи ҳад i=16+4, бу ҳолда аввалгича фикр юритиб, i=i+4 деган хулосага келамиз ва х.к.
Юқори чегара эса i<100. Демак, кетмакетликнинг ҳар бир ҳади аввалги ҳади билан i=i+4 кўринишда боғланган.
Уларнинг йиғиндисини топиш учун яна битта рекуррент боғланиш топилиши керак бўлади. Йиғинди учун бирор S ўзгарувчидан фойдаланайлик.
Аввал йиғинди сақланадиган ўзгарувчи қийматини тозалаш (нолга тенглаш) зарур. Бунинг учун унинг биринчи қийматини 0 га тенг қилиб оламиз, S=0. Йиғинди (…((12+16)+20)…) га тенг. Ушбу йиғиндини хосил қилиш учун кетмакетликнинг ҳар бир кейинги ҳадини аввалги ҳадига қўшишга тўғри келади.
Алгоритм юқоридан i<100 билан чегараланади. Юқоридагича фикр юритиб, ушбу боғланишни s=s+i кўринишида эканлигига ишонч хосил қилиш мумкин.
Масала. Фибоначчи кетмакетлигининг охирги nҳадини топиш рекуррент боғланиши ва алгоритми тузилсин.
a_i=a_i1+a_i2 (i>2 бутун сон)
Бу боғланишда кетмакетликнинг учинчи ҳади аввалги иккита ҳадининг йиғиндисига тенг шунинг учун ҳисоблаш жараёнида аввалги иккита ҳад қийматини сақлаш зарур. Бу қийматларни a ва b катталиклар билан белгилаймиз, яъни a=a_i1, b=a_i2.
Кетма кетликнинг учинчи элементини ҳосил қилиш учун a ни b га қўшиш кифоя. лекин i катталашганда a ва b ларнинг аввалги қийматларини сақлашга тўғри келади.
a=a_i=a_i1+a_i2=a+b (i>2 бутун сон) b эса a нинг аввалги қийматига тенг бўлганлиги учун, ушбу боғланишдан олдин c=a, қийматининг сақланиши талаб қилинади. Сўнгра асосий боғланиш a=a+b дан сўнг, b=c муносабатни ўрнатиш билан тўла рекуррент боғланиш ҳосил қилинади.
Демак, рекуррент муносабат a=1, b=1 дан сўнг цикл ичида c=a, a=a+b, b=c кўринишда бўлади.