Семестр

Львів-2003

1. Задання алгоритму

Поняття алгоритму.

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

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

1. Масовість Алгоритм повинен бути застосовним до широкого класу задач.

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

3. Дискретність. Процес, який визначається алгоритмом, повинен мати дискретний (перервний) характер, тобто явля­ти собою послідовність окремих завершених кроків. Кожна операція алгоритму повинна виконуватися за скін­ченний час, а виконання наступної операції повинно почина­тися після завершення попередньої.

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

Кожен алгоритм передбачає наявність деяких вхідних даних і його виконання за скінченний час приводить до цілком пев­них результатів.

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

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

7. Дружелюбність. Алгоритим завжди готовий вказати виконавцю на його помилки.

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

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

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

Зображення алгоритму у вигляді блок-схеми.

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

Символ ПРОЦЕС зображається у вигляді прямокутника з відношенням сторін a:b =2:3, де a вибирається з множини { 10, 15, 20, 50, 75, 100 мм.}. Необхідно відмітити, що всі наступні символи вписуватимуться у задані розміри. Інформація про перетворення, які виконує символ, записуються всередині символа.

Приклад. Змінній Y присвоюється значення sin(x) і значеннязмінної i збільшується на 1.

Символ РОЗГАЛУЖЕННЯ зображається у вигляді ромба, діагоналі якого рівні a та b. Цей символ має один вхід і два виходи, кожен з яких у залежності від виконання умови, позначається “так” або “ні” і задає напрям продовження обчислень. Ми відмітили стрілочками напрями потоків, які входять у символ розгалуження і виходять з нього. У майбутньому лінії потоків, що йдуть зверху-вниз та зліва-направо, вважатимемо природніми і стрілочками не позначатимемо.

Символ ПОЧАТОК-КІНЕЦЬ обчислень зображається графічно як прямокутник з заокругленими кінцями і висотою a/2 та служить для задання початку і кінця алгоритму.

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

Етапи ВВОДУ-ВИВОДУ відображаються при допомозі символа паралелограма.

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

ПРИКЛАД: При такому запиcі (декілька перетворень в одному оимволі), порядок їхнього виконання відповідає порядку запису.

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

ПРИКЛАД:

ПРИКЛАД. Розглянемо довільне ціле чиcло N. Як перевірити, чи задане число є парним і двоцифровим. Цю задачу можна розбити на дві підзадачі:

а) перевірити, чи N - парне;

б) перевірити, чи N - двоцифрове.

При реалізації алгоритмів ми вже використовували математичні функції (sinx. cosх. lnх, e^x і т.п. ). Для реалізацїї нашого завдання у вигляді алгоритму скориcтаємось функцією entier(х), яка виділяє цілу чаcтину аргумента х, для прикладу: entier(5.7)=5, entier(-4.2)=-4. Тоді для перевірки парності числа N можна запиcати умову, 2*entier(N/2)= N, а entier(N/10), якщо N - двоцифрове чиcло, задає кількість десятків у ньому. Дійсно, нескладно перевірити, що при N = 25, entier(25/10)=2.

Поняття про структурний підхід

правило, містить жодних дій. Вказану конструкцію можна використовувати швидше,як виняток. цикли. Тіло циклу - це сукупність етапів, які необхідно багаторазово повторювати в процесі виконання алгоритму. Число повторень тіла циклу задаєтьcя умовою, яка називається умовою завершення циклу. Перед виконанням циклу ряду змінних, які в нього входять, необхідно присвоїти початкові значення. Цей етап називається етапом ініціалізації циклу.

Два типи циклів використо­вуються в алгоритмізаціі. Це цикли з відомим числом повторень (іноді їх ще називають циклами типу перерахунку або циклами типу До) і цикли з невідомим числом повторень (ітераційні цикли або цикли типу ПОКИ).

Цикли з відомим числом повторень

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

Приклад: Обчислити суму перших N натуральних чисел.

Цикли з невідомим числом повторень.

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

Попередній приклад можна реалізувати і з допомогою циклу з невідомим числом повторень.

Обчислення сум та добутків.

Задача обчислення сум та добутків дуже часто зустрічається при побудові алгоритмів. Ми вже розглянули приклад накопичення суми перших N натуральних чиcел. Характерною ознакою цього алгоритму є присвоєння змінній, якою ми позначаємо суму, нульового початкового значення. При обчисленні добутків, змінній, якою позначатимемо добуток, необхідно очевидно присвоїти початкове значення 1.

ПРИКЛАД: Згідно з означенням, факторіалом натурального числа N

називаєтьоя добуток всіх натуральних чисел, які не перевищують N, тобто

N! = 1 * 2 * 3 * …*(N-і) * N, при цьому 0! приймаотьоя рівним 1.

Складемо блок-охему алгоритму обчиолення N!

Побудова алгоритмів складних виразів

Алгоритми математичних формул

Розглянемо вирази типу

Або

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

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

У випадку обчиcлення суми S= , , а наступний за ним член . Тоді .

Таким чином .

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

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

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

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

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

Алгоритм виконання певного завдання, поданий як деяка скінченна послідовність операцій із системи операцій комп'ютера, називають програмою.

2.МОВАПРОГРАМУВАННЯПАСКАЛЬ

Мова Паскаль, названа в честь французського математика і філософа Блеза Паскаля (1623-1662), створена як навчальна мова програмування в 1968-1971 рр. Ніклаусом Віртом у вищій технічній школі в Цюріху. В теперішній час дана мова програмування має більш широку сферу застосування, ніж передбачалось при її створенні. Метою роботи Вірта було створення мови, котра будувалася б на невеликій кількості базових понять, мала простий синтаксис, допускала перевід програм в машинний код простим компілятором. Лінгвістична концепція Паскаля пропагує системний підхід, що виражається, зокрема, в розбитті великих проблем на менші по складності і розміру задачі, що легше розв’язуються.

Основні принципи Паскаля такі:

n структурне програмування. Його суть полягає в оформленні послідовностей команд, як замкнених функцій або процедур і в об’єднанні даних, пов’язаних по змісту, в складні структури даних. Завдяки такому підходу підвищується наглядність тексту, спрощується його відлагодження.

n об’єктно-орієнтоване програмування робить наступний крок від ремесла до науки програмування. Дані об’єднуються з властивими їм операціями обробки в об’єкти.

2.1. Алфавіт, Імена, числа, рядки

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

Алфавіт мови Паскаль містить букви, десяткові цифри, а також такі спеціальні символи:

1) знаки операцій +, -, *, =, /, <>, <, >, <=, >=, :=

2) обмежувачі: , . ; : ( ) [ ] { } ­ .. _

3) службові слова AND | ARRAY | BEGIN | CASE | CONST | DIV | DO | DOWNTO | ELSE | END | FILE | FOR | FUNCTION | GOTO| IF | IN | LABEL | MOD | NIL | NOT | OF | OR | PACKED | PROCEDURE | PROGRAM | RECORD | REPEAT |SET | THEN | TO | TYPE | UNTIL | VAR | WHILE | WITH

Службові слова інтерпретуються як єдині символи з фіксованим значенням.

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

Інколи в реалізаціях мови деякі з основних символів можуть бути відсутні, тоді замість них використовують ком­бінації інших символів.

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

Ім'ям може бути будь-яка послідовність букв, цифр і знаку підкреслювання, яка починається з букви (пропус­ки в іменах не припустимі). Імена не повинні збігатися із службовими словами. Кількість символів імені (довжина імені), взагалі кажучи, може бути довільною. Проте, в де­яких реалізаціях мови вимагається, щоб імена, які позна­чають різні об'єкти, відрізнялися першими вісьмома сим­волами. Для кращого розуміння програми доцільно виби­рати значущі імена, а не просто довільний набір симво­лів. Знак підкреслювання в іменах зручно використовувати тоді, коли імена складаються з кількох слів. Тоді слова сполучають знаком підкреслювання. Наприклад, modul— junga, середня -температура.

Для зображення чисел, які є константами цілого (inte­ger) чи дійсного (real) типу в мові Паскаль використовується десяткове подання. Дійсні константи можуть бути написа­ні в двох формах: у звичайній (з фіксованою крапкою) (1.2, —0.5, 14.0), в експоненціальній (з плаваючою крап­кою) (7.2Е-2,19.2Е+3, 8.0.Е4, 5Е—2). Якщо число записано в експоненціальній формі, то порядку передує буква Е, яку слід читати як «помножити на десять в степені...». Якщо число містить десяткову крапку, то синтаксис мови вимагає, щоб перед нею і після неї було принайні по одній цифрі.

У мові Паскаль можна використовувати константи-рядки. Рядок — це будь-яка послідовність символів, взятих в апострофи.. Якщо одним із символів рядка повинен бути апостроф, то його повторюють двічі. Наприклад, 'Два розвозки', 'PASCAL', 'Pascal', 4988', 'C,';'.

Рядки, що містять лише один символ, є константами стандартного символьного типу (типу char).