Розробка блок-схеми алгоритму розв’язання задачі - практична робота

відповіді на контрольні питання;

висновки по практичній роботі.

1.2. Загальні відомості

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

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

Основними характерними властивостями алгоритму є:

детермінованість (визначеність) - при заданих вихідних даних забезпечується однозначність бажаного результату;

масовість - придатність для задач даного типу при вихідних даних, що належать заданому подмножеству;

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

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

Виділяють такі типи обчислювальних процесів:

Лінійний обчислювальний процес.

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

Розгалужений обчислювальний процес.

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

Циклічний обчислювальний процес

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

У свою чергу, існують також кілька типів циклічного обчислювального процесу. а саме:

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

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

Пошукові цикли - це циклічні процеси, з яких можливі два варіанти виходу:

- вихід із завершення процесу;

- достроковий вихід з якого-небудь додатковій умові.

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

- алгоритми лінійної структури;

- алгоритми розгалуженої структури;

- алгоритми циклічної структури.

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

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

- словесний (записи на природній мові);

- структурно-стилізований (записи на алгоритмічній мові і псевдокод);

- графічний (зображення схем і графічних символів);

- програмний (тексти на мовах програмування).

Словесний спосіб опису алгоритму є опис послідовних пронумерованих етапів обробки даних і поставив у довільному викладі природною мовою.

Алгоритм складання двох чисел (a і b).

Запитати, чому дорівнює число a.

Запитати, чому дорівнює число b.

Скласти a і b, результат привласнити с.

Повідомити результат с.

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

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

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

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

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

Блок-схема алгоритму - це графічне представлення ходу виконання завдання. Блок-схема складається з блоків, з'єднаних лініями, а блоки зображуються у вигляді геометричних фігур, які називаються символами. Усередині символів записуються вказівки про виконувані блоком функціях - формули, текст, логічні вирази. Вид символів і правила виконання блок-схем стандартизовані - ГОСТ 19.701-90 містить перелік символів, їх найменування, які відображаються функції, форми і розміри, а також правила виконання схем. При розробці алгоритму кожна дія позначають відповідним блоком, показуючи їх послідовність лініями зі стрілками на кінці. Назви, позначення і призначення елементів блок-схем наводиться на рис. 1.1.

Малюнок 1.1 - Основні блоки

Слід згадати деякі основні правила виконання блок-схем, якими слід керуватися при графічному описі алгоритмів. Початок алгоритмів відзначається символом "Термінатор", з якого виходить одна лінія. У ньому записується слово "Пуск" ( "Початок"). Кінець алгоритму відзначається цим же символом, в якому записується слово "Зупинка" ( "Кінець"). У цьому випадку даний символ не має жодної вихідний лінії, а на нього може замикатися одна або більше ліній. Символ "Процес" може мати одну або кілька вхідних ліній і тільки одну вихідну. Усередині символу може бути записано кілька приписів - в цьому випадку вони виконуються в порядку запису. Подання окремих операцій досить вільно. Для позначення обчислень можна використовувати математичні вирази, для пересилки даних - стрілки, для інших дій - пояснення природною мовою, наприклад, А: = Х + 4; i: = i + 1, -> B.

Для запису алгоритму будь-якої складності досить трьох базових структур.

слідування - позначає послідовне виконання дій (рис. 1.2, а);

розгалуження - відповідає вибору одного з двох варіантів дій (рис. 1.2, б);

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

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

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

вибір - вибір одного варіанта з декількох в залежності від значення деякої величини (рис. 1.3, а, б);

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

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

Малюнок 1.3 - Реалізація додаткових алгоритмічних структур

через базові структури

Розглянемо приклади графічного опису алгоритмів різних типів: лінійного, разветвляющегося, циклічного та комбінованого (рис. 1.4 - 1.7).

Приклад 1.2. Лінійний алгоритм.

Алгоритм обчислення значення виразу K = 3b + 6а (рис. 1.4).

Малюнок 1.4 - Приклад блок-схеми лінійного алгоритму

Приклад 1.3. Розгалужується алгоритм.

Алгоритм, який визначає, чи пройде графік функції y = 3x + 4 через точку з координатами x1, y1 (рис. 1.5).

Малюнок 1.5 - Приклад блок-схеми разветвляющегося алгоритму

Приклад 1.4. Циклічний алгоритм.

Алгоритм, який визначає факторіал натурального числа n (рис. 1.6):

Малюнок 1.6 - Приклад блок-схеми циклічного алгоритму

Приклад 1.5. Комбінований алгоритм.

Необхідно визначити найбільший спільний дільник двох натуральних чисел А і В.

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

Приклад (а): А = 225, В = 125. Застосовуючи алгоритм Евкліда, отримуємо для А і В найбільший спільний дільник, рівний 25.

Приклад (б): А = 13, В = 4. У цьому випадку найбільший спільний дільник А і В дорівнює 1.

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

Малюнок 1.7 - Приклад блок-схеми комбінованого алгоритму

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

Приклад 1.6.Опісаніе алгоритму Евкліда на псевдокоді.

Таблиця 1.1 - Приклад псевдокоду для запису базових алгоритмічних структур

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

Дано ціле число m> 1.

Отримати найменше ціле k, при якому 4 k> m.

Дано натуральне число n. Обчислити твір.

Дано натуральне число n.

Дано ціле число n.

Отримати найменше число виду 2 r. перевершує n (r - натуральне).

Дано цілі числа n, k (n  k  0).

Дано натуральне число n і дійсне число a.

Дано натуральне число n.

Дано натуральне число n.

Обчислити суму n перших доданків

Дано послідовність чисел. число n - кількість елементів послідовності і число x. Визначити кількість входжень числа x в задану послідовність.

Дано натуральне число n. обчислити:

Дано дійсне число а, натуральне число n.

Дано послідовність чисел і число n - кількість елементів послідовності. Знайти кількість негативних елементів послідовності.

Дано дійсне число а, натуральне число n.

Нехай. Знайти перший член yn. для якого виконується нерівність. де  - заданий дійсне позитивне число.

Дано дійсні числа a і h, натуральне число n.

Дано натуральне число n. обчислити:

Дано послідовність чисел і число n - кількість елементів послідовності. Знайти суму позитивних елементів послідовності.

Дано натуральне n, дійсне х.

Дано послідовність чисел і число n - кількість елементів послідовності. Знайти твір негативних елементів послідовності.

Дано дійсне число х і натуральне число n.

Обчислити, не використовуючи операцію піднесення до степеня.

Дано дійсне число х і натуральне число n.

Обчислити. не використовуючи операцію піднесення до степеня.

Дано натуральне число n.

Дано дійсні числа x і a, натуральне n.

Нехай послідовність чисел утворена по наступному закону: = 1; ak = k * ak-1 + 1 / k; k = 1,2. Дано ціле число n. Отримати an.

Дано натуральне число n. Знайти кількість цифр цього числа і їх суму.

Нехай n- натуральне число. Обчислити суму.

Дано дійсне число х.

Дано натуральні числа n, m. Отримати суму m останніх цифр числа n.

Нехай n- натуральне число. Обчислити суму.

Дано натуральне число n.

Дайте визначення алгоритму.

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

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

Які способи опису алгоритмів вам відомі?

Що розуміється під графічним способом опису алгоритмів? У чому полягає перевага даного способу перед словесним описом алгоритму?

Назвіть базові алгоритмічні структури і поясніть їх призначення.

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