Елементи послідовності, які обчислюємо через попередні
Початок: 3
Додаємо 4 щоразу
3 → 7 → 11 → 15 → 19
Збережене значення допомагає отримати нове
За номером або через попереднє значення
Раніше ми підставляли номер i у формулу, наприклад aᵢ = 1/i. Тепер обчислюватимемо новий елемент, використовуючи вже знайдені значення.
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; у складених виразах перевіряй також проміжні добутки.
Дано натуральне n. Надрукуйте з 5 знаками після крапки n чисел:
Послідовність 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...).
Послідовність 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 ...).
Дано натуральне n. Надрукуйте з 6 знаками після крапки послідовність із n чисел:
Послідовність 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 ...).
Дано натуральне n. Надрукуйте з 3 знаками після крапки послідовність із n чисел: