Тема №3 ЦИКЛИ З ПАРАМЕТРОМ

Теоретичні відомості

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

· підготовка (ініціювання) циклу;

· виконання обчислень циклу (тіло циклу);

· модифікація параметрів;

· перевірка умови закінчення циклу.

Перша (найпростіша) конструкція мови Turbo Pascal, що дозволяє реалізувати повторення, називається циклом із заданим числом повторень (циклом з параметром, циклом із лічильником).

При виконанні ОПЕРАТОРА ЦИКЛУ З ПАРАМЕТРОМобов'язково вказуються наступні характеристики:

· ім'я змінної циклу (параметра, лічильника циклу), у якій зберігається номер повторення циклу,

· деяке початкове значення для змінної циклу (параметра, лічильника), що вона одержує при першому виконанні циклу,

· деяке кінцеве значення для змінної циклу, досягнувши котре повторення циклу припиняється (умова завершення циклу).

На мові Turbo Pascal конструкція виглядає в такий спосіб:

for i:=k₁ to k₂ do

оператор;

У наведеному записі циклу для опису об’єктів i, k₁, k₂ необхідно застосувати деякий порядковий тип. Значення i (лічильник або параметр циклу) змінюється від початкового значення k₁ до кінцевого значення k₂ збільшуючись на одиницю того порядкового типу, яким користуються (на це вказує службове слово to). Значення лічильника циклу може змінюватися в протилежному напрямку - зменшуватись на одиницю того порядкового типу, яким користуються (якщо службове слово to замінити на downto). Тобто, крок, з яким змінюється лічильник циклу, дорівнює 1 або -1. Якщо необхідно організувати перебирання об’єктів з іншим кроком, рекомендується використовувати більш універсальні циклічні конструкції while-do та repeat-until. Тілом циклу є оператор. Він може бути простим (не поділяється на менш складні) і структурованим (поділяється на менш складні), а може взагалі бути відсутнім (такі цикли називають пустими, вони застосовувалися раніше для затримки роботи програми, а зараз використовують процедуру delay).

Зауваження: Не рекомендується в тілі циклу змінювати значення параметра. Це неочікувано може змінити результати роботи програми. А таку її особливість (скоріше помилку) дуже важко знайти.

Приклад

Скласти таблицю значень функції e^x в інтервалі з кроком 1.

1) x - дійсне число, яке змінюється від -5 до 5 із кроком 1.

2) Для знаходження значень функції скористаємося стандартною (убудованою) функцією exp(x). Значення x обчислюємо за формулою: x=x+h, де h=1.

Число повторень n обчислюється за формулою: .

3) Алгоритм:

4) Вибираємо типи даних: a, b, h, x, y - дійсний тип, i, n - цілий тип.

5) Текст програми:

Program p3;

var a, b, h, x, y: real; i, n: integer;

Begin

writeln('Введіть ліву границю, праву границю та крок');

Readln(a,b,h);

n:=trunc((b-a)/h+1);

x:=a;

writeln(' Таблиця значень функції');

writeln('____________________________');

writeln('| x | y |');

for i:=1 to n do begin

y:=exp(x);

writeln('|',x:4:0,' |',y,' |');

x:=x+h;

End;

writeln('____________________________');

End.

6) Тестовий приклад: Для x=0 функція y=e^x приймає значення 1.

7) Робочий розрахунок:

Введіть ліву границю, праву границю та крок

-5 5 1

Таблиця значень функції

____________________________

| x | y |

| -5 | 6.7379469991E-03 |

| -4 | 1.8315638889E-02 |

| -3 | 4.9787068368E-02 |

| -2 | 1.3533528324E-01 |

| -1 | 3.6787944117E-01 |

| 0 | 1.0000000000E+00 |

| 1 | 2.7182818285E+00 |

| 2 | 7.3890560989E+00 |

| 3 | 2.0085536923E+01 |

| 4 | 5.4598150033E+01 |

| 5 | 1.4841315910E+02 |

____________________________

Варіанти завдань

1. Скласти таблицю функції tg(x) на інтервалі (0°,45°) із кроком 5°.

2. Обчислити частоту використання цифри c у n-значному (n<9) цілому числі a.

3. Обчислити кількість цілих чисел на проміжку (A,B) які складаються з непарних цифр.

4. Для натурального числа n обчислити .

5. Для натурального числа n обчислити значення виразу 1*2*3+2*3*4+…+n*(n+1)*(n+2).

6. Для натурального числа k обчислити значення k!! За формулою

7. Для натурального числа m обчислити значення m², користуючись наступною схемою: 1²=1, 2²=1+3, 3²=1+3+5, . . .

8. Для натурального числа n<10 обчислити y=1!+2!+3!+…+n!.

9. У кінцевій послідовності, що складається з К невід’ємних цілих чисел, знайти максимальний елемент, що ділиться на 3 без залишку.

10. Для натурального числа n обчислити .

11. Вивести на екран усі прості числа, що належать діапазону [2,n].

12. Обчислити суму m останніх цифр цілого числа с.

13. Визначити, чи є натуральне число n досконалим, тобто дорівнює сумі всіх своїх додатних дільників, крім самого цього числа. Наприклад, число 6 є досконалим: 6=1+2+3.

14. Для натурального числа n обчислити .

15. Знайти всі додатні прості дроби, знаменник яких менший за а.

16. Вивести на екран у зростаючому порядку всі трьохзначні числа, що не мають у десятковому записі цифр, які повторюються.

17. Три натуральних числа k, l, m визначають піфагорову трійку, якщо k²+l²=m². Для натурального числа n знайти всі піфагорові трійки чисел, менших за n.

18. Вивести на екран таблицю відповідності між вагою у фунтах та вагою у кілограмах для значень 10, 20, ... , 250 фунтів, врахувавши, що 1 фунт = 453 грам.

19. У послідовності чисел визначити кількість змін знаку.

20. У послідовності чисел відібрати всі додатні цілі числа та визначити їх середнє геометричне.

21. Визначити, чи є послідовність n чисел впорядкованою.

22. Знайти суму n перших парних за номером членів геометричної прогресії з першим членом b та знаменником q.

23. Обчислити кількість та вивести на екран натуральні числа у проміжку 1000 - 10000, що складаються з непарних цифр.

24. Визначити, чи є середнє арифметичне значення всіх елементів послідовності більшим за середнє арифметичне значення найменшого та найбільшого елементів.

25. Щасливим називають білет, якщо сума перших трьох цифр його шестизначного номера дорівнює сумі останніх трьох цифр номера. Розв’язати задачу пошуку щасливих білетів однієї серії кількома способами та відібрати найоптимальніший з них за часом.

Запитання для контролю та самоконтролю

1. Що таке цикл?

2. Як можна організувати повторення в програмі?

3. Які існують особливості структури та використання циклу з параметром?

4. Чи можна всі циклічні конструкції замінити однією?

5. З яких етапів складається організація циклів?

6. Які оптимальні умови застосування циклів з параметром?

7. Які властивості циклу з параметром зменшують його гнучкість?

8. Чому не рекомендується змінювати значення параметру циклу в процесі виконання цього циклу?

9. Наведіть приклади задач, де найоптимальніше користуватися саме циклом з параметром?

10. У чому цикл з параметром зменшує, а у чому збільшує витрати часу?

11. Як у циклі з параметром організувати зменшення значення параметру?

12. Чому дорівнює значення змінної циклу одразу після завершення виконання оператору циклу?

Тема №4 ЦИКЛИ З НЕВІДОМИМ ЧИСЛОМ ПОВТОРЕНЬ

Теоретичні відомості

Коли заздалегідь невідомо, скільки разів повинні бути повторені визначені дії, використовуються оператори циклів із невідомим числом повторень. У мові Turbo Pascal таких операторів два: оператор циклу с передумовою та оператор циклу с післяумовою.

ОПЕРАТОР ЦИКЛУ З ПЕРЕДУМОВОЮ while … do використовується для перевірки деякої умови на початку циклу. Формат оператора циклу:

while логічний_вираз do

Оператор;

Якщо логічний_вираз має значення True, тіло циклу (оператор) виконується, інакше виконання циклу завершується, оператор може бути простим або складеним.

ОПЕРАТОР ЦИКЛУ З ПІСЛЯУМОВОЮ repeat … until використовується для перевірки умови після кожної ітерації. Загальний вигляд оператора:

Repeat

Оператор1;

Оператор2;

…

until логічний_вираз;

Тіло циклу повторюється доти, поки значення логічного_виразу не стане True.

Для гнучкого керування циклічними операторамидо складу мови Turbo Pascal включена процедура break, яка реалізує негайний вихід із циклу. Дія процедури полягає в передачі керування оператору, що знаходиться у програмі відразу після оператора циклу.

Зауваження: Часто один циклічний оператор можна замінити іншим. Циклічні дії можна виконати без застосування операторів циклу, але технологія програмування критично відноситься до такого підходу.

Приклад

Знайти кількість членів нескінченного ряду: менших за деяке число e.

1) Дійсне число e<1 з відомим значенням, n - (результат) кількість членів ряду, менших за e.

2) Для k=1,2, … обчислюємо значення члена ряду за формулою і порівнюємо його з e. Доки для значення поточного члена ряду виконується умова a_k<e, n збільшуємо на одиницю.

3) Алгоритм:

4) Вибираємо типи даних: eps - дійсний тип; n, k - цілий тип.

5) Текст програми:

Program p4;

var n,k: integer; eps: real;

Begin

writeln('Введіть точність eps < 1');

Readln(eps);

k:=0;

n:=0;

while (k+1)/(k+2)<eps do

Begin

n:=n+1;

k:=k+1

End;

writeln('Усього ',n,' членів ряду менших за ',eps);

End.

6) Тестовий приклад:

Для e=0.81 чотири члени ряду є меншими за e.

7) Робоче обчислення:

Введіть точність eps < 1

0.95

Усього 18 членів ряду менших за 9.5000000000E-01

Варіанти завдань

1. Для цілих чисел А та В (А>В). Визначити результат ділення А на В і залишок від ділення А на В, не використовуючи стандартну операцію обчислення залишку.

2. Скласти програму обчислення значення квадратного кореня з числа а>0 з точністю e, користуючись ітераційним співвідношенням , де x_n - попереднє, x_n+1 - наступне наближення кореня. Значенням початкового наближення вважати а/2.

3. Відомо, що винахідник шахів зажадав у царя таку винагороду: за першу клітинку шахівниці дати одне пшеничне зернятко, а за кожну наступну - вдвічі більше, ніж за попередню. Запасів зерна царя виявилося недостатньо, щоб розрахуватися. Скласти програму, яка визначить, скільки клітинок можна сплатити, маючи m зерен.

4. Собака женеться за кроликом, який знаходиться попереду на m метрів. Кожен стрибок собаки дорівнює s метрів, стрибок кролика - k метрів. За скільки стрибків собака дожене кролика?

5. Користуючись формулою члена ряду з номером k скласти програму обчислення суми всіх членів ряду, більших за число а.

6. У році Х населення міста становило n людей. Визначити, через який час місто стане міліонером, якщо річний темп збільшення населення дорівнює Р%.

7. Обчислити суму з точністю ε>0 і визначити значення p, якщо відомо, що ця сума наближується до числа .

8. У деякій державі користуються грішми з номіналами 1, 2, 4, 8, 16, 32 і 64. Як найменшою кількістю таких грошей можна сплатити суму К (вказати отриману лінійну комбінацію).

9. Обчислити наближене значення нескінченної суми (справа від суми для порівняння надається її точне значення): (=1). Результат вважається отриманим, якщо модуль різниці двох послідовно обчислених доданків не перевищує деякого числа ε>0.

10. Обчислити наближене значення нескінченної суми (для порівняння її точне значення дорівнює ). Потрібне наближення вважається отриманим, якщо модуль різниці двох послідовно обчислених доданків суми не перевищує деякого числа ε>0.

11. За формулою члена ряду з номером k скласти програму обчислення суми всіх членів ряду, не більших заданого числа ε.

12. Обчислити наближене значення нескінченної суми (для порівняння її точне значення дорівнює ). Потрібний результат вважається отриманим, якщо модуль різниці двох послідовних доданків суми не перевищує деякого числа ε>0.

13. Скориставшись формулою члена ряду з номером k скласти програму обчислення суми членів ряду, не менших деякого числа ε>0.

14. Числа Фибоначчі визначаються формулами: ; . Обчислити перше число Фибоначчі, більше за деяке число m та суму всіх чисел Фибоначчі, які не перевищують m.

15. За формулою члена ряду з номером k обчислити суму всіх членів ряду, більших за деяке додатне число ε.

16. Послідовність a₁ , a₂ , . . створена за наступним законом: Знайти перший від’ємний член вказаної послідовності, якщо b дійсне додатне число.

17. Послідовність отримана з n цілих чисел із інтервалу від 0 до 66. Визначити, чи можна вважати цю послідовність чисел рядом костей доміно, що викладені за правилами цієї гри.

18. Дійсні числа x, ε такі, що x>1, ε>0. Обчислити з точністю ε значення виразу . Вважати, що необхідна точність досягнута, якщо модуль чергового доданку став меншим за ε.

19. Скласти програму обчислення значення функції sin(x) з точністю ε, використовуючи наступну формулу розкладання в ряд . Результат порівняти зі значенням, отриманим за допомогою стандартної функції sin.

20. Скласти програму знаходження значення функції cos(x) з точністю ε, використовуючи розкладання в ряд за формулою . Порівняти з результатом, отриманим за допомогою стандартної функції cos.

21. Скласти програму знаходження числа p з точністю ε, шляхом знаходження відношення площі круга радіусу 1 до площі описаного квадрата, використавши метод Монте-Карло (метод статистичних випробувань). Метод полягає в застосуванні формули класичної ймовірності для обчислення ймовірності влучання точки площини з координатами рівномірно розподіленими на проміжку (0,1) у межі круга. Кількість випробувань залежить від значення ε.

22. Скласти програму знаходження числа е з точністю ε, використовуючи розкладання в ряд за наступною формулою . Порівняти з результатом, отриманим за допомогою стандартної функції exp.

23. За двома датами визначити кількість діб, що пройшли між першою та другою датою.

24. Обчислити корінь рівняння f(x)=0 на відрізку [a,b] методом дихотомії (половинного поділу) з точністю ε.

25. Для двох натуральних чисел a, b організувати знаходження найменшого спільного дільника (НСД) за алгоритмом Евкліда.

Запитання для контролю та самоконтролю

1. Які циклічні конструкції можна використовувати в програмах?

2. У чому полягають особливості структури та використання циклів з передумовою?

3. У чому полягають особливості структури та використання циклів з післяумовою?

4. Чи можна одні циклічні конструкції замінювати іншими?

5. Чи є універсальна конструкція, за допомогою якої можна організувати повторення в програмі?

6. Якими засобами можна достроково завершити виконання циклу? Як ставиться технологія програмування до випадків дострокового завершення циклів?

7. Як і чому саме так технологія структурного програмування ставиться до можливості організації повторень у програмі без використання циклічних конструкцій?

8. Чому і які циклічні конструкції називають цикл ДО/цикл ПОКИ, передумовна/післяумовна, «суворий» цикл/«несуворий» цикл?

9. У яких випадках конструкції while-do- та repeat-until- можна замінювати конструкцією for-to-do- ?

10. Які правила графічного зображення циклічних конструкцій?

11. Чому у деяких циклічних конструкціях тіло циклу записують як складений оператор, а у деяких такий підхід зайвий?

12. Що отримаємо у результаті, якщо після службового слова do поставити знак «;»?

13. Що таке вкладені цикли? Яку вони мають структури та які правила їх виконання?

Тема №5 ВИКОРИСТАННЯ МАСИВІВ

Теоретичні відомості

У мові Turbo Pascal виділяються прості та структуровані об’єкти, тобто при описуванні цих об’єктів застосовуються так звані прості (не поділяються на більш прості) та структуровані (поділяються на більш прості) типи даних. До перших відносять цілий тип (integer) та його різновиди (shortint, byte, word, longint), дійсний або реальний (real) та його різновиди (single, double, comp, extended), логічний тип (boolean), символьний або літерний (char), перелічуваний та інтервальний типи. До других відносять масиви (array), рядковий тип (string), множинний тип (set), записи (record), файловий тип (file).

Масив - структура даних, що складається з фіксованої кількості компонент одного типу. Масив можна визначити як упорядковану сукупність елементів деякого типу, що адресуються за допомогою деякого індексу. Індексна змінна, що використовується для вказівки окремого елемента масиву повинна бути порядкового типу. При оголошенні масиву необхідно зазначити ім'я масиву, тип елементів масиву, у яких межах робиться нумерація елементів масиву, тобто діапазон (початкове і кінцеве значення) для індексної змінної. Тим самим указується максимальна кількість елементів у масиві - його розмір. Масиви поділяють на одновимірні, двовимірні і т.д. Масив зручно асоціюється з математичним об’єктом - матрицею.

Одновимірний масив можна оголосити наступним способом:

var Ім'я : array[поч_індекс . . кін_індекс] of Тип_даних;

Оголошення двовимірного масиву виглядає в такий спосіб:

var Ім'я:array[поч_індекс1..кін_індекс1,

поч_індекс2..кін_індекс2] of Тип_даних;

Зауваження: Тип елементів масиву (Тип_даних) може бути будь-яким крім файлового. При роботі з масивами зручно користуватися оператором циклу з параметром. Масиви, особливо статичні, дуже вимогливі до ресурсів пам’яті. Тому, розробляючи програму, слід уважно обмірковувати межи зміни індексів елементів масивів.

За допомогою масивів та спеціальних методів ефективно розв’язуються відомі задачі сортування (методи простого обміну, вибору, вставки, підрахунку та ін.) та задачі пошуку (методи перебирання, бінарного пошуку та ін.).

Приклад

Дано прямокутну матрицю. Розділивши всі її елементи на число z, одержати нову матрицю.

1) Відомі елементи дійсної прямокутної матриці A і дійсне число z.

2) Якщо вихідний масив , тоді

3) Алгоритм

4) Типи даних вибираємо наступним способом: A і B - дійсні двомірні масиви розмірністю 3 х 4; z - дійсне число; i, j - цілі числа.

5) Текст програми:

Program p5;

var i,j: integer; z: real;

A,B: array[1..4,1..3] of real;

Begin

writeln('Введіть дійсне число z');

Readln(z);

writeln('Введіть елементи матриці A розміром 4 на 3');

for i:=1 to 4 do

Begin

for j:=1 to 3 do

read(A[i,j]);

Readln

End;

for i:=1 to 4 do

for j:=1 to 3 do

B[i,j]:=A[i,j]/z;

for i:=1 to 4 do

Begin

for j:=1 to 3 do

write(B[i,j]);

Writeln

End;

Readln

End.

6) Тестовий приклад:

z=2

Елементи матриці A розміром 4 х 3

2 4 6

2 6 6

4 2 4

2 2 2

Матриця В буде мати вигляд

1 2 3

1 3 3

2 1 2

1 1 1

7) Робочий розрахунок:

Введіть дійсне число z

Введіть елементи матриці A розміром 4 х 3

2 6 8

3 5 9

3 5 4

2 7 10

6.6666666667E-01 2.0000000000E+00 2.6666666667E+00

1.0000000000E+00 1.6666666667E+00 3.0000000000E+00

1.0000000000E+00 1.6666666667E+00 1.3333333333E+00

6.6666666667E-01 2.3333333333E+00 3.3333333333E+00

Варіанти завдань

1. Для квадратної матриці з дійсними елементами знайти скалярний добуток рядка, в якому знаходиться найбільший елемент матриці, на стовпець із найменшим елементом.

2. Симетрична матриця задана верхнім трикутником у вигляді одновимірного масиву. Знайти квадрат цієї матриці не перетворюючи її до квадратного виду.

3. Знайти круг мінімального радіусу, що є покриттям деякої множини точок площини. Координати точок зберігаються у двовимірному масиві.

4. Для дійсної квадратної матриці отримати , де - максимальне значення елементів k-го стовпця матриці.

5. Визначити, чи утворюють точки площини, координати яких зберігаються в двох масивах, опуклий багатокутник.

6. Визначити, чи є задана ціла квадратна матриця n-го порядку магічним квадратом, тобто такою матрицею, суми елементів у кожному рядку, стовпці та діагоналі якої однакові.

7. Дві послідовності містять дійсні елементи. Знайти найменше з тих чисел першої послідовності, що не належать до другої послідовності.

8. Отримати впорядкований по зростанню вектор максимальних елементів рядків деякої квадратної матриці.

9. Розмістити елементи числової послідовності в порядку зменшення частоти їхньої появи в цій послідовності.

10.У квадратній матриці обміняти місцями рядок з максимальним елементом і стовпець з мінімальним елементом.

11.Скласти програму обчислення добутку двох заданих матриць.

12.Натуральне число m задається масивом своїх двійкових цифр. Вивести число m у десятковому виді.

13.Знайти максимальний елемент у кожному рядку квадратної матриці й обміняти його з тим елементом цього ж рядка, який розміщений на головній діагоналі.

14.Якщо послідовність цілих чисел впорядкована за правилом , тоді залишити її без змін. Інакше встановити в послідовності протилежний порядок, тобто .

15.Перетворити дійсну квадратну матрицю, розмістивши елементи кожного рядка в порядку неспадання, якщо перший елемент цього рядка більший за останній, і в порядку незростання, в протилежному випадку.

16.Знайти суму двох “довгих” (кількість знаків більше 10) натуральних чисел в десятковій системі числення.

17.Для дійсних чисел одержати .

18.Масив X містить n елементів. Перетворити масив X, перемістивши всі від’ємні елементи в його початок, зберігаючи початкове взаємне розташування як серед від’ємних, так і серед інших елементів.

19.Визначити, чи є задана квадратна матриця непарного порядку симетричною відносно центрального елемента.

20.Для дійсних чисел одержати .

21.Дано дійсну квадратну матрицю непарного порядку. Знайти найбільший серед елементів, обох діагоналей і поміняти його місцями з центральним елементом.

22.Дано прямокутну матрицю. Обчислити скалярний добуток векторів, складених із максимальних і мінімальних елементів рядків.

23.Скласти програму перевірки факту, що датчик випадкових чисел генерує числа дійсно випадково. Для цього генерувати 1000 чисел із проміжку [1,7], підрахувати частоту появи кожного числа, побудувати відповідну гістограму, зробити висновки.

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

25.У масиві зберігаються дійсні числа без повторень. Знайти залежність часу сортування t від кількості елементів n (n=100,200,300,400,500) для методів простого обміну, вибору, підрахування.

Запитання для контролю та самоконтролю

1. У чому полягає різниця між простими та структурованими типами даних?

2. Які в мові Turbo Pascal використовуються прості та структуровані типи даних?

3. Що таке масив? Які його складові елементи? Як звертатися до елементів масиву?

4. Які різновиди масивів можна використовувати в програмах? У чому їх особливості?

5. Які алгоритмічні структури оптимізують обробку елементів масивів?

6. Які обмеження необхідно враховувати при використанні масивів?

7. Про що йде мова в задачі сортування? Які методи використовуються для її розв’язання? У чому полягають відомі методи сортування?

8. Як формулюється задача пошуку? Якими методами її вирішують? У чому вони полягають?

9. Як зберігається масив в оперативній пам’яті?

10. Як працює алгоритм пошуку в масиві найбільшого (найменшого) елемента?

11. Які правила пошуку суми елементів масиву?

12. Які правила пошуку добутку елементів масиву?

13. Як організувати виведення елементів одновимірного масиву у рядок та у стовпчик? Чому не раціонально виводити у стовпчик масив, де кількість елементів перевищує число 24?

14. Як організувати виведення елементів двовимірного масиву у вигляді таблиці?

15. Які існують інструменті позиціювання екрану в текстовому режимі? Як скористуватися цими інструментами для виведення таблиці?

16. Як за описом визначити який об’єм пам’яті виділяється для масиву?