C++ • Послідовності

Тема 4 • Від попереднього до наступного

Знаємо попереднє
обчислюємо наступне

Елементи послідовності, які обчислюємо через попередні

Початок: 3

Додаємо 4 щоразу

3 → 7 → 11 → 15 → 19

Збережене значення допомагає отримати нове

За номером або через попереднє значення

Раніше ми підставляли номер i у формулу, наприклад aᵢ = 1/i. Тепер обчислюватимемо новий елемент, використовуючи вже знайдені значення.

a_1=3;\quad a_i=a_{i-1}+4\quad (i=2,3,\ldots)

a₁ = 3 задає перший елемент. Запис aᵢ₋₁ означає попередній елемент, а не віднімання одиниці від значення a.

У програмі a = a + 4 спочатку обчислює праву частину зі старим значенням a, а потім записує нове значення в ту саму змінну.

Початкове значення задаємо до циклу. Якщо перший елемент уже виведено, цикл починаємо з номера 2. Номер i залишається потрібним, якщо він входить у формулу.

Деякі послідовності можна обчислювати обома способами. Наприклад, арифметична прогресія має й формулу за номером, і правило додавання сталої різниці.

Від однієї змінної до трьох

Спочатку розбери просте додавання. Приклади з факторіалами та двома попередніми значеннями опрацьовуй послідовно.

1. Нагадування: за номером

Формула aᵢ = 1/i дозволяє обчислити кожен елемент окремо. Попереднє значення не потрібне.

for (int i = 1; i <= 5; i++) {
    double a = 1.0 / i;
    cout << fixed;
    cout.precision(2);
    cout << a << " ";
}
1.00 0.50 0.33 0.25 0.20
Повна програма
#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 5; i++) {
        double a = 1.0 / i;
        cout << fixed;
        cout.precision(2);
        cout << a << " ";
    }
    return 0;
}

2. Через один попередній елемент

Починаємо з 3. Для кожного наступного числа додаємо 4. Спочатку виводимо перший елемент, потім обчислюємо й виводимо решту.

int a = 3;
cout << a << " ";
for (int i = 2; i <= 5; i++) {
    a = a + 4;
    cout << a << " ";
}
3 7 11 15 19
Повна програма
#include <iostream>
using namespace std;

int main() {
    int a = 3;
    cout << a << " ";
    for (int i = 2; i <= 5; i++) {
        a = a + 4;
        cout << a << " ";
    }
    return 0;
}

3. Факторіали 1!, 2!, …, n!

Факторіал i! є добутком цілих чисел від 1 до i. Маємо 1! = 1, 2! = 2, 3! = 6. Починаємо з f = 1 та на кожному кроці множимо його на i.

int n;
cin >> n;
long long f = 1;
for (int i = 1; i <= n; i++) {
    f = f * i;
    cout << f << " ";
}
Для n = 5: 1 2 6 24 120

Вводь n від 1 до 20. Тип long long зберігає більші цілі числа, ніж звичайний int. Значення 20! ще вміщується, 21! уже ні.

Повна програма
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long f = 1;
    for (int i = 1; i <= n; i++) {
        f = f * i;
        cout << f << " ";
    }
    return 0;
}

4. Факторіал і окрема формула

Для aᵢ = i! + 2 зберігаємо факторіал у f, а значення елемента в a. Не додаємо 2 до самого накопиченого факторіала.

int n;
cin >> n;
long long f = 1;
for (int i = 1; i <= n; i++) {
    f = f * i;
    long long a = f + 2;
    cout << a << " ";
}
Для n = 4: 3 4 8 26

Вводь n від 1 до 20.

Повна програма
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long f = 1;
    for (int i = 1; i <= n; i++) {
        f = f * i;
        long long a = f + 2;
        cout << a << " ";
    }
    return 0;
}

5. Факторіали непарних чисел

Для aᵢ = (2i + 1)! перші значення: 3!, 5!, 7!, 9!. Від попереднього факторіала до наступного бракує двох множників.

int n;
cin >> n;
long long a = 6;
cout << a << " ";
for (int i = 2; i <= n; i++) {
    a = a * (2 * i) * (2 * i + 1);
    cout << a << " ";
}
Для n = 4: 6 120 5040 362880

Вводь n від 1 до 9. Для переходу від 3! до 5! множимо 6 на 4 та на 5: отримаємо 120.

Повна програма
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 6;
    cout << a << " ";
    for (int i = 2; i <= n; i++) {
        a = a * (2 * i) * (2 * i + 1);
        cout << a << " ";
    }
    return 0;
}

6. Обернені факторіали непарних чисел

Для aᵢ = 1/(2i + 1)! окремо накопичуємо знаменник f. Ділення записуємо як 1.0 / f.

int n;
cin >> n;
long long f = 6;
cout << fixed;
cout.precision(8);
cout << 1.0 / f << " ";
for (int i = 2; i <= n; i++) {
    f = f * (2 * i) * (2 * i + 1);
    double a = 1.0 / f;
    cout << a << " ";
}
Для n = 3: 0.16666667 0.00833333 0.00019841

Вводь n від 1 до 9. Дуже малі значення за точності 8 знаків можуть відображатися як 0.00000000.

Повна програма
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long f = 6;
    cout << fixed;
    cout.precision(8);
    cout << 1.0 / f << " ";
    for (int i = 2; i <= n; i++) {
        f = f * (2 * i) * (2 * i + 1);
        double a = 1.0 / f;
        cout << a << " ";
    }
    return 0;
}

7. Через два попередні: числа Фібоначчі

Перші два числа дорівнюють 1. Починаючи з третього, кожне наступне є сумою двох попередніх. Третя змінна тимчасово зберігає нове число.

int n;
cin >> n;
long long f1 = 1, f2 = 1;
cout << f1 << " ";
if (n >= 2) {
    cout << f2 << " ";
}
for (int i = 3; i <= n; i++) {
    long long f3 = f1 + f2;
    cout << f3 << " ";
    f1 = f2;
    f2 = f3;
}
Для n = 7: 1 1 2 3 5 8 13

Вводь n від 1 до 92. За n = 1 друкуємо лише одну одиницю. У циклі не обчислюємо зайвий елемент після останнього потрібного.

Повна програма
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long f1 = 1, f2 = 1;
    cout << f1 << " ";
    if (n >= 2) {
        cout << f2 << " ";
    }
    for (int i = 3; i <= n; i++) {
        long long f3 = f1 + f2;
        cout << f3 << " ";
        f1 = f2;
        f2 = f3;
    }
    return 0;
}

Простеж появу кожного елемента

Екран програми

Не обчислюй зайве

У всіх наведених програмах виводимо рівно n потрібних елементів. Після останнього не рахуємо наступний «про запас»: він може бути завеликим для обраного типу.

Для Фібоначчі спочатку обчислюємо f3 = f1 + f2, а вже потім зсуваємо значення: f1 = f2; f2 = f3;. Інакше можна втратити одне зі старих значень.

Факторіал зростає швидко. Точність виведення не збільшує місткість типу. Для дробових виразів використовуй double і дробове ділення, наприклад 1.0 / f.

Варіанти для самостійної роботи

Збережено всі 17 варіантів і задану точність. У формулах без початкових значень i = 1, 2, …, n; за одного початкового елемента обчислюємо наступні від i = 2, за двох від i = 3.

Починай перевірку з n від 1 до 5. Це не універсальна межа: для довільних x і b добирай невеликі значення. Для точних цілих факторіалів у long long аргумент факторіала має бути не більшим за 20; у складених виразах перевіряй також проміжні добутки.

Варіант 1

  1. Надрукуйте у рядок 10 чисел з 1 знаком після крапки, якщо перше число 0.5, а кожне наступне число є сумою попереднього та числа 3.5.
  2. Дано натуральне n. Надрукуйте n чисел ai=2*i!, де i=1, 2, ...n.
↑ До вибору варіанта

Варіант 2

  1. Надрукуйте у рядок 10 чисел з 3 знаками після крапки, якщо перше число 1, а кожне наступне число є добутком попереднього та 0.5.
  2. Дано натуральне n. Надрукуйте n чисел ai=(i+1)! , де i=1, 2, ...n.
↑ До вибору варіанта

Варіант 3

  1. Надрукуйте у рядок 10 чисел з 3 знаками після крапки, якщо перше число 5, а кожне наступне число є добутком попереднього та дійсного числа b.
  2. Дано натуральне n. Надрукуйте n чисел ai=(2*i)! , де i=1, 2, ...n.
↑ До вибору варіанта

Варіант 4

  1. Надрукуйте у рядок 10 чисел з 1 знаком після крапки, якщо перше число 1000, а кожне наступне число є добутком попереднього та числа 0.5.
  2. Дано натуральне n. Надрукуйте n чисел ai=(2*i-1)! , де i=1, 2, ...n.
↑ До вибору варіанта

Варіант 5

  1. Дано натуральне n. Надрукуйте n чисел: a1=1, ai=2*ai-1+1 де i=2,3...n
  2. Дано натуральне n. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{1}{i!}
↑ До вибору варіанта

Варіант 6

  1. Дано натуральне n. Надрукуйте n чисел: a1=1, ai=3*ai-1+2 де i=2,3...n
  2. Дано натуральне n. Надрукуйте з 7 знаками після крапки n чисел:
    a_i=\frac{1}{(2i)!}
↑ До вибору варіанта

Варіант 7

  1. Дано натуральне n. Надрукуйте з 2 знаками після крапки n чисел:
    a_1=1;\quad a_i=1+\frac{a_{i-1}}{i}
  2. Дано натуральне n. Надрукуйте з 7 знаками після крапки n чисел:
    a_i=\frac{1}{(2i-1)!}
↑ До вибору варіанта

Варіант 8

  1. Дано натуральне n. Надрукуйте з 4 знаками після крапки n чисел:
    a_1=1;\quad a_i=1+\frac{1}{a_{i-1}}
  2. Дано натуральне n. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{(i+1)^2}{i!}
↑ До вибору варіанта

Варіант 9

  1. Дано натуральне n. Надрукуйте з 4 знаками після крапки n чисел:
    a_1=1;\quad a_i=a_{i-1}+\frac{1}{i}
  2. Дано натуральне n. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{(i+2)^2}{(i+1)!}
↑ До вибору варіанта

Варіант 10

  1. Дано натуральне n. Надрукуйте з 2 знаками після крапки n чисел:
    a_1=1;\quad a_i=i a_{i-1}+\frac{1}{i}
  2. Дано натуральне n та дійсне х. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{x^i}{i!}
↑ До вибору варіанта

Варіант 11

  1. Дано натуральне n. Надрукуйте з 6 знаками після крапки n чисел:
    a_1=2;\quad a_i=2+\frac{1}{a_{i-1}}
  2. Дано натуральне n та дійсне х. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{x^{2i}}{(2i)!}
↑ До вибору варіанта

Варіант 12

  1. Дано натуральне n. Надрукуйте з 6 знаками після крапки n чисел:
    a_1=1;\quad a_i=\frac{a_{i-1}}{i}
  2. Дано натуральне n та дійсне х. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{x^{2i+1}}{(2i+1)!}
↑ До вибору варіанта

Варіант 13

  1. Дано натуральне n. Надрукуйте з 6 знаками після крапки n чисел:
    a_1=1;\ a_2=2;\quad a_i=\frac{a_{i-2}+2a_{i-1}}{3}
  2. Дано натуральне n та дійсне х. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{x^{2i-1}}{(2i-1)!}
↑ До вибору варіанта

Варіант 14

  1. Дано натуральне n. Надрукуйте з 4 знаками після крапки n чисел:
    a_1=0;\ a_2=1;\quad a_i=\frac{2a_{i-2}+3a_{i-1}}{4}
  2. Дано натуральне n. Надрукуйте з 5 знаками після крапки n чисел:
    a_i=\frac{(i!)^2}{(2i)!}
↑ До вибору варіанта

Варіант 15

  1. Дано натуральне n. Надрукуйте з 5 знаками після крапки n чисел:
    a_1=1;\quad a_i=a_{i-1}+\frac{1}{i}
  2. Послідовність u1, u2, u3, ... утворюється за законом u1=0; u2=1; ui=ui-2+ui-1+fi (i=3,4, ...), де fi відповідний член послідовності Фібоначчі (f1=1; f2=1; f3=2; f4=3; f5=5;...). Дано натуральне число n. Надрукуйте послідовність u1, u2, u3,..., un (0 1 3 7 15 30...).
↑ До вибору варіанта

Варіант 16

  1. Послідовність u1, u2, u3, ... утворюється за законом u1=0; u2=1; ui=ui-2+ui-1+fi-1 (i=3,4, ...), де fi-1 відповідний член послідовності Фібоначчі (f1=1; f2=1; f3=2; f4=3; f5=5;...). Дано натуральне число n. Надрукуйте послідовність u1, u2, u3,..., un (0 1 2 5 10 20 ...).
  2. Дано натуральне n. Надрукуйте з 6 знаками після крапки послідовність із n чисел:
    b_i=\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{i!}
↑ До вибору варіанта

Варіант 17

  1. Послідовність u1, u2, u3, ... утворюється за законом u1=0; u2=1; ui=ui-2+ui-1+fi-2 (i=3,4, ...), де fi-2 відповідний член послідовності Фібоначчі (f1=1; f2=1; f3=2; f4=3; f5=5;...). Дано натуральне число n. Надрукуйте послідовність u1, u2, u3,..., un (0 1 2 4 8 15 ...).
  2. Дано натуральне n. Надрукуйте з 3 знаками після крапки послідовність із n чисел:
    b_i=i\left(\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{i!}\right)
↑ До вибору варіанта