Інформатика - Навчальний посібник
Структурограмми (діаграми Несс-Шнейдермана)
Зображення алгоритму за допомогою структурограмми відповідає всім основним вимогам структурного програмування. Головне - заборонені довільні передачі управління, а сама схема передачі зображується не за допомогою ліній як в блок-схемах, а за допомогою вкладених структур.
Кожен блок структурограмми має форму прямокутника і може бути вписана в будь-який прямокутник іншого блоку. Пояснювальні записи всередині блоків виконуються на природній мові або звичайними математичними виразами. Для зображення алгоритму використовуються наступні блоки:
ДДДДДДДДДДДДДДДД - блок обробки (обчислень); будь-який прямокутник всередині структурограмми є також блок обробки
ДДДДДДДДДДДДДДДД - блок проходження: послідовність блоків обробки
ДДДДДДДДДДДДДДДД - блок рішення; позначає структуру розгалуження
ДДДДДДДДДДДДДДДДД - блок варіанту; є розширенням блоку рішення.
Варіанти, відомі точно, розміщуються зліва. Решта об'єднують в один, званий виходом по недотримання умов, і розташовують праворуч
ДДДДДДДДДДДДДДДДД - якщо всі умови відомі, праву частину блоку варіанти залишають незаповненою або опускають зовсім
ДДДДДДДДДДДДДДДДД - блок циклу з передумовою і блок циклу з параметром
ДДДДДДДДДДДДДДДДД - блок циклу з умовою поста; внизу розташовується умова закінчення циклу
Як приклад наведемо структурограмму алгоритму розв'язання задачі табуляції функції, умови якої наводилися вище.
Вкладені алгоритмічні структури
Якщо одна алгоритмічна структура є частиною іншої алгоритмічної структури, то вона вважається вкладеною. Так, в попередньому прикладі структура розгалуження входить в цикл, а остання є частиною слідування. Таким чином, можна говорити і про рівень вкладеності.
Найбільший інтерес з точки зору створення ефективного алгоритму представляє випадок, коли до складу одного циклу входить інший цикл. Така алгоритмічна структура зазвичай називається складним циклом; цикл, що охоплює інший (інші) цикл, називається зовнішнім, а цикл, що входить у зовнішній, - внутрішнім або вкладеним. Існують певні правила організації таких структур, для знайомства з якими спочатку розглянемо приклад.
Нехай потрібно написати алгоритм розв'язання задачі табулювання функції 2-х змінних z = x + y. в якій х змінюється від 1 до 3 з кроком х = 0.5, а y змінюється від -1 до 1 з таким же кроком.
Спочатку слід продумати вид виведеного результату обчислень, щоб внести певну організацію і уникнути непотрібних повторів в видаваної інформації. Ми маємо справу зі складною функцією, яка залежить від двох змінних в рівній мірі, тому можна запропонувати наступну організацію виведення:
y = -1.0 z =. y = -0.5 z =.
Якщо ми приймаємо таку структуру виведення, то очевидно, що параметром зовнішнього циклу є х, а параметром вкладеного - змінна y. Блок-схему такого алгоритму можна змалювати таку картину:
Обчислимо, скільки разів повинен повторитися цикл по х для вирішення нашої задачі. Згідно приводившейся вище формулою,
Для самостійно виділеного внутрішнього циклу по y маємо число повторень
З отриманих розрахунків слід, що в процесі вирішення даного завдання загальна кількість повторень тіла внутрішнього циклу, в тому числі і обчислень за формулою для z, складе n = n * n = 5 * 5 = 25. Тут цілком можна поміняти місцями зовнішній і вкладений цикли , від цього не зміняться ні структура алгоритму, ні необхідний для вирішення обсяг обчислень.
Змінимо частина умови задачі, припустивши, що крок зміни змінної х залишився тим же, а ось y = 0.1. Тоді число повторень циклу по y дорівнюватиме n = (1 + 1) /0.1 + 1 = 21. Якщо цей цикл зробити внутрішнім, то в процесі виконання завдання тіло циклу по у повториться 5
* 21 = 105 раз. Тіло зовнішнього циклу, в яке крім тіла циклу по у входять і інші дії, повториться 5 разів. Таким чином, загальний обсяг обчислень в алгоритмі можна охарактеризувати цифрою n * n + n = 105 + 5 = = 110. Поміняємо тепер цикли по х і по у місцями. Число повторів внутрішнього циклу залишається тим же - 105, а ось загальний обсяг обчислень зміниться, оскільки всі операції зовнішнього циклу повторяться 21 разів, отже, загальний обсяг обчислень в даному випадку пропорційний n * n + n = 105 +
Змінимо ще раз умову задачі. Нехай змінні х і у змінюються як в первинному варіанті, а ось сама функція z
Здавалося б, обсяг обчислень не залежить від того, який цикл є зовнішнім, а який - вкладеним, і пропорційний n * n + n = 25 + 5 = 30. Розглянемо, однак, дві структурограмми алгоритму для випадку, коли цикл по у є зовнішнім :
Якщо алгоритм рішення реалізується по лівій структурограмме, то, в принципі, немає різниці, з якого параметру організовується зовнішній цикл. Все одно обчислення за формулою для z, включаючи експоненту, будуть виконуватися 25 разів. Згідно правому алгоритму, обчислення експоненти винесено у зовнішній цикл і тому виконується тільки 5 разів. Завдання буде вирішена швидше, однак тепер змінні х і у нерівнозначні.
Отже, можна сформулювати такі правила організації вкладених циклів:
1) якщо умови задачі прямо не визначають, з якого параметру організовується зовнішній цикл, а з якого - внутрішній, слід зовнішній цикл формувати по змінної, з якою пов'язані найбільш складні обчислення;
2) за інших рівних умов завдання буде вирішуватися швидше, якщо зовнішній цикл має менше число повторень, ніж окремо взятий внутрішній цикл.
Читати: Анотація
Читати: Введення
Читати: Інформація
Читати: Етапи виконання завдання на ЕОМ
Читати: Засоби запису алгоритмів
Читати: Четвертий етап є завершальним серед тих, які можуть виконуватися без використання ЕОМ.
Читати: Базові алгоритмічні структури
Читати: Основи структурного програмування
Читати: Структурограмми (діаграми Несс-Шнейдермана)
Читати: Модульне програмування
Читати: Про стиль програмування
Читати: Типи даних
Читати: ахітектури компютера
Читати: Комп'ютерні віруси
Читати: Комп'ютер в експерименті
Читати: Моделювання випадковості
| Зміст |