3566

Основні визначення. Приклади алгоритмів

Лекция

Информатика, кибернетика и программирование

Основні визначення. Приклади алгоритмів Аналіз (від др. греч. «розкладання, розчленовування») — операція уявного або реального розчленовування цілого (речі, властивості, процесу або відношення між предметами) на складові частини, виконуван...

Украинкский

2012-11-03

122 KB

23 чел.

Основні визначення. Приклади алгоритмів

Аналіз (від др. греч. «розкладання, розчленовування») — операція уявного або реального розчленовування цілого (речі, властивості, процесу або відношення між предметами) на складові частини, виконувана в процесі пізнання або наочно-практичної діяльності людини.

На додаток до синтезу, метод аналізу дозволяє отримати інформацію про структуру об'єкту дослідження.

Синтез — процес (як правило — цілеспрямований) з'єднання або об'єднання раніше розрізнених речей або понять в щось якісно нове, ціле або таке, що представляє набір. Термін походить від греч. уэниеуйт — поєднання, приміщення разом .

Можливий синтез рішень. У кібернетиці процес синтезу тісно пов'язаний з процесом попереднього аналізу. Синтез — інжинірингова побудова складних систем із заздалегідь підготовлених блоків або модулів різних типів. Низькорівневе, глибоке структурне об'єднання компонентів різних типів.

У доповненні до аналізу, метод синтезу дозволяє отримати уявлення про зв'язки і потоки між складовими об'єкту дослідження.

НИЗХІДНЕ ПРОГРАМУВАННЯ (Н.п.) (top-down programming). Спосіб розробки програм, при якому програмування ведеться методом зверху "вниз", від загального до деталей. Алгоритм рішення задачі розбивається на декілька простіших частин або підзадач. Їх виділяють таким чином, щоб програмування підзадач було незалежним. При цьому складають план рішення всієї задачі, пунктами якого і є виділені частини. План записують графічно у вигляді блок-схеми, де визначають головну і підлеглі підзадачі і зв'язки між ними, тобто інтерфейс. Тут же встановлюють, які початкові дані (або аргументи) отримує кожна підзадача для правильного функціонування і які результати вона видає. По блок-схемі складається програма, в якій містяться виклики підпрограм (процедур або функцій), відповідних виділеним підзадачам. Цю програму можна відразу відладжувати, тимчасово замінивши "заглушками" підпрограми для підзадач. Потім аналогічно проводять деталізацію і програмування кожної підзадачі. Процес послідовної деталізації йде до тих пір, поки не буде написана програма для кожного фрагмента алгоритму. При цьому на кожному етапі Н. п. є варіант програми, відладка якої ведеться по ходу всієї розробки програми, що діє.

ВИСХІДНЕ ПРОГРАМУВАННЯ (bottom up programming). Спосіб розробки програм, при якому програмування ведеться методом "знизу-вгору", від деталей до загального. Спочатку розробляються і тестуються функції (підпрограми) нижнього рівня. Потім на їх основі програмуються функції більш високого рівня і так далі При цьому структура і функціональне призначення функцій вищих рівнів витікає з функцій нижніх рівнів.

МОДУЛЬНЕ ПРОГРАМУВАННЯ (modular programming). Спосіб розробки програм, при якому програма розбивається на відносно незалежні складові частини - програмні модулі. При цьому кожен модуль може розроблятися, програмуватися, транслюватися і тестуватися незалежно від інших. Внутрішня будова модуля для функціонування всієї програми, як правило, значення не має. При модифікації алгоритму, що реалізовується модулем, структура програми не повинна мінятися.

СТРУКТУРНЕ ПРОГРАМУВАННЯ (С.п.)(structured programming). Методологія програмування, направлена на створення логічно простих і зрозумілих програм. С. п. засновано на припущенні, що логічність і зрозумілість програми полегшує розробку, доказ правильності і подальший супровід програми, а також забезпечує її надійність

ЗАГЛУШКА (З.) (module stub). Фіктивна підпрограма, що імітує одну або декілька функцій тимчасово відсутнього модуля програми, що розробляється. Наприклад, 3. застосовуються при модульному програмуванні для того, щоб можна було проводити компіляцію, тестування і відладку незавершеної програми, не чекаючи, коли деякі відсутні в ній модулі будуть розроблені в належному вигляді і випробувані. Залежно від функцій замінюваного модуля 3. може видавати або правдоподібний результат (наприклад, значення з таблиці), або деяке повідомлення (наприклад, що фіксує виклик відсутньої підпрограми)

ПІДПРОГРАМА (subroutine). Виділена частина програми, що реалізовує певний алгоритм, і що допускає звернення з різних місць решти частини програми.

ПРОГРАМА (П. )(program). Послідовність вказівок (команд або описів і операторів), задаюча алгоритм обчислювальній машині. П. указує, в якому порядку, над якими даними і які операції повинні бути виконані ЕОМ і в якій формі повинен бути виданий результат. Пристрій управління ЕОМ сприймає П., задану у вигляді послідовності машинних команд. Складання П. на машинній мові - незручний і трудомісткий процес. Тому зазвичай П. для ЕОМ складається людиною на одній з мов програмування, а потім сама ЕОМ перекладає (транслює) цю програму машинною мовою.

МАШИННА МОВА (М.м.)(computer language, machine language). Мова програмування, призначена для представлення програм і даних у формі, придатній для безпосереднього сприйняття їх пристроями даної обчислювальної машини. Є системою команд, даних і інструкцій, що мають форму цифрових кодів (у більшості ЕОМ - двійкових), які не вимагають трансляції і безпосередньо інтерпретуються процесором ЕОМ. Програми, написані на інших мовах програмування, спочатку транслюються на М. м., а вже потім виконуються обчислювальною машиною

МОВА ПРОГРАМУВАННЯ (М.п.)(programming language). Формальна мова, призначена для зв'язку людини з обчислювальною машиною. На М. п. ЕОМ задаються інформація (дані) і алгоритм обробки даних (програма). Процесор ЕОМ безпосередньо сприймає програму, представлену на машинній мові, програмування на якому вельми незручно для людини. Тому розроблені мови програмування високого рівня, програмування, що істотно спрощують процес, і не залежні від конкретної ЕОМ. Також існують проблемно-орієнтовані мови програмування, спеціально пристосовані для вирішення завдань певного класу. З розвитком інтелектуальних систем програмування в якості М. п. почне уживатися природна мова. Див. машинно-орієнтована мова, машинно-незалежна мова, візуальна мова програмування

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

СТЕК (С.) (stack). Впорядкований набір елементів даних, в якому можна видаляти і додавати елементи, причому новий елемент завжди записується в його кінець, а черговий читаний або такий, що видаляється елемент також завжди вибирається з його кінця. Таким чином, останній елемент, що додається, С. є єдиним доступним і першим елементом, що видаляється (за принципом "останнім увійшов - першим пішов"). Така влаштована, наприклад, пам'ять оболонки Norton Commander, в якій зберігається послідовність раніше виконаних команд на випадок їх повторного виконання.

ПАМ'ЯТЬ (memory, storage, store). 1. Загальна назва для будь-яких реальних або абстрактних засобів і механізмів фіксації і збереження інформації. 2. Те ж, що пам'ять ЕОМ. 3. Те ж, що пристрій, що запам'ятовує

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

ОПЕРАЦІЙНА СИСТЕМА (ОС) (operating system (OS)). Комплекс програм, організуючих обчислювальний процес в обчислювальній системі. Основними функціями ОС є розподіл ресурсів обчислювальної системи між завданнями з метою їх найбільш ефективного використання і полегшення роботи користувача з обчислювальною системою. Виконуючи першу функцію, ОС враховує і розподіляє ресурси, управляє центральним процесором, пам'яттю, введенням-виводом, забезпечує виконання операцій над файлами, виступає в ролі диспетчера, запускаючи на виконання прикладні програми, забезпечує взаємодію програм з технічними пристроями і користувачем. Виконуючи другу функцію, вона надає користувачеві зручний інтерфейс з програмним забезпеченням і пристроями комп'ютера, а також виконує допоміжні дії, такі як копіювання або друк файлів. ОС може одночасно підтримувати роботу на комп'ютері одного завдання - бути однозадачною або одночасно підтримувати роботу декількох програм - бути багатозадачною (мультизадачною). Користувач управляє ОС за допомогою команд операційної системи. Для управління роботою персональних IBM-сумісних комп'ютерів найчастіше використовуються ОС MS-DOS і Windows. На персональних комп'ютерах на базі процесорів 80486 або Pentium з великою оперативною пам'яттю (не нижче 32 Мб) можлива установка ОС OS/2, Windows NT або UNIX.

РЕСУРС (Р.) (resource). Час, апаратні, програмні і інші засоби, які можуть бути надані обчислювальною системою або її окремими компонентами обчислювальному процесу або користувачеві. Наприклад, Р. є час центрального процесора, область оперативної або зовнішньої пам'яті і пристрої введення-виводу, які можуть бути виділені для роботи деякої програми.

ПРОЦЕС (process). Послідовність операцій при виконанні програми або її частини разом з використовуваними даними. Операційна система розглядає процес як єдине ціле при розподілі ресурсів.

Як скласти алгоритм?

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

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

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

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

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

Починати рішення задачі необхідно з осмислення її умови. Завдання необхідно зрозуміти: Що свідчить завдання? Що дане? Що слід знайти? Першим кроком у вирішенні цих питань є запис заголовка алгоритму. Заголовок алгоритму відповідає на питання "Що дане?", "У якому вигляді дано?", "Що знайти?", "У якому вигляді представити результат?". Фактично ми виконаємо частину етапу формалізації завдання (щодо структури даних).

Можна вважати, що завдання ми зрозуміли, якщо вдається записати алгоритм в наступному вигляді:

АЛГ <Назва> (<Список аргументів і результатів з описом типів, розмірностей масивів і тому подібне>) АРГ <Список аргументів>

РЕЗ <Список результатів>

НАМ <Короткий словесний опис того, що слід зробити>

КОН

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

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

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

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

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

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

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

Приклад 1. Скласти алгоритм, в результаті виконання якого величина А прийняла б значення величини В, а В прийняла б значення А.

Рішення 1.

1. А := У

2. У := А

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

Рішення 2. Скористаємося допоміжною моделлю даного завдання. Хай А - це стакан з чаєм (тут "стакан" - ім'я величини, а "чай" - її значення), а В - чашка з кавою (тут чашка" – ім'я іншої величини, а "кава" - її значення). Необхідно перелити каву в стакан, а чай в чашку так, щоб напої не змішати.

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

1. Вміст стакана перелити в кухоль ( кухоль := стакан )

2. Вміст чашки перелити в стакан ( стакан := чашка )

3. Вміст кухля перелити в чашку ( чашка := кухоль )

Повертаючись до початкового завдання і вводячи допоміжну (проміжну) величину Р (такого ж типу як А і В), отримаємо правильне рішення:

1. Р:=а АБО 1. Р:=в

2. А:=в 2. У := А

3. В:=р 3. А := Р

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

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

1. поставити стілець на стіл.

2. переставити стіл (із стільцем) на необхідне місце.

3. знятий! стілець із столу, поставивши на нове місце.

Для числових величин А і В подібний алгоритм виглядав би

1 . А = А + У

2. У = А - В

3. А = А - В

Моделей і, відповідно, алгоритмів рішення може бути багато. Важливо (якщо їх багато) вибрати той, який буде легко реалізувати. Простота при виборі алгоритму перший великий крок на шляху до отримання програм .

Провідні фахівці програмування рекомендують при виборі алгоритму дотримувати так званий KISS - принцип:Keep It Simple, Stupid (роби простіше, дурень!).

Витончене програмування може обійтися дуже дорого. Навіть авторові програми часто важко відладити або модифікувати таку програму і довести її до робочого стану.

Приклад 2. Обчислити суму елементів лінійної таблиці A[N].

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

SUM = A[1]+ A[2]+ A[3]+ А[4]+ А[5]

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

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

1. ВКЛЮЧИЛИ МК (СТИРАЄМО ВМІСТ ІНДИКАТОРА)

2. НАБИРАЄМО ПЕРШЕ ЧИСЛО, НАБИРАЄМО ДРУГЕ ЧИСЛО І ДОДАЄМО ЙОГО ДО ВМІСТУ ІНДИКАТОРА, НАБИРАЄМО ТРЕТЄ ЧИСЛО І ДОДАЄМО ЙОГО ДО ВМІСТУ ІНДИКАТОРА » т.д.

Якщо через SUM позначити вміст індикатора, то виконувані дії можна записати таким чином:

SUM =0

SUM = А[1] або, що те ж саме, SUM= SUM + А[1]

SUM = SUM + А[2]

SUM = SUM + А[3] і так далі

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

SUM = SUM + A[k], де k= 1, 2, 3 ... N. Весь алгоритм має вигляд:

ЯСКРАВО-ЧЕРВОНИЙ Г СУМА (ЦІЛИЙ N. ВЕЩ ТАБ А| I .: N]. ВЕЩ SUM )

АРГ N, A РЕЗ SUM НАЧ ЦІЛИЙ до

SUM =0

ДЛЯ від 1 ДО N

Почати цикл

SUM = SUM + A[k]

Кінець циклу

Кінець

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

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

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

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

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

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

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

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

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

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

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

Приклад 3.1. Обчислення функції з умовою

Початкові дані: h

Результат: у

Обчислити:

де а = sin 2ph, b = cos 2ph

Алгоритм Обчислення_функції_з_умовою

Почало

введення (h, p)а := sin 2phb := cos 2ph якщо а > b і b > 0 те

у := а / b

інакше

якщо а < b і b <= 0 то

у := ab

інакше

все

все вивід (y)

Кінець

 

Приклад 3.2. Визначення квадранта

Початкові дані: X, Y - координати крапок

Результат: A - номер квадранта

Обчислити: номер квадранта, якому належить крапка із заданими координатами

 

Алгоритм Номер_квадранта

Почало

введення ( X, Y) якщо X >= 0 і Y >= 0 то

A := 1

інакше

якщо X < 0 і Y >= 0 то

A := 2

інакше

якщо X <= 0 і Y < 0 то

A := 3

інакше

A := 4

все

все

все вивід (A)

Кінець

Приклад 3.3. Пошук максимального елементу масиву і його номера

Обчислити максимальний елемент в масиві A[1:n] і його номер.

Початкові дані: n, A[1:n]

Результат: Max, Nmax

Алгоритм Пошук_максимума

Почало

введення(n, A[1:n])Max := A1Nmax := 1цикл від i:=2 до n

якщо Ai > Max то

Max := AiNmax := i

все

кц вивід (Max, Nmax)

Кінець

Приклад 3.4. Пошук максимального і мінімального елементів масиву і їх номерів

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

Початкові дані: n, A[1:n]

Результат: Min, Max, Nmin, Nmax

Алгоритм Найбільший_і_найменший

Початок

введення (n, A[1:n])Max := -10Min := 10цикл від i:=1 до n

якщо Ai > Max то

Max := ANmax := i

все якщо Ai < Min те

Min := AiNmin := i

все

кц вивід (Max, Min, Nmax, Nmin)

Кінець

Приклад 3.5. Сума натурального ряду

Обчислити суму n - членів натурального ряду: Sum = 1+2+3+...+ n

Початкові дані: n

Результат: Sum

Алгоритм Сума_натурального_ряду

Початок

введення (n)Sum:=0 цикл від i:=1 до n

Sum:=Sum+i

кц вивід (Sum)

Кінець

Приклад 3.6. Факторіал

Обчислити факторіал будь-якого цілого числа n: f = n!

Початкові дані: n

Результат: f

Алгоритм Факторіал

Початок

введення (n)f:=1цикл від i:=1 до n

f:=f*i

кц вивід (f)

Кінець

Приклад 3.7. Обчислення середнього арифметичного

Обчислити середнє арифметичне позитивних елементів масиву А[1:n]

Початкові дані: n, A[1:n]

Результат: SrPol чи ні позитивних елементів"

Алгоритм Середнє Арифметичне

Початок

введення (n, A[1:n])Sum := 0npol := 0цикл від i:=1 до n

якщо Ai > 0 то

Sum := Sum + Ainpol := npol + 1

все

кц якщо npol <> 0 те

SrPol := Sum / npolвивід(SrPol)

інакше

вивід("немає позитивний елементів")

все

Кінець

Приклад 3.8. Табуляція

Обчислити значення функції:

для x, змінного від 0 до 3 з кроком h. Надрукувати для кожного значення x відповідне значення(x)

Початкові дані: а, h

Результат: набір x і у

Алгоритм Табуляція

Початок

введення (а, h)x := 0цикл поки x <= 3

y:=a3/(a2+x2) виведення (x, у)x := x + h

кц

Кінець

Приклад 3.9. Видалення елементів в масиві

Видалити з масиву A[1:k] всі елементи, що задовольняють умові l <= Ai <= h шляхом зрушення (тобто без формування нового масиву).

Початкові дані: до, A[1:k], h, l

Результат: n, A[1:n] або повідомлення про відсутність видалення або повідомлення про повне видалення

Алгоритм Видалення

Початок

введення (до, A[1:k], h, l)n := 0цикл від i:=1 до до

якщо і ( Ai <= h ) то

n := n + 1An := Ai

все

кц якщо n=0 те

вивід ('повне видалення')

інакше

якщо n=k то

вивід ('видалення немає')

інакше

вивід (n, A[1:n])

все

все

Кінець

Приклад 3.10. Формування масиву

Сформувати масив, елементи якого обчислюються таким чином:

Початкові дані: n, A[1:n]

Результат: C[1:n], тобто в новому масиві стільки ж елементів, скільки в початковому масиві

Алгоритм Формування_масиву

Початок

введення (n, A[1:n])цикл від i:=1 до n

якщо Ai < 0 то

Ci:=-1

інакше

якщо Ai <= 10 то

Ci : = 0

інакше

Ci: = 1

все

все

кц вивід(C[1:n]))

Кінець

Приклад 3.11. Формування масиву з невідомим числом елементів

Обчислити масив, що містить від’ємні елементи заданого масиву A[1:n], що задовольняють умові:

Початкові дані: n, A[1:n], з

Результат: j, B[1:j]

Алгоритм Формування_масиву

Початок

введення (з, n, A[1:n]) j := 0 { номер элементв в масиві В}цикл від i:=1 до n

якщо ( Ai < 0 ) то

якщо ln |Ai| > з то

j:=j+1 Bj:=Ai

все

все кц якщо j <> 0 те

вивід(j, B[1:j])

інакше

вивід ('масив B порожній')

все

Кінець

Приклад 3.11. Формування двох масивів

Обчислити два масиви. Перший містить елементи Yi такі, що Yi-1 < Yi < Yi+1, другий, - решта елементи.

Початкові дані: до, Y[1:k]

Результат:n, A[1:n], m, B[1:m]

Алгоритм Формування_двух_масивів

Початок

введення (до, Y[1:k])n := 0 { число елементів в масиві A }m := 1 { число елементів в масиві B, оскільки перший елемент початкового масиву Y завжди буде в другому масиві }цикл від i:=2 до до - 1

якщо Yi-1 < Yi і Yi < Yi+1 те

n:=n+1 An:=Yi

інакше

m:=m+1 Bm:=Yi

все

кц якщо до <> 1 те { останній елемент Y завжди буде в другому масиві}

m : = m + 1Bm : = Yk

все якщо n <> 0 то

вивід (n, A[1:n])

все вивід(B[1:m])

Кінець

Приклад 3.12. Видалення елементів масиву між першим мінімальним і першим максимальним елементами.

У заданому одновимірному масиві X[1:n] видалити всі елементи, що знаходяться між першим мінімальним і першим максимальним елементами, не використовуючи додаткові масиви.

Розробимо укрупнений алгоритм рішення задачі, а потім детальний.

Алгоритм Видалення_елементів_масиву (укрупнений)

- знайти номер першого мінімального елементу (Nmin);- знайти номер першого максимального елементу (Nmax)- упорядкувати їх так, щоб в Nmin був менший з двох номерів номер:якщо Nmax < Nmin то

tmp:= Nmax;Nmax:=Nmin;Nmin:= tmp

все - дослідження можливості видалення:якщо Nmax-Nmin > 1, тобто максимальний і мінімальний елементи не сусідні то

{ видалення зрушенням}

все

Кінець - видалення зрушенням:цикл від i : = Nmax до n

XNmin + i - Nmax +1: = Xi

кц - зменшення кількості елементів в масиві: n : = n - (Nmax - Nmin) + 1

Алгоритм Видалення_елементів_масиву (детальний)

Початок

введення(n, x[1:n]){ визначення Nmin, Nmax }Nmin:=1Nmax:=1цикл від i : = 2 до n

якщо Xi < XNmin то

Nmin : = i

все якщо Xi > XNmax то

Nmax : = i

все

кц { впорядковування Nmin і Nmax }якщо Nmax < Nmin то

tmp : = Nmax;Nmax : = Nmin;Nmin : = tmp

все { перевірка умови видалення }якщо (Nmax - Nmin ) > 1 то

цикл від i : = Nmax до n

XNmin + i - Nmax +1: = Xi

кц

n : = n - (Nmax - Nmin) + 1 все вивід(n, X[1:n])

Кінець

Приклад 3.13. Вставка елементів в масив

Дано два масиви A[1:n] і B[1:m] . Потрібно вставити елементи масиву B в масив A після його мінімального елементу.

Алгоритм Вставка_елементу_в_масив (укрупнений)

пошук номера мінімального елементу Nmin в масиві A;

зрушення елементів масиву A, розташованих правіше мінімального (звільнення місця для елементів, що вставляються);

вставка елементів масиву B в масив A;

Кінець

Алгоритм Вставка_елементу_в_масив (детальний)

Початок

введення(n, A[1:n], m, B[1:m])) { визначення Nmin, Nmax }Nmin:=1цикл від i : = 2 до n

якщо Ai < ANmin те

Nmin : = i

все

кц { зрушення елементів масиву A управо на M позицій }цикл від i : = 1 до n - Nmin

An+m-i+1 : = An-i+1

кц { вставка елементів масиву B }цикл від i : = 1 до m

ANmin+i : = Bi

кц вивід (n+m, A[1:(n+m)])

Кінець

Відмітимо, що якщо мінімальний елемент виявиться останнім в початковому масиві, то зрушення елементів в масиві A не відбувається, а відразу виконується вставка елементів, яка по суті буде дописуванням елементів масиву B після останнього елементу масиву A, адже в цьому випадку Nmin рівне n.

Приклад 3.14. Достроковий вихід з циклу

Дане n, A[1:n], X. Обчислити суму елементів масиву, наступних за першим елементом, який рівний деякій величині X.

Алгоритм Достроковий_вихід_з_циклу

Початок

введення( X, n, A[1:n])Flag : = 0i : = 1 Пошук першого елементу рівного X }цикл поки Flag=0 і i < n

якщо Ai = X то

до : = i + 1Flag : = 1

інакше

i := i + 1

все

кц якщо Flag = 1 то

{ обчислення суми }Sum : = 0цикл від i : = до до n

Sum : = Sum + Ai

кц вивід(S)

інакше

вивід (елемент рівний ', X, 'незнайдений')

все

Кінець


 

А также другие работы, которые могут Вас заинтересовать

26810. Аппроксимация функций. Основные задачи протокола IP 159 KB
  Архитектура файлсервер имеет существенный недостаток: при выполнении некоторых запросов к БД клиенту могут передаваться большие объемы данных что загружает сеть и приводит к непредсказуемости времени реакции. средний уровень представляет собой сервер приложений на котором выполняется прикладная логика BL и с которого логика обработки данных DL вызывает операции с БД DS; верхний уровень представляет собой специализированный сервер БД выделенный для услуг обработки данных DS и файловых операций FS без риска использования хранимых...
26811. Квадратичная аппроксимация (МНК). Методология IDEF 1 80.5 KB
  Нужно найти уравнение либо прямой линии либо кривой второй степени параболы либо еще более высокой степени полином алгебраический многочлен который лучше всего передавал бы на чертеже наиболее характерные свойства расположения заданных экспериментальных точек. Управление маркетингом подразумевает сбор и анализ данных о фирмахконкурентах их продукции и ценовой политике а также моделирование параметров внешнего окружения для определения оптимального уровня цен прогнозирования прибыли и планирования рекламных кампаний.Методология IDEF...
26812. Системный подход, системные исследования и системный анализ 21.87 KB
  Системный подход системные исследования и системный анализ Для анализа сложных объектов и процессов применяются системный подход системные исследования и системный анализ. Системный подход к исследованиям предполагает необходимость исследования объекта с разных сторон комплексно в отличие от ранее принятого разделения исследований на физические химические и другие. Однако заимствованные при таком подходе понятия теории систем вводились не строго не исследовался вопрос каким классом систем лучше отобразить объект какие свойства и...
26813. Методы и модели описания систем. Качественные методы описания систем 175.47 KB
  Однако позднее обязательное требование явно выраженных временных координат было снято и сценарием стали называть любой документ содержащий анализ рассматриваемой проблемы или предложения по ее решению по развитию системы независимо от того в какой форме он представлен. Таким образом сценарий помогает составить представление о проблеме а затем приступить к более формализованному представлению системы в виде графиков таблиц для проведения экспертного опроса и других методов системного анализа. Основная идея морфологических методов –...
26814. Модели систем. Алгоритм разрешения имен в службе DNS 73.86 KB
  Журнализация и буферизация Журнализация изменений тесно связана не только с управлением транзакциями но и с буферизацией страниц базы данных в оперативной памяти. Если бы запись об изменении базы данных которая должна поступить в журнал при выполнении любой операции модификации базы данных реально немедленно записывалась бы во внешнюю память это привело бы к существенному замедлению работы системы. Проблема состоит в выработке некоторой общей политики выталкивания которая обеспечивала бы возможность восстановления состояния базы данных...
26815. Индивидуальный откат транзакции 188.67 KB
  Соответствующий протокол журнализации и управления буферизацией называется Write Ahead Log WAL пиши сначала в журнал и состоит в том что если требуется записать во внешнюю память измененный объект базы данных то перед этим нужно гарантировать запись во внешнюю память журнала транзакций записи о его изменении. Другими словами если во внешней памяти базы данных находится некоторый объект базы данных по отношению к которому выполнена операция модификации то во внешней памяти журнала обязательно находится запись соответствующая этой...
26816. Структура и свойства информационных процессов 84.74 KB
  Воздействуя на параметры переносчика можно осуществить передачу данных на требуемое расстояние по выбранному каналу. Действия сервера и клиента: Клиент устанавливает связь и посылает запрос на 21 порт сервера с порта N N 1024 Сервер посылает ответ на порт N N 1024 клиента Сервер устанавливает связь для передачи данных по порту 20 на порт клиента N1 Активный режим 5. Он предназначен для обеспечения надежного хранения данных в БД. А это требование предполагает в частности возможность восстановления согласованного состояния базы данных...
26817. Численное дифференцирование. Сущность структурного подхода проектирования ИС 232.5 KB
  Численное дифференцирование используется для приближенного вычисления производных функции заданной таблицей и для функций, которые по разным причинам неудобно или невозможно дифференцировать аналитически. В последнем случае вычисляется таблица функции в окрестности исследуемой точки и по этим значениям вычисляется приближенное значение производной.
26818. Оценка затрат на разработку ПО 138.5 KB
  Например можно сократить сроки разработки за счет уменьшения функциональности системы или использовать в качестве составных частей ИС продукцию других фирм вместо собственных разработок.Определение системы. Определение системы. Первое определение системы: Система есть средство достижения цели.