Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования.pdf
Добавлен: 29.03.2023
Просмотров: 87
Скачиваний: 3
Циклическим называется процесс многократного повторения некоторого участка вычислений при изменении хотя бы одной из входящих в него величин.
Повторяющийся участок вычисления называется циклом. Цикл организуют по определенным правилам. Циклический алгоритм состоит из подготовки цикла, тела цикла, условия продолжения цикла. В подготовку цикла входят действия, связанные с заданием исходных значений для параметра цикла (начальное и конечное значения, шаг параметра цикла). Иногда при подготовке цикла задаются начальные значения и другим величинам, использующимся в цикле [7].
Операции, осуществляемые в цикле, составляют тело цикла. В тело цикла входят многократно повторяющиеся действия для вычисления искомых величин; подготовка следующего значения параметра цикла; подготовка других значений, необходимых для повторного выполнения действий в теле цикла.
В условии продолжения цикла определяется необходимость дальнейшего выполнения повторяющихся действий (тела цикла). Если параметр цикла превысил конечное значение, то выполнение цикла должно быть прекращено.
При разработке алгоритма циклической структуры выделяют следующие понятия: параметр цикла – величина, с изменением которой связано многократное выполнение цикла; начальное и конечное значения параметров цикла; шаг цикла – значение, на которое изменяется параметр цикла при каждом повторении. Зависимость, связывающая текущее и предыдущее значения параметра цикла, определяет закон изменения параметра цикла.
Зависимость, предписывающая повторение цикла, либо выход из него, называется условием повторения цикла.
Все циклические процессы по признаку определения количества повторений разделяются на два класса [7].
Арифметическим называется циклический процесс, число повторений в котором может быть определено заранее, т.е. не зависит от результатов счёта в теле цикла.
Итерационным является циклический процесс, число повторений в котором зависит от результатов вычислений в теле цикла и не может быть определено заранее [7].
На приведенных ниже рисунках показаны примеры циклических процессов (рисунок 14, 15).
Рисунок 14. Блок-схема цикла с предусловием
Рисунок 15. Блок-схема цикла с постусловием
Таким образом, при разработке алгоритма структуры выделяют следующие понятия: параметр цикла, начальное и конечное значения параметров цикла, шаг цикла. Зависимость, связывающая текущее и предыдущее значения параметра цикла, определяет закон изменения параметра цикла.
4 ОБЗОР ПРОГРАММНЫХ СРЕДСТВ АЛГОРИТМИРОВАНИЯ
Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов – языков программирования. Смысл появления такого языка – оснащенный набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм [2].
Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который настолько «близок к машине», что всеми основными машинными аспектами можно легко и просто оперировать достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько «близок к решаемой задаче», чтобы концепции ее решения можно было выражать прямо и коротко [5].
Связь между языком, на котором мы думаем/программируем, и задачами, и решениями, которые мы можем представлять в своем воображении, очень близка. По этой причине ограничивать свойства языка только целями исключения ошибок программиста в лучшем случае опасно. Как и в случае с естественными языками, есть огромная польза быть, по крайней мере, двуязычным. Язык предоставляет программисту набор концептуальных инструментов, если они не отвечают задаче, то их просто игнорируют. Например, серьезные ограничения концепции указателя заставляют программиста применять вектора и целую арифметику, чтобы реализовать структуры, указатели и т.п. Хорошее проектирование и отсутствие ошибок не может гарантироваться чисто за счет языковых средств.
Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идей простые операции производятся со скоростью молнии на двоичных числах.
Персональные компьютеры IBM используют машинный язык микропроцессоров семейства 8086, т.к. их аппаратная часть основывается именно на данных микропроцессорах [3].
Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации (в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал [13]. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят «исходный код» (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Существует два основных вида трансляторов:
- интерпретаторы, которые сканируют и проверяют исходный код в один шаг,
- компиляторы, которые сканируют исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.
Интерпретаторы
Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает «непосредственный режим». Непосредственный режим позволяет вам задавать компьютеру задачу вроде PRINT 3.14159*3/2.1 и возвращает вам ответ, как только вы нажмете клавишу ENTER (это позволяет использовать компьютер стоимостью 3000 долларов в качестве калькулятора стоимостью 10 долларов). Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение [21].
Больше всего программистам нравится в интерпретаторах возможность получения быстрого ответа. Здесь нет необходимости в компилировании, так как интерпретатор всегда готов для вмешательства в вашу программу. Введите RUN и результат вашего самого последнего изменения оказывается на экране.
Однако интерпретаторные языки имеют недостатки. Необходимо, например, иметь копию интерпретатора в памяти все время, тогда как многие возможности интерпретатора, а, следовательно, и его возможности могут не быть необходимыми для исполнения конкретной программы.
Слабо различимым недостатком интерпретаторов является то, что они имеют тенденцию отбивать охоту к хорошему стилю программирования. Поскольку комментарии и другие формализуемые детали занимают значительное место программной памяти, люди стремятся ими не пользоваться. Хуже всего то, что интерпретаторы тихоходны. Ими затрачивается слишком много времени на разгадывание того, что делать, вместо того чтобы заниматься действительно делом [17].
При исполнении программных операторов, интерпретатор должен сначала сканировать каждый оператор с целью прочтения его содержимого (что этот человек просит меня сделать?), а затем выполнить запрошенную операцию. Операторы в циклах сканируются излишне много.
Компиляторы
Компилятор-это транслятор текста на машинный язык, который считывает исходный текст. Он оценивает его в соответствии с синтаксической конструкцией языка и переводит на машинный язык. Другими словами, компилятор не исполняет программы, он их строит. Интерпретаторы невозможно отделить от программ, которые ими прогоняются, компиляторы делают свое дело и уходят со сцены. При работе с компилирующим языком, таким как Турбо-Бейсик, вы придете к необходимости мыслить о ваших программах в признаках двух главных фаз их жизни: периода компилирования и периода прогона. Большинство программ будут прогоняться в четыре — десять раз быстрее их интерпретаторных эквивалентов. Если вы поработаете над улучшением, то сможете достичь 100-кратного повышения быстродействия. Оборотная сторона монеты состоит в том, что программы, расходующие большую часть времени на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости [21].
Алгоритмический язык Pascal
Паскаль (англ. Pascal - это высокоуровневый язык программирования общего назначения. Один из самых известных языков программирования, широко используемый в промышленном программировании, преподавая программирование в средней школе, является основой для большого количества других языков.
Паскаль был создан Никлаусом Виртом в 1968-69 годах после его участия в работе Комитета по разработке языковых стандартов ALGOL-68. Он был опубликован в 1970 году фирмой Wirth как небольшой и эффективный язык для продвижения хорошего стиля программирования, использования структурированного программирования и структурированных данных [16].
Паскаль был создан как язык для обучения процедурному программированию (хотя, по мнению Вирта, язык нельзя считать только образовательным, поскольку язык непригоден для написания реальных программ, для обучения его использовать не следует). Название было дано в честь выдающегося французского математика, физика, писателя и философа Блеза Паскаля.
Компилятор Паскаля был написан на самом Паскале, используя метод продвижения.
Особенностями языка являются строгая типизация и наличие структурного (процедурного) программирования. Паскаль был одним из первых таких языков. По мнению Н. Вирта, язык должен способствовать дисциплине программирования, поэтому, наряду со строгой типизацией, Паскаль минимизировал возможные синтаксические неоднозначности, а синтаксис автора старался сделать интуитивным еще при первом знакомстве с языком.
Однако изначально язык имел ряд ограничений: невозможность передачи массивов переменной длины в функции, отсутствие обычных средств работы с динамической памятью, ограниченность библиотеки ввода-вывода, отсутствие средств подключения функций, написанных на других языках, отсутствие отдельных средств компиляции и др. Подробный анализ недостатков языка Паскаль того времени был выполнен Брайаном Керниганом в статье «Почему Паскаль не является моим любимым языком программирования» (эта статья была опубликована в начале 1980-х годов, когда уже существовал язык Modula-2, потомок Паскаля, освобожденный от большинства его пороков, а также более развитых диалектов Паскаля). Некоторые недостатки Pascal были исправлены в стандарте ISO 1982 года, в частности, в языке появились открытые массивы, что позволило использовать одни и те же процедуры для обработки одномерных массивов разных размеров [22].
Следует отметить, что многие недостатки языка не проявляются или даже становятся достоинствами при обучении программированию. Кроме того, по сравнению с основным языком программирования в академической среде 1970-х годов (которым был Fortran, имевший гораздо более существенные недостатки), Pascal представлял собой значительный шаг вперед. В начале 1980-х годов академик А. П. Ершов разработал в СССР алголо-Паскалоподобный «алгоритмический язык» для обучения школьников основам информатики и вычислительной техники [14].
Наиболее известной реализацией Pascal, обеспечившей широкое распространение и развитие языка, является Turbo Pascal от Borland, который затем перерос в object Pascal для DOS (начиная с версии 5.5) и Windows, а затем в Delphi, где были введены значительные расширения языка.
Диалекты Pascal, используемые в Turbo Pascal для DOS и Delphi для Windows, стали популярными из-за отсутствия других успешных коммерческих реализаций.
Описание каждого элемента языка определяется его синтаксисом и семантикой. Синтаксические определения задают правила построения языковых элементов. Семантика определяет смысл и правила употребления тех элементов языка, для которых даны синтаксические определения. Паскаль в своей первоначальной форме является чисто процедурным языком и включает в себя множество структур и конструкций с зарезервированными словами, такими как if, then, else, while, for и т. д. Однако Pascal также содержит большое количество возможностей для структурирования информации и абстракций, которые отсутствуют в оригинальном ALGOL-60, таких как определения типов, записи, указатели, перечисления и наборы.
Электронные таблицы Excel
Таблицы используются для представления данных удобным способом. Компьютер позволяет представлять их в электронном виде, а это дает возможность не только отображать, но и обрабатывать данные. Класс программ, используемых для этой цели, называется электронными таблицами.
Особенностью электронных таблиц является возможность использования формул для описания взаимосвязи между значениями различных ячеек. Расчет по приведенным формулам производится автоматически. Изменение содержимого ячейки приведет к пересчету значений всех ячеек, связанных с ней отношениями формул, и, таким образом, обновит всю таблицу в соответствии с измененными данными [5].
Использование электронных таблиц упрощает работу с данными и позволяет получать результаты без ручных вычислений или специального программирования. Наиболее широкое применение электронные таблицы находят в экономических и бухгалтерских расчетах, но и в научно-технических задачах, электронные таблицы могут эффективно использоваться, например, для:
- проведение однотипных вычислений по большим наборам данных;
- автоматизация окончательных расчетов;
- решение задач путем подбора значений параметров, табулирования формул;
- обработка результатов экспериментов;
- поиск оптимальных значений параметров;
- подготовка табличных документов;
- построение диаграмм и графиков, на основе имеющихся данных.