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

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

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

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

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

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

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

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

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

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

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

 

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

Назва	Характеристика	Розмір, біт	Діапазон значень (для найбільшого з розмірів)
char	Цілочисельний (символьний)	8	0 ... 255
short	Цілочисельний	16	0 ... 65535
int	Цілочисельний	16	– 2147483648 … + 2147483647
bool	Логічне значення значення	1	true (істина) або false (неправда)
float	Дійсне число одинарної точності	4	від ±3.4е-38 до ±3.4е+38 (7 значущих цифр)
double	Дійсне число подвійної точності	8	від ±1.7е-308 до ±1.7е+308 (15 значущих цифр)
longdouble	Дійсне число збільшеної точності	10	від ±1.2е-4932 до ±1.2е+4932

 

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

Intalfa, beta, c; 

FloatSum; 

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

double e = 2.71;  intEarthRadius = 6357; 

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

ConstintEarthRadius = 6357; 

ConstfloatPi = 3.1415926;  

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

Операція	Опис	Математичний вираз	Вираз мови С/С++
( )	Виклик функції	sin a	sin(a)
++	Постфікснийінкремент		a++
--	Постфікснийдекремент		a--
++	Префікснийінкремент		++a
--	Префікснийдекремент		--a
–	Унарний мінус	–– a	–a
*	Множення	ab	a * b
/	Ділення		a / b
%	Обчислення залишку	a mod b	a % b
+	Додавання	a + b	a + b
–	Віднімання	a – b	a – b
=	Привласнення	a = b	a = b

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

Математичний вираз	Вираз мови С/С++
y = a +bx	y = a + b * x
	y = (sin(x) – cos(y)) / (a * a + b * b);
	y = exp(a * x * x + b * x + c);

 

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

Назвафункц ії	Опис	Формат
abs	Модуль цілочисельного значення	intabs (int)
fabs	Модуль значення з плаваючою точкою	doublefabs (double)
pow	Зведення у степінь	doublepow (double, double)
sqrt	Квадратний корінь	doublesqrt (double)
exp	Експонента (e x )	doubleexp (double)
log	Логарифм натуральний	doublelog (double)
log10	Логарифм десятковий	double log10 (double)
asin	Арксинус	doubleasin (double)
acos	Арккосинус	doubleacos (double)
atan	Арктангенс	doubleatan (double)
sin	Синус	doublesin (double)
cos	Косинус	doublecos (double)
tan	Тангенс	doubletan (double)

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

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

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

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

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

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

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

 

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

 

Специфікатор	Тип	Формат виводу
c	int	Символ (unsignedchar)
d, i	int	Десяткове ціле число із знаком
o	int	Вісімкове ціле число без знаку
u	int	Десяткове ціле число без знаку
x, X	int	Шістнадцяткове ціле число без знаку(літери маленькі або великі)
e, E	float, double	Число з плаваючою точкою у вигляді: [–] m.ddd e ± xxx або [–] m.ddd E ± xxx
f	float, double	Число з плаваючою точкою у вигляді: [–] m.ddd e ± xxx або [–] m.ddd E ± xxx
p	void*	Адреса покажчика (виводиться у форматі X)
s	char*	Рядок символів (виводиться до символа з кодом нуль – „\0‟)

Приклад: 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	Задані моменти початку і кінця деякого проміжку часу в годинах, хвилинах і секундах (в межах доби). Знайти тривалість цього проміжку в кожній з перелічених одиниць.
3	Задане квадратне рівняння ax 2 + bx + c = 0. Знайти його корені, якщо відомо, що дискримінант цього рівняння додатній.
4	У рівнобедреному прямокутному трикутнику відома висота h, опущена на гіпотенузу. Знайти сторони трикутника.
5	Довжина відрізка задана в дюймах (1 дюйм = 2,54 см). Перевести значення довжини в метричну систему, тобто виразити її в метрах, сантиметрах і міліметрах.
6	Тваринник на початку кожної зими підвищує відпускну ціну на

 

	молоко на p процентів, а кожного літа – знижує на стільки ж процентів. Як зміниться ціна на молоко через n років?
7	Знайти площу кільця, внутрішній радіус якого R1, а зовнішній – R2 (R2> R1).
8	Ланцюг з трьох опорів: R1, R2 і R3 увімкнених послідовно, підключений до джерела з напругою U. Знайти сумарний опір ланцюга і падіння напруги на кожному з опорів.
9	Знайти координати вершини параболи y = ax 2 + bx + c.
10	Знайти внутрішні кути трикутника, заданого координатами своїх вершин на площині.
11	Заданий радіус кола R. Визначити різницю площ кола і квадрата, вписаного в це коло.
12	Задані координати точки підвіски математичного маятника A (x0, y0, z0) і координати одної з точок його найвищого положення B (x1, y1, z1). Знайти координати найнижчої точки траєкторії та іншої найвищої точки підйому.
13	Трикутник заданий координатами своїх вершин на площині. Знайти площу трикутника.
14	Комерсант, який мав стартовий капітал k гривень, зайнявся торгівлею, яка щомісяця збільшує капітал на p %. Через скільки років він накопить суму s, достатню для купівлі власного магазину?
15	З кола радіусом R вирізаний прямокутник, велика сторона якого дорівнює a. Знайти максимальний радіус кола, яке можна вирізати з отриманого прямокутника.
16	Велосипедист проїхав відстань S км рухаючись першу третину шляху із швидкістю v1 км/год, а іншу частину шляху зі швидкістю v2 км/год. Скільки часу рухався велосипедист?
17	Трикутник заданий довжинами двох сторін a і b та кутом φ між ними. Знайти довжину третьої сторони трикутника.
18	Знайти площу сектора, радіус якого дорівнює R, а дуга містить φ радіан.
19	Селекціонер вивів новий сорт зернової культури і зняв з дослідної ділянки k кг насіння. Посіявши 1 кг насіння, можна за сезон зібрати p кг насіння. Через скільки років селекціонер зможе засіяти новою культурою поле площею S гектарів, якщо норма висіву n кг/гектар?
20	Задана довжина ребра куба. Знайти площу бокової поверхні куба та його об‟єм.
21	Автомобіль і зовнішнім діаметром колеса d см проїхав S км. Скільки обертів зробило кожне колесо автомобіля?
22	У квадрата ABCD на площині відомі координати двох протилежних вершин – точок A і C. Знайти координати точок B і D. Зауваження: розташування квадрата є довільним.
23	Задане трьохзначне ціле число x. За допомогою операцій виділення цілої та дробової частини визначити кількість десятків
	у ньому.
24	Визначити час падіння металевої кулі з k-го поверху будівлі, якщо висота одного поверху складає z метрів.
25	Знайти периметр і площу прямокутного трикутника у якого відомі довжини катетів.
26	При підключенні до акумулятора навантаження з опором R1 амперметр показав струм I1, а при підключенні навантаження з опором R2 – струм I2, що протікає в ланцюзі. Визначити струм короткого замикання акумулятора.
27	Задане ціле двохзначне число x. За допомогою операцій виділення цілої і/або дробової частини визначити суму квадратів цифр, що його складають.
28	Трикутник ABC заданий довжинами своїх сторін. Знайти довжину висоти, опущеної з вершини A.
29	Задане дробове число x з трьома знаками після коми. За допомогою операцій виділення цілої та дробової частини визначити його другий знак після коми.
30	Пішохід рухався протягом t1 хвилин з деякою швидкістю v1 і t2 хвилин з іншою швидкістю v2, яка у півтори рази більша за v1. Знайти швидкості руху пішохода v1 і v2, якщо пройдений ним шлях склав S метрів.

 

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

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 с.