§ 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 — Онлайн-энциклопедия целочисленных последовательностей.