ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.06.2024
Просмотров: 114
Скачиваний: 1
I
Если обрабатывается я строк каждого наряда, то процесс полу чения ВНД ЗП Д можно представить как
в н д = 2 ^ х ^ ; -
п |
|
i=i |
|
где k — количество деталеопераций; |
1 |
t-—норма времени; |
|
р — расценка; ,
. п — количество строк в одном документе; i — номер строки в одном документе.
Логика решения задачи сводится к последовательному получе нию времени нормированного (ВН) и заработной платы (ЗП) по каждой строке. Для упрощения расчета принимаем, что количест во заполненных строк в каждом документе (п) равно пяти. Затем ВН и ЗП по пяти строкам каждого документа суммируются с полу чением соответственно ВНД и ЗПД .
Результатная информация выводится в виде следующих сооб щений:
|
Номер до кумента |
Цех |
Участок , |
Заказ |
Табельный номер |
Вид опла ты |
'Время нормиро |
Заработная |
ванное по |
плата по |
документу |
документу |
Блок-схема решения данной задачи представлена |
на рис. 7, где |
обозначения имеют следующие значения: |
|
j — порядковый номер наряда (всего их 100); |
- |
k — номер строки в наряде; |
|
п — количество строк в наряде. |
|
Приведенный пример позволяет сформулировать выводы о неко торых основных достоинствах и недостатках блок-схемного метода алгоритмизации.
Блок-схема является формой представления алгоритма решения задачи в общем виде. Преимущества его сводятся к следующему:
1. Обеспечивается обмен методами решения между специалис тами, использующими различные машины.
2. Облегчается работа по составлению машинной программы, так как заранее составлено укрупненное описание всего процесса решения задачи.
3. Создается возможность отдельно программировать каждый блок, а программу решения всей задачи получать путем объедине
ния таких программ. |
|
4. Облегчается чтение и понимание программ. |
\ |
61
5.Уменьшается количество ошибок при программировании.
6.Упрощается проверка и отладка готовых программ. Недостатки этого метода связаны прежде всего с невозможно
стью использовать его при автоматизации программирования, так как для^более сложных задач словесное описание блок-схем оказы вается громоздким для ввода в машину.
(ввод раЪочих\
|
1 норидо8 |
) |
|
°К*1 |
|
|
|
|
|
||
|
1 |
|
Подсчет дремени |
||
|
о н |
нормированного |
|||
|
|
||||
|
|
|
по |
документу |
|
|
|
|
|
— ^ |
1 |
|
< |
|
Подсчет заро5от-\ |
||
|
|
ной |
платы |
по |
|
©ч К: = ! |
|
||||
|
документу |
|
|||
о н |
Умножение |
но |
|
|
|
количества |
|
|
|
||
норму времени |
|
|
|
||
Умножение количество на расценку
Рис. 7
Другой серьезный недостаток состоит в том, что при составле нии блок-схемы не устанавливается определенная степень детали зации, .которая впоследствии необходима при разработке програм мы. Причем четкость и полнота описания отдельных блоков зачас тую зависят от квалификации составителей. И получается, что не которые блоки описаны с излишней подробностью, а другие — в об щих чертах.
Эти недостатки приводят к большим трудностям при переводе блок-схемы в рабочую программу машины и не, позволяют сформу лировать четкие правила такого перевода, которые необходимы при автоматизации программирования.
62-
Таким образом, из изложенного выше следует общий вывод о том, что блок-схемный метод алгоритмизации может быть рекомен дован при ручном методе программирования как этап, облегчаю щий составление рабочей программы.
Кроме того, блок-схемным методом удобно пользоваться при со ставлении сложных алгоритмов, в качестве предварительной про варки и наглядного представления логики решения задачи.
Если абстрактные алгоритмические системы служат для реше ния таких проблем, как алгоритмическая разрешимость или нераз-> решимость задач, то остальные системы используются практически для записи реальных алгоритмов. Они служат тем аппаратом, ко торый используется для формализации алгоритмов (записи в фор мулах и терминах той или иной алгоритмической системы).
Однако в связи с возникновением ЭВМ эти алгоритмические сис темы оказались не совсем удобными, так как для решения задач, представленных аппаратом той или иной алгоритмической системы на ЭВМ, необходимо алгоритмы перевести в команды конкретной машины. Этот перевод выполнялся вручную и требовал много тру да и времени.
Для ускорения процесса перевода алгоритмов задач с языка ал горитмической системы в язык машиныбыли разработаны специ альные алгоритмические системы, получившие название алгоритми ческие языки. •
Строгая формализация и однозначность описания алгоритмов в алгоритмическом языке позволила переложить на машину и сам перевод с алгоязыка на язык машины, т. е. автоматизировать про цесс подготовки задач для выполнения их на ЭВМ, автоматизиро вать программирование. Для этого необходимо снабдить машину так называемой «программирующей программой» — транслятором, которая, анализируя описание, сделанное на алгоритмическом язы ке, перерабатывает его в программу, состоящую только из машин ных команд.
В настоящее время разработано и используется более 700/раз личных алгоритмических языков. Наиболее распространенные из них АЛГОЛ, КОБОЛ, ФОРТРАН. У нас в СССР разработаны АЛГЭК, АЛГЭМ, АЛМО и др.
Детальным изучением алгоязыков занимается курс «Алгоритми ческие языки». В данном курсе изучаются общие принципы построе ния таких языков — формальная грамматика.
Упражнения:
Воператорной системе Ляпунова
1.Составить алгоритм вычисления по формуле
Ci = ai —
2. Составить алгоритм вычисления по формуле
ck= |
— М 1 < ' < 1 , 1 < * < т ) . |
|
2 = 1 |
v 6 3
3. Составить алгоритм вычисления по формуле ct =at X bt{\<i<n).
4. доставить алгоритм вычисления по формуле
т
5. Составить алгоритм вычисления по формуле
п
Пс, = а, : Ь;.
6.Составить алгоритм определения количества одинаковых чи-
еел в последовательности а{, аг, ..., ап.
7.Составить алгоритм умножения матрицы на матрицу.
8.Составить блок-схему алгоритма поразрядного сложения двух чисел-произвольной разрядности.
9.Составить блок-схему алгоритма поразрядного умножения двух чисел произвольной разрядности.
10. Составить блок-схему алгоритма упорядочения массива из п чисел в порядке возрастания элементов.
11.Составить блок-схему алгоритма поиска минимального-эле мента из массива п чисел.
12.Составить блок-схему алгоритма умножения матрицы на вектор.
13.Составить блок-схему алгоритма умножения матрицы на матрицу.
14.Составить блок-схему алгоритма транспонирования матрицы.
15.Составить блок-схему алгоритма поиска минимального (мак симального) элемента матрицы.
16.Составить блок-схему алгоритма определения количества по ложительных (отрицательных) элементов матрицы.
17.Составить блок-схеТЙу алгоритма вычислений по формуле
т |
|
|
ck= П |
fljXMKK". |
1 < & < т ) . |
18. Составить блок-схему алгоритма вычислений по формуле
c f t = 2 а < - М 1 < * < в ) . |
' |
1.6. Методы оценки алгоритмов
В теории алгоритмов понятие «алгоритм» обычно уточняется посредством описания «математической модели» вычислительной машины. Здесь возможны два подхода в зависимости от того, оце нивается ли сложность алгоритма (машины, программы) или спо собность вычислительного процесса, протекающего в соответствии с алгоритмом.
В качестве меры сложности алгоритмов рассматривается функ ционал, соотносящий каждому алгоритму Л некоторое число ц(Л), характеризующее (в Подходящем смысле) его громоздкость, на пример: число команд в А , длина записи А , или какой-нибудь дру гой числовой параметр, характеризующий объем информации, со
держащийся в А . Подобные функционалы уже давно |
применяются |
в теоретико-кибернетических исследованиях схем, |
реализующих |
функции алгебры логики (Шеннон, Яблонский, Ляпунов и Др.), а также в вычислительной математике, где мощность схемы, по ко торой вычисляется многочлен, измеряется числом арифметических операций, фигурирующих в схеме. Различие заключается лишь в том, что в указанных работах рассматриваются специальные уз кие классы функций и специальные способы описания алгоритмов. Мы же заинтересованы в разработке и применении аналогичных понятий в более общей ситуации (любые вычислимые функции, об щие концепции алгоритма). Первые публикации, в которых такие меры сложности нашли применения, принадлежат А. А. Маркову и
А.Н. Колмогорову.
Вкачестве меры сложности вычислений рассматривается функ ционал, соотносящий каждой паре (А, а ) , где А — алгоритм, а — индивидуальная задача из того класса задач, которые алгоритм А решает, некоторое число о (А, а ) . Это число характеризует слож
ность работы алгоритма А применительно |
к исходным |
данным а |
|
до выдачи соответствующего |
результата. |
Например, |
в качестве |
о (Л, а) можно брать число элементарных |
шагов, из которых скла |
||
дывается эта работа (иначе |
говоря, длительность процесса вычис |
||
ления) или объем памяти, который может понадобиться для реали
зации всех выкладок по ходу данного процесса, и т. д. |
Поскольку |
||||
для каждого алгоритма Л однозначно определен тот класс задач Q, |
|||||
который |
он |
решает (например, та функция f, значение |
которой он |
||
вычисляет), |
то можно |
считать, что в |
рассматриваемой ситуации |
||
каждый |
алгоритм Л |
характеризуется |
функцией |
переменного |
|
а ад (а) |
= а(Л, а) . Иными словами, мерой сложности работы алго- |
||||
|
df |
|
|
1 |
|
ритма (вычисления) является оператор, сопоставляющий с каждым алгоритмом Л соответствующую функцию ал (а).
Такой подход к оценке сложности вычислений содержался в ра боте советского математика Г. С. Цейтина, сделанной им в 1959 г., в которой сложность работы нормального алгоритма измерялась функцией, указывающей зависимость числа шагов алгоритма от слова, к которому он применяется. Примерно в то же время и неза висимо от Г. С. Цейтина Б. А. Трахтенброт ввел аналогичные функ ции, измеряющие объем памяти, необходимой для рекурсивных вы числений, и назвал их сигнализирующими функциями.
Определяя некоторую меру сложности для алгоритмов (или вы числений), мы тем самым надеемся получить удобный инструмент* для сравнения алгоритмов, а также для оценки объективной труд ности, присущей различным вычислимым функциям. В связи с этим можно отметить различие в осуществлении такого замысла в завиг
5-1861 |
65 |