§ 6. Выкарыстанне асноўных алгарытмічных канструкцый для рашэння задач

6.2. Выкарыстанне лікавых паслядоўнасцей

Лікавыя паслядоўнасці дазваляюць апісваць шмат якія працэсы, што адбываюцца ў прыродзе і грамадстве. Для задання элементаў лікавай паслядоўнасці звычайна выкарыстоўваюць адзін з двух спосабаў:

1. Запісваецца залежнасць значэння элемента паслядоўнасці ад значэння нумара  (прыклад 6.9).
2. Запісваецца рэкурэнтная формула залежнасці значэння элемента ад значэння аднаго ці некалькіх папярэдніх значэнняў  (прыклад 6.10).

Ёсць паслядоўнасці, якія можна задаваць як першым спосабам, так і другім (прыклад 6.11).

Паслядоўнасці могуць будавацца з выпадковых лікаў.

Прыклад 6.12. Вывесці на экран першыя k элементаў паслядоўнасці, зададзенай формулой   begin mathsize 18px style a subscript n space equals space fraction numerator n over denominator n squared space plus space 1 end fraction end style.

Этапы выканання задання

I. Зыходныя даныя: k (колькасць лікаў).

II. Вынік: k лікаў паслядоўнасці.

III. Алгарытм рашэння задачы.

1. Увод ліку k. 
2. Паколькі колькасць лікаў загадзя вядомая, то для іх атрымання можна выкарыстаць цыкл  for. 
3. Бягучы лік будзем захоўваць у пераменнай а. Значэнне a вылічваецца па формуле і залежыць ад значэння n — лічыльніка цыкла. Пераменная n будзе змяняцца ад 1 (нумар першага цотнага ліку) да k (нумар апошняга ліку). 
4. Атрыманыя лікі будзем выводзіць у цыкле праз прабел.

IV. Апісанне пераменных: k – int, n – double.

Прыклад 6.13. Знайсці першы элемент паслядоўнасці, зададзенай рэкурэнтна a subscript n space equals space fraction numerator a subscript n space minus space 1 over denominator cube root of 2 n squared end root end fraction comma space space space a 1 space equals space b left parenthesis b space greater than space 0 right parenthesis; меншы за 10−3. Таксама вывесці нумар знойдзенага элемента. Значэнне b уводзіцца.

Этапы выканання задання

I.Зыходныя даныя: лік b.

II. Вынік: элемент паслядоўнасці, меншы за 0.001, і яго нумар.

III. Алгарытм рашэння задачы.

1.Увод ліку b.
2. Паколькі вядома ўмова працягвання работы, то выкарыстаем цыкл  while. Умова цыкла: a >= 0.001.
3. У цыкле вылічваем бягучае значэнне a і павялічваем на 1 нумар шуканага значэння.
4. Вывад выніку.

IV. Апісанне пераменных: a, b – double, n - int.

Пацверджаннем важнасці лікавых паслядоўнасцей з’яўляецца той факт, што створана цэлая энцыклапедыя лікавых паслядоўнасцей OEIS [1].

Прыклад 6.9. Формула  begin mathsize 14px style a subscript n space equals space fraction numerator n over denominator n squared space plus space 1 end fraction end style задае наступную паслядоўнасць: 0.5, 0.4, 0.3, 0.235, 0.192, … .

Прыклад 6.10. Адной з найбольш вядомых паслядоўнасцей, якую можна апісаць рэкурэнтна, з’яўляецца паслядоўнасць Фібаначы: 1, 1, 2, 3, 5, 8, 13… . Нескладана заўважыць, што кожны яе элемент, пачынаючы з трэцяга, роўны суме двух папярэдніх. Гэта можна запісаць так: an = an − 1 + an − 2, a1 = 1,  a2 =1.

Прыклад 6.11. У паслядоўнасці 2, 4, 8, 16,… кожны лік з’яўляецца ступенню 2, таму яе можна задаць формулай an = 2n. З іншага боку, кожны элемент паслядоўнасці, пачынаючы з другога, у два разы большы за папярэдні. Атрымаем формулу an = 2an − 1 (для n > 1, a1 = 2).

Прыклад 6.12.

V. Праграма:

#include <iostream>

 

using namespace std;

 

int main()

{

  int k;

  cout << "k = ";

  cin >> k;

  for (int n = 1; n <= k; n++){

    double a = 1. * n / (n * n + 1);

    cout << a << endl;

  }

  return 0;

}

VI. Тэсціраванне.

Пры вылічэнні значэння a важна памятаць, што вынікам дзялення двух цэлых лікаў (у дадзеным выпадку гэта лікі n і n2 + 1) будзе цэлы лік, таму неабходна пераўтварэнне тыпу ў рэчыўны да выканання аперацыі дзялення. Радок, у якім вылічваецца значэнне a, можна запісаць і так:

  double a = static_cast<double> n) / (n * n + 1);

Прыклад 6.13.

V. Праграма:

#include <iostream>

#include <cmath>

 

using namespace std;

 

int main()

{

  double a, b;

  cout << "b = ";

  cin >> b;

  a = b;

  int n = 1;

  while (a > 0.001){

    n++;

    a = a / cbrt(2 * n * n);

  }

  cout << "n = " << n << endl;

  cout << "a = " << a << endl;

  return 0;

}

VI. Тэсціраванне.


[1] http://oeis.org/?language=russian — Онлайн-энцыклапедыя цэлалікавых паслядоўнасцей.