ПРОГРАМУВАННЯ ЛІНІЙНИХ АЛГОРИТМІВ (мова С/С++)

ПРОГРАМУВАННЯ ЛІНІЙНИХ АЛГОРИТМІВ

(мова С/С++) Мета роботи: 

•      узагальнити навички побудови лінійних алгоритмів для розв’язання різних класів задач; 

•      навчитись використовувати базові типи даних мови С/С++ при розв’язанні різних класів задач; 

•      закріпити знання правил побудови виразів та застосування арифметичних операцій і математичних функцій; 

•      закріпити знання базових функцій форматного вводу і виводу даних;

•      отримати навички програмної реалізації найпростіших лінійних алгоритмів.

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

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

Базові типи даних мови С/С++ Перелік типів даних, які програміст може використовувати у своїх програмах залежить від використовуваного середовища розробки. Наприклад, IDE BDS 2006 підтримує біля десяти базових типів даних, однак, більшість з них навряд чи знайдуть застосування при виконанні завдань з даного методичного посібника. Найбільш використовувані числові типи даних мови С/С++ представлені у вигляді структурної схеми на наступному рисунку.

З рисунку видно, що цілочисельні типи даних можуть використовуватись у двох модифікаціях: знаковій (signed) і беззнаковій (unsigned). Типи даних з плаваючою точкою завжди є знаковими. В наступній таблиці приведені характеристики цих та інших числових типів даних залежно у різних середовищах розробки.

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

Intalfa, beta, c; 

FloatSum; 

Змінна може бути ініціалізована в момент оголошення, для чого використовується операція привласнення – “ = ”, наприклад: 

double e = 2.71;  intEarthRadius = 6357; 

Для оголошення змінної, значення якої в процесі виконання програми повинно залишатись сталим, використовуються так звані константи. Оголошення константи відрізняється від оголошення змінної наявністю модифікатора const перед типом константи. Крім того, константа повинна обов’язково бути проініціалізована в момент оголошення. Приклади оголошення констант: 

ConstintEarthRadius = 6357; 

ConstfloatPi = 3.1415926;  

Побудова виразів. Вирази – це конструкції мови програмування, які підлягають обчисленню. В загальному випадку до виразів можуть входити: константи, змінні, виклики функцій, знаки операцій, круглі дужки, що змінюють порядок виконання дій. Вирази слід записувати в один рядок. Обчислення виразів виконується зліва направо; при цьому спочатку виконуються дії, записані в круглих дужках. Порядок виконання операцій визначається їх пріоритетами. Перелік деяких арифметичних операцій мови С/С++ в порядку зменшення пріоритетів приведений в наступній таблиці.

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

Основні математичні функції. Широкий спектр математичний функцій представлений в модулі math.h. Деякі, найбільш часто використовувані математичні функції цього модуля представлені у наступній таблиці. 

При використанні математичних функцій слід уважно перевіряти, чи входять значення аргументів до області визначення використовуваної функції. Наприклад, аргументом функції sqrt не може бути від’ємне число, а другий аргумент (показник степені) функції pow при від’ємному першому аргументові (значенні, яке зводиться) не може бути дробовим. 

Функції форматного вводу і виводу

Форматний вивід даних. Для виводу форматованих даних, як правило, застосовуються функції printf і fprintf, оголошені в модулі stdio.h. Перша функція записує дані у стандартний потік виводу – stdout, а друга – у заданий файл або потік. Аргументами функції printf є:

•            рядок, який необхідно вивести на екран (якщо необхідно, також, вивести значення деяких змінних, то цей рядок повинен містити елементи

форматування); 

•            перелік змінних, значення яких необхідно вивести на екран. 

Для кожної змінної з переліку формат задається за наступною загальною схемою (у трикутних дужках записані обов’язкові, а у квадратних – необов’язкові поля):<%> [прапори][ширина][.точність][h|l] <специфікатор>

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

Приклад: intCount;  floatPrice, Cost; 

... 

printf (“Кількість товару складає %d одиниць”, Count); 

printf (“При ціні %f гр вартість складає %f гр”, Price, Cost);

Методичні вказівки

Завданням даної лабораторної роботи є побудова лінійного алгоритму для розв’язання певної (арифметичної, геометричної, логічної) задачі та створення, компіляції, відладки та виконання програми за цим алгоритмом.  Результатом виконання роботи має бути схема алгоритму, текст програмита демонстрація правильного функціонування програми. Лабораторну роботу рекомендується виконувати у наступній послідовності: 

1)   постановка задачі; 

2)   математична формалізація задачі; 

3)   вибір методу розв’язування задачі; 

4)   побудова схеми алгоритму; 

5)   створення, компіляція, відладка та виконання програми за складеним алгоритмом, згідно завдання; 6) перевірка алгоритму. 

Постановка задачі – це чітке формулювання задачі, визначення вхідних даних для її розв’язування і точні вказівки відносно того, які результати і в якому вигляді повинні бути отримані. Первинна постановка задачі – це завдання на лабораторну роботу. Однак перед виконанням наступних кроків роботи необхідно: 

•     уважно перечитати задачу (можливо декілька разів) до чіткого розуміння

її суті і вимог; 

•     визначити, які дані є вхідними, тобто такими, які задаються користувачем алгоритму; 

•     визначити, які дані є вихідними, тобто такими, які треба отримати в результаті розв’язання задачі. 

Математична формалізація задачі – це опис задачі у вигляді формул, рівнянь, співвідношень, обмежень. Цей крок є найважливішим при виконанні даної роботи. Більша частина задач потребують математичної формалізації. Математична формалізація вимагає певного рівня знань, вмінь та навичок в області, до якої належить поставлена задача. Вибір методу розв’язування задачі полягає у виборі сукупності способів та підходів до розв’язання задачі. Вибір методу залежить як від самої задачі, так і від можливостей комп’ютера. При оцінюванні якості розв’язку задачі враховуються наступні показники: 

•     оригінальність розв’язку; 

об’ємпам’яті, який займає і використовує алгоритм (програма); 

•     трудомісткість обчислень, тобто ефективність алгоритму;  лаконічність і наочність алгоритму. 

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

Створення, компіляція, відладка та виконання програмипередбачає роботу у середовищі програмування з використанням мови програмування (Pascal

Перевірка алгоритму полягає в ручній перевірці окремих розв’язків задачі. Отриманий алгоритм необхідно обов’язково перевірити за допомогою тестів.

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

•  “тепличні” – перевіряють роботу алгоритму при коректних, нормальних вихідних даних найпростішого вигляду;

•  “екстремальні” – на межі області визначення, в ситуаціях, які можуть відбутись і на які треба коректно реагувати; 

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

Приклад.Уряд гарантує, що інфляція в поточному році складатиме p % на місяць. Якого зростання цін за рік можна очікувати? 

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

Проведемо математичну формалізацію задачі. Позначимо ціну деякого товару в даний час с1, а ціну того ж товару в кінці року – c12. Тоді ціна товару в кінці року обчислюється наступним чином:

де k – коефіцієнт зростання ціни, який в свою чергу визначається як

Якщо за 1 місяць ціна збільшується на p %, це означає, що до початкової ціни додається p її сотих частин, тобто:

Звідси легко побачити:

Таким чином, коефіцієнт збільшення ціни за рік становитиме:

Схема алгоритму представлена на рисунку.

Лістинг програми мовою С/С++ : 

 #include<math.h> #include<conio.h> #include<stddio.h>

float p, k;  voidmain () {  clrscr (); 

printf (“Програма обчислення рівня зростання цін\n”);  printf (“Введіть рівень місячної інфляції: ”);  scanf (“%f”, &p);  k = pow (1.0 + p / 100, 12);  printf (“Збільшення цін за рік складе %.2f разів”, k);  getch (); 

}

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

Контрольні запитання

1)    дайте визначення алгоритму в не суворому розумінні; 

2)    назвіть види схем алгоритмів, передбачених ISO 5807:1985;

3)    сформулюйте основні правила побудови схем алгоритмів згідно ISO 5807:1985.

4)    дайте визначення алгоритмізації та перелічіть основні етапи розв’язання задачі на ЕОМ; 

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

6)    перелічіть емпіричні властивості алгоритмів; 

7)    перелічіть та охарактеризуйте основні числові типи даних мови С/С++; 

8)    сформулюйте правила оголошення змінних і констант у програмі мовою С/С++; 

9)    сформулюйте правила побудови арифметичних виразів мовою С/С++;  10)        опишіть структуру рядка форматування функції printf; 11)   опишіть структуру рядка форматування функції scanf.

ПЕРЕЛІК РЕКОМЕНДОВАНОЇ ЛІТЕРАТУРИ 

1. Б. Страуструп. Языкпрограммирования С++. – М.: “Бином-Пресс”, 2006. – 1104 с.  2.Глушаков С. В., Коваль А. В., Смирнов С. В. Языкпрограммирования С++: Учебный курс. – Харьков.: “Фолио”, 2001. – 500 с.  3. Х. М. Дейтел, П. Дж. Дейтел. Какпрограммировать на С++:

Четвертоеиздание. Пер. с англ. – М.: ООО “Бином-Пресс”, 2005. – 1248 с.  4.Шилдт Г. “С++ Руководство для начинающих”. – М.: Издательскийдом “Вильямс”, 2005. – 669 с.

5.                 Лехан С.А. «Мова програмування С++ Спецкурс». – Шепетівка, «Аспект», 2007 – 160 с.

6.                 Левченко В. В. Основи програмування та алгоритмічні мови: методичні вказівки до виконання лабораторних робіт– К.: ПЕК НАУ, 2010. – 128 с.