Алгоритми на обчислення елементів послідовності

Задачі на обчислення елементів послідовності з заданою точністю

Ми обчислювали елементи послідовності таким чином: або підставляли номер елемента послідовності у формулу, або використовували значення попередніх елементів. Але ми завжди знали, скільки елементів послідовності потрібно обчислити та надрукувати, тому використовували оператор FOR.

В описаному нижче алгоритмі, обчислення та друк елементів послідовності обмежується не їх кількістю, а значенням обчисленого елементу або різницею між значеннями двох сусідніх елементів. Ясно, що для реалізації цього алгоритму потрібно використовувати цикл while, бо спочатку потрібно перевірити значення обчисленого елементу, а потім, в залежності від значення, або друкувати цей елемент та обчислювати наступний, або завершувати цикл.

Приклад 1

Друкувати числа , i=1, 2, 3... поки a_i >=1.2

У цій задачі елементи послідовності обчислюються підставленням їх номера у формулу. Підставимо та отримаємо:

a₁=2.0000, a₂=1.5000, a₃=1.3333, a₄=1.2500, a₅=1.2000.

Обчислений елемент a₆= 1.1667 менший, ніж 1.2, тому він на екран вже не виводиться.

Результат роботи програми

Відповідь
2.0000 1.5000 1.3333 1.2500 1.2000

Змінні:

Вхідних даних немає.

Вихідні:

• a – елемент послідовності (дійсного типу, бо є ділення)

Проміжні:

• i – номер елемента послідовності (цілого типу)

Алгоритм

1. До початку циклу присвоїмо початкові значення змінним a та i. Вони повинні співпадати з даними першого елемента послідовності. Номер елемента i:=1, значення елемента a:=2.
2. Нам потрібно друкувати елементи послідовності, які >=1.2. Тому у заголовку циклу while будемо перевіряти цю умову:
   • якщо умова вірна, то тіло циклу буде виконуватись, перехід на п 3;
   • якщо умова невірна, то тіло циклу пропускається, виконується перехід на оператори після циклу; в нашому випадку на кінець.
3. У тілі циклу, в операторних дужках будемо виконувати такі дії:
   • Надрукуємо обчислений елемент послідовності оператором write(a:1:4,' ').
   • Обчислимо порядковий номер наступного елементу послідовності оператором i:=i+1.
   • Обчислимо наступний елемент послідовності оператором a:=1+1/i.
   • Наприкінці тіла циклу виконується перехід на заголовок, для перевірки значення обчисленого елементу (на пункт 2).

Програма

var i:integer; a:real; begin  i:=1; a:=2;  while a >=1.2 do  begin    write(a:1:4,' ');    i:=i+1; a:=1+1/i;  end; end.

Приклад 2

Дано дійсне число e. Друкувати числа , i=1, 2, 3... поки a_i >=e.

Ця задача відрізняється від попередньої тільки тим, що число e, яке обмежує друк обчислених елементів послідовності, вводиться з клавіатури і, в залежності від введеного числа, на екран виводиться більше або менше елементів послідовності.

Результат роботи програми

Ввід	Вивід
1.1	2.0000 1.5000 1.3333 1.2500 1.2000 1.1667 1.1429 1.1250 1.1111 1.1000
1.3	2.0000 1.5000 1.3333

Змінні:

Вхідні:

• e – число, яке обмежує друк елементів послідовності (дійсного типу, за умовою)

Вихідні:

• a – елемент послідовності (дійсного типу, бо є ділення)

Проміжні:

• i – номер елемента послідовності (цілого типу)

Програма

var i:integer; a,e:real; begin  read(e);  i:=1; a:=2;  while a >=e do  begin    write(a:1:4,' ');    i:=i+1; a:=1+1/i;  end; end.

Приклад 3

Дано дійсне число e. Знайти суму всіх чисел , i=1, 2, 3..., які a_i >=e

Ця задача відрізняється від попередньої тим, що елементи послідовності, які a_i>=e, не виводяться на екран, а накопичуються у суму, яка виводиться на екран після завершення циклу.

Результат роботи програми

Ввід	Вивід
1.1	12.9290
1.3	4.8333

Змінні:

Вхідні:

• e – число, яке обмежує друк елементів послідовності (дійсного типу, за умовою)

Вихідні:

• s – сума елементів послідовності (дійсного типу, бо елементи дійсні)

Проміжні:

• i – номер елемента послідовності (цілого типу)
• a – елемент послідовності (дійсного типу, бо є ділення)

Алгоритм

1. До початку циклу присвоїмо початкові значення змінним a та i. Вони повинні співпадати з даними першого елемента послідовності (номер елемента i:=1, значення елемента a:=2).
2. Ми будемо накопичувати суму. Тому присвоїмо початкове значення суми s:=0.
3. Введемо з клавіатури значення e оператором read(e).
4. Нам потрібно друкувати елементи послідовності, які >= e. Тому у заголовку циклу while будемо перевіряти цю умову:
   • якщо умова вірна, то тіло циклу буде виконуватись, перехід на п 5;
   • якщо умова невірна, то тіло циклу пропускається, виконується перехід на оператори після циклу, в нашому випадку на пункт 6.
5. У тілі циклу, в операторних дужках будемо виконувати такі дії:
   • Накопимо обчислений елемент послідовності у суму оператором s:=s+a.
   • Обчислимо порядковий номер наступного елементу послідовності оператором i:=i+1.
   • Обчислимо наступний елемент послідовності оператором a:=1+1/i.
   • Наприкінці тіла циклу виконується перехід на заголовок для перевірки значення обчисленого елементу (на пункт 4).
6. Коли цикл закінчиться, виведемо на екран накопичену суму оператором writeln(s:1:4).

Програма

var i:integer; a,e,s:real; begin  read(e);  i:=1; a:=2; s:=0;  while a >=e do  begin     s:=s+a;     i:=i+1; a:=1+1/i;  end;  writeln(s:1:4); end.

Приклад 4

Дано дійсне число e. Знайти серед чисел , i=1, 2, 3..., перше число a_i < e і його порядковий номер i.

Ця задача відрізняється від задачі у прикладі 2 тим, що елементи послідовності, які a_i >=e, обчислюються, але не виводяться на екран. Цикл завершиться при a_i < e, яке можна вивести на екран, якщо поставити оператор виводу після завершення циклу.

Результат роботи програми

Ввід	Вивід
1.2	1.1667 6

Змінні:

Вхідні:

• e – число, яке обмежує обчислення елементів послідовності (дійсного типу, за умовою)

Вихідні:

• a – елемент послідовності (дійсного типу, бо є ділення)
• i – номер елемента послідовності (цілого типу)

Програма

var i:integer; a,e:real; begin  read(e);  i:=1; a:=2;  while a >=e do  begin     i:=i+1; a:=1+1/i;  end;  writeln(a:1:4,' ',i); end.

Приклад 5

Дано дійсне число e. Друкувати числа , i=1, 2, 3,..., поки a_i-1 -  a_i >=e

Ця задача відрізняється від задачі у прикладі 2 тим, що елементи послідовності обчислюються та виводяться на екран тоді, коли різниця між „попереднім” та „наступним” елементами досить велика та перевищує введене число e.

Тобто потрібно додатково використовувати вже відомий алгоритм: для зберігання елементів послідовності використовувати дві змінних – „попереднє” (a1) та „наступне” (a2). Причому, кожний елемент послідовності (крім першого та останнього) на одному витку циклу є „наступним”, а на другому витку „попереднім”.

Результат роботи програми

Ввід	Вивід
0.03	2.0000 1.5000 1.3333 1.2500 1.2000 1.1667
0.02	2.0000 1.5000 1.3333 1.2500 1.2000 1.1667 1.1429

Змінні:

Вхідні:

• e – число, яке обмежує друк елементів послідовності (дійсного типу, за умовою)

Вихідні:

• a1 – "попередній' елемент послідовності (дійсного типу)
• a2 – "наступний" елемент послідовності (дійсного типу)

Проміжні:

• i – номер елемента послідовності (цілого типу)

Алгоритм

1. Введемо з клавіатури значення e оператором read(e).
2. Оскільки ми будемо порівнювати різницю між „попереднім” та „наступним” елементами послідовності та число e, та використовувати цикл з передумовою while, то до початку циклу потрібно:
   • обчислити значення двох перших елементів послідовності та їх порядкових номерів, операторами: i:=1; a1:=2; i:=2; a2:=1.5;
   • вивести на екран значення першого („попереднього”) елемента послідовності оператором write(a1:1:4,' ').
3. Нам потрібно друкувати елементи послідовності, різниця між якими >=e. Тому у заголовку циклу while будемо перевіряти цю умову:
   • Якщо умова вірна (різниця між двома сусідніми елементами >=e), то тіло циклу буде виконуватись (перехід на п 4).
   • Якщо умова невірна, то тіло циклу пропускається, виконується перехід на оператори після циклу, в нашому випадку на кінець.
4. У тілі циклу, в операторних дужках будемо виконувати такі дії:
   • Виведемо на екран значення обчисленого раніше „наступного” елементу оператором write(a2:1:4,' ').
   • Виведений елемент a2 на цьому витку циклу є "наступним". На наступному витку циклу він буде "попереднім". Тому до переходу на наступний виток циклу потрібно виконати оператор a1:=a2.
   • Обчислимо порядковий номер нового „наступного” елементу послідовності оператором i:=i+1.
   • Обчислмо новий „наступний” елемент послідовності оператором a2:=1+1/i.
   • Наприкінці тіла циклу виконується перехід на заголовок для перевірки різниці між „попереднім” та „наступним” елементами (на пункт 3).

Програма

var a1,a2,e:real; i:byte; begin  read(e);  i:=1; a1:=2; write(a1:1:4,' ');  i:=2; a2:=1.5;  while a1-a2>=e do  begin   write(a2:1:4,' ');   a1:=a2;    i:=i+1; a2:=1+1/i;  end; end.

Приклад 6

Дано дійсне число e. Знайти серед чисел , i=1, 2, 3,..., перше число a_i і його номер i, таке що a_i-1 - a_i < e

Ця задача відрізняється від задачі у прикладі 5 тим, що елементи послідовності, які a_i-1 - a_i>=e, обчислюються? але не виводяться на екран. Цикл завершиться при a_i-1- a_i< e. Значення a_i та його порядкового номеру i можна вивести на екран, якщо поставити оператор виводу після завершення циклу.

Результат роботи програми

Ввід	Вивід
0.03	1.1429 7
0.02	1.1250 8

Змінні:

Вхідні:

• e – число, яке обмежує друк елементів послідовності (дійсного типу, за умовою)

Вихідні:

• a2 – "наступний" елемент послідовності (дійсного типу)
• i – номер елемента послідовності (цілого типу)

Проміжні:

• a1 – "попередній" елемент послідовності (дійсного типу)

Програма

var a1,a2,e:real; i:byte; begin  read(e);  i:=1; a1:=2; i:=2; a2:=1.5;  while a1-a2>=e do  begin    a1:=a2;    i:=i+1; a2:=1+1/i;  end;  writeln(a2:1:4,' ',i); end.

Приклад 7

Дано натуральне число n<>1. Чи є воно елементом послідовності Фібоначчі? 

Згадаємо послідовність Фібоначчи: 1, 1, 2, 3, 5, 8, 13, 21, ...

Результат роботи програми

Ввід	Вивід
6	no
13	yes

У послідовності Фібоначчі елементи обчислюються через два попередніх, тому для їх зберігання потрібно три змінних.

Змінні:

Вхідні:

• n – число, яке перевіряється (цілого типу, за умовою)

Вихідні:

• f3 – "наступне число", яке будемо порівнювати з n (цілого типу)

Проміжні:

• f1 – "перше попереднє" число (цілого типу)
• f2 – "друге попереднє" число (цілого типу)

Алгоритм

1. Введемо з клавіатури значення n оператором read(n).
2. Оскільки ми будемо обчислювати елементи послідовності через два попередніх, то до початку циклу потрібно присвоїти початкові значення першим двом змінним (f1, f2). Вони повинні співпадати з двома першими елементами послідовності.
3. Далі, у циклі, будемо обчислювати елемент f3 до тих пір, поки його значення не стане більшим або рівним введеному числу n. Тобто цикл завершиться при f3>=n. Можливі два випадки: цикл завершився при f3>n , тобто всі наступні елементи послідовності більші n і такого числа у послідовності немає; або цикл завершився при f3=n, тоді таке число є у послідовності.
4. Оскільки ми спочатку будемо обчислювати f3, а потім порівнювати його з n, краще використовувати цикл repeat.
5. У циклі будемо обчислювати елементи послідовності Фібоначчі таким чином:
   • за формулою обчислимо значення третьої змінної оператором f3:=f2+f1;
   • перед переходом на наступний виток циклу переприсвоюємо значення двох „попередніх” елементів: f1:=f2, f2:=f3.
6. Перевіримо умову завершення циклу:
   • Якщо обчислений елемент f3>=n , то обчислювати елементи більше не потрібно і цикл завершується; виконується перехід на перший оператор після циклу (пункт 7).
   • Якщо обчислений елемент f3< n , то потрібно ще обчислювати елементи послідовності і цикл продовжується; виконується перехід на перший оператор тіла циклу (пункт 5).
7. Після завершення циклу потрібно перевірити, як завершився цикл:
   • Якщо по умові f3=n, то ми знайшли елемент послідовності рівний n, і оператор writeln('yes') виведе на екран 'yes';
   • Якщо по умові f3>n, то ми обчислили елемент більший за n, і тому такого числа в послідовності немає; оператор writeln('no') виведе на екран 'no'.

Програма

var n,f1,f2,f3:longint; begin  readln(n);  f1:=1; f2:=1;  repeat     f3:=f2+f1;     f1:=f2; f2:=f3;  until f3>=n;  if f3=n then writeln('yes')          else writeln('no'); end.

Варіанти задач

1. Дано дійсне число e. Друкувати числа  i=2, 3,... ,поки a_i<=e.
2. Дано дійсне число e. Друкувати числа , i=1, 2, 3,..., поки a_i >=e.
3. Дано дійсне число e. Друкувати числа , i=2, 3, ... , поки a_i<=e.
4. Дано дійсне число e. Знайти суму всіх чисел a_i>=e, якщо числа  , i=1, 2, 3, ...
5. Дано ціле число e. Знайти суму всіх чисел a_i<=e, якщо числа , i=1, 2, 3, ...
6. Дано дійсне число e. Знайти серед чисел , i=1, 2, 3, ...,  перше число a_i< e і його номер i.
7. Дано дійсні числа e, z(0< z <1), q(q >e). Знайти серед чисел , i=2, 3, ...,  перше число a_i< e і його номер i.
8. Дано дійсне число e. Знайти серед чисел  , i=2, 3, ...,  перше число a_i>e і його номер i.
9. Дано натуральні числа e, x. Друкувати числа  , i=1, 2, 3, ...,  поки a_i - a_i-1<=e
10. Дано дійсне число e. Друкувати числа ,  i=2, 3, ...,  поки  .
11. Дано дійсне число e. Знайти суму всіх чисел, у яких , якщо числа , i=1, 2, 3, ...
12. Дано дійсне число e. Знайдіть суму всіх чисел, у яких , якщо числа , i=2,3...
13. Дано дійсне число e та натуральне число x. Знайти серед чисел , i=1, 2, 3, ...,  перше число a_i і його номер i, таке що a_i - a_i-1< e.
14. Дано дійсні додатні числа e, x, b. Знайти серед чисел  i=1, 2, 3, ..., перше число a_i і його номер i, таке що .
15. Дано натуральні числа e, z (z>1), q (q< e). Чи є серед чисел  i=2, 3, ... число e?
16. Дано натуральне число b. Чи є це число серед чисел послідовності , i=3, 4, ...?
17. Дано натуральні числа x, b, c, d, q, r. Чи є число x серед чисел послідовності  , i=3, 4, ...? Якщо ні, то надрукувати перше число a_i і його номер i , таке що a_i> x.