Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Теоретическое понятие алгоритма).pdf

Программа— описание структуры алгоритма на языке алгоритмического программирования. Выше отмечалось, что один и тот же алгоритм может статься записан по-разному. Можно записывать алгоритм естественным языком. В таком варианте мы используем рецепты, инструкции и т. п. Для записи алгоритмов, специализированных формальным исполнителям, разработаны особые языки программирования. Любой алгоритм можно описать графически в виде блок-схемы. Чтобы достичь желаемого результата изобретена особая система обозначений (Приложение № 1)

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

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

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

Такой язык принято называть языком программирования, а запись алгоритма на данном языке — программой для компьютера.

1.3. Виды структур алгоритмов и примеры их использования

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

Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.

Самый простой пример реализации линейного алгоритма – путь из университета домой.

Словесный способ записи данного алгоритма:

выйти из университета на остановку;

подождать нужный автобус;

сесть на нужный автобус;

оплатить проезд;

выйти на требуемой остановке;

дойти до дома.

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

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

---

В алгоритме разветвленной структуры (ветвлении) в зависимости от истинности или ложности некоторого условия выбирается одна из двух серий команд.

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

Например вы отправляетесь в кино. Подойдя к кинотеатру, вы обнаруживаете, что сегодня идут два фильма: новая серия «Гарри Поттера» и новый боевик с Сильвестром Сталлоне. Если есть билеты на первый, то пойдете смотреть его, иначе будете смотреть боевик.

Рис. 1 Пример разветвляющегося алгоритма

Идти в кино

Есть билеты на Гарри Потера?

Купить билет на этот фильм

Купить билет на боевик

Идти смотреть фильм

Идти смотреть боевик

Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.

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

Рис. 2 Пример циклического алгоритма

Открыть книгу

Книга не закончилась

Нет

Да

Прочесть страницу

Перевернуть страницу

Закрыть книгу

1.4. Обзор программных и аппаратных средств

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

Паскаль был создан Никлаусом Виртом в 1968-69 годах после его участия в работе комитета разработки стандарта языка Алгол-68. Он был опубликован в 1970 году Виртом как небольшой и эффективный язык, чтобы способствовать хорошему стилю программирования, использовать структурное программирование и структурированные данные.

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

Компилятор Паскаля был написан на самом Паскале c использованием метода раскрутки.

---

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

Тем не менее, первоначально язык имел ряд ограничений: невозможность передачи функциям массивов переменной длины, отсутствие нормальных средств работы с динамической памятью, ограниченная библиотека ввода-вывода, отсутствие средств для подключения функций написанных на других языках, отсутствие средств раздельной компиляции и т. п. Подробный разбор недостатков языка Паскаль того времени был выполнен Брайаном Керниганом в статье «Почему Паскаль не является моим любимым языком программирования» (эта статья вышла в начале 1980-х, когда уже существовал язык Модула-2, потомок Паскаля, избавленный от большинства его пороков, а также более развитые диалекты Паскаля). Некоторые недостатки Паскаля были исправлены в ISO-стандарте 1982 года, в частности, в языке появились открытые массивы, давшие возможность использовать одни и те же процедуры для обработки одномерных массивов различных размеров.

Необходимо заметить, что многие недостатки языка не проявляются или даже становятся достоинствами при обучении программированию. Кроме того, по сравнению с основным языком программирования в академической среде 1970-х (которым был Фортран, обладавший гораздо более существенными недостатками), Паскаль представлял собой значительный шаг вперёд. В начале 1980-х годов в СССР для обучения школьников основам информатики и вычислительной техники академик А.П. Ершов разработал алголо-паскалеподобный «алгоритмический язык».

Наиболее известной реализацией Паскаля, обеспечившая широкое распространение и развитие языка, является Turbo Pascal фирмы Borland, выросшая затем в объектный Паскаль для DOS (начиная с версии 5.5) и Windows и далее в Delphi, в которой были внедрены значительные расширения языка.

Диалекты Паскаля, применяемые в Turbo Pascal для DOS и Delphi для Windows, стали популярны из-за отстутствия других успешных коммерческих реализаций.

Описание каждого элемента языка задается его синтаксисом и семантикой. Синтаксические определения устанавливают правила построения элементов языка. Семантика определяет смысл и правила использования тех элементов языка, для которых были даны синтаксические определения. Паскаль, в его первоначальном виде, представляет собою чисто процедурный язык и включает в себя множество алголоподобных структур и конструкций с зарезервированными словами наподобие if, then, else, while, for, и т. д. Тем не менее, Паскаль также содержит большое количество возможностей для структурирования информации и абстракций, которые отсутствуют в изначальном Алголе-60, такие как определение типов, записи, указатели, перечисления, и множества. Эти конструкции были частично унаследованы или инспирированы от языков Симула-67, Алгол-68, созданного Никлаусом ВиртомAlgolW и предложены Хоаром.

---

В современных диалектах (Free Pascal) доступны такие операции как перегрузка операторов и функций.

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

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

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

· проведения однотипных расчетов над большими наборами данных;

· автоматизации итоговых вычислений;

· решения задач путем подбора значений параметров, табулирования формул;

· обработки результатов экспериментов;

· проведения поиска оптимальных значений параметров;

· подготовки табличных документов;

· построения диаграмм и графиков по имеющимся данным.

Одним из наиболее распространенных средств работы с документами, имеющими табличную структуру, является программа Microsoft Excel.

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

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

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

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

---

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

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

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

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

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

· ввод на компьютере разнообразных математических выражений (для дальнейших расчетов или создания документов, презентаций, Web-страниц);

· проведение математических расчетов;

· подготовка графиков с результатами расчетов;

· ввод исходных данных и вывод результатов в текстовые файлы или файлы с базами данных в других форматах;

· подготовка отчетов работы в виде печатных документов;

· подготовка Web-страниц и публикация результатов в Интернете;

· получение различной справочной информации из области математики.

Со всеми этими (а также некоторыми другими) задачами с успехом справляется Mathcad:

---