double arrow

Лекция 4.. Проектирование алгоритмов и структур данных


Проектирование алгоритмов и структур данных.

Наиболее трудоёмкий этап, в котором документируется алгоритм. При этом алгоритм записывается на одном из языков алгоритмов, либо на языке блок-схем, либо на псевдокоде.

Сравнивая язык блок-схем и псевдокод можно отметить:

1) Блок-схема, как графическое изображение алгоритма более наглядна, но она не содержит описание данных. Поскольку блок-схема двумерна, а программа для ЭВМ линейна, т.е. некоторые сложности перехода от блок-схемы к программам на ЯП;

2) Эти два недостатка не имеют способ описания алгоритмов на псевдокоде, однако запись алгоритмов на псевдокоде представляет собой своеобразный текст, к восприятию которого не готов каждый пользователь. Как и блок-схема, псевдокод непосредственно воспринимается ЭВМ, в силу чего также необходим переход от записей алгоритмов на псевдокоде к программе на ЭВМ.

На этом этапе алгоритм проектируется в соответствии с технологией структурного программирования пошаговыми методами с использованием ограниченного набора базовых управляющих структур (БУС).

Цель структурного программирования – разработка легко понимаемых программ.

Понимаемость программы- возможность судить по тексту программы о производимых её вычислениях.

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

Структурные алгоритмы – это такие алгоритмы, которые строятся с использованием только трёх базовых правил композиции вычислительных действий:

а) последовательные действия => БУС "Следование"

б) альтернативные => БУС "Ветвление"

в) повторение => БУС "Цикл"

Важно:

Каждая БУС должна быть технологична, т.е. должна соответствовать принципу – «один вход – один выход». Вход любой БУС может соединяться только с выходом одной – другой БУС. А выход БУС может соединяться либо с входом, либо с выходом другой БУС.

БУС алгоритмов (программ)

① БУС "Следование"

↓вход

↓конец

② БУС "Ветвление"

↓вход

_____ _____

| |

↓ ↓

|___________ ___________|

↓выход

Альтернативные действия одновременно не выполняются.

Допускается использовать производную от этой БУС – БУС "Полу-ветвление"

↓вход

_________ __________

↓ |

|

|

|_______________ ________________

↓выход

③ БУС "Цикл"

В качестве базовой циклической структуры использовался БУС "Цикл-ПОКА"

I. Подготовка к первому выполнению

II. Тело цикла

III. Подготовка ко второму выполнению

IV. Управление циклом

-------→ --------

↑ ↓ |

| |

| ↓ |

| |

| ↓ |

| |

| ________ ↓ |

____________|

↓выход

Такая БУС предназначена для представления итерационных вычислений, для которых число повторения цикла и число параметров, а, следовательно, заранее неизвестны и не могут быть установлены (вычислены) до начала выполнения цикла.

Тело такого цикла будет выполняться пока истинно условие цикла.

Условие такого цикла определяется либо самой задачей, либо методом е решения, но оно не содержит в своей записи имени параметра цикла.

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

Если условие цикла сразу же будет ложным, то тело цикла не будет выполнено ни разу.

Разрешено использование дополнительных БУС циклов:

БУС "Цикл-ДО".

Такая БУС также предназначена для представления итерационных вычислений.

↓вход

I

-------------→↓

| II

|

| III

|

-------- IV

↓выход

Тело такого цикла повторно выполняется до того момента, когда условие цикла получит значение истина. Не содержит имени параметра цикла и записывается в соответствии с задачей или методом её решения. Для такого цикла тело цикла всегда выполняется по крайней мере один раз, т.к. условие цикла проверяется после выполнения тела цикла.

БУС "Цикл, управляемый параметром" (БУС "ЦУП") является частным случаем цикла ДО, поэтому имеет структуру, идентичную циклу ДО. Применяется в тех случаях, когда известно число повторения цикла => конечное значение параметра цикла заранее известны и легко устанавливаются (вычисляются) до начала выполнения цикла. Управление таким циклом организуется путём контроля текущего состояния цикла. Но после выхода из такого цикла (по условию цикла) значение параметра цикла становится неопределённым, т.е. теряется. Из такого набора БУС (3 основные + 3 дополнительные) можно проектировать алгоритм любой сложности. Типовой сложной структурой является кратный цикл.

Кратный цикл – это такой цикл (внешний), в теле которого (и только там!) содержится другой цикл (внутренний). Тот в свою очередь может содержать в себе (в своём теле цикла) другой (другие) вложенный цикл(-ы). Кратность кратного цикла определяется (измеряется) числом вложенных друг в друга циклов.

Покажем типовую структуру кратного цикла (кратность 2) для двух циклов, управляемых параметром (двух циклов ДО).

Внешний цикл – ВНШ;

Внутренний цикл – ВНТР.

↓вход

------------------------↓

-----------------↓-----------------

| | |

| ↓ |

| |

| ↓ |

| |

| ↓ |

| |

-----------------↓-----------------

Нет

↓да

выход


Сейчас читают про: