Разработка алгоритмов нисходящим способом

Нисходящее проектирование алгоритмов

Нисходящим проектированием алгоритмов, проектированием алгоритмов «сверху вниз» или методом последовательной (пошаговой) нисходящей разработки алгоритмов называется такой метод составления алгоритмов, когда исходная задача (алгоритм) разбивается на ряд вспомогательных подзадач (подалгоритмов), формулируемых и решаемых в терминах более простых и элементарных операций (процедур). Последние, в свою очередь, вновь разбиваются на более простые и элементарные, и так до тех пор, пока не дойдём до команд исполнителя. В терминах этих команд можно представить и выполнить полученные на последнем шаге разбиений подалгоритмы (команд системы команд исполнителя).

В рамках структурного программирования применяются две стратегии: «нисходящая» и «восходящая».

При использовании метода восходящего проектирования приложение собирается из компонентов или блоков.

Метод нисходящего проектирования.

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

Предположим, что требуется разработать алгоритм для некоторой конкретной функции 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, если до конца файла остались строки, заполненные пробелами.

Источник

Начало разработки алгоритма

В основе разработки алгоритма исходной задачи лежит следующая аксиома.

Аксиома о возможности построения алгоритма решения исходной задачи, она требует:

1. задача может быть решена только в рамках формальной логики, поэтому текст задачи, для которой строится алгоритм, должен быть полным и допускать только однозначную трактовку, то есть задача должна быть формализована;
2. каждый шаг построенного алгоритма должен быть однозначно понят исполнителем алгоритма,
3. разрабатываемый алгоритм должен использовать только систему команд исполнителя, то есть каждый шаг алгоритма для исполнителя должен быть не только понятен, но и выполнимым;
4. разработанный алгоритм должен быть. конечным.

При невыполнении любого из этих требований алгоритм решения задачи построить невозможно.

Алгоритм решения задачи

Одним из основных алгоритмов является алгоритм решения задачи. В настоящее время существует множество всевозможных его вариантов. Авторы предлагают следующий алгоритм решения (любой решаемой) задачи, запишем его в виде сценария с детализацией:

Начало алгоритма

1. Постановка задачи:

• анализ текста исходной задачи,
• построение модели исследуемого объекта (или процесса) в рамках формальной логики и соответствующих естественно – научных представлений;
• формализация текста задачи;

2. Построение алгоритма (для формализованной задачи):

• разработка алгоритма,
• его представление,
• тестирование алгоритма;

Реализация алгоритма:

• выбор среды реализации, разработка реализации в выбранной среде с учетом ее возможностей, реализация алгоритма,
• тестирование реализации,
• получение результата, его анализ,
• если необходимо, модификация с возвратом на п.1 или п.2,

Составление документации (если есть необходимость).

Рассмотрим в качестве примера постановки задачи следующую задачу.

Задача.
Имеется шляпа, галоши, трансформатор, секундомер. Определить высоту здания.

1.

Шляпа, галоши, трансформатор, секундомер – наличие этих предметов подсказывает о возможности решения данной задачи с точки зрения физики, точнее исследуя движение тела в поле тяготения. В этом случае важнейшей характеристикой предмета для нас будет парусность предмета, с которой связана сила сопротивления воздуха, а, следовательно, точность определения высоты здания.

2.

Для определения высоты данного здания можно предложить следующий эксперимент: определить время свободного падения предмета с нулевой начальной скоростью. В качестве предмета необходимо использовать трансформатор, имеющий наименьшую парусность на единицу массы из всех предложенных предметов (секундомер не в счет, так как ему хватит одного падения, чтобы он перестал работать). По полученному времени, используя закон всемирного тяготения, определить высоту здания.

3.

С крыши здания свободно падает трансформатор. Время его падения определяем секундомером. Используя закономерности свободного падения тела в гравитационном поле, определить высоту здания.

Формулировка данной задачи существенно отличается от формулировки исходной, но с ее помощью мы сможем решить исходную задачу.

Далее для формализованной задачи можно разрабатывать алгоритм решения.

Рассмотренный алгоритм – это первое приближение решения исходной задачи. Здесь важно понять, что для решения поставленной задачи необходима детальная проработка первого шага алгоритма, то есть постановки задачи. По исходной задаче необходимо получить формализованную задачу, которая и будет решаться.

Рассмотрим возможности построения алгоритма формализованной задачи.

Принцип нисходящего проектирования алгоритма

Для дальнейшей разработки решения задачи можно воспользоваться основным инструментом построения алгоритма – это принципом нисходящего проектирования алгоритма.

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

И объясняется, что данная задача разбивается на несколько подзадач, каждая из которых решает свою часть поставленной задачи. Это первый уровень детализации поставленной задачи. При необходимости одну или несколько подзадач первого уровня детализации разбивают (каждую) на несколько подзадач, образуя второй уровень детализации и т.д. Принцип нисходящего проектирования алгоритма реализуется, как принцип декомпозиции структур. Все это можно найти в любом учебнике по началам алгоритмики и программирования.

Основным следствием принципа нисходящего проектирования алгоритма (по мнению авторов) является следующее утверждение, относящееся к самому первому уровню детализации алгоритма:

Следствие. Для любого исполнителя, любая решаемая задача может быть разбита на три подзадачи:

• ввод (исходной) информации,
• обработка информации,
• вывод результатов.

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

Подобное разбиение мы видим при решении задач физики, математики, химии и т. д. (дано…решение [в буквенном виде…числовое решение]…ответ) названия разные – суть одна.

Это определяется тем, что исходные данные вводятся извне. Данным исполнителем проводится обработка информации. Результат обработки выводится на внешние носители информации. Наиболее четко это видно на вычислительных задачах.

Таким образом, самый верхний уровень необходимо рассматривать как один неделимый блок – формулировка исходной (формализованной) задачи. Далее самый первый уровень детализации необходимо представляется тремя подзадачами. Назовем это ТРИЕДИНОЙ ЗАДАЧЕЙ АЛГОРИТМИКИ. Она едина потому, что каждая из подзадач отдельно от остальных не имеет смысла. И это три задачи, так как каждая из них достаточно замкнута, имеет свои особенности и, поэтому, может разрабатываться отдельно от остальных. А так как задач ВводаИнформации и ВыводаРезультатов ограниченное количество и они решаются отдельно, то далее принцип нисходящего проектирования алгоритма применяется только к задаче ОбработкиИнформации.

Триединая задача алгоритмики

Сформулируем понятие триединой задачи алгоритмики в следующем определении.

Опр. ТРИЕДИНОЙ ЗАДАЧЕЙ АЛГОРИТМИКИ называется совокупность подзадач первого уровня детализации исходной формализованной задачи:

• ВводИнформации,
• ОбработкаИнформации,
• ВыводРезультатов.

Каждую из этих задач можно рассматривать в данном алгоритме как вспомогательный алгоритм. В приложениях №№ 1, 2 (Приложение 1, Приложение 2) рассмотрены задачи Ввода/Вывода для простой переменной. Важно отметить, что разработку алгоритма любой решаемой задачи не только можно, а чаще и необходимо, начинать с триединой задачи алгоритмики.

В дальнейшем геометрическое представление триединой задачи удобно делать в виде:

Над стрелкой задаются имена переменных и их типы, под стрелкой ограничения на эти переменные в заданной задаче; как уже говорилось, стрелки суть входной и выходной потоки, прямоугольник – блок обработки информации.

Важно уяснить, что триединая задача алгоритмики есть не что иное, как алгоритм решения задачи на первом уровне. Действительно, в виде сценария этот алгоритм можно представить в виде:

НАЧАЛО_АЛГОРИТМА

1. ВводИнформации( ).
2. ОбработкаИнформации( ; ).
3. ВыводРезультатов( ).

Для самостоятельной работы ученикам можно предложить любые (по сложности), но формализованные задачи. Основное задание – сформулировать триединую задачу для исходной задачи, то есть выделить и сформулировать задачи: ввода информации, вывода результатов и сформулировать задачу обработки информации. В Приложении 3 приведен пример решения подобных задач.

Обобщая изложенное, можно утверждать, что…

В основе разработки алгоритма исходной задачи лежит следующая аксиома.

Аксиома о возможности построения алгоритма решения исходной задачи требует:

1. задача может быть решена только в рамках формальной логики, поэтому текст задачи, для которой строится алгоритм, должен быть полным и допускать только однозначную трактовку, то есть задача должна быть формализована;
2. каждый шаг построенного алгоритма должен быть однозначно понят исполнителем алгоритма,
3. разрабатываемый алгоритм должен использовать только систему команд исполнителя, то есть каждый шаг алгоритма для исполнителя должен быть не только понятен, но и выполнимым;
4. разработанный алгоритм должен быть . конечным.

Авторы предлагают следующий алгоритм решения (любой решаемой) задачи:

НАЧАЛО АЛГОРИТМА

1. Постановка задачи:
2. Построение алгоритма (по формализованной задаче):
3. Реализация алогоритма.
4. Составление документации (если есть необходимость).

Первым шагом в построении алгоритма является, согласно принципа нисходящего проектирования алгоритма, ТРИЕДИНАЯ ЗАДАЧА АЛГОРИТМИКИ – это алгоритм решения формализоанной задачи. Он представляет исходную формализованную задачу как совокупность трех подзадач (вспомогательных алгоритмов):

НАЧАЛО АЛГОРИТМА

• ВводИнформации,
• ОбработкаИнформации,
• ВыводРезультатов.

При этом задачи ВводаИнформации и ВыводаРезультатом можно и нужно решать самостоятельно.

В заключении отметим, что данный материал нужно использовать в 10–11-х классах. Для его проработки с учениками требуется не менее 1часа.

Источник