Нисходящее проектирование алгоритмов
Нисходящим проектированием алгоритмов, проектированием алгоритмов «сверху вниз» или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
В рамках структурного программирования применяются две стратегии: «нисходящая» и «восходящая».
При использовании метода восходящего проектирования приложение собирается из компонентов или блоков.
Метод нисходящего проектирования.
Нисходящее программирование — это процесс пошагового разбиения алгоритма на всё более мелкие части, с целью получить такие элементы, для которых можно легко написать конкретные команды. Структурное нисходящее программирования — процесс программирования сверху вниз, ограниченный использования структурных блок — схем.
Предположим, что требуется разработать алгоритм для некоторой конкретной функции f. Пускай можно доказать, что f — есть композиция двух других, более простых функций, g и h. Тогда проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для g и h. Пускай функция g равна некоторой функции i , когда заданный параметр х неотрицателен, или равна некоторой другой функции j, когда х отрицателен, то есть g (x)=i, x>=0 и g (x)=j, x
Если выполнилась операция записи в n-ю компоненту файла, то указатель автоматически продвигается к (n+1)-й компоненте, то есть для записи становится доступной уже только (n+1)-я компонента.
Длиной файла называется число записанных компонент. Файл, не содержащий компонент, называется пустым, его длина равна нулю. Читать файл можно также только последовательно по одной компоненте.
Для того, чтобы определять готовность файла к чтению либо к записи информации , существует стандартная функция EOF(F), где F-имя файла. Если указатель файла продвинулся за конец файла (готовность к записи), то эта функция принимает значение TRUE, во всех остальных случаях значение FALSE.
Общий вид описания типа FILE:
TYPE R = FILE OF TC;
Здесь R — идентификатор типа, TC — тип компонент (может быть любым, кроме типа FILE).
Файлы могут быть разных типов: состоять из целых компонент, либо вещественных, либо записей и т.д. Как и другие переменные, каждую переменную-файл надо описать в разделе VAR. Вводя имя переменной файла (имя файла), надо указать, какого типа файл. Этот тип должен быть обозначен каким-либо именем и описан в разделе TYPE.
Например, файл F вещественных чисел:
TYPE N = FILE OF REAL;
VAR F:N;(*описание переменной файла*)
Файл может быть описан и непосредственно при описании переменной, например:
VAR F:FILE OF REAL;
В первом случае введено имя файла F и соответствующий тип обозначен N; во втором введено имя файла F, а его тип имени не имеет и поэтому в разделе TYPE не описывается.
Возможно описание переменной без указания типа компонент:
Замечение редактора: в этом случае файл называется нетипизированным. Для работы с такими файлами используются отличные от указанных ниже процедуры и функции.
Для того, чтобы ассоциировать переменную F с именем файла, с которым будем работать, в паскале используется функция Assign.
Общий вид функции:
Здесь F — имя переменной типа FILE с которой теперь связан файл My_file.alr. Далее в программе, когда мы будем обращаться к переменной F, например записывать данные , то мы будем работать с файлом My_file.alr. Вместе с файлом может указываться и путь.
1. Открытие, чтение и запись в файл.
RESET открывает только уже существующие файлы на чтение и запись.
RESET (F); (* Считается, что файл My_file.alr существует *)
TYPE NF:FILE OF INTEGER;
WHILE NOT EOF(F) DO
2. Процедура REWRITE.
REWRITE открывает существующий файл на перезапись т.е. с потерей всей предыдущей хранящейся в нем информации, или если файла не существует, то создает новый файл с тем именем, с которым ассоциирована файловая переменная.
Пример. Надо создать файл для записи массива целых чисел.
VAR F:FILE OF INTEGER;I:INTEGER;
FOR I:=1 TO 100 WRITELN(F,SQR(I));
Ввод и вывод осуществляется с помощью процедур READ и WRITE
Общий вид: READ(F,P1,P2,P3. PN);
P1,P2,P3. PN — Переменные в которые считываются значения из файла.
T1,T2,T3. TN — Переменные, значения которых запишутся в файл.
3. После использования процедур RESET и REWRITE файл НЕОБХОДИМО закрыть. Это делается с помощью процедуры CLOSE.
VAR F:FILE OF INTEGER;U: STRING;
WRITELN (‘Содержание файла Autoexec.bat’)
WHILE NOT EOF(F) DO
Текстовые файлы
Особое место в языке ПАСКАЛЬ занимают текстовые файлы, компоненты которых имеют символьный тип. Для описания текстовых файлов в языке определен стандартный тип Тext:
var TF1, TF2: Text;
Текстовые файлы представляют собой последовательность строк, а строки — последовательность символов. Строки имеют переменную длину, каждая строка завершается признаком конца строки.
С признаком конца строки связана функция EOLn(var T:Text):Boolean,
где Т — имя текстового файла. Эта функция принимает значение TRUE, если достигнут конец строки, и значение FALSE, если конец строки не достигнут. Для операций над текстовыми файлами, кроме перечисленных, опредtлены также операторы обращения к процедурам:
ReadLn(T) — пропускает строку до начала следующей;
WriteLn(T) — завершает строку файла, в которую производится запись, признаком конца строки и переходит к началу следующей. Для работы с текстовыми файлами введена расширенная форма операторов ввода и вывода. Оператор
Read(T,X1,X2. XK) эквивалентен группе операторов
Здесь Т — текстовый файл, а переменные Х1, Х2. ХК могут быть либо переменными целого, действительного или символьного типа, либо строкой. При чтении значений переменных из файла они преобразуются из текстового представления в машинное.
Оператор Write(T,X1,X2. XK) эквивалентен группе операторов
Здесь Т — также текстовый файл, но переменные Х1,Х2. ХК могут быть целого, действительного, символьного, логического типа или строкой. При записи значений переменных в файл они преобразуются из внутреннего представления в текстовый.
К текстовым файлам относятся стандартные файлы INPUT, OUTPUT.
Рассмотренные ранее операторы ввода — вывода являются частным случаем операторов обмена с текстовыми файлами, когда используются стандартные файлы ввода — вывода INPUT, OUTPUT.
Работа с этими файлами имеет особенности:
-имена этих файлов в списках ввода — вывода не указываются;
-применение процедур Reset, Rewrite и Close к стандартным файлам ввода — вывода запрещено;
-для работы с файлами INPUT, OUTPUT введена разновидность функции EOLn без параметров.
TURBO PASCAL вводит дополнительные процедуры и функции, применимые только к текстовым файлам, это SetTextBuf, Append, Flush, SeekEOLn, SeekEOF.
Процедура SetTextBuf( var f: Text; var Buf; BufSize: Word ) служит для увеличения или уменьшения буфера ввода — вывода текстового файла f. Значение размера буфера для текстовых файлов по умолчанию равно 128 байтам. Увеличение размера буфера сокращает количество обращений к диску. Рекомендуется изменять разиер буфера до открытия файла. Буфер файла начнется с первого байта переменной Buf. Размер буфера задается в необязательном параметре BufSize, а если этот параметр отсутствует, размер буфера определяется длиной переменной Buf.
Процедура Append( var f: Text ) служит для специального открытия выходных файлов. Она применима к уже существующим физическим файлам и открывает из для дозаписи в конец файла.
Процедура Flush( var f: Text ) применяется к открытым выходным файлам. Она принудительно записывает данные из буфера в файл независимо от степени его заполнения.
Функция SeekEOLn( var f: Text ): Boolean возвращает значение True, если до конца строки остались только пробелы. Функция SeekEOF( var f: Text ): Boolean возвращает значение True, если до конца файла остались строки, заполненные пробелами.
Источник
Методы разработки и анализа алгоритмов
Нисходящим проектированием алгоритмов, проектированием алгоритмов «сверху вниз» или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача ( алгоритм ) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь , вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).
Восходящий метод, наоборот, опираясь на некоторый, заранее определяемый корректный набор подалгоритмов, строит функционально завершенные подзадачи более общего назначения, от них переходит к более общим, и так далее, до тех пор, пока не дойдем до уровня, на котором можно записать решение поставленной задачи. Этот метод известен как метод проектирования «снизу вверх».
Структурные принципы алгоритмизации ( структурные методы алгоритмизации) – это принципы формирования алгоритмов из базовых структурных алгоритмических единиц (следование, ветвление , повторение), используя их последовательное соединение или вложение друг в друга с соблюдением определённых правил, гарантирующих читабельность и исполняемость алгоритма сверху вниз и последовательно.
Структурированный алгоритм – это алгоритм , представленный как следования и вложения базовых алгоритмических структур . У структурированного алгоритма статическое состояние (до актуализации алгоритма) и динамическое состояние (после актуализации) имеют одинаковую логическую структуру, которая прослеживается сверху вниз («как читается, так и исполняется»). При структурированной разработке алгоритмов правильность алгоритма можно проследить на каждом этапе его построения и выполнения.
Теорема (о структурировании). Любой алгоритм может быть эквивалентно представлен структурированным алгоритмом, состоящим из базовых алгоритмических структур .
Одним из широко используемых методов проектирования и разработки алгоритмов (программ) является модульный метод (модульная технология).
Модуль – это некоторый алгоритм или некоторый его блок, имеющий конкретное наименование, по которому его можно выделить и актуализировать. Иногда модуль называется вспомогательным алгоритмом, хотя все алгоритмы носят вспомогательный характер. Это название имеет смысл, когда рассматривается динамическое состояние алгоритма; в этом случае можно назвать вспомогательным любой алгоритм , используемый данным в качестве блока (составной части) тела этого динамического алгоритма. Используют и другое название модуля – подалгоритм. В программировании используются синонимы – процедура, подпрограмма .
- функциональная целостность и завершенность (каждый модуль реализует одну функцию, но реализует хорошо и полностью);
- автономность и независимость от других модулей (независимость работы модуля-преемника от работы модуля-предшественника; при этом их связь осуществляется только на уровне передачи/приема параметров и управления);
- эволюционируемость (развиваемость);
- открытость для пользователей и разработчиков (для модернизации и использования);
- корректность и надежность;
- ссылка на тело модуля происходит только по имени модуля, то есть вызов и актуализация модуля возможны только через его заголовок.
Свойства (преимущества) модульного проектирования алгоритмов:
- возможность разработки алгоритма большого объема (алгоритмического комплекса) различными исполнителями;
- возможность создания и ведения библиотеки наиболее часто используемых алгоритмов (подалгоритмов);
- облегчение тестирования алгоритмов и обоснования их правильности ;
- упрощение проектирования и модификации алгоритмов ;
- уменьшение сложности разработки ( проектирования ) алгоритмов (или комплексов алгоритмов);
- наблюдаемость вычислительного процесса при реализации алгоритмов.
Тестирование алгоритма – это проверка правильности или неправильности работы алгоритма на специально заданных тестах или тестовых примерах – задачах с известными входными данными и результатами (иногда достаточны их приближения). Тестовый набор должен быть минимальным и полным, то есть обеспечивающим проверку каждого отдельного типа наборов входных данных, особенно исключительных случаев.
Пример. Для задачи решения квадратного уравнения ax 2 + bx + c = 0 такими исключительными случаями, например, будут: 1) a = b = c = 0; 2) a = 0, b, c – отличны от нуля; 3) D = b 2 – 4ac и др.
Тестирование алгоритма не может дать полной (100%-ой) гарантии правильности алгоритма для всех возможных наборов входных данных, особенно для достаточно сложных алгоритмов.
Полную гарантию правильности алгоритма может дать описание работы и результатов алгоритма с помощью системы аксиом и правил вывода или верификация алгоритма.
Пример. Составим алгоритм нахождения числа всех различных двоичных сообщений (двоичных последовательностей) длины n битов, используя при этом не более одной операции умножения, и докажем правильность этого алгоритма. Вначале найдем число всех таких сообщений. Число двоичных сообщений длины 1 равно 2 = 2 1 (это «0» и «1»), длины 2 равно 4 = 2 2 («00», «01», «10», «11»). Отправляясь от этих частных фактов, методом математической индукции докажем, что число различных сообщений длины n равно 2 n . Этот индуктивный вывод докажет правильность алгоритма.
Пусть это наше утверждение верно для n = k . Тогда для n = k + 1 получаем, что добавление каждого бита (0 или 1) к любому из 2 k сообщений длины k приведет к увеличению числа сообщений в 2 раза, то есть их число будет равно 2 x 2 k = 2 k+1 , что и доказывает наше индуктивное предположение.
Составим теперь алгоритм вычисления числа x = 2 n с использованием операции умножения только один раз.
Прологарифмируем последнее равенство . Получим ln(x) = ln(2 n ) = n ln(2) .
Используя равенство exp(ln(x)) = x , получим, что exp(ln(x)) = x = exp(n ln(2)) .
Остается теперь записать простейший алгоритм вычисления числа x .
Для несложных алгоритмов грамотный подбор тестов и полное тестирование может дать полную картину работоспособности (неработоспособности).
Источник
