Масовість

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

30. Форми представлення алгоритму.

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

Форми запису алгоритму:

· словесна або вербальна (мовна, формульно-словесна);

· псевдокод (формальні алгоритмічні мови);

· схемна:

· структурограми (схеми Нассі-Шнайдермана);

· графічна (блок-схема, виконується за вимогами стандарту).

31. Базові структури алгоритму (лінійна, розгалужена, циклічна).

Всього існують чотири базових структури алгоритмів:

· лінійні;

· розгалужені;

· циклічні;

· змішані.

Найпростіша в написанні та виконанні перша з цих структур - лінійна. До неї відносяться алгоритми, що складаються лише з простих команд. Які ж команди можна назвати простими? Простими з точки зору комп'ютера являються ті команди, що виконуються виконавцем безумовно, тобто після першої команди виконується друга, потім третя і т.д.
Загальний вигляд лінійного алгоритму, поданий мовою блок-схем, наступний:

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

· проснутися;

· зробити ранковий туалет;

· одягнутися;

· поснідати;

· зібрати речі;

· одягнути верхній одяг;

· вийти до школи.

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

Тепер розберемось, що ж таке умова з точки зору виконавця. Умовою називається таке речення, на яке можна дати відповідь "так" чи "ні". Як правило, кажуть, що в першому випадку (коли ми відповіли на речення "так") умова являється істиною, а в другому хибною.Виходячи з цього, речення "Якого кольору твій піджак?" не можна вважати умовою, а речення "Твоє волосся русяве?" - можна.Однак, навіть маючи в своєму арсеналі команду розгалуження, важко реалізувати алгоритми, що потребують багаторазового повторення деякої послідовності однакових дій. В цих випадках нас виручає циклічний алгоритм. У нашому житті дуже часто зустрічаються алгоритми з повторами, причому чітко визначаються два типи повторів. В одному випадку ми чітко знаємо, скільки разів необхідно повторити задану послідовність команд, а в іншому - ні. Наприклад, в першому класі вчителька дає завдання дітям: "Діти, напишіть, будь ласка, в зошитах десять цифр "1", а потім рядочок цифр "2". Чим відрізняються ці два завдання? В першому випадку дитина отримала чітку вказівку написати десять одиниць, а в другому - ця вказівка була не точною (рядочок двійок). Чому другий випадок не такий точний? Тому що кількість отриманих кожним учнем цифр буде залежати від їх власного почерку: одні учні пишуть охайно маленькими цифрами, інші - неохайно величезними кривулями.В залежності від того, чи знаємо ми скільки разів необхідно повторювати якусь послідовність команд розрізняють цикли з лічильником (кількість повторень відома заздалегідь) та цикли з умовою (цикл робиться доки не виконається якась умова). Примітка: Знов запропонуйте дітям пофантазувати і придумати ситуації, коли можна визначити кількість повторень, а коли не можна.Крім того, в циклах з умовою теж можна виділити два різних випадки:

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

· цикл с післяумовою - спочатку ми виконуємо хоч один раз необхідну послідовність дій, а потім перевіряємо, чи не досягли ми бажаного результату (коли ми хочемо пити, ми спочатку ковтаємо хоч глоток води, а потім починаємо контролювати, чи не вгамували ми свою спрагу).

Мовою блок-схем обидва типи циклів виглядають наступним чином:

змішаний тип алгоритму, в якому поєднуються елементи лінійних, розгалужених та циклічних алгоритмів.
Блок-схеми алгоритмів.

32. Основні прийоми роботи в мові Паскаль.

Програма наПаскале у випадку складається з кількох файлів. Одне з них містить головну програму, інші ж – модулі. Головна програма складається з заголовка, блоки і закінчується точкою — ознакою кінця програми. Натомість, блок містить розділи описів і розподіл операторів. У випадку «скелет» програми можна так:

{ >Спецификация програми }

>program <ім'я програми> (заголовок програми);

>uses (розділ оголошення модулів);

>label (розділ оголошення міток);

>const (розділ оголошення констант);

>type (розділ оголошення типів);

>var (розділ оголошення змінних);

>procedure (>function) (розділ оголошення підпрограм: процедур чи функцій);

>begin

<оператори > (розділ операторів, обов'язкова частина);

end.

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

Розділ операторів має бути присутнім на будь-який програмі і є основним. Попередні розділи носять характер описів і обов'язково утримуватися у програмі.

Заголовок програми складається з зарезервованого слова >program й імені програми (з переліком параметрів, ув'язнених у круглі дужки). Завершується заголовок точкою з коми.

У TurboPascal є особливості у структурі програми. Так, заголовок програми необов'язковий і ігнорується компілятором. Порядок розміщення розділів довільний, можна кілька однакових розділів. Єдине правило, що слід витримувати, - будь-де програми можна використовувати лише елементи (мітки, типи, константи, перемінні, підпрограми тощо. буд.), окреслених раніше за текстом програми або є спричиненими елементами мови. Винятком від цього правила може лише визначеннятипа-указателя через невизначений доти тип. Однак це тип надалі може бути обов'язково визначено.

Оператори розділ операторів відокремлюються друг від друга точкою з коми. Перед e>nd точка з коми не ставиться, але її наявність перестав бути помилкою, а лише означає присутність між останнім виконуваним оператором і службовим словом end чергового оператора - порожнього оператора. Закінчується програма словом end, після якого обов'язково ставиться точка.

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

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

- конструкції рівня вкладеності записуються однією вертикальному рівнях (розпочинаються з однієї позиції з рядку);

- вкладена конструкція записується зміщеною по рядку сталася на кілька позицій вправо щодо зовнішньої нею конструкції.

33. Структура програми на мові Паскаль.

Program – розділ в якому можна вказати назву програми. Цей розділ не обов’язковий і використовується скоріше для зручності розпізнання програми. Назва програми може складатися з літер англійської мови та цифр(причому вона повинна складатися з одного слова і починатися на літеру. Довжина слова не повина перевищувати 8 знаків).

Uses – розділ підключення модулів.

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

Const – розділ опису констант.

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

Type – розділ створення власних типів змінних.

Змінна – це величина, значення якої може змінюватися в процесі виконання програми.

Var – розділ опису змінних.

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

Наприклад: Var a:integer; b:real; {даний запис вказує на те, що програма буде використовувати змінну а – цілого типу та змінну b – дійсного типу.}

Begin … end. – операторні душки, що містять в собі набір команд з якого власне і складається програма.

34. Математичні операції на мові Паскаль.

Математичні операції

У таблиці наведені основні математичні операції Турбо Паскаль.

Символ операції	Назва операції	Приклад
*	Множення	2*3 (результат: 6)
/	Ділення	30/2 (результат: 1.5E+01)
+	Додавання	2+3 (результат: 5)
-	Віднімання	5-3 (результат: 2)
div	Неповна частка від ділення по модулю	5 div 2 (результат: 2)
mod	Остача від ділення по модулю	5 mod 2 (результат: 1)

Логічні операції

Над логічними аргументами в Турбо Паскаль визначені наступні операції:

NOT - логічне заперечення ("НІ")

AND - логічне множення ("Кон'юнкція", "І")

OR - логічне додавання ("Диз'юнкція", "АБО")

XOR - логічне виключення ("Виключна диз'юнкція", "Виключне АБО")

Результати виконання цих операцій над змінними А і В логічного типу наведені в таблиці істинності.

A	B	not A	A and B	A or B	A xor B
true	true	false	true	true	false
true	false	false	false	true	true
false	true	true	false	true	true
false	false	true	false	false	false

Операції відношення

До операцій відношення в Турбо Паскаль відносяться наступні операції:

> - Більше

< - Менше

= - Дорівнює

<> - Не дорівнює

>= - Більше або дорівнює

<= - Менше або дорівнює

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

Пріоритет операцій

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

нарна операція not, унарний мінус -, взяття адреси @

операції типу множення: * / div mod and

операції типу додавання: + - or xor

операції відношення: = <> < > <= >= in

Порядок виконання операцій може бути перевизначений за допомогою дужок. Наприклад 2 * 5 +10 дорівнює 20, але 2 * (5 +10) дорівнює 30.

35. Процедура введення і виведення на мові Паскаль.

Введення та виведення даних здійснюється в мові Паскаль за допомогою відповідних процедур:

read ({список змінних}) - дозволяє ввести значення для вказаних змінних з клавіатури
write ({список змінних}) - виводить значення елементів списку виведення на екран монітора.

writeln ({список змінних}) - після друку елементів списку переводить курсор на наступний рядок на екрані.

 

36. Типи величин на мові Паскаль.

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

скалярні (прості),

структуровані (складені).

Скалярні типи у свою чергу підрозділяються на стандартні та типи користувача. Стандартні типи пропонуються користувачам розроблювачами системи Turbo Pascal. Типи користувача - розробляються самим програмістом.
До стандартних скалярних типів відносяться наступні типи:

цілі,

дійсні,

літерні,

булівські.

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

Дійсні типи даних являють собою дійсні значення, що використовуються в арифметичних виразах і займають у пам'яті від 4 до 10 байт. Паскаль допускає представлення дійсних значень у вигляді, як із плаваючою, так і з фіксованою крапкою.

37. Оператор присвоєння.

Оператор присвоєння має вигляд: < зміна >:=< вираз >;

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

Вирази, присутні в операторі присвоєння, можуть бути арифметичними, логічними і рядковими. Розглянемо арифметичні вирази. До їх складу входять числа, числові змінні та константи, стандартні функції, з'єднанні арифметичними операціями та круглими дужками.

Для арифметичних операцій над числовими операндами встановлена така черговість (пріоритет) виконання:

1)обчислення функцій; 2) множення (*), ділення (/), ділення націло div), остача від ділення (mod); 3) додавання (+), віднімання (-).

Для зміни порядку виконання арифметичних операцій використовують круглі дужки. Операції одного і того ж самого пріоритету виконуються зліва направо у порядку їх появи у виразі.

38. Розгалуження на мові Паскаль.

Розгалужений процес вміщує декілька шляхів. Вибір того чи іншого шляху залежить від виконання деяких умов. У багатьох випадках виникає потреба в зміні послідовного порядку операторів, що стає можливим завдяки операторам управління. До них в першу чергу відносяться IF та CASE.

Оператор IF реалізує операцію умовного переходу (операцію розгалуження на два напрямки).

Загальний вигляд:

If умовний вираз then…else…;

В умовному виразі задається умова розгалуження. При виконанні оператора IF цей вираз обчислюється з отриманням логічного результату. Якщо результат True, то виконується простий або складний оператор після слова Then. Якщо результат False, то виконується оператор після Else.

Наприклад:

If A<7.2 then Y:=5*A else Y:=5/A;

Частину оператора Else … можна не вживати:

If X>0 then K:=K+1;

Це означає, що у випадку, коли число Х більше нуля, буде виконано оператор K:=K+1. Якщо така умова для конкретного числа хибна, то змінення К не відбувається, а управління передається на оператор, який в програмі записано після оператора If.

Складений оператор Begin…End суттєво розширює можливості If:

If A<0 then begin

K:=K+1;

R:=a;

End

Else begin

L:=L+1;

Q:=A;

End;

У складному операторі записують будь-яку кількість операторів. Вони виконуються “як одне ціле”. Тут можуть бути “свої” If, цикли, тощо.

Зверніть увагу на те, що після оператора, який стоїть перед Else, не ставиться крапка з комою.

Оператор Case забезпечує розгалуження на декілька напрямків.

Загальний вигляд:

 

Case індекс вибору of список вибору;

Else…; End;

 

де індекс вибору – проста змінна цілого, символічного, перелічуваного або логічного типу;

список вибору – сукупність простих або складних операторів, перед кожним з яких стоїть константа вибору, тип якої співпадає з типом індексу вибору.

Після слова Else може стояти простий або складний оператор (ця конструкція може бути відсутня).

Приклад:

 

Case Kit of

1: Y:=sin(x);

2: Y:=cos(x);

3: Y:=sin(x)+cos(x);

Else Y:=0;

End; {case}

 

Змінна Kit (цілого типу) повинна бути визначеною до виконання оператора Case. Якщо Kit дорівнює 1, обчислюється функція Y:=sin(x), якщо вона дорівнює 2, то: Y:=cos(x). У тому випадку, коли Kit відрізняється від 1, 2 або 3, буде виконано оператор Y:=0.

У списку вибору можна вживати складний оператор Вegin… End.

 

39. Цикл з передумовою і цикл з лічильником на мові Паскаль.

Цикл — це процес виконання певного набору команд деяку кількість разів. Цикл реалізують або за допомогою конструкції if–goto, або, що значно ефективніше, за допомогою команд циклу. Є три види команд циклів: з параметром, з передумовою та з післяумовою.

Цикл із лічильником (із покроковою зміною аргумен­ту) — це цикл, у якому тіло циклу виконується заздалегідь відому кількість разів. У різних алгоритмічних мовах реалізація цього циклу може передбачати використання аргументів різних типів, зміну аргументу на різний крок, діапазон зміни аргументу і т. д.Цикл із лічильником аргументу реалізовується таким чином:

1) аргументу надається початкове значення;2) якщо значення входить у заданий діапазон, то виконується тіло циклу;3) аргумент змінюється на заданий крок; виконується 2);

4) якщо значення не входить у заданий діапазон, то виконання циклу припиняється і керування передається оператору, наступному за оператором циклу.

У мові Паскаль реалізовано два оператори циклу з покроковою зміною аргументу: «цикл For-То» і

«цикл For-DownТо».Загальний вигляд оператора циклу з параметром (з лічильником):

for <параметр циклу>:=N1 to N2 do <тіло циклу >;

де N1 та N2 - початкове та кінцеве значення параметра циклу, тіло циклу може бути простим або складеним оператором. <Параметр циклу > ще називають лічильником циклу. Оператор for забезпечує виконання тіла циклу до тих пір, поки не будуть перебрані всі значення параметра циклу від початкового до кінцевого. Параметр циклу, його початкове та кінцеве значення повинні бути одного і того ж скалярного типу. При цьому можливий будь який стандартний тип, крім real. Якщо N1 та N2 цілі числа, а параметр циклу - цілочисельна змінна, то крок завжди рівний одиниці.

Цикл по спадних значеннях параметра від N2 до N1 має вигляд:

for <параметр циклу>:= N2 downto N1 do <тіло циклу>;

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

Цикл із передумовою (або цикл-«поки») — це цикл, у якому тіло циклу виконується тільки у разі виконання умови, заданої перед тілом циклу. Якщо умова стає невірною, то робота циклу припиняється і керування передається оператору, наступному за оператором циклу.На мові Паскаль оператор циклу з перед­умовою ще називається «циклом While-Do».WHILE <умова> DO <оператор>;

40. Одновимірні масиви. Способи їх задання.

41. Двовимірні масиви.

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

Індексом називається порядковий номер елемента масиву.Отже, введено новий тип — масив. Усі типи, які досі були вам відомі, називаються простими. Масив є прикладом структурованого типу, тобто він, у свою чергу, складається з елементів іншого типу.

Масиви бувають одновимірними (у вигляді послідовності чисел), двовимірними (у вигляді таблиць чисел розміром m x n) і багатовимірними (3-,4-вимірні і т.д. 3-вімірні - це об'ємний простір з комірками, а 4-вимірні і більше - це фантастично-абстрактні поняття).

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

Масив називається двовимірним, якщо для задання місцеположення елемента в масиві необхідно вказати значення двох індексів.

Запам'ятайте, що у двовимірних масивах перший індекс завжди вказує на номер рядка, а другий - на номер стовпчика в цьому рядку!

Розмірність масивів у Pascal необмежена, вона визначається лише об'ємом пам'яті вашого комп'ютера.

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

<ім'я змінної>: array [<межі зміни індексів>] of <тип>.

Наприклад,
varA: array[1..10] of real;B: array[1..100,1..100] of byte;C: array[1..100] of array[1..100] of byte.

Порядок роботи з масивом:

1) оголосити про масив у розділі описів, вказавши його розмір і тип елементів, що в нього входять (тобто приготувати місце в пам'яті, де будуть зберігатися значення елементів);

2) заповнити необхідними значеннями масив для розв'язування задачі;

3) якщо треба, вивести масив на екран для зорової перевірки роботи з ним;

4) робота з даним масивом;

5) виведення отриманих результатів.