§ 6. Использование основных алгоритмических конструкций для решения задач

6.2. Использование числовых последовательностей

Числовые последовательности позволяют описывать многие процессы, происходящие в природе и обществе. Для задания элементов числовой последовательности обычно используют один из двух способов:

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

Есть последовательности, которые можно задавать как первым способом, так и вторым (пример 6.11).

Последовательности могут строиться из случайных чисел.

Пример 6.12. Вывести на экран первые k элементов последовательности заданной формулой  «math style=¨font-family:`Courier New`¨ xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mstyle mathsize=¨18px¨»«msub»«mi»a«/mi»«mi»n«/mi»«/msub»«mo»§#160;«/mo»«mo»=«/mo»«mo»§#160;«/mo»«mfrac»«mi»n«/mi»«mrow»«msup»«mi»n«/mi»«mn»2«/mn»«/msup»«mo»§#160;«/mo»«mo»+«/mo»«mo»§#160;«/mo»«mn»1«/mn»«/mrow»«/mfrac»«/mstyle»«/math».

Этапы выполнения задания

I. Исходные данные: k (количество чисел).

II. Результат: k чисел последовательности.

III. Алгоритм решения задачи.

1. Ввод числа k. 
2. Так как количество чисел заранее известно, то для их получения можно воспользоваться циклом for. 
3. Текущее число будем хранить в переменной а. Значение a вычисляется по формуле и зависит от значения n — счетчика цикла. Переменная n будет изменяться от 1 (номер первого четного числа) до k (номер последнего числа). 
4. Полученные числа будем выводить в цикле через пробел.

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

Пример 6.13. Найти первый элемент последовательности, заданной рекуррентно «math style=¨font-family:Arial¨ xmlns=¨http://www.w3.org/1998/Math/MathML¨»«msub»«mi»a«/mi»«mi»n«/mi»«/msub»«mo»§#160;«/mo»«mo»=«/mo»«mo»§#160;«/mo»«mfrac»«mrow»«msub»«mi»a«/mi»«mi»n«/mi»«/msub»«mo»§#160;«/mo»«mo»-«/mo»«mo»§#160;«/mo»«mn»1«/mn»«/mrow»«mroot»«mrow»«mn»2«/mn»«msup»«mi»n«/mi»«mn»2«/mn»«/msup»«/mrow»«mn»3«/mn»«/mroot»«/mfrac»«mo»,«/mo»«mo»§#160;«/mo»«mo»§#160;«/mo»«mo»§#160;«/mo»«mi»a«/mi»«mn»1«/mn»«mo»§#160;«/mo»«mo»=«/mo»«mo»§#160;«/mo»«mi»b«/mi»«mo»(«/mo»«mi»b«/mi»«mo»§#160;«/mo»«mo»§#62;«/mo»«mo»§#160;«/mo»«mn»0«/mn»«mo»)«/mo»«/math», который меньше 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. Формула «math style=¨font-family:Tahoma¨ xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mstyle mathsize=¨14px¨»«msub»«mi»a«/mi»«mi»n«/mi»«/msub»«mo»§#160;«/mo»«mo»=«/mo»«mo»§#160;«/mo»«mfrac»«mi»n«/mi»«mrow»«msup»«mi»n«/mi»«mn»2«/mn»«/msup»«mo»§#160;«/mo»«mo»+«/mo»«mo»§#160;«/mo»«mn»1«/mn»«/mrow»«/mfrac»«/mstyle»«/math» задает следующую последовательность: 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 — Онлайн-энциклопедия целочисленных последовательностей.