Модел ва алгоритм тушунчаси

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 кўринишида эканлигига ишонч хосил қилиш мумкин.
program karrali;
label 1;
var
i:byte; s:integer;
begin
s:=12; i:=4;
1: s:=s+i;
i:=i+4;
if i<=99 then goto 1;
writeln(‘s=’,s);
readln;
end.


Масала. Фибоначчи кетмакетлигининг nҳадини топиш рекуррент боғланиши ва алгоритми тузилсин. Фибоначчи кетма-кетлигида биринчи ва иккинчи ҳад 1 га тенг бўлиб, қолган ҳадлари 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 кўринишда бўлади.