Требования, предъявляемые к алгоритмам



  1. Чисто программное решение
  2. Скорости процессов, число процессоров неизвестны
  3. Условие взаимоисключения
  4. Условие прогресса
  5. Условие ограниченного ожидания

 

14

Наименование Обозначение Функция
Блок начало-конец (пуск-остановка) Элемент отображает вход из внешней среды или выход из неё (наиболее частое применение − начало и конец программы). Внутри фигуры записывается соответствующее действие.
Блок вычислений (вычислительный блок) Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания: a = 10*b + c.
Логический блок (блок условия) Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода:true, false) и case (множество выходов).
Предопределённый процесс Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании − вызов процедуры или функции.
Данные (ввод-вывод) Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).

Схе́ма — графическое представление определения, анализа или метода решения задачи, в котором используются символы для отображения операций, данных, потока, оборудования и т. д.[1]

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

17 Массив (в некоторых языках программирования также таблица, ряд) — набор однотипных компонентов (элементов), расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу (индексам). В отличие от списка, массив является структурой с произвольным доступом[1].

Размерность массива — количество индексов, необходимое для однозначного доступа к элементу массива[2][3].

Форма или структура массива — количество размерностей и размер (протяжённость) массива для каждой размерности[4], может быть представлен одномерным массивом[5].

В языке программирования APL массив является основным типом данных (при этом нуль-мерный массив называется скаляром, одномерный — вектором, двумерный — матрицей)[5].

В ряде языков программирования, например, Лисп, JavaScript, PHP, Ruby применяются также ассоциативные массивы (или хэш-массивы), в которых элементы не обязательно являются однотипными, а доступ к ним не обязательно осуществляется по индексу.

Достоинства

· лёгкость вычисления адреса элемента по его индексу (поскольку элементы массива располагаются один за другим)

· одинаковое время доступа ко всем элементам

· малый размер элементов: они состоят только из информационного поля

[править]Недостатки

· для статического массива — oотсутствие динамики, невозможность удаления или добавления элемента без сдвига других

· для динамического и/или гетерогенного массива — более низкое (по сравнению с обычным статическим) быстродействие и дополнительные накладные расходы на поддержку динамических свойств и/или гетерогенности.

· при работе с массивом в стиле C (с указателями) и при отсутствии дополнительных средств контроля — угроза выхода за границы массива и повреждения данных

Первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых языков программирования, однако этот метод был использован в языках более высокого уровня языком программирования Си.

18 Циклический алгоритм. Работу циклического алгоритма рассмотрим на примере нахождения суммы чётных чисел, находящихся в диапазоне от 0 до n (n вводится с клавиатуры)

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

Подпрограммы могут быть двух видов: подпрограмма без параметров и подпрограмма с параметрами. Обращение к подпрограмме может быть организовано из любого места основной программы или другой подпрограммы сколько угодно раз.

При работе с подпрограммами важными являются понятия формальных и фактических параметров. Формальные параметры — это идентификаторы входных данных для подпрограммы. Если формальные параметры получают конкретные значения, то они называютсяфактическими. Формальные параметры могут получить конкретные значения только в той программе, где производится обращение к данному модулю-подпрограмме. Тип и порядок записи фактических параметров должны быть такими же, как и формальных параметров. В противном случае результат работы программы будет непредсказуемым. Из этого следует, что фактические параметры используются при обращении к подпрограмме из основной, а формальные параметры — только в самом модуле.

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

При составлении подпрограмм с параметрами надо соблюдать следующие правила:

1) каждая подпрограмма имеет свое имя и список формальных параметров;

2) процедура из основной программы вызывается командой вызова, которая по форме ничем не отличается от вызова команды исполнителя. Результат присваивается одной или нескольким переменным, которые находятся в списке формальных параметров. Но результатом могут быть, конечно, не только значения переменных, но какое либо действие, выполненное ЭВМ.

Подпрограмма — это часть всей программы, оформленная особым образом. Как правило, в виде подпрограммы записывается какая-то логически завершённая часть программы. Активное использование подпрограмм при разработке программного обеспечения составляет основу модульного программирования

Преимущества от использования подпрограмм:

1. Возможность создания достаточно больших программ (ограничение — порядка 50000 строк. Разработка программ практически неограниченного размера требует применения классов. Речь о них пойдёт дальше).

2. Достаточно просто повторно использовать ранее написанный код.

3. Разработку отдельных частей программы, т.е. подпрограмм, можно поручить разным людям.

4. Сокращается срок разработки программы в целом за счёт повторного использования кода и благодаря возможности привлечения к программному проекту целой группы программистов.

5. Повышается надёжность программы, потому что подпрограммы, как правило, не велики, их можно досконально изучить, к тому же повторное использование в новых программах подпрограмм, которые уже применялись ранее и не давали «сбоев», повышает надёжность новой программы в целом.

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

Недостатки от применения подпрограмм:

1. Использование подпрограмм всегда уменьшает скорость работы программы. Это становится заметным, когда размер подпрограммы слишком мал, например, один-два оператора.

2. Размер исходного кода и исполняемого модуля не всегда, но часто возрастает при использовании подпрограмм.

3. Грамотное применение подпрограмм требует более высокой квалификации от программиста, чем работа без подпрограмм.

Виды подпрограмм

Существует две категории подпрограмм: процедуры и функции.

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

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

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

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

Общая идея использования подпрограмм очевидна: если в программе требуется многократно выполнять один и тот же фрагмент, его можно оформить в виде подпрограммы и вызвать по мере необходимости. Если подпрограмма не требует для своего выполнения никаких параметров и не должна возвращать в основную программу результат своей работы, то дело ограничивается оформлением текста подпрограммы в виде процедуры, завершающейся командой ret, и вызовом этой процедуры с помощью команды call. Как уже отмечалось ранее, подпрограмма может и не образовывать процедуру, а быть просто частью основной программы. Важно только, чтобы у нее была входная метка, и чтобы она завершалась командой ret.
В следующем примере подпрограмма delay используется для включения в основной текст программы программных задержек фиксированной величины.

21Применяемые в программировании алгоритмические приемы позволяют писать программы, которые работают быстрее и потребляют меньше системных ресурсов. Кроме того, они приучают находить корректные решения рядовых задач.


Дата добавления: 2018-05-02; просмотров: 302; Мы поможем в написании вашей работы!






Мы поможем в написании ваших работ!