Словесная форма записи алгоритмов

Министерство образования и науки, молодежи и спорта Украины

Приазовский государственный технический университет

Кафедра металлургии и технологии сварочного производства 

                                                              

 

 

                                                    Составитель: Алистратов В. Н.

 

 

Конспект лекций

по дисциплине «Алгоритмизация и компьютеризация технических задач»                                                

галузь знань: 0505 – Машинобудування та матеріалообробка,

напрям підготовки: 6.050504– зварювання,

ОКР «бакалавр»

 

 

 

 

 

  

 

Мариуполь, ПГТУ- 2012 .

 

                                                          

                                                             СОДЕРЖАНИЕ

 

 

Введение                                                                                              3

1. Основные принципы разработки алгоритмов и программ.

1.1 Этапы решения задачи на ЭВМ.                                              4                                1.2. Виды записи алгоритмов.                                                             6

1.3. Псевдокод.                                                                                           7

1.4. Схемы алгоритмов.                                                                                     8

1.5 Структурное программирование.                                                            12

1.6 Структурограммы.                                                                         15                                                                   2. Общие сведения о MS Excel.                             

3. Нахождение значений функции с помощью MS Excel.                         17

3. Построение диаграмм в среде MS Excel.                                                     

4. Нахождение уравнения регрессии с помощью MS Excel.                      19

5. Решение оптимизационных задач с помощью MS Excel.

5.1 Общие сведения о оптимизационных задачах                                  

5.2 Постановка транспортной задачи                                                  

5.3 Средство “Поиск решения” для решения оптимизационных задач  

5.4 Решение оптимизационной задачи

Рекомендуемая литература                                                                  20

Контрольные вопросы выносимые на зачет                                       21

 

 

ВВЕДЕНИЕ

 Внедрение и широкое использование средств вычислительной техники является одним из главных факторов ускорения научно-технического прогресса в нашей стране. Стремительно возрастает роль ЭВМ во всех областях человеческой деятельности. Без использования быстродействующих ЭВМ немыслимо решение задач интенсификации экономического развития ведущих отраслей народного хозяйства.                                                                                                                                                   

Темпы научно-технического прогресса, усиление роли науки в значительной степени определяются качеством и номенклатурой средств вычислительной техники и их программным обеспечением. Именно развитие этих средств обеспечивает успехи в автоматизации производственных процессов, в разработке новых технологий, в повышении эффективности труда и управления, в совершенствовании системы образования и в ускорении подготовки кадров.

  Мета вивчення курсу. Курс «Алгоритмізація і компьютерізація технічних задач» є однією з загальнотехнічних дисциплін фахів вищої технічної школи. Метою вивчення дисципліни є придбання студентами комплексу знань по класификации технічних завдань,  складанню алгоритму їх рішення і рішенню з використанням стандартних програм або розроблених з використанням мов високого рівня.

Програма курсу базується на отриманих студентами знаннях по ряді загальноосвітніх і загальнотехнічних дисциплін, передбачених навчальним планом.

Задача вивчення курсу. В результаті вивчення даного курсу студенти повинні знати:

   - класифікацію завдань оптимізації, основні методи вирішення завдань;

- послідовність роботи при ухваленні оптимальних рішень, основні етапи робіт, аналіз вирішуваних завдань, види запису алгоритмів;     

- поняття бази даних, створення бази даних, функції бази даних, дослідження фінансових питань;

- використання мови високого рівня Паскаль для вирішення завдань оптимізації;

- вирішення завдань оптимального програмування за допомогою стандартних програм EXCEL.

Вміти:

   - проводити класифікацію завдань оптимізації, аналіз вирішуваних завдань, вибирати види запису алгоритмів;

- послідовність роботи при ухваленні оптимальних рішень, основні етапи робіт, аналіз вирішуваних завдань, види запису алгоритмів;

  - використовувати мови високого рівня для вирішення завдань оптимізації;

- працювати з електронною таблицею - будувати діаграми, визначати рівняння регресії.;

- вирішувати завдання оптимального програмування за допомогою електронної таблиці EXCEL;

- проводити фінансово – економічний аналіз зварювальних технологій.

Для успішного вивчення дисципліни потрібно добре знати наступні курси: вища математика, фізика, информатика, теорія зварювальних процесів, теоретична механіка та ін.

Робота студентів над курсом включає: слухання лекцій, виконання лабораторних робіт, домашнього завдання, самостійне вивчення матеріалу по підручниках і іншій літературі відповідно до програми курсу.

Над вивченням курсу варто працювати систематично, переходячи до наступної теми після закріплення знань з попередньої. Рекомендується упорядкування стислого конспекту з виписуванням виникаючих питань для консультацій із викладачем кафедри. Розглядаючи аналітичні залежності і формули, необхідно звертати увагу на фізичний смисл результату. Рекомендується в процесі вивчення курсу детально вивчати вирішення завдань оптимізації з використанням стандартних програм або розроблених з використанням мов високого рівня по додатковій літературі.

 

Лекция №1  1. Основные принципы разработки алгоритмов и программ.

Этапы решения задачи на ЭВМ

Решение любой задачи на ЭВМ состоит из нескольких этапов, среди которых основными являются следующие:
1) постановка задачи;
2) формализация (математическая постановка за­дачи);                                                             
3) выбор (или разработка) метода решения;
4) разработка алгоритма (алгоритмизация);
5) составление программы (программирование);
6) отладка программы;
7) вычисления и обработка результатов.
Последовательное выполнение перечисленных этапов составляет полный цикл разработки, отладки и счета программы. Приведенное разделение является условным. Рассмотрены наиболее общие и необходимые этапы. Вместе с указанными пользователь ЭВМ в процессе решения задачи может выполнять также такие этапы, как выбор языка программирования, описание структуры данных, оптимизация программы, тестирование, документирование и др.

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

рассматриваемого физического явления или объекта; |анализу возможностей конкретной ЭВМ и данной системы программирования. На этом этапе требуется глубокое понимание существа поставленной задачи. Правильно сформулировать задачу иногда не менее сложно, чем ее решить.

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

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

Полная постановка многих сложных задач невыпол­нима средствами вычислительной техники. Поэтому эти задачи нужно упрощать. Грамотное упрощение задачи невозможно без хорошего представления о том, какие факторы и параметры наиболее важны для изучаемой задачи, а какие — менее существенны. При этом также очень важно знать, какая из возможных расчетных схем может привести к упрощениям вычислительного харак­тера, обусловленным выбором вычислительного метода.

Если имеющихся средств недостаточно, тогда необходимо разработать, новый подход, новые методы исследования.

 

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

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

 

 

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

 

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

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

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

В процессе разработки алгоритма могут использовать­ся различные способы его описания, отличающиеся по простоте, наглядности, компактности, степени формали­зации, ориентации на машинную реализацию и другим показателям. В практике программирования наибольшее распространение получили:

1) словесная запись алгоритмов;

2) псевдокод (формальные алгоритмические языки);

3) схемы алгоритмов;

4) структурограммы (диаграммы Насси— Шнейдер­мана).

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

 

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

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

 

 

 что, как бы мы тщательно ни действовали, первоначально составленная программа обычно содержит ошибки и машина или не может дать ответа, или приводит неправильное решение.

Отладка начинается с того, что программа, аккуратно записанная на бланке, проверяется непосредственно лицом, осуществившим подготовку и программирование задачи. Выясняется правильность написания программы, выявляются смысловые и синтаксические ошибки и т. п. Затем программа вводится в память ЭВМ и ошибки, оставшиеся незамеченными, выявляются уже непосредственно с помощью машины.

Опытный пользователь ЭВМ знает, что необходим действенный контроль над процессом вычислений, позволяющий своевременно обнаруживать и предотвращать ошибки. Для этого используются различного рода интуитивные соображения, правдоподобные рассуждения и контрольные формулы. Начинающий пользователь часто считает отладку излишней, аполучение контрольных точек - неприятной дополнительной работой. Однако очень скоро убеждается, что поиск пропущенной ошибки требует значительно большего времени, чем время, затраченное на контроль.

 

Гарантией правильности решения может служить, например:

а) проверка выполнения условий задачи (например, для алгебраического уравнения найденные корни под­ставляются в исходное уравнение и проверяются расхождения левой и правой частей);       

б) качественный анализ задачи;

в) пересчет (по возможности другим методом).

Для некоторых сложных по структуре программ процесс отладки может потребовать значительно больше машинного времени, чем собственно решение на ЭВМ, так как плохо спланированные процессы алгоритмизации, программирования и отладки приводят к ошибкам, которые могут быть обнаружены лишь после многократных проверок.

Вычисления и обработка результатов. Только после того как появится полная уверенность, что программа обеспечивает получение правильных результатов, можно

приступать непосредственно к расчетам по программе. Непосредственное решение задачи на ЭВМ не требует обязательного участия пользователя. Эта работа выполняется оператором ЭВМ. Порядок работы на машине при решении задачи обстоятельно описывается в инструкции к программе. После завершения расчетов наступает этап использования результатов вычислений в практиче­ской деятельности или, как говорят, этап внедрения ре­зультатов. Интерпретация результатов вычислений снова относится к той предметной области знаний, откуда воз­никла задача.

Словесная форма записи алгоритмов

                

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

Рассмотрим пример — алгоритм отыскания минимума и максимума в любой конечной последовательности из n вещественных чисел а , а ,..., а ,…, а . При небольшом количестве чисел доста­точно беглого взгляда, чтобы указать максимум и мини­мум. Однако, если n велико, задача усложняется. В этом легко убедиться, если попытаться отыскать максимум и минимум среди нескольких сотен многоразрядных чисел. Поэтому необходимо придерживаться определенной системы. Например, взять в качестве начального значе­ния

 

 

 как для максимума, так и для минимума первое число, далее последовательно перебирать числа и срав­нивать каждое из них с установленным к текущему мо­менту значением максимума. Если очередное число пре­вышает максимум, считать его новым значением макси­мума (прежнее значение «забыть»), после чего можно переходить к новому числу. Если анализируемое число не больше максимума, то сравнить его с установленным к текущему моменту значением минимума. Если число оказывается меньшим минимума, считать его новым зна­чением минимума и перейти к следующему числу; если число не меньше минимума, просто переходить к анализу следующего числа. Перебрав, таким образом, все числа, получим окончательные значения максимума и миниму­ма. Изложенные правила можно представить в виде словесной записи:                                                                                                                          

             Начало.                                                                                                                                        

   1. Ввести (а , i= 1, 2, ..., n).

  2. min:=a ; max:=a .

   3. i:=2.

   4. Если а  > mах, то перейти к п. 5, иначе перейти к п. 6.

   5. max:=a ; перейти к п. 8.

   6. Если a < min, перейти к п. 7, иначе перейти к п. 8.

   7. min:=a .

   8. i:=i+1.

   9. Если i ≤ n, то перейти к п. 4, иначе перейти к п. 10.

   10. Печатать (max, min).

   Конец.

 

Псевдокод

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

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

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

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

 

    алг нахождение минимума и максимума в последовательности

чисел (цел k, n, вещтаб a [k : n], вещ max, min)

       арг k, n, а

       рез mах, min                                                                                                                                   

начцел i

       min: = a[ k ]

       max: = a[ k ]

       i : = k +1

       пока i ≤ n

       нц                                                                                                                                               

             если а[ i ] > max

             то max: = а[ i ]

             иначеесли а[ i ] < min

                        то min: = а[ i ]

                        все

                     i : = i + 1

 кц

кон

Схемы алгоритмов

Схема - это графическое представление алгоритма, дополненное элементами словесной записи. Каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой — блоком (блочным символом), причем различным по типу выполняемых действий блокам соответствуют различные геометрические фигуры, изображаемые по ГОСТу. Правила выполнения схем алгоритмов регламентирует ГОСТ 19.002—80 (который полностью соответствует международному стандарту ИСО 2636—73). Применяемые графические символы, отражающие основные операции процесса обработки данных, устанавливает ГОСТ 19.003—80 (обозначение символов соответствует международному стандарту ИСО 1028—73). В табл. 1.1 приведены наиболее часто употребляемые блоки и даны пояснения к ним.

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

 

 

        

 

                               

 

 

Рис. 1.1 Примеры условных графических обозначений на схемах.

 

 

Таблица 1.1  Условные графические обозначения, применяемые при  составлении схем алгоритмов

№ п/п	Название  символа	Символ	Отображаемая функция
1	Блок вычисле­ний (процесс)		Вычислительное действие или последовательность вычисли­тельных действий
2	Логический блок  (решение)		Выбор направления выполне­ния алгоритма в зависимости от некоторых условий (условия)
3	Блоки ввода - вывода		Общее обозначение ввода или вывода данных (в независимо­сти от физического носителя)
			Вывод данных, носителем ко­торых служит документ (печа­тающее устройство)
4	Начало - ко­нец (вход - выход)		Начало или конец программы, останов, вход или выход в под­программах
5	Предопреде-лен­ный процесс (под­программа)		Вычисления по стандартной подпрограмме или подпрограм­ме пользователя
6	Блок модифи­кации (заголовок цикла)		Выполнение действий, изме­няющих пункты алгоритма
7	Соединитель		Указание связи между пре­рванными линиями потока ин­формации в пределах одной страницы
8	Межстранич­ный соединитель		Указание связи между частя­ми схемы, расположенными на разных листах

 

 

 

При большом количестве пересекающихся линий, большой их длине и многократных

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

 

 

Рис. 1.2 Cхема алго­ритма метода нисходящего проектирования, который, в                                                                 свою очередь, является основой структурного                                                                программирования.

Внутри блоков и рядом с ними делают записи и обозначения (для уточнения выполняемых ими функций) так, чтобы их можно было читать слева направо и сверху вниз независимо от направления потока. Например, на рис. 1.1,а и вид 2 читаются идентично. Порядковые номера блоков проставляют в верхней части графического символа в разрыве его контура              (рис. 1.1, б, в, г). При выполнении схем алгоритмов не­обходимо выдерживать минимальное расстояние 3 мм между параллельными линиями потоков и 5 мм между остальными символами. В блоках приняты размеры: а=10, 15, 20мм; b=1,5 а,5а (см. рис 1.1, а). Если необходимо увеличить размер схемы, то допускается увеличивать а на число, кратное 5.

На рис. 1.2 приведена схема алго­ритма поиска мак­симума и минимума в конечной последо­вательности чисел.

 Схема является исключительно на­глядным и простым способом представления алгоритма. При этом не накладывается никаких ог­раничений на степень детализации визображении алгоритма. Выбор ее це­ликом зависит отпрограммиста. Одна­ко необходимо иметь в виду, что излишне общий харак­тер схемы нежелателен из-за малой информативности, а очень детальная схема проигрывает в наглядности. По­этому, особенно для сложных и больших алгоритмов, целесообразно составлять несколько схем различных уровней детализации. Схема 1-го уровня отображает весь алгоритм целиком. Схемы 2-го уровня раскрывают логи­ку отдельных блоков схемы 1-го уровня. При необходимо­сти могут быть составлены схемы последующих уровней с ещё большей степенью детализации. Такое            пошаговое уточнение схемы алгоритма составляет сущность         

 

 

                       § 1. 5  Структурное программирование

Практика программирования показала необходимость научно обоснованной методологии разработки и документирования алгоритмов и программ. Эта методология должна касаться анализа исходной задачи, разделения её на достаточно самостоятельные части и программирования этих частей по возможности независимо друг от друга. Такой методологией, зародившейся в начале 70-х годов и    

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

1. Алгоритм и программа должны составляться поэтапно (по шагам).

2. Сложная задача должна разбиваться на достаточно простые, легко воспринимаемые части, каждая из которых имеет только один вход и один выход.

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

     Использование этих положений позволяет внести определённую систему в труд программиста и составлять удобочитаемые алгоритмы (и программы), которые легко изучать и проверять. Фундаментом структурного программирования является теорема о структурировании. Этатеорема устанавливает, что, как бы сложна ни была задача, схема соответствующей программы всегда может быть представлена с использованием весьма ограничен­ного числа элементарных управляющих структур. Элементарные структуры могут соединяться между собой, образуя более сложные структуры, по тем же самым элементарным схемам. Базовыми элементарными структурами являются структуры, изображенные на рис. 1.3. Они обладают функциональной полнотой, т. е. любой алгоритм может быть реализован в виде композиции этих трёх конструкций. Каждая из конструкций имеет свое название.

 

                                  Рис.1.3 Базовые элементарные структуры.

 Так, первая из них (рис. 1.3, а) называется структурой типа последовательность (или просто после­довательностью), вторая (рис. 1.3, б) — структурой выбора (разветвлением), третья (рис. 1.3, в) — структурой цикла с предусловием. При словесной записи алгоритма указанные структуры имеют соответственно следующий смысл: «выполнить S ; выполнить S », «если P, то выполнить S , иначе выполнить S », «до тех пор, пока Р, вы­полнять S», где Р — условие; S, S , S  — действия.

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

алгоритма обеспечивает упрощение последующих этапов решения задачи на ЭВМ.

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

 Пусть функция z ( x ) имеет вид

                                                          z ( x )= ,

           sin x, если х ≤ а,

где у = x , если а < х < b,

             если х ≥ b;

                          х = -3; h =1;

           x =10; а=0; b =3,85.

 

       Рис. 1.4 -Дополнительные элементарные структуры.

 

 Рис. 1.5 -  Нисходящее проектирование схемы алгоритма табулирования функции z = z(х)  

 

 Процесс нисходящего проектирования схемы алгоритма табулирования функции z = z(х) показан на рис. 1.5. На первом уровне детализации схема (блоки 1.1—1.5) отражает процесс табулирования функции в наиболее общем виде. Для этого используются структуры типов последовательность и цикл с постусловием (подробнее о проектировании алгоритмов и программ циклической структуры см. § 3.2). Далее осуществляется детализация блока 1.3, который представляется в виде последовательности блоков 2.1-2.3 второго уровня. Так как функция     у = у(х), входящая в качестве аргумента в определение функции z = z(х), является сложной, то она определяется разветвляющейся структурой, детализация которой осуществлена на 3-м и 4-м уровнях. Проведенную детализацию блоков, осуществляющих определение функции у = у(х), можно пояснить с помощью зависимостей

               y = sinx, если х ≤ а,

                                 y ( x ), если х > а,

 

где y = х , если х < b ,

  , если х ≥ b ,

которые легко обеспечивают применение структуры разветвления.

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

 

 

          

 Рис. 1.6 - Схема алгоритма табулирования функции z = z ( x )

 

 

1.6  Структурограммы

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

1. Блок обработки (вычислений). Каждый символ структурограммы является блоком обработки. Каждый прямоугольник внутри любого символа представляет собой также блок обработки (рис. 1.7 а).

 

 

2. Блок следования. Этот символ объединяет ряд следующих друг за другом блоков обработки (рис, 1.7 б).

3. Блок решения. Этот символ применяется для обозначения структуры типа разветвления. Условие располаг­ается в верхнем треугольнике, варианты решения — по сторонам треугольника, а процессы обработки обозначаются прямоугольниками (рис. 1.7 в).

4. Блок варианта. Этот символ представляет собой расширение блока решения. Те варианты выхода из этого блока, которые можно сформулировать точно, размеща­ются слева. Остальные объединяются в один, называемый выходом по несоблюдению условий, и располага­ются справа. Если можно перечислить все возможные случаи, правую часть можно оставить незаполненной или совсем опустить (рис. 1.7 г).

5. Блок цикла с предусловием. Этот символ обозначает циклическую конструкцию с проверкой условия в начале цикла. Условие продолжения цикла размещается в верхней полосе, сливающейся с левой полосой, указывающей границу цикла. Данная структура может быть использована также для обозначения цикла с параметром. При этом вверху указывают закон изменения параметра цикла (рис. 1.7, д).

6. Блок цикла с постусловием. Этот символ аналогичен блоку цикла с предусловием, но условие располагается внизу. Это условие окончания цикла (рис. 1.7, е).

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

 

 

 

 

                   Рис. 1.7 - Блоки структурограмм.

 

Примеры применения структурограмм  для описания алгоритмов нахождения наибольшего общего делителя и поиска максимума и минимума в конечной последовательности чисел приведены на рис. 1.8.

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

 Например, на рис. 1.9 показана модифицированная структурограмма

алгоритма поиска максимума и минимума в последовательности чисел а , а , …, а . В структурограмме отдельно изображены блоки ввода исходных данных и печати рез

ультатов, а также упрощено изображение блока решения с условием а < min.

 

                     Рис.1.9 - Модифицированная структурограмма.

 

         

 

---

Дата добавления: 2020-12-12; просмотров: 89; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

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