Бураков П.В., Косовцева Т.Р. Інформатики. Алгоритми та програмування. Навчальний посібник.-СПб НДУ ІТМО, 2013. - 83с.

Навчальний посібник призначений для студентів економічних спеціальностей 080100 «Економіка» гуманітарного факультету, які вивчають дисципліну «Інформатика». Посібник є вступним курсом по побудові алгоритмів і з програмування мовою Турбо Паскаль. Посібник містить багато прикладів. Докладно викладаються теоретичні аспекти побудови алгоритмів та основ програмування. У другій частині навчального посібника наводиться лабораторний практикум.

2009 року Університет став переможцем багатоетапного конкурсу, в результаті якого визначено 12 провідних університетів Росії, яким присвоєно категорію «Національний дослідницький університет». Міністерством освіти і науки Російської Федерації було затверджено Програму розвитку державної освітньої установи вищої професійної освіти «Санкт-Петербурзький державний університет інформаційних технологій, механіки та оптики» на 2009-2018 роки.

© Санкт-Петербурзький національний дослідницький університет інформаційних технологій, механіки та оптики, 2013 © П.В. Бураков, Т.Р.Косовцева

Постановка задачі................................................ .................................................. .......................
Розробка математичної моделі............................................... .............................................
Вибір методу чисельного рішення.............................................. ...............................................
Розробка алгоритму та структури даних............................................. ...................................
Реалізація алгоритму як програми............................................. ......................................
Налагодження та тестування програми.............................................. ..............................................
Розв'язання задачі на комп'ютері.............................................. .................................................. ...
ПОБУДУВАННЯ АЛГОРИТМУ РІШЕННЯ ЗАДАЧІ.............................................. ...............................
Опис алгоритму................................................ .................................................. ....................
Схема алгоритму................................................ .................................................. ........................
Структуровані схеми алгоритмів............................................... .....................................
ЗАСОБИ РЕАЛІЗАЦІЇ АЛГОРИТМУ............................................... ...........................................
Критерії вибору мови програмування.............................................. ...............................
СТРУКТУРА ПРОГРАМИ І ЇЇ ЕЛЕМЕНТИ............................................. ....................................
Основні елементи програмування............................................... ....................................
Алфавіт і словник TurboPascal (TPascal).......................................... .............................
Структура програми................................................ .................................................. ...............
ТИПИ ДАНИХ................................................ .................................................. ....................................
Скалярні типи даних............................................... .................................................. ............
Структуровані типи даних............................................... ..............................................
ВВЕДЕННЯ-ВИСНОВОК ДАНИХ.............................................. .................................................. .......................
Процедури введення-виводу.............................................. .................................................. ...........
ОПЕРАТОРИ................................................. .................................................. .........................................
Загальні відомості................................................ .................................................. .........................
Прості оператори................................................ .................................................. ...................
Структурні оператори................................................ .................................................. ...........
Умовні оператори................................................ .................................................. .................
Оператори циклу................................................ .................................................. .......................
МАСИВИ................................................. .................................................. .............................................
Дії над масивами............................................... .................................................. ............
Дії над елементами масиву.............................................. ..............................................
Операції з матрицями............................................... .................................................. ...............
ПРОЦЕДУРИ ТА ФУНКЦІЇ............................................... .................................................. ..................
Необхідність структуризації у програмуванні.............................................. ..............
Підпрограми у мові ТPascal.............................................. .................................................. ..
Процедури................................................. .................................................. .................................
Функції................................................. .................................................. ....................................
Механізм передачі параметрів............................................... .................................................
ФАЙЛИ................................................. .................................................. ..................................................
Загальні відомості................................................ .................................................. .........................
Опис файлового типу............................................... .................................................. .........
Засоби обробки файлів............................................... .................................................. ......
Текстові файли................................................ .................................................. .......................

ЛАБОРАТОРНИЙ ПРАКТИКУМ................................................ .................................................. ........
Лабораторна робота 1.		Програмування лінійних та	розгалужених
обчислювальних процесів................................................ .................................................. ...........
Лабораторна робота №2.	Циклічні обчислювальні процеси...................................
Лабораторна робота №3.		Операції з масивами............................................... ..................
Лабораторна робота №4.	Операції з файлами............................................... ......................
Лабораторна робота 5. Процедури та функції........................................... ...........................
БІБЛІОГРАФІЧНИЙ СПИСОК................................................ .................................................. ...

ЕЛЕМЕНТИ ТЕХНОЛОГІЇ РІШЕННЯ ПРАКТИЧНИХ ЗАВДАНЬ НА КОМП'ЮТЕРІ

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

1. Постановка задачі.

2. Розробка математичної моделі.

3. Вибір методу чисельного рішення для розрахункових завдань.

4. Розробка алгоритму розв'язання та структури даних.

5. Реалізація алгоритму як програми.

6. Налагодження та тестування програми.

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

Постановка задачі

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

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

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

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

Розробка математичної моделі

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

Математичною моделлю завдання, сформульованої в прикладі 1 є формула: S = 0,5 a t 2 , де в якості основної змінної виступає час t параметром руху є прискорення а . Формула показує залежність між довжиною шляху та часом відповідно до закону механіки.

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

S = ∫ V (t) dt ,

при цьому закон зміни швидкості V(t) залежно від часу може бути досить складним та визначити значення інтегралу аналітично не вдається. Тому здебільшого практично доцільно використовувати наближені методи рішення.

Особливу увагу слід приділяти адекватності математичної моделі стосовно вихідного опису завдання та умов її вирішення з одного боку. Невиправдана складність призводить до непотрібних витрат сил, коштів та часу. З іншого боку, недостатня точність математичного опису (грубість моделі) призводить до великих похибок у рішенні, інколи ж і до помилкових висновків.

Вибір методу чисельного рішення

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

∫ f (x ) dx ≈ ∆ x ∑ f (x i ) , де ∆х - крок інтегрування (const), ∆х=(b-a)/n,

x i+1 =xi +∆ х, x1 =a , xn+1 =b

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

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

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

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

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

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

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

Реалізація алгоритму як програми

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

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

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

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

Налагодження та тестування програми

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

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

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

Розв'язання задачі на комп'ютері

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

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

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

1. Які фактори впливають на ефективність вирішення завдань на комп'ютері?

2. Перерахуйте етапи розв'язання задач на комп'ютері.

3. Які основні вимоги до математичної моделі задачі?

4. Назвіть основні параметри алгоритмів.

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

6. Чим завершується розробка алгоритму?

ПОБУДУВАННЯ АЛГОРИТМУ РІШЕННЯ ЗАВДАННЯ

Опис алгоритму

Під алгоритмом розуміється кінцева послідовність точно сформульованих правил розв'язання деякого каса задач. Алгоритм має такі властивості:

Визначеність. Всі дії, які необхідно зробити, повинні бути суворо визначені.

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

Кінцевість. Обов'язковість завершення кожного з дій, що становлять алгоритм і завершність виконання алгоритму загалом.

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

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

Правильність. Здатність алгоритму давати правильні результати вирішення поставлених завдань.

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

Розглянемо алгоритми розв'язання кількох завдань. Завдання 1 . Скласти алгоритм обчислення x за формулою

x = a (r − q ) 2 , де p ≠ -12.

p + 12

1. Початок;

2. Обчислити b: = p + 12;

3. Обчислити c:= r – q;

4. Обчислити d: = c;

5. Обчислити e: = ad;

6. Обчислити x:= e/b;

7. Записати результат: x;

У записі алгоритму розв'язання задачі 1 введені літерні позначення

- Змінні. Так, через b позначено p + 12 через c - різниця r - q. Запис

b:= p+12 означає, що спочатку повинна бути знайдена сума p + 12 за певних значень p, а потім це значення присвоюється змінною b.

Надаючи a, p, q, r різні значення, отримуватимемо різні завдання на обчислення x . Тому алгоритм зазвичай дозволяє вирішувати не одну, а цілий клас завдань. Таку особливість алгоритму називають масовістю алгоритму. Можливі алгоритми, що вирішують лише єдине завдання.

Величини a, p, q, r, 12 складають вихідні дані для алгоритму, 12

- Постійну складову, a, p, q, r - змінну складову інформації. Величини b, c, d, e є допоміжними змінними, x результат виконання алгоритму.

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

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

Завдання 2 . За формулою

x = − b ± b 2 − 4 ac скласти алгоритм розв'язання квадратного рівняння

ax2 + bx + c = 0 (a ≠ 0).

1. Початок;

2. p: = 2a;

3. D:= b 2 - 4ac;

4. Якщо D ≥ 0, то перейти до п. 5 інакше до п. 10;

5. d: = D;

6. x 1 : = − b − d; p

7. x 2 : = − b + d; p

8. Записати результат: x 1, x2;

9. Перейти до п. 11;

10. Записати результат: рівняння дійсних коренів не має;

11. Кінець.

У виконанні алгоритму виконуються в повному обсязі його команди, отже, алгоритм розв'язання завдання 2 перестав бути лінійним. Крім арифметичних дій та операцій вилучення квадратного кореня, обчислювальний процес містить у правилі 4 операцію перевірки умови: залежно від виконання умови (так) або невиконання умови (ні) вибирається одне з двох можливих продовжень. Такий алгоритм називають розгалужується. Операцію, яка може змінити послідовність виконання правил алгоритму, назвемо оператором керування.

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

У командах умовного переходу обов'язково є логічна умова типу: якщо α ◊ β , то …(де ◊ - один з операторів > , ≥ ,< , ≤ , = , ≠ ).

Схема алгоритму

Схема алгоритму є графічне зображення алгоритму з допомогою певним чином пов'язаних між собою блоків. Кожен блок зображується певною фігурою. Блоки у схемі з'єднуються дугами. Дуги вказують порядок прямування блоків під час виконання алгоритму. Типи блоків представлені малюнку 1.

Рис.1. Типи блоків

Прямокутник разом із укладеним у ньому етапом обчислення S називають функціональним блоком, або процесом (рис.1, а). Ромб із укладеною в ньому умовою P називають блоком перевірки умови, або рішенням (рис.1 б). Він використовується для управління порядком виконання блоків у схемі алгоритму. З функціонального блоку виходить одна стрілка, а з блоку перевірки умови – дві. Останнє пояснюється тим, що в результаті виконання команди перевірки умови отримуємо або виконання (так) або невиконання (ні) заданої умови P. Інформаційний блок(рис.1, в) використовується для введення та виведення А. Блоки (рис.1, г) та (рис.1, д) називають відповідно початковим і кінцевим . Блок-схема розв'язання задачі починається у початковому блоці та закінчується в кінцевому.

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

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

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

На малюнках 2 і 3 зображені схеми алгоритмів розв'язання задачі знаходження суми n - чисел: a1, a2, a3, a4,.., an.

Анотація: Предмет науки програмування. Приклад та властивості алгоритму. Парадигми програмування (директивне, об'єктно-орієнтоване та функціонально-логічне програмування).

Цей розділ, з якого починається вивчення курсу, служить двом основним цілям:

• підготувати необхідну теоретичну базу для подальшого оволодіння різними методами обробки інформації, навичками програмування в малому та побудови правильних ефективних програм;
• дати мінімально необхідні для практичного програмування знання про мову Java та надати зразки невеликих типових програм.

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

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

І останнє зауваження – суто технологічне. На першій стадії вивчення мови Java корисно відволіктися від того факту, що він є об'єктно-орієнтованим, і зосередитись на змістовних проблемах коректної реалізації алгоритму. Однак це не так просто зробити – написання навіть найпростішої програми на ньому неможливе без розуміння основних концепцій ОВП. Для часткового вирішення цієї проблеми використовується створений спеціально для цього клас Xterm, що захищає програміста-початківця від складностей реального світу мови Java.

Предмет науки програмування

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

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

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

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

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

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

Приклад та властивості алгоритму

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

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

Алгоритм розв'язання задачі.

Алгоритм П:

П1: Покласти ціле число рівним двом і перейти на крок П2.

П2: Якщо ділиться націло на , то завершити роботу алгоритму, видавши як результат ; інакше перейти на крок П3.

П3: Збільшити значення на одиницю та перейти на крок П2.

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

k = 3	k = 4	k = 2
П1: i = 2	П1: i = 2	П1: i = 2
П2: i = 2	П2: i = 2	П2: i = 2
П3: i = 3
П2: i = 3

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

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

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

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

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

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

Вихід (output). Алгоритм завжди повинен мати одну або кілька вихідних величин. У разі алгоритму П такою величиною є число. Алгоритми, які мають вихідних даних, марні практично, і ми їх вивчатимемо.

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

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

Зі сказаного вище, що у ЕОМ практично неможливо працювати з дійсними числами, Що, мабуть, може здатися вам неправдоподібним. Насправді, це так. Більше того, навіть зі справжніми цілими числами на комп'ютері працюють не так часто. Зазвичай замість множини цілих і дійсних чисел доводиться працювати зі своїми замінниками

Поняття алгоритму належить до основних понять інформатики. Розглянемо основні поняття, що з поняттям алгоритму.

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

Виконавець - людина або автомат (наприклад, комп'ютер), що вміє виконувати певний кінцевий набір дій.

Припис - наказ виконання дій із зазначеного кінцевого набору.

Система розпоряджень - Сукупність допустимих наказів.

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

У разі, коли виконавцем є комп'ютер, припис називається командою , а система розпоряджень називається системою команд комп'ютера . p align="justify"> Різні комп'ютери залежно від їх пристрою можуть мати різні системи команд.

Програмування - Складання послідовності команд, яка необхідна для вирішення поставленого завдання.

Складання програми передує розробка алгоритму.

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

Будь-який алгоритм має такі властивості:

• 1. Дискретність. Виконання алгоритму розбивається на послідовність елементарних процесів - кроків. Кожна дія має бути закінчена виконавцем, перш ніж він перейде до виконання наступної дії. Здійснити кожну окрему дію виконавцю наказує спеціальна вказівка ​​в записі алгоритму, зване командою.
• 2. Точність чи детермінованість. Запис алгоритму повинен бути таким, щоб виконавши чергову команду, виконавець точно знав, яку команду треба виконувати наступною.
• 3. Зрозумілість. Кожен алгоритм будується з розрахунку на конкретного виконавця, який має змогу виконати кожну команду алгоритму у суворій відповідності до її призначення.
• 4. Результативність. При точному виконанні всіх розпоряджень алгоритму процес повинен завершиться за кінцеве число кроків і при цьому має бути отримана будь-яка відповідь на поставлене завдання. Як одне з можливих рішень може бути встановлення того факту, що завдання не має рішення
• 5. Масовість. допомогою одного й того алгоритму можна вирішувати однотипні завдання і робити це неодноразово. Властивість масовості значно підвищує практичну цінність алгоритмів.

p align="justify"> Велика цінність алгоритмів полягає в тому, що виконавець може не вникати в зміст того, що він робить, і разом з тим отримувати необхідне більше знань, ніж від виконавця.

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

Кожен алгоритм передбачає наявність деяких вихідних даних. Наприклад, для медичного рецепту (алгоритму) вихідними даними є медикаменти, а результатом – флакон із готовими ліками. Для алгоритму складання вихідними даними є пара доданків, а результатом – їх сума. Для кожного алгоритму існує клас об'єктів, допустимих як вихідні дані. Іноді вихідними даними є матеріальні об'єкти, інколи ж - числа.

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

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

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

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

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

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

Являє собою послідовне виконання дій (рис. 12).

Мал. 12.

Застосовується у разі, коли в залежності від істинності деякої логічної умови необхідно виконати ту чи іншу дію (рис. 13).

Мал. 13.

Дії 1 і 2 можуть, у свою чергу, включати інші алгоритмічні структури.

Цикл . Застосовується, коли деякі дії потрібно виконати кілька разів. Існують два різновиди циклу.

Застосовується, коли деякі операції треба повторювати доти, доки деяка умова стане помилковою (рис. 14).

Мал. 14. Цикл До.

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

Застосовується, коли деякі операції треба повторювати доти, доки деяка умова стане істинним (рис. 15).

Мал. 15. Цикл Бувай.

2.4.1. Поняття базових алгоритмів

2.4.2. Алгоритми лінійної структури

2.4.3. Базові алгоритми структур, що розгалужуються, і приклади їх програмування

2.4.4. Базові алгоритми регулярних циклічних структур та приклади їх програмування

2.4.5. Базові алгоритми ітеративних циклічних структур та приклади їх програмування

2.4.6. Базові алгоритми обробки одновимірних масивів

2.4.7. Базові алгоритми обробки двовимірних масивів

2.4.8. Контрольні питання на тему «Базові алгоритми та приклади їх реалізації»

2.4.9. Тестові завдання на тему «Базові алгоритми та приклади їх реалізації»

2.4.1. Поняття базових алгоритмів

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

До базових алгоритмів імперативного програмування можна віднести:

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

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

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

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

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

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

2.4.2. Алгоритми лінійної структури

Приклад 2.4.2-1.

де x = -1,4; y = 0,8; змінні kим – цілого типу, інші змінні - речовинного типу; [n] - ціла частина числа n.

Схема алгоритму та програми мовами QBasic, Pascal, C++ представлені на рис. 2.4.2-1.

Слід звернути увагу на те, що ціла змінна kотримала округлене значення n, а ціла змінна m- усічене за допомогою функції FIX()до цілої частини значення n.

Приклад 2.4.2-2. Обчислити та вивести на екран значення наступних величин:

де x = 2.9512; y = 0.098633; змінні – цілого типу; інші змінні – матеріального типу.

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

Мал. 2.4.2-2.

Результати виконання програми при зазначених вище значеннях вихідних даних мають такий вигляд:

Приклад 2.4.2-3.Обчислити та вивести на екран значення першої космічної швидкості.

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

де – гравітаційна стала; M – маса Землі;
- Відстань від центру Землі до космічного апарату.

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

Мал. 2.4.2-3.

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

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

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

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

У інформатиці універсальним виконавцем алгоритмів є комп'ютер.

2. Властивості алгоритмів

Можна виділити такі основні властивості алгоритмів:

1) Зрозумілістьдля виконавця – тобто. Виконавець алгоритму повинен знати, як його виконувати.

2) Дискретність(перервність, роздільність) - тобто. алгоритм повинен представляти процес розв'язання задачі як послідовне виконання простих чи раніше певних кроків.

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

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

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

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

Найбільш поширеними формами представлення алгоритмівє: словесна, графічна, псевдокоди та програмна.

1) Словесна формазапису є опис послідовних етапів обробки даних природною мовою (наприклад, російською).

приклад.Записати алгоритм знаходження найбільшого загального дільника (НДД) двох натуральних чисел.

Алгоритм: 1) задати два числа; 2) якщо числа рівні, то взяти будь-яке з них як відповідь і зупинитися, інакше продовжити виконання алгоритму; 3) визначити більше із чисел; 4) замінити більше з чисел різницею більшого та меншого з чисел; 5) повторити алгоритм із кроку 2.

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

Словесний спосіб не має широкого поширення, оскільки такі описи:

а) строго не формалізуються;

б) страждають багатослівністю записів;

в) припускають неоднозначність тлумачення окремих розпоряджень.

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

Докладніше про це нижче…

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

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

приклад. 1) задати два числа x та y; 2) ЯКЩО x=y, ТО НОД=x і КІНЕЦЬ; 3) ЯКЩО x>y, ТО x=x-y, інакше y=y-x; 4) ПЕРЕЙТИ до пункту 2.

4) Програмна формає тексти програм, написаних різними мовами програмування.

Нижче наведено графічні позначення на блок-схемах.

Структура "дотримання"	Повна розвилка	Неповна розвилка
Цикл з передумовою (цикл ПОКИ)	Цикл із постумовою (цикл ДН)	Цикл із параметром

На схемах СЕРІЯ позначає один або кілька операторів; УМОВА є логічним виразом (ЛВ) (якщо його значення ІСТИНА, перехід відбувається по гілці ТАК, інакше - по НІ). На схемі циклу з параметром використані позначення: ПЦ – параметр циклу, НЗ – початкове значення параметра циклу, КЗ – кінцеве значення параметра циклу, Ш – крок зміни параметра циклу.

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

Принтери