[Ç̲ÑÒ]              [Äàë³]                   [Íàçàä]

 

3.2. Ïðîãðàìóâàííÿ ðåêóðåíòíèõ ñï³ââ³äíîøåíü

 

          3.9. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ åëåìåíò³â ïîñë³äîâíîñòåé

à)  ;                            ä) ;

á)  ;                   å) ;

â)  ;                          æ) ;

ã)  ;                   ç) .

 

          Ðîçâ`ÿçîê ã) Ñêëàäåìî ðåêóðåíòíå ñï³ââ³äíîøåííÿ äëÿ îá÷èñëåííÿ xk

          x0=x, xk=, k=1,2...

          Ïåðåäáà÷èâøè ââåäåííÿ ³ âèâåäåííÿ, îòðèìàºìî

                   àëã Ðåêóð öå

                             çì³í õ,ó:ä³éñí;

                                      ³,ï:íàò;

                   ïî÷

                             âçÿòè (õ,ï);

                             ó¬1;³¬0;

                             ïîâò ï ðàç

                                      ³¬³+1;

                                      ó¬ó*õ/³

                             êö;

                             ïîêàçàòè (ó)

                   êà.

 

          3.10. ×èñëàìè Ô³áîíà÷÷³ íàçèâàºòüñÿ ÷èñëîâà ïîñë³äîâí³ñòü {Fn}, çàäàíà ðåêóðåíòíèì ñï³ââ³äíîøåííÿì äðóãîãî ïîðÿäêó

          F0=0; F1=1; Fk=Fk-1+Fk, k=2,3,...

          Ñêëàñòè àëãîðèòì äëÿ îá÷èñëåííÿ Fn

 

          Ðîçâ`ÿçîê.ßêùî çì³ííà f áóäå ïðîá³ãàòè ïîñë³äîâí³ñòü Ô³áîíà÷÷³, òî äâîõ äîäàòêîâèõ çì³ííèõ sf ³ t áóäå äîñòàòíüî äëÿ ïîçíà÷åííÿ íàñòóïíèõ äâîõ ÷èñåë

                   Àëã Ô³áîíà÷÷³ öå

                             çì³í n,f,sf,t:íàò;

                   ïî÷

                             âçÿòè (ï);

                             f¬0;sf¬1;

                             {f =F0, sf =F1}

                             ïîâò ï ðàç

                                      t¬f+sf;

                                      f¬sf;sf¬t

                             êö;

                             {f =Fn, sf=Fn+1}

                             ïîêàçàòè (f)

                   êà.

 

          3.11. Ñêëàñòè àëãîðèòì îá÷èñëåííÿ äîâ³ëüíîãî ÷ëåíà ïîñë³äîâíîñòåé, ÿê³ çàäàí³ ðåêóðåíòíèìè ñï³ââ³äíîøåííÿìè:

 

à)  xn=xn-1+xn-3,               x0=x1=1, x2=2,       n=3,4,...;

á)  xn=2xn-1+3xn-2,             x0=0, x1=9,            n=2,3,...;

â)  xn=xn-1+xn-2+xn-3,         x0=x1=1, x2=6,       n=3,4,...;

ã)  xn=xn-1+4xn-3,              x0=x1=x2=2,           n=3,4,...;

ä)  xn=xn-1*(xn-2+1),          x0=1, x1=1,            n=2,3,...;

å)  xn=,   x0=0, x1=, n=2,3,...;

 

          3.12. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ ñóì:

 

à)  Sn=;       

 

á)  Sn =;

 

â)  Sn =;

 

ã)  Sn =;

 

ä)  Sn =1-2-3+4-5-6+...+(3n-2)-(3n-1)-3n;

 

å)  Sn =1+2+3+...+n;                æ)      Sn =a+2a2+3a3+...+nan;

 

ç)  Sn =;                  ³) Sn =;                  ê) Sn =;

 

ë)  Sn =;                   ì) Sn =;              í) Sn =;

 

î)      Sn =;                       ï) Sn =.

 

          Âêàç³âêè. Ñóìó Sn îá÷èñëèòè çà äîïîìîãîþ ðåêóðåíòíîãî ñï³â­â³äíîøåííÿ S0=0, Sk=Sk-1+ak, k=1,2,...n, äå ak - k-òèé äîäàíîê.

 

ç)  Si=2Si-1+i2; ³)     Sn =2n;       ë)      Sn =;       ì)      ak =2kak-1.

 

          3.13. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ äîáóòê³â:

 

à)  ;         á)    ;

 

â)  ;           ã)    .

 

          Âêàç³âêà. Äîáóòîê Pn îá÷èñëèòè çà äîïîìîãîþ ðåêóðåíòíîãî ñï³ââ³äíîøåííÿ P0=1; Pk=Pk-1*ak, k=1,2,...,n, äå ak - k- òèé ìíîæíèê.

 

          3.14. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ ëàíöþãîâèõ äðîá³â

 

à)  ;     

 

 

 

 

 

          Âêàç³âêà. Âèêîðèñòàòè ðåêóðåíòí³ ñï³ââ³äíîøåííÿ

à)  b0=b, bk=b+, k=1,2,...n;

â)  b0=4n+2, bk=4(n-k)+2+, k=1,2,...n.

 

          3.15. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ

 

à)  ìíîãî÷ëåíà ×åáèøîâà

          T0(x)=1, T1(x)=x,

          Tn(x)=2xTn-1(x) - Tn-2(x), n=2,3,...;

 

á)  ìíîãî÷ëåíà Åðì³òà

          H0(x)=1, H1(x)=2x,

          Hn(x)=2xHn-1(x) - 2(n-1)Hn-2(x), n=2,3,...

çàäàíîãî ñòåïåíþ n â òî÷ö³ õ.

 

          3.16. Ñêëàñòè àëãîðèòì îá÷èñëåííÿ äîâ³ëüíîãî åëåìåíòà ïîñë³äîâíîñòåé, çàäàíèõ ðåêóðåíòíèìè ñï³ââ³äíîøåííÿìè

 

à)  v0=1,v1=0.3,               vi=(i+2)vi-2 , i=2,3,...

 

á)  v0=v1=v2=1,                vi=(i+4)(vi-1 - 1)+(i+5)vi-3  ,       i=3,4,...

 

â)       v0=v1=0,v2=,       vi=,     i=3,4,...  

 

          3.17. Ñêëàñòè àëãîðèòì îá÷èñëåííÿ äîâ³ëüíîãî åëåìåíòà ïîñë³äîâ­íîñò³ vn, âèçíà÷åíî¿ ñèñòåìîþ ñï³ââ³äíîøåííü

 

v0=v1=1,                vi =  ,           i=2,3,..;

 

äå u0=u1=0 ,          ui = , i=2,3,... .

 

          3.18. Ñêëàñòè àëãîðèòì äëÿ îá÷èñëåííÿ ñóì

 

à)  Sn =,   äå a1=0, a2=1, ak=ak-1+k*ak-2, k=3,4,...;

 

á)  Sn =,     äå a1=1, a2=1, ak= ,     k=3,4,...;

 

â)  Sn =,      äå a1=1, a2=1, ak=,      k=3,4,...;

 

ã)  Sn =,    äå a1=0, a2=1, ak=ak-1+,      k=3,4,...;

 

ä)  Sn =,     äå a1=a2=a3=1, ak=ak-1+ak-3,   k=4,5,...;

 

å)  Sn =, äå a0=1, ak=kak-1+,                        k=1,2,...

 

          Âêàç³âêà. Ïîçíà÷èìî çàãàëüíèé ÷ëåí ðÿäó ÷åðåç bk. Ïîñë³äîâí³ñòü àk çàäàºòüñÿ çàëåæíîñòÿìè  âèãëÿäó (R1) äëÿ å), (R2) äëÿ à)--ã) òà (R3) äëÿ ä); Sk=g(Sk-1, bk). Çíà÷åííÿ àk áóäóòü îá÷èñëþâàòèñü çà òåîðåìàìè 1-2. Äëÿ îá÷èñëåííÿ ïîñë³äîâíîâíîñò³ Sk öèêëè äîïîâíþþòüñÿ îäí³ºþ çì³ííîþ.

          Ðîçâ`ÿçîê ä). Ââîäÿ÷è äîïîì³æíó çì³ííó äëÿ îá÷èñëåííÿ  2k ³ âèêîðèñòîâóþ÷è ðåêóðåíòí³ ñï³ââ³äíîøåííÿ t0=1, tk=2tk-1, k=2,3,.. äëÿ çíàõîäæåííÿ ö³º¿ ñèñòåìè îòðèìàºìî àëãîðèòì

                   àëã  Ñóìà  öå

                             çì³í u , v, w, t, r, s: ä³éñ;

                                      n: íàò;

                   ïî÷

                             âçÿòè (n);

                             u¬1;  v¬1; w¬1;  t¬1;  s¬0;

                             { u=a1,  v=a2,  w=a3 }

                             ïîâò  n  ðàç

                                      t¬t*2;  

                                      s¬s+u/t;

                                      r¬u+w;  u¬v;  v¬w;  w¬r

                             êö;

                             ïîêàçàòè (s)

                   êà.

 

          3.19. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ ñóì

 

à)  Sn =,

 

äå      ,    ; k=3,4,...;

 

á)  Sn =,

 

äå      ;        ;      k=2,3,...;

 

u,v - çàäàí³ ä³éñí³ ÷èñëà;

 

â)  Sn =,

 

äå      ; ;      k=2,3,...;

 

ã)  Sn =,

 

äå      ;         ; k=2,3,...;

 

ä)  Sn =,

 

äå      ;           ; k=1,2,... .

 

          Ðîçâ`ÿçîê ä). Ïîñë³äîâíîñò³ {an} ³ {bn} çàäàí³ ðåêóðåíòíèì ñï³ââ³äíîøåííÿìè ïåðøîãî ïîðÿäêó, ïðîòå çàëåæí³ñòü ïåðåõðåñíà. Âèêîðèñòî­âóºìî ïî îäí³é äîïîì³æí³é çì³íí³é äëÿ êîæíî¿ ç ïîñë³äîâíîñòåé. Îòðèìàºìî àëãîðèòì

 

                   àëã   Ñóìà   öå

                             çì³í a, b, aa, bb, s:ä³éñ;

                                      n:íàò;

                   ïî÷

                             âçÿòè (n);

                             a¬1; b¬1; s¬0,5;

                             ïîâò n ðàç

                                      aa¬a*b; bb¬a+b;

                                      a ¬aa; b¬bb; s¬s+a/(1+b)

                             êö;

                             ïîêàçàòè (s)

                   êà.

 

          Íåâàæêî ïîáà÷èòè, ùî çì³ííó bb ëåãêî âèêëþ÷èòè.

 

          3.20. Ñêëàñòè àëãîðèòìè äëÿ îá÷èñëåííÿ äîáóòê³â

 

à)  ,            äå ,                 k=3,4,...;

 

á)  ,

 

äå         , k=2,3,... .

 

          Ðîçâ`ÿçîê à) Ïîñë³äîâí³ñòü {an} çàäàíà ðåêóðåíòíèì ñï³ââ³äíî­øåííÿì òðåòüîãî ïîðÿäêó. Äëÿ îá÷èñëåííÿ ¿¿ äîâ³ëüíîãî åëåìåíòà ak âèêîðèñòàºìî òåîðåìó 2. Òîä³ äîáóòîê Pn îá÷èñëþºòüñÿ çà äîïîìîãîþ ðåêóðåíòíîãî ñï³ââ³äíîøåííÿ P0=1, Pk=Pk-1*, äå zk -- ê-òèé ñòåï³íü ÷èñëà 3, âèçíà÷åíèé ³ç ñï³ââ³äíîøåíü z0=1, zk=zk-1*3. Ïåðåäáà÷èâøè òàêîæ çì³ííó t äëÿ îá÷èñëåííÿ ñòåïåíÿ 2ê-1, îòðèìàºìî àëãîðèòì

                   àëã   Äîáóòîê   öå

                             çì³í a0, a1, a2, w, p, z, t:ä³éñí;

                                      n:íàò;

                   ïî÷

                             âçÿòè  (n);

                             a0¬1;  a1¬1;  a2¬3;  z¬1;  p¬1;  t¬2;

                             ïîâò  n  ðàç       

                                      z¬z*3;  p¬p*a1/z;

                                      t¬t*2;

                                      w¬a0+a1/t;

                                      a0¬a1;  a1¬a2;  a2¬w

                             êö;

                             ïîêàçàòè (p)

                   êà.

 

[Ç̲ÑÒ]              [Äàë³]                   [Íàçàä]