Лінійні алгоритми: приклади, структура та особливості

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

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

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

Розглянемо кілька прикладів лінійних алгоритмів із повсякденного життя:

Алгоритм приготування бутерброду:
Взяти хліб Намазати масло|мастило| Покласти інгредієнти (сир, ковбаса і т.д.) Зібрати і нарізати бутерброд
Алгоритм шляху на роботу:
Вийти з дому Дойти до зупинки Дочекатися потрібного автобуса Сісти до автобуса Вийти на потрібній зупинці Дойти до роботи

Як видно з прикладів, для лінійних алгоритмів характерно:

• Послідовне, покрокове виконання команд
• Відсутність розгалужень, умов чи циклів

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

Графічне представлення лінійних алгоритмів

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

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

На малюнку представлений приклад блок-схеми для лінійного алгоритму дзвінка приятелю Петі:

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

Інша перевага графічного уявлення в тому, що його легко перетворити на програмний код будь-якою мовою програмування.

Аналіз ефективності лінійних алгоритмів

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

Для аналізу використовуються такі критерії як:

• Тимчасова складність - який час потрібний алгоритм для виконання
• Місткість - обсяг використовуваної пам'яті

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

Методи підвищення ефективності лінійних алгоритмів

• Зменшення кількості операцій
• Заміна менш ефективних операцій на більш швидкі
• Кешування проміжних даних

Наприклад, в алгоритмі приготування яєць некруто можна отримати невеликий виграш за рахунок кешування значення часу. Замість 12-15 хвилин можна залишити їх варитися на хвилин 5 або 8.

Типові помилки під час роботи з лінійними алгоритмами

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

• Порушення послідовності команд
• Некоректний опис логічних умов
• Неправильне використання циклів

Розглянемо деякі методи, які допомагають уникнути таких помилок:

1. Тестування алгоритму на простих тестових даних
2. Налагодження алгоритму покроковим виконанням
3. Використання візуального подання у вигляді блок-схем

Рекомендації щодо застосування лінійних алгоритмів

Отже, підсумовуючи всього сказаного, можна дати такі рекомендації:

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

Приклад лінійного алгоритму

Давайте наведемо ще один приклад лінійного алгоритму – приготування бутерброду:

1. Взяти два шматки хліба
2. Покласти на один шматок сиру
3. Покласти поверх інший шматок хліба
4. Зрізати краї бутерброду
5. Розрізати бутерброд навпіл

Це класичний приклад, коли всі дії виконуються послідовно одна за одною.

Алгоритм та властивості алгоритму¶

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

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

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

Типи алгоритмічних моделей¶

1. Обчислювальний алгоритм
2. Пристрій, що виконує примітивні операції
3. Формальні алгоритми

Запис алгоритму деякою мовою є програмою. Якщо програма написана спеціальною алгоритмічною мовою (наприклад, на ПАСКАЛі або С++), то говорять про вихідну програму, написану мовою, яка безпосередньо розуміє комп'ютер (як правило, це двійкові коди). ), називається машинною, або двійковою.

Основні способи запису алгоритмів

• вербальний - алгоритм описується людською мовою;
• символьний - алгоритм описується за допомогою набору символів;
• графічний алгоритм описується за допомогою набору графічних зображень.

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

Базові алгоритмічні структури

Алгоритми можна як деякі структури, які з окремих базових елементів. Логічна структура будь-якого алгоритму може бути представлена ​​комбінацією трьох базових структур: прямування, розгалуження, цикл. Характерною особливістю базових структур є наявність у них одного входу та одного виходу.

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

Розгалуження¶

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

Цикл¶

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

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

1. Цикл із передумовою (while) – тіло циклу виконується доти, доки виконується умова;

1. Цикл із постумовою (repeat…until) – тіло циклу виконується доти, доки умова не виконується;

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

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

Дані та величини¶

У програмуванні вивчаються методи програмного управління роботою комп'ютера, який виступає як виконавець. p align="justify"> Комп'ютер працює з величинами - різними інформаційними об'єктами: числами, символами, кодами та ін, тому алгоритми, призначені для управління комп'ютером, називаються алгоритмами роботи з величинами.

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

По відношенню до програми розрізняють вихідні, остаточні (результати) та проміжні дані, які отримують у процесі обчислень. Величина має три основні властивості: ім'я, значення та тип. На рівні команд процесора величина ідентифікується за допомогою адреси комірки пам'яті, в якій зберігається. В алгоритмах та мовах програмування величини поділяються на константи та змінні Костанта - Постійна величина, і в алгоритмі вона представляється власним значенням, наприклад: 15, 34.7, k, true і т.д. Змінна може змінювати свої значення в ході виконання програми і представляється символічним ім'ям ідентифікаторомнаприклад, X, S2, cod 15.

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

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

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

Лінійний обчислювальний алгоритм

Створити алгоритм поділу звичайних дробів.

Математична модель:

1. Чисельник першого дробу помножити на знаменник другого дробу.
2. Знаменник першого дробу помножити на чисельник другого дробу.
3. Записати дріб, чисельник якого є результатом виконання пункту 1, а знаменник — результатом виконання пункту 2.

Блок - схема та текст алгоритмічною мовою (псевдокодом) виглядають наступним чином:

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

Розгалуження¶

Скласти алгоритм розв'язання квадратного рівняння ax 2 + bx + c = 0

Математична модель

Рішенням у загальному випадку будуть два корені x₁, і x₂ , що обчислюються за формулою:

Блок-схема алгоритму представлено малюнку

Псевдокод

Цикли¶

Дано ціле позитивне число п. Потрібно обчислити n! (N-факторіал).

Математична модель

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

Блок-схема В алгоритмі використовуються три змінні цілого типу: n - Аргумент; i-проміжна змінна; F - Результат. Для перевірки правильності алгоритму побудовано трасувальну таблицю.

Псевдокод

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

Виконання серії команд (тіла циклу) повторюється, поки умова циклу істинна. Коли умова стає хибною, цикл закінчує виконання. Службові слова нц і кц позначають початок циклу та кінець циклу відповідно.

Допоміжні алгоритми¶

Алгоритм, що повністю використовується у складі іншого алгоритму.

Скласти алгоритм обчислення статечної функції з цілим показником у = х k , де до — ціле число, що не дорівнює 0

Математична модель

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

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

а та k - формальні параметри-аргументи, z - параметр-результат.Між формальними та фактичними параметрами процедури мають виконуватися такі правила відповідності: * за кількістю (скільки формальних, стільки та фактичних параметрів); * за послідовністю (першому формальному відповідає перший фактичний параметр, другому - другий і т.д.); * за типами (типи відповідних формальних та фактичних параметрів повинні збігатися)

Звернення до процедури ініціює такі дії:

1. Значення параметрів-аргументів надаються відповідним формальним параметрам.
2. Виконується тіло процедури (команди всередині процедури).
3. Значення результату передається відповідному фактичному параметру і відбувається перехід до виконання наступної команди основного алгоритму.

Використання процедур дозволяє будувати складні алгоритми методом послідовної деталізації

Лінійні алгоритми

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

На даний момент ви не можете подивитися чи роздати відеоурок учням

Щоб отримати доступ до цього та інших відеоуроків комплекту, потрібно додати його до особистого кабінету.

Отримайте неймовірні можливості

Конспект уроку "Лінійні алгоритми"

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

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

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

Давайте розглянемо ще один приклад лінійного алгоритму:

Шестикласницю Таню мама попросила посадити цибулю. Таня з радістю погодилася допомогти. Опишемо послідовність дій Тані:

1. Викопати на грядці ямку;

2. Покласти в ямку цибулю;

3. Засипати ямку із цибулею землею;

Представимо цей алгоритм за допомогою блок-схеми:

Початок алгоритму зображується за допомогою овалу (Таня прийшла на грядку)

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

Кінець алгоритму також зображується овалом (Таня вирушила до мами сказати, що її прохання виконано)

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

Система команд виконавця Обчислювач складається із двох команд:

Давайте придумаємо для обчислювача алгоритм, за допомогою якого він отримає з 0 число 50.

Алгоритм розв'язання цього завдання може бути, наприклад, таким:

0 – додати 1 – додати 1 – додати 1 – помножити на 2 – помножити на 2 – помножити на 2 – додати 1 – помножити на 2.

Для того щоб зрозуміти, чим же для нас може бути корисний лінійний алгоритм, давайте проведемо комп'ютерний практикум. Створимо презентацію «Годинник» за допомогою редактора презентацій Power Point. Давайте нашій презентації зробимо те щоб час на циферблаті змінювалося кожні 10 хвилин, тобто. поставимо лінійний алгоритм зміни часу.

1. Нагадаємо, що відкрити програму Power Point можна, натиснувши в меню Пуск – Усі програми.

2. Виберемо вкладку Головна потім у групі Слайди натиснемо на кнопці Макет тут нам потрібний Порожній слайд.

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

Тепер ми можемо зображати годинник. Почнемо із циферблату. Вибираємо вкладку Вставка, натискаємо на Фігури і за допомогою готових фігур зображаємо циферблат та дві стрілки.

Копіюйте повторювані зображення. Не забувайте їх можна редагувати, повертати.

4. Далі на вкладці Слайди лівої панелі натискаємо на слайд з годинником, переходимо на вкладку Головна і клацаємо на Копіювати. Вставимо в презентацію 4 копії нашого слайду (загалом у нас буде 5 слайдів), для цього на вкладці Головна натиснемо 4 рази Вставити.

5. Наш годинник повинен показувати час, тому змінимо положення стрілок на слайдах, наприклад, на 12.00, 12.10, 12.20, 12.30 та 12.40.

6. Для того, щоб слайди змінювалися, перейдемо на вкладку Переходи і в групі Час показу слайдів встановимо мінімальну тривалість переходу (00,01) потім натиснемо кнопку Застосувати до всіх.

7. Запустимо презентацію. Вибираємо вкладку Показ слайдів, натискаємо З початку.

8. Збережемо презентацію в папці з вашим прізвищем під назвою Мої годинники.

Отже, у нашій презентації «Годинник» лінійний алгоритм – це послідовна зміна часу кожні 10 хвилин.

Таким чином, сьогодні на уроці ми дізналися, що

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

Також навчилися застосовувати лінійні алгоритми для створення цікавих презентацій у PowerPoint.