Лекции по "Языкам и методам программирования" (PascalABC)

 

 

 

Отметим, что данная структура  имеет один вход и один выход. Словесно эту структуру можно сформулировать следующим образом: «Если условие  истинно, то выполнять Действие 1, иначе (если условие ложно) Действие 2».

Б) Неполное ветвление, которое состоит из блока проверки условия и действия только по стрелке «да». Схематически такую структуру можно представить так:

 

 

 

                                        

                  

 

 

 

 

 

 

 

 

Отметим, что и данная структура имеет один вход и один выход. Словесная формулировка данной структуры: «Если условие истинно, то выполнять Действие1».

3.Структура повторение (цикл).  Циклы позволяют многократно выполнять некоторые действия, причем эти действия не нужно многократно записывать, достаточно записать их один раз. Цикл всегда состоит из действий, которые многократно повторяются – это тело цикла, и условия, которое позволяет выйти из цикла. Условие так и называется «условие выхода из цикла». Такая структура должна состоять из условия, т.е. блока проверки условия, и действия – любой базовой структуры.

Данная структура в  блок-схемах может быть двух видов:

А) Цикл – пока. Такой цикл еще называют циклом с предусловием, т.к. сначала в структуре идет условие цикла, а затем тело цикла. Схематически такой  цикл можно представить так:

 

 

 

 

                                             

 

 

 

 

                               

 

 

 

 

 

Эта структура имеет один вход и  один выход. Словесно этот цикл можно сформулировать так: «Пока условие истинно выполнять тело цикла». В этой структуре тело кила может не выполниться ни разу, если с самого начала условие примет значение ложь.

Б) Цикл – до. Такой цикл еще называют циклом с постусловием, т.к. в блок-схеме сначала идет тело цикла, а потом проверка условия. Схематически такую структуру можно представить в следующем виде:

 

 

 

 

 

                                     

                                          

 

                          

                           

 

 

Эта структура имеет  один вход и один выход. Такой цикл словесно сформулировать можно так: «Выполнять тело цикла до истинности условия». В этом цикле тело цикла всегда выполнится один раз, потому что сначала идет тело цикла, а затем проверка условия.

Понятие структурированной  блок-схемы

Поскольку всякая базовая  структура имеет только один вход и один выход, то любая блок-схема  построенная из этих структур также  будет иметь один вход и один выход.

В 1966 году Бом и Якопини доказали следующую теорему:

Любую блок-схему с  одним входом и одним выходом  можно построить, используя следующее  базисное множество базовых структур {следование, ветвление, цикл-пока}.

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

 

 

 

 

 

 

                                                            

 

 

                                                                                               

 

 

                                    

 

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

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

 

Пошаговая детализация

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

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

 

1 этап.

2 этап.

 

3 этап.

 

 

 

 

 

 

 

4 этап.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Виды блок-схем

Приведем примеры построения блок-схем алгоритмов для решения некоторых задач.

Задача 1. Даны координаты трех точек A(x1,y1), B(x2,y2), C(x3,y3). Найти расстояния между этими точками.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Блок-схема, которая состоит  только из блоков обмена информацией и функциональных блоков называется линейной.

 

Задача 2. Даны три числа. Определить, могут ли эти числа  быть длинами сторон треугольника.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Блок-схема, в которой присутствуют базовые структуры следование и  ветвления, называется ветвящейся.

Задача 3. Даны два целых числа  А и В. Найти наибольший общий  делитель этих чисел по алгоритму  Евклида.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                                                          

 

 

 

 

Блок-схема, в которой  присутствует хотя бы одна циклическая  базовая структура, называется циклической.

 

 

Представление алгоритмов в виде программ.

Алгоритм – это  точно определенное описание способа  решения задачи в виде конечной по времени последовательности действий. Такое описание называют формальным. Для представления алгоритма в виде, понятном для компьютера, служат языки программирования.

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

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

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

Процесс нахождения ошибок в программе называется тестированием, а процесс исправления ошибок – отладкой программы.

Трансляторы делятся  на компиляторы и интепретаторы. Они отличаются порядком действия над операторами.

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

Компиляторы полностью обрабатывают весь текст программы в поисках синтаксических ошибок. И только после исправления синтаксических ошибок во всем тексте программы начинается выполнение программы. В рензультате программы, которые транслируются с помощью компиляторов, работают быстрее.

В реальных системах прогораммирования  перемешены технологии и компиляции, и интерпретации. Поэтому в процессе отладки программы она может  выполняться по шагам.

Разные типы процессоров  имеют разные наборы команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его  особенности, то такой язык программирования называется языком программирования низкого уровня. В данном случае “низкий” не обозначает плохой. Имеется в виду, что операторы такого языка программирования очень близки к машинным кодам и ориентированы на конкретные команды процессора. Примером может служить язык прогнраммирования Ассемблер, который просто представляет каждую команду машинного кода, но не в виде чисел, а с помощью символьных условных обозначений, называемых мнемониками. Так как наборы инструкций для каждой модели процессора отличаются, то конкретной компьютерной архитектуре соответствует свой язык ассемблера, и написанная на нем программа может быть использована только  в компьютерах с такой моделью процессора.

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

Языки программирования высокого уровня значительно ближе и понятней человеку. Особенности конкретных компьютерных архитектур у них не учитываются. Разрабатывать программы на языках высокого уровня значительно легче и проще, а ошибок при создании программ допускается значительно меньше. Разрабатывать программы на языках высокого уровня значительно проще и допускается меньше ошибок. К языкам высокого уровня можно отнести такие Фортран (Fortran), Бейсик (Basic), Паскаль (Pascal), Си (C), Си++(C++), Джава (Java) и многие другие.

Примером языка высокого уровня является язык программирования Паскаль. Этот язык был создан профессором  Тюрихского Федерального технологического института Николаусом Виртом. Этот  язык был назван в честь известного французского математика и философа Блеза Паскаля (1623 – 1662). Блез Паскаль в 1643 году создал первый в мире настольный счетный механизм – арифмометр.

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

Популярности языка  Паскаль среди программистов  способствовали следующие факторы:

1.Благодаря своей компактности  и удачному первоначальному описанию  Паскаль оказался достаточно  легким для изучения.

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

3.Язык позволяет четко  реализовать идеи структурного  программирования и структурной организации данных.

4.Паскаль сыграл большую  роль в развитии методов аналитического  доказательства правильности программ  и позволил реально перейти  от методов отладки программ  к системам автоматической проверки  правильности программ.

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

6.Использование в Паскаль простых и гибких структур управления: ветвления, циклов.

 

 

Современные системы  программирования.

Трудоемкость создания сложных компьютерных программ и  разнообразие средств, используемых в  процессе разработки программы, компиляции и отладки, привело в 80-х годах ХХ века к созданию интеграции этих средств. В те годы фирма Borland International (США) разработала систему Тurbo Pascal, которую называют интегрированной средой программирования, так как она объединяет в себе возможности ранее разрозненных средств, используемых при разработке программ:

1.Редактора текстов программ, который позволяет вносить исправления в текст программы, выделять отдельные фрагменты программы, копировать эти фрагменты, удалять, восстанавливать, выделять цветом отдельные слова, поддержка мыши, возможность открытия окон, которые можно перемещать и изменять в размере и т.п.

2.Компилятора программ.

3.Отладчика программ.

4.Справочной системы языка.

 

 «Модель – алгоритм - программа» - методологический принцип решения задач на компьютере.

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