Основы программирования и алгоритмизации лекции. Основы алгоритмизации и программирования
Курс "Основы программирования и алгоритмические языки" является фундаментом образования будущего программиста. В этом курсе он должен научиться придумывать и программировать алгоритмы, и это умение будет служить ему всю программистскую жизнь по будням и даже в праздники. По этой причине пособие состоит из двух частей: первая - основы алгоритмизации (разделы с 1 по 5) и вторая - основы программирования на С++(разделы с 6 по 21).
Первая часть посвящена технологии разработки алгоритмов и описанию некоторых широко известных алгоритмов, преимущественно из области поиска и сортировки. Последние не только представляют практический интерес, но и служат прекрасными образцами алгоритмического творчества.
Во второй части излагаются основы алгоритмического языка C++ - инструмента профессионального программирования. Выбор C++ в качестве первого алгоритмического языка может вызвать справедливые возражения, но дело в том, что для подавляющего большинства первокурсников "компьютерных" специальностей это не первый изучаемый язык, а второй или третий. Как показал опыт, некоторые трудности в изучении этого развитого объектно-ориентированного языка с лихвой перекрываются интересом, который он вызывает.
Хотя материал по алгоритмизации отделен в пособии от материала по программированию, изучать алгоритмы и язык надо параллельно. Очередной раздел из первой части следует проходить, как только будут освоены соответствующие языковые средства. Например, после изучения массивов можно рассмотреть алгоритмы поиска и упорядочения массивов, после изучения файлов – сортировку файлов, после освоения функций можно рассмотреть рекурсивные алгоритмы и т.п.
В заключение отметим, что программирование – наука практическая и освоить ее, только читая книжки, нельзя. Решайте побольше задач, хороших и разных, за компьютером и за письменным столом, в "школе" и дома, и тогда фундамент вашего программистского образования будет прочным.
Основы алгоритмизации
1 Основные этапы решения задачи на эвм
В настоящее время на ЭВМ решают самые разнообразные задачи, от расчета баллистических траекторий до завоевания инопланетных территорий (пока только в компьютерных играх). В каждом случае ЭВМ выполняет какую-то программу, обычно довольно сложную. Некоторые из программ требуют от пользователя специальных знаний и высокой квалификации, например, программы электронной верстки или автоматизированного проектирования, но здесь мы будем говорить не об использовании, а об изготовлении программ. Несмотря на бесконечное разнообразие программ, в самом процессе их изготовления можно усмотреть нечто общее и выделить несколько этапов решения задачи на ЭВМ.
1.1 Постановка задачи
Под постановкой задачи понимают математическую или иную строгую формулировку решаемой задачи. Этот этап включает определение целей создаваемой программы и определение ограничений, налагаемых на программу. При постановке задачи должны быть определены требования:
Ко времени решения поставленной задачи;
Объему необходимых ресурсов, например, оперативной памяти;
Точности достигаемого результата.
Алгоритмом называется строго определенное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Термин «алгоритм» происходит от латинской формы имени среднеазиатского математика Аль-Хорезми – Algorithmi. Алгоритм является одним из основных понятий информатики и математики.
Исполнителем алгоритма предстает некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, которая способна выполнить действия, предписываемые алгоритмом.
Для характеристики исполнителя используют несколько понятий:
среда;
система команд;
элементарные действия;
отказы.
Среда (или обстановка) представляет собой «место обитания» исполнителя.
Любой из исполнителей может выполнять команды только из некоторого строго заданного списка, который является системой команд исполнителя. Для каждой команды задаются условия применимости (в каких состояниях среды может быть выполнена команда) и приводятся результаты выполнения команды.
После вызова команды исполнитель производит соответствующее элементарное действие.
Может возникнуть и отказ исполнителя в случае, если команда вызывается при недопустимом для нее состоянии среды. Чаще всего исполнитель ничего не знает о цели алгоритма. Он выполняет все предложенные ему действия, не задавая вопросов «почему» и «зачем».
В информатике универсальным исполнителем алгоритмов является компьютер.
К основным свойствам алгоритмов относятся:
1) понятность для исполнителя – исполнитель алгоритма должен знать, как его выполнять;
2) дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное исполнение простых (или ранее определенных) шагов (этапов);
3) определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Это свойство обеспечивает выполнение алгоритма механически, не требуя никаких дополнительных указаний или сведений о решаемой задаче;
4) результативность (или конечность) – алгоритм должен приводить к решению задачи за конечное число шагов;
5) массовость – алгоритм решения задачи производится в общем виде, т. е. его можно будет применять для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из определенной области, которая называется областью применимости алгоритма.
На практике чаще всего встречаются следующие формы представления алгоритмов:
словесная – записывается на естественном языке;
графическая – с помощью изображения из графических символов;
псевдокоды – полуформализованные описания алгоритмов на некотором условном алгоритмическом языке, которые включают в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.;
программная – тексты на языках программирования.
Словесный способ записи алгоритмов является описанием последовательных этапов обработки данных. Алгоритм может быть задан в произвольном изложении на естественном языке. Например, алгоритм нахождения наибольшего общего делителя двух натуральных чисел можно представить как следующую последовательность действий:
1) задание двух чисел;
2) если числа равны, то выбор любого из них в качестве ответа и остановка, в противном случае – продолжение выполнения алгоритма;
3) определение большего из чисел;
4) замена большего из чисел разностью большего и меньшего из чисел;
5) повтор алгоритма с шага 2.
Приведенный алгоритм используется для любых натуральных чисел и должен приводить к решению поставленной задачи.
Словесный способ не имеет широкого распространения, так как обладает некоторыми недостатками:
данные описания строго не формализуемы;
отличаются многословностью записей;
допускают неоднозначность толкования отдельных предписаний.
Графический способ представления алгоритмов оказывается более компактным и наглядным по сравнению со словесным. При данном виде представления алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению некоторого числа действий.
Для графического представления алгоритм использует изображение в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Это графическое представление называется схемой алгоритма, или блок-схемой.
В блок-схеме каждый из типов действий (ввод исходных данных, вычисление значений выражений, проверка условий, управление повторением действий, окончание обработки и т. п.) соответствует геометрической фигуре, представленной в виде блочного символа. Блочные символы соединены линиями переходов, которые определяют очередность выполнения действий.
Псевдокод является системой обозначений и правил, которая предназначена для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками. С одной стороны, псевдокод похож на обычный естественный язык, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, благодаря чему запись алгоритма приближается к общепринятой математической записи.
В псевдокоде не применяются строгие синтаксические правила для записи команд, которые присущи формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде чаще всего имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. Например, в псевдокоде, также каки в формальных языках, существуют служебные слова, смысл которых определен раз и навсегда. Их выделяют в печатном тексте жирным шрифтом, а в рукописном тексте подчеркивают. Единый или формальный подход к определению псевдокода не существует, поэтому используются различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Программная форма представления алгоритмов иногда характеризуется некоторыми структурами, состоящими из отдельных базовых (основных) элементов. При данном подходе к алгоритмам изучение основных принципов их конструирования следует начинать с этих базовых элементов. Их описание осуществляется с использованием языка схем алгоритмов и алгоритмического языка.
9.2. Системы программирования
Машинно-ориентированные языки относятся к машинно-зависимым языкам программирования. Основные конструктивные средства таких языков позволяют учитывать особенности архитектуры и принципов работы определенной ЭВМ, т. е. они имеют те же возможности и требования к программистам, что и машинные языки. Однако в отличие от последних они требуют предварительной трансляции на машинный язык составленных с их помощью программ.
Данными видами языков программирования могут быть: автокоды, языки символического кодирования и ассемблеры.
Для машинно-независимых языков не требуется полного знания специфики компьютеров. С их помощью можно записывать программу в виде, допускающем ее реализацию на ЭВМ с различными типами машинных операций, привязка к которым возлагается на соответствующий транслятор.
Причина бурного развития и применения высокоуровневых языков программирования заключается в быстром росте производительности ЭВМ и хронической нехватке программистских кадров.
Промежуточное место между машинно-независимыми и машинно-зависимыми языками отводится языку Си. Он создавался при попытке объединения достоинств, присущих языкам обоих классов. Данный язык обладает рядом особенностей:
максимально использует возможности конкретной вычислительной архитектуры; из-за этого программы на языке Си компактны и работают эффективно;
позволяет налучшим образом использовать огромные выразительные средства современных языков высокого уровня.
Языки разделяют на процедурно-ориентированные и проблемно-ориентированные.
Процедурно-ориентированные языки, например Фортран, Кобол, Бейсик, Паскаль, наиболее часто используются для описания алгоритмов решения широкого класса задач.
Проблемно-ориентированные языки, в частности РПГ, Лисп, АПЛ, GPSS, применяются для описания процессов обработки информации в более узкой, специфической области.
Объектно-ориентированные языки программирования позволяют разрабатывать программные приложения для большого круга разнообразных задач, имеющих общность в реализуемых компонентах.
Рассмотрим методы использования языков программирования.
Интерпретация представляет собой пооператорную трансляцию и последующее выполнение оттранслированного оператора исходной программы. Существует два основных недостатка метода интерпретации:
1) интерпретирующая программа должна располагаться в памяти ЭВМ на протяжении всего процесса выполнения исходной программы. Другими словами, она должна занимать некоторый установленный объем памяти;
2) процесс трансляции одного и того же оператора повторяется такое число раз, которое должна исполнять эта команда в программе. Это приводит к резкому снижению производительности работы программы.
Трансляторы-интерпретаторы являются достаточно распространенными, так как они поддерживают диалоговый режим.
Процессы трансляции и выполнения при компиляции разделяются во времени: сначала исходная программа в полном объеме переводится на машинный язык, после чего оттранслированная программа может многократно исполняться. Для трансляции методом компиляции необходим неоднократный «просмотр» транслируемой программы, т. е. трансляторы-компиляторы являются многопроходными. Трансляция методом компиляции носит название объектного модуля, который представляет собой эквивалентную программу в машинных кодах. Необходимо, чтобы перед исполнением объектный модуль обрабатывался специальной программой ОС и преобразовывался в загрузочный модуль.
Применяют также трансляторы интерпретаторы-компиляторы, объединяющие в себе достоинства обоих принципов трансляции.
9.3. Классификация языков программирования высокого уровня
Высокоуровневые языки используются в машинно-независимых системах программирования. Такие системы программирования в сравнении с машинно-ориентированными системами предстают более простыми в использовании.
Языки программирования высокого уровня подразделяют на процедурно-ориентированные, проблемно-ориентированные и объектно-ориентированные.
Процедурно-ориентированные языки применяются для записи процедур или алгоритмов обработки информации на каждом определенном круге задач. К ним относятся:
а) язык Фортран (Fortran), название которого происходит от слов Formulae Translation – «преобразование формул». Фортран представляет собой один из старейших языков программирования высокого уровня. Длительность его существования и применения можно объяснить простотой структуры данного языка;
б) язык Бейсик (Basic), который расшифровывается как Beginner"s All-purpose Symbolic Instruction Code, что в переводе означает – «многоцелевой символический обучающий код для начинающих», разработан в 1964 г. как язык для обучения программированию;
в) язык Си (С), применяемый с 1970-х гг. как язык системного программирования специально для написания ОС UNIX. В 1980-е гг. на основе языка С был разработан язык C++, практически включающий в себя язык С и дополненный средствами объектно-ориентированного программирования;
г) язык Паскаль (Pascal), который назван в честь французского ученого Б. Паскаля, начал применяться с 1968–1971 гг. Н. Виртом. При создании Паскаль использовался для обучения программированию, но со временем стал широко применяться для разработки программных средств в профессиональном программировании.
Проблемно-ориентированные языки используются для решения целых классов новых задач, возникших в связи с постоянным расширением области применения вычислительной техники:
а) язык Лисп (Lisp – List Information Symbol Processing), который был изобретен в 1962 г. Дж. Маккарти. Первоначально он применялся как средство для работы со строками символов. Лисп употребляется в экспертных системах, системах аналитических вычислений и т. п.;
б) язык Пролог (Prolog – Programming in Logic), используемый для логического программирования в системах искусственного интеллекта.
Объектно-ориентированные языки развиваются и в настоящий момент. Большинство из этих языков являются версиями процедурных и проблемных языков, но программирование с помощью языков этой группы является более наглядным и простым. К наиболее часто употребляемым языкам относятся:
а) Visual Basic (~ Basic);
б) Delphi (~ Pascal);
в) Visual Fortran (~ Fortran);
д) Prolog++ (~ Prolog).
9.4. Система VBA
Система VBA представляет собой подмножество VB и вклю – чает себя средства образования приложений VB, его структуры данных и управляющие структуры, дающие возможность создавать пользовательские типы данных. Так же как и VB, VBA – является системой визуального программирования, управляемого событиями. В ней имеется возможность создания форм со стандартным набором элементов управления и написания процедур, обрабатывающих события, которые возникают при тех или иных действиях системы и конечного пользователя. Также она позволяет использовать элементы ActiveX и автоматизации. Система VBA представляет собой полноценную систему программирования, но не имеет полного набора возможностей, которыми обладает последняя версия VB.
Программирование в среде VBA обладает рядом особенностей. В частности, в ней нельзя создавать проект независимо от этих приложений.
Из-за того что VBA является визуальной системой, программист способен создавать видимую часть приложения, которая является основой интерфейса «программа – пользователь». Благодаря этому интерфейсу производится взаимодействие пользователя с программой. На принципах объектно-ориентированного подхода, который реализуется в VBA применительно к приложениям, выполняемым под управлением Windows, разрабатывается программный интерфейс.
Характерным для данных приложений является то, что на экране в любой момент присутствует множество объектов (окон, кнопок, меню, текстовых и диалоговых окон, линеек прокрутки). С учетом алгоритма программы пользователь обладает определенной свободой выбора относительно использования этих объектов, т. е. он может сделать щелчок по кнопке, перенести объект, ввести данные в окно и т. п. При создании программы программист не должен ограничивать действия пользователя, он должен разрабатывать программу, правильно реагирующую на любое действие пользователя, даже некорректное.
Для любого объекта определяется ряд возможных событий. Одни события обусловлены действиями пользователя, например одинарным или двойным щелчком мыши, переносом объекта, нажатием клавиши клавиатуры и т. п. Некоторые события происходят в результате свершения других событий: окно открывается или закрывается, элемент управления становится активным или теряет активность.
Любое из событий проявляется в определенных действиях программы, а виды возможных действий можно разделить на две группы. Действия первой группы являются следствием свойств объекта, устанавливающихся из некоторого стандартного перечня свойств, которые задаются системой программирования VBA и самой системой Windows, например свертывание окна после щелчка по кнопке Свернуть. Вторую группу действий на события может определить только программист. Для любого возможного события отклик обеспечивается созданием процедуры VBA. Теоретически возможно создать процедуру для каждого события, но практически программист заполняет кодом процедуры только для событий, представляющих в данной программе интерес.
Объекты VBA являются функциональными, т. е. они действуют определенным образом и способны откликаться на конкретные ситуации. Внешний вид объекта и его поведение влияют на его свойства, а методы объекта определяют функции, которые способен выполнять данный объект.
Свойствами-участниками являются свойства, которые задают вложенные объекты.
Объекты способны реагировать на события – инициируемые пользователем и генерируемые системой. События, инициируемые пользователем, появляются, например, при нажатии клавиши, щелчка кнопками мыши. Исходя из этого любое действие пользователя может привести к целому набору событий. События, генерируемые системой, проявляются автоматически в случае, предусмотренном программным обеспечением компьютера.
9.5. Язык программирования VBA
Язык программирования VBA предназначен для написания кода программы. Он обладает своим алфавитом, который включает в себя:
строчные и прописные буквы латинского алфавита (А, B....,Z,a,b....,z);
строчные и прописные буквы кириллицы (А-Я, а-я);
неотображаемые символы, используемые для отделения лексем (лексических единиц) друг от друга;
специальные символы, участвующие в построении конструкций языка: +-*?^=><():{}" &©;
цифры от 0 до 9;
символ подчеркивания «_»;
составные символы, воспринимаемые как один символ: <=, >=, <>.
Лексема является единицей текста программы, которая имеет определенный смысл для компилятора и не может быть разбита в дальнейшем.
Программный код VBA – это последовательность лексем, записанных в соответствии с принятыми синтаксическими правилами, которая реализует нужную семантическую конструкцию.
Идентификатор представляет собой последовательность букв, цифр и символов подчеркивания.
Система VBA определяет некоторые ограничения, которые накладываются на имена:
1) имя следует начинать с буквы;
2) имя не должно включать в себя точки, пробелы, разделительные символы, знаки операций, специальные символы;
3) имя должно быть уникальным и не совпадать с зарезервированными словами VBA или другими именами;
4) длина имени не должна превышать 255 символов;
5) при составлении имен необходимо соблюдать соглашения по стилю;
6) идентификатор должен ясно отражать назначение переменной для понимания программы;
7) в именах лучше применять строчные буквы; если имена включают в себя несколько названий, их нужно отделять друг от друга подчеркиванием или начинать новое слово с прописной буквы;
8) имена констант следует составлять из прописных букв;
9) название идентификатора необходимо начинать со специального знака, указывающего на тип данных, связанный с этим идентификатором.
Переменные являются объектами, которые предназначены для хранения данных. Перед применением переменных в программе необходимо их объявлять (декларировать). Правильный выбор типа переменной обеспечивает эффективное использование памяти компьютера.
Строковые переменные могут быть переменной и фиксированной длины.
Объекты, значения которых не изменяются и не могут быть изменены во время выполнения программы, носят название констант. Их подразделяют на именованные и неименованные.
Перечни используются для декларации группы констант, объединенных общим именем, к тому же они могут быть объявлены только в разделе глобальных объявлений модуля или формы.
Переменные подразделяют на два вида – простые и переменные структурного вида. Массивы бывают одномерными и многомерными.
После декларации значение переменной может оказаться произвольным. Для присвоения переменной необходимого значения применяется операция присваивания.
Математические операции используются для записи формулы, представляющей собой программный оператор, который содержит числа, переменные, операторы и ключевые слова.
Операции отношения могут привести к появлению значения, причем существуют только два результирующих значения: истина и ложно.
Логические операции используются в логических выражениях, это происходит при существовании нескольких условий выбора в операциях отношения.
Операции для работы со строками – это операции конкатенации, которые позволяют объединить значения двух или нескольких строковых переменных или строковых констант. Результатом такой операции является более длинная строка, составленная из исходных строк.
Западно-Казахский Аграрно-Технический университет Жангир-хана
Кафедра: «Информатики»
Основы алгоритмизации
Подготовил: Иванов П.
Проверил: Кухта В.С.
Уральск 2010
1.Понятие алгоритма и его свойства
2.Способы описания алгоритмов
3.Основные структурные алгоритмические конструкции
4. Список литературы
Понятие алгоритма и его свойства
Алгоритм – описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления; описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.). Свойством, характеризующим любого исполнителя, является то, что он умеет выполнять некоторые команды. Совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя. Алгоритм описывается в командах исполнителя, который будет его реализовывать. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.
Дискретность(разрывность – противоположно непрерывности) – это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».
Массовость – применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных. Например, алгоритм решения квадратного уравнения в области действительных чисел должен содержать все возможные исходы решения, т.е., рассмотрев значения дискриминанта, алгоритм находит либо два различных корня уравнения, либо два равных, либо делает вывод о том, что действительных корней нет.
Определенность(детерминированность, точность) - свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь - голову потеряешь, направо пойдешь - жену найдешь, налево пойдешь – разбогатеешь». Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.
Результативность – свойство, состоящее в том, что любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов. Вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.
Формальность – это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.
Способы описания алгоритмов
Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесноеописание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг, электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е. словесное описания алгоритма, в соответствии которому данный прибор должен использоваться.
Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
Псевдокод - описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основные этапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика.
Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема – описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура пли связанная линиями совокупность фигур.
Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем алгоритмов программ, регламентированные ГОСТ 19.701-90.
Блок, характеризующий начало/конец алгоритма (для подпрограмм - вызов/возврат)
Блок - процесс, предназначенный для описания отдельных действий
Блок - Предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам)
Блок - ввода/вывода с неопределенного носителя или описания исходных данных
Блок - решение (проверка условия или условный блок)
Блок - границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»
Соединительные блоки
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем она настолько достаточна, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования.
Программа – описание структуры алгоритма на языке алгоритмического программирования.
Основные структурные алгоритмические конструкции
Элементарные шаги алгоритма можно объединить в следующие алгоритмические конструкции: линейные (последовательные), разветвляющиеся, циклические с предусловием и циклические с постусловием. Любой алгоритм можно составить, используя эти четыре алгоритмические конструкции.
Линейнойназывают алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие - не конец алгоритма.
Разветвляющейся(иливетвящейся) называется алгоритмическая конструкция, обеспечивающая выбор между двумя альтернативами в зависимости от значения входных данных. При каждом конкретном наборе входных данных разветвляющийся алгоритм сводится к линейному. Различают неполное (если – то) и полное (если – то – иначе) ветвления. Полное ветвление позволяет организовать две ветви в алгоритме (то или иначе), каждая из которых ведет к общей точке их слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран (рис. 1). Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния.
Рис. 1. Полное ветвление
Циклической (или циклом) называют алгоритмическую конструкцию, в которой некая, идущая подряд группа действий (шагов) алгоритма можем выполняться несколько раз, в зависимости от входных данных или условия задачи. Группа повторяющихся действий на каждом шагу цикла называется телом цикла. Любая циклическая конструкция содержит в себе элементы ветвящейся алгоритмической конструкции.
Основы алгоритмизации и программирования. Семакин И.Г., Шестаков А.П.
3-е изд. - М.: 2016. - 304 с.
В учебнике рассмотрены основы принципы алгоритмизации и программирования на базе языка Паскаль (версия Турбо Паскаль 7.0) Даны основные понятия объектно-ориентированного программирования и его реализация на языке Турбо Паскаль. Описана интегрированная среда программирования Delphi и визуальная технология создания графического интерфейса программ. Показана разработка программных модулей в этой среде. Учебник может быть использован при изучении общепрофессиональной дисциплины ОП «Основы алгоритмизации и программирования» в соответствии с требованиями ФГОС СПО для специальностей 230113 «Компьютерные системы и комплексы» и 230401 «Информационные системы (по отраслям)» укрупненной группы специальностей 230000 «Информатика и вычислительная техника». Для студентов средних профессиональных учебных заведений.
Формат: pdf
Размер: 7,3 Мб
Смотреть, скачать: drive.google
ОГЛАВЛЕНИЕ
Предисловие 4
Глава 1. Основные принципы алгоритмизации и программирования 8
1.1. Алгоритмы и величины 9
1.2. Линейные вычислительные алгоритмы 13
1.3. Ветвления и циклы в вычислительных алгоритмах 17
1.4. Логические основы алгоритмизации 26
1.5. Вспомогательные алгоритмы и процедуры 30
1.6. Основы структурного программирования 33
1.7. Развитие языков и технологий программирования 39
1.8. Структура и способы описания языков программирования высокого уровня 44
Глава 2. Программирование на языке Паскаль 49
2.1. Первое знакомство с языком Паскаль 50
2.2. Некоторые сведения о системах программирования на Паскале 56
2.3. Элементы языка Турбо Паскаль 57
2.4. Концепция типов данных 59
2.5. Арифметические операции, функции, выражения. Оператор присваивания 64
2.6. Ввод данных с клавиатуры и вывод на экран 70
2.7. Управление символьным выводом на экран 75
2.8. Логические величины, операции, выражения 81
2.9. Функции, связывающие различные типы данных 83
2.10. Программирование ветвящихся алгоритмов 86
2.11. Программирование циклических алгоритмов 90
2.12. Подпрограммы 96
2.13. Вычисление рекуррентных последовательностей 104
2.14. Графические средства Турбо Паскаля 113
2.15. Символьные строки 123
2.16. Массивы 129
2.17. Рекурсивные подпрограммы 139
2.18. Множества 144
2.19. Файлы 151
2.20. Комбинированный тип данных 162
2.21. Указатели и динамические структуры данных 168
2.22. Внешние подпрограммы и модули 179
Глава 3. Методы построения алгоритмов 189
3.1. Метод последовательной детализации 190
3.2. Рекурсивные методы 19В
3.3. Методы перебора в задачах поиска 201
3.4. Методы сортировки данных и сложность алгоритмов 208
Глава 4. Объектно-ориентированное программирование 217
4.1. Что такое объектно-ориентированное программирование 218
4.2. Объекты в Турбо Паскале 221
4.3. Интегрированная среда программирования Delphi 230
4.4. Компоненты Delphi. Свойства компонентов 234
4.5. Событийно-управляемое программирование 248
4.6. Технология создания приложенийв Delphi 253
4.7. Примеры разработки приложений Delphi 256
4.8. Иерархия классов 269
Приложения 275
Турбо Паскаль. Модуль CRT 275
Турбо Паскаль. Модуль GRAPH 278
DELPHI, Некоторые подпрогаммы 291
Список литературы 298
Тема 1.3: Системное программное обеспечение
Тема 1.4: Сервисное программное обеспечение и основы алгоритмизации
Введение в экономическую информатику
1.4. Сервисное программное обеспечение ПК и основы алгоритмизации
1.4.2. Основы алгоритмизации и языки программирования
Алгоритм и его свойства
Решение задач на компьютере основано на понятии алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к исходному результату.
Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация – это техника разработки (составления) алгоритма для решения задач на ЭВМ.
Изобразительные средства для описания (представление) алгоритма
Для записи алгоритма решения задачи применяются следующие изобразительные способы их представления:
- Словесно- формульное описание.
- Блок-схема (схема графических символов).
- Алгоритмические языки.
- Операторные схемы.
- Псевдокод.
Для записи алгоритма существует общая методика:
- Каждый алгоритм должен иметь имя, которое раскрывает его смысл.
- Необходимо обозначить начало и конец алгоритма.
- Описать входные и выходные данные.
- Указать команды, которые позволяют выполнять определенные действия над выделенными данными.
Общий вид алгоритма:
- название алгоритма;
- описание данных;
- начало;
- команды;
- конец.
Формульно-словесный способ записи алгоритма характеризуется тем, что описание осуществляется с помощью слов и формул. Содержание последовательности этапов выполнения алгоритмов записывается на естественном профессиональном языке предметной области в произвольной форме.
Графический способ описания алгоритма (блок - схема) получил самое широкое распространение. Для графического описания алгоритмов используются схемы алгоритмов или блочные символы (блоки), которые соединяются между собой линиями связи.
Каждый этап вычислительного процесса представляется геометрическими фигурами (блоками). Они делятся на арифметические или вычислительные (прямоугольник), логические (ромб) и блоки ввода-вывода данных (параллелограмм).
Рис. 1.
Порядок выполнения этапов указывается стрелками, соединяющими блоки. Геометрические фигуры размещаются сверху вниз и слева на право. Нумерация блоков производится в порядке их размещения в схеме.
Алгоритмические языки - это специальное средство, предназначенное для записи алгоритмов в аналитическом виде. Алгоритмические языки близки к математическим выражениям и к естественным языкам. Каждый алгоритмический язык имеет свой словарь. Алгоритм, записанный на алгоритмическом языке, выполняется по строгим правилам этого конкретного языка.
Операторные схемы алгоритмов. Суть этого способа описания алгоритма заключается в том, что каждый оператор обозначается буквой (например, А – арифметический оператор, Р – логический оператор и т.д.).
Операторы записываются слева направо в последовательности их выполнения, причем, каждый оператор имеет индекс, указывающий порядковый номер оператора. Алгоритм записывается в одну строку в виде последовательности операторов.
Псевдокод – система команд абстрактной машины. Этот способ записи алгоритма с помощью операторов близких к алгоритмическим языкам.
Принципы разработки алгоритмов и программ
Типы алгоритмических процессов
По структуре выполнения алгоритмы и программы делятся на три вида:
- линейные;
- ветвящиеся;
- циклические;
Линейные вычислительные процессы
Линейный алгоритм (линейная структура) – это такой алгоритм, в котором все действия выполняются последовательно друг за другом и только один раз. Схема представляет собой последовательность блоков, которые располагаются сверху вниз в порядке их выполнения. Первичные и промежуточные данные не оказывают влияния на направление процесса вычисления.
Алгоритмы разветвляющейся структуры
На практике часто встречаются задачи, в которых в зависимости от первоначальных условий или промежуточных результатов необходимо выполнить вычисления по одним или другим формулам.
Такие задачи можно описать с помощью алгоритмов разветвляющейся структуры. В таких алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия. Ветвящиеся процессы описываются оператором IF (условие).
Рис. 2.
Циклические вычислительные процессы
Для решения многих задач характерно многократное повторение отдельных участков вычислений. Для решения таких задач применяются алгоритмы циклической структуры (циклические алгоритмы). Цикл – последовательность команд, которая повторяется до тех пор, пока не будет выполнено заданное условие. Циклическое описание многократно повторяемых процессов значительно снижает трудоемкость написания программ.
Существуют две схемы циклических вычислительных процессов.
Рис. 3.
Особенностью первой схемы является то, что проверка условия выхода из цикла проводится до выполнения тела цикла. В том случае, если условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.
Особенностью второй схемы является то, что цикл выполняется хоты бы один раз, так как первая проверка условия выхода из цикла осуществляется после того, как тело цикла выполнено.
Существуют циклы с известным числом повторений и итерационные циклы. При итерационном цикле выход из тела цикла, как правило, происходит при достижении заданной точности вычисления.
Языки программирования
Языки программирования – это искусственные языки записи алгоритмов для исполнения их на ЭВМ. Программирование (кодирование) - составление программы по заданному алгоритму.
Классификация языков программирования. В общем, языки программирования делятся на две группы: операторные и функциональные. К функциональным относятся ЛИСП, ПРОЛОГ и т.д.
Операторные языки делятся на процедурные и непроцедурные (Smalltalk, QBE). Процедурные делятся на машино - ориентированные и машино – независимые.
К машино – ориентированным языкам относятся: машинные языки, автокоды, языки символического кодирования, ассемблеры.
К машино – независимым языкам относятся:
- Процедурно – ориентированные (Паскаль, Фортран и др.).
- Проблемно – ориентированные (ЛИСП и др.).
- Объектно-ориентированные (Си++, Visual Basic, Java и др.).