Контакты
Главная › ›

Русский алгоритмический язык. Алгоритмические языки и программирование. Базовая структура ветвление

Министерство образования Российской Федерации Пермский Государственный технический университет

Кафедра информационных технологий и автоматизированных систем

Викентьева О. Л.

Конспект лекций по курсу «Алгоритмические языки и программирование» (Основы языка С++, I семестр)

Введение

В первом семестре рассматриваются основные конструкции языка Си и базовая технология программирования (структурное программирование).

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

1.1. Алгоритм и программа

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

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

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

1.2.Свойства алгоритма

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

2. Результативность: алгоритм должен приводить к получению результата за конкретное число шагов (при делении 1 на 3 получается периодическая дробь 0,3333(3), для достижения конечного результата надо оговорить точность получения этой дроби, например, до 4 знака после запятой).

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

4. Дискретность – процесс должен быть описан с помощью неделимых

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

Алгоритмы можно представить в следующих формах:

1) словесное описание алгоритма.

2) графическое описание алгоритма.

3) с помощью алгоритмического языка программирования

1.2. Компиляторы и интерпретаторы

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

ходу работы, переводя каждый оператор на машинный язык.

1.3.Языки программирования

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

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

Языками высокого уровня являются:

1. Фортран – первый компилируемый язык, созданный в 50-е годы 20 века. В нем были реализован ряд важнейших понятий программирования. Для этого языка было создано огромное количество библиотек, начиная от статистических комплексов и заканчивая управлением спутниками, поэтому он продолжает использоваться во многих организациях.

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

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

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

5. Си – был создан в 70- е годы первоначально не рассматривался как массовый язык программирования. Он планировался для замены ассемблера, чтобы иметь возможность создавать такие же эффективные и короткие программы, но не зависеть от конкретного процессора. Он во многом похож на Паскаль и имеет дополнительные возможности для работы с памятью. На нем написано много прикладных и системных программ, а также операционная система Unix.

6. Си++ - объектно-ориентированное расширение языка Си, созданное Бьярном Страуструпом в 1980г.

7. Java – язык, который был создан компанией Sun в начале 90-х годов на основе Си++. Он призван упростить разработку приложений на СИ++ путем исключения из него низкоуровневых возможностей. Главная особенность языка – это то, что он компилируется не в машинный код, а в платформно-независимый байт-код (каждая команда занимает один байт). Этот код может выполняться с помощью интерпретатора – виртуальной Java-машины (JVM).

2.Структура программы на Си++

Программа на языке Си имеет следующую структуру: #директивы препроцессора

. . . . . . . . .

#директивы препроцессора функция а ()

операторы функция в ()

операторы

void main () //функция, с которой начинается выполнение программы операторы

описания

присваивания

функция пустой оператор

составной

перехода

Директивы препроцессора - управляют преобразованием текста программы до ее компиляции. Исходная программа, подготовленная на СИ в виде текстового файла, проходит 3 этапа обработки:

1) препроцессорное преобразование текста;

2) компиляция;

3) компоновка (редактирование связей или сборка).

После этих трех этапов формируется исполняемый код программы. Задача препро-

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

1) #define - указывает правила замены в тексте. #define ZERO 0.0

Означает, что каждое использование в программе имени ZERO будет заменяться

2) #include< имя заголовочного файла> - предназначена для включения в текст программы текста из каталога «Заголовочных файлов», поставляемых вместе со стандартными библиотеками. Каждая библиотечная функция Си имеет соответствующее описание в одном из заголовочных файлов. Список заголовочных файлов определен стандартом языка. Употребление директивы include не подключает соответствующую стандартную биб-

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

После выполнения препроцессорной обработки в тексте программы не остается ни одной препроцессорной директивы.

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

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

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

int y = 10 ; //именованная константа float x ; //переменная

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

Операторы - определяют действия программы на каждом шаге ее исполне-

Пример программы на Си:

#include //препроцессорная директива

Контрольные вопросы

1. Из каких частей состоит программа на С++?

2. Чем определение отличается от объявления?

3. Перечислить этапы создания исполняемой программы на языке С++.

4. Что такое препроцессор?

5. Что такое директива препроцессора? Привести примеры директив препроцессора.

6. Составить программу, которая печатает текст «Моя первая программа на С++»

2. Базовые средства языка СИ++ 2.1.Состав языка

В тексте на любом естественном языке можно выделить четыре основных элемента: символы, слова, словосочетания и предложения. Алгоритмический язык также содержит такие элементы, только слова называют лексемами (элементарными конструкциями), словосочетания – выражениями, предложения – операторами. Лексемы образуются из символов, выражения из лексем и символов, операторы из символов выражений и лексем (Рис. 1.1)

Рис. 1.1. Состав алгоритмического языка Таким образом, элементами алгоритмического языка являются:

Идентификаторы – имена объектов СИ-программ. В идентификаторе могут быть использованы латинские буквы, цифры и знак подчеркивания. Прописные и строчные буквы различаются, например, PROG1, prog1 и Prog1 – три различных идентификатора. Первым символом должна быть буква или знак подчеркивания (но не цифра). Пробелы в идентификаторах не допускаются.

Ключевые (зарезервированные) слова – это слова, которые имеют специальное значение для компилятора. Их нельзя использовать в качестве идентификаторов.

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

Константы – это неизменяемые величины. Существуют целые, вещественные, символьные и строковые константы. Компилятор выделяет константу в качестве лексемы (элементарной конструкции) и относит ее к одному из типов по ее внешнему виду.

Разделители – скобки, точка, запятая пробельные символы.

2.1.1. Константы в Си++

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

Константы делятся на 5 групп:

Целые;

- вещественные (с плавающей точкой);

Перечислимые;

Символьные;

Строковые.

Компилятор выделяет лексему и относит ее к той или другой группе, а затем вну-

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

Целые константы могут быть десятичными, восьмеричными и шестнадцатеричными. Десятичная константа определяется как последовательность десятичных цифр, начинающаяся не с 0, если это число не 0 (примеры: 8, 0, 192345). Восьмеричная константа – это константа, которая всегда начинается с 0. За 0 следуют восьмеричные цифры (примеры: 016 – десятичное значение 14, 01). Шестнадцатеричные константы – последовательность шестнадцатеричных цифр, которым предшествуют символы 0х или 0Х (примеры: 0хА, 0Х00F).

В зависимости от значения целой константы компилятор по-разному представит ее

в памяти компьютера (т. е. компилятор припишет константе соответствующий тип данных).

Вещественные константы имеют другую форму внутреннего представления в памяти компьютера. Компилятор распознает такие константы по их виду. Вещественные константы могут иметь две формы представления: с фиксированной точкой и с плавающей точкой. Вид константы с фиксированной точкой:[цифры].[цифры] (примеры: 5.7, . 0001, 41.).Вид константы с плавающей точкой: [цифры][.][цифры]E|e[+|-][цифры] (приме- ры:0.5е5, .11е-5, 5Е3). В записи вещественных констант может опускаться либо целая, либо дробная части, либо десятичная точка, либо признак экспоненты с показателем степени.

Перечислимые константы вводятся с помощью ключевого слова enum. Это обычные целые константы, которым приписаны уникальны и удобные для использования обозначения. Примеры: enum { one=1, two=2, three=3,four=4};

enum {zero,one,two,three} – если в определении перечислимых констант опустить знаки = и числовые значения, то значения будут приписываться по умолчанию. При этом самый левый идентификатор получит значение 0, а каждый последующий будет увеличиваться на 1.

enum { ten=10, three=3, four, five, six};

enum {Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Satur-

Символьные константы – это один или два символа, заключенные в апострофы. Символьные константы, состоящие из одного символа, имеют тип char и занимают в памяти один байт, символьные константы, состоящие из двух символов, имеют тип int и занимают два байта. Последовательности, начинающиеся со знака \ , называются управляющими, они используются:

- Для представления символов, не имеющих графического отображения, например:

\a – звуковой сигнал,

\b – возврат на один шаг, \n – перевод строки,

\t – горизонтальная табуляция.

- Для представления символов: \ , ’ , ? , ” (\\, \’ ,\? ,\”).

- Для представления символов с помощью шестнадцатеричных или восьмеричных кодов (\073, \0хF5).

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

Внутри строк также могут использоваться управляющие символы. Например: “\nНовая строка”,

“\n\”Алгоритмические языки программирования высокого уровня \”” .

2.2. Типы данных в Си++

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

1) внутреннее представление данных в памяти компьютера;

2) множество значений, которые могут принимать величины этого типа;

3) операции и функции, которые можно применять к данным этого типа.

В зависимости от требований задания программист выбирает тип для объектов программы. Типы Си++ можно разделить на простые и составные. К простым типам относят типы, которые характеризуются одним значением. В Си++ определено 6 простых типов данных:

int (целый)

char (символьный)

wchar_t (расширенный символьный) bool (логический) float(вещественный)

double (вещественный с двойной точностью)

Существует 4 спецификатора типа, уточняющих внутреннее представление и диапазон стандартных типов

short (короткий) long (длинный) signed (знаковый)

unsigned (беззнаковый)

2.2.1. Тип int

Значениями этого типа являются целые числа.

Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 16-разрядного процессора под него отводится 2 байта, для 32-разрядного – 4 байта.

Если перед int стоит спецификатор short, то под число отводится 2 байта, а если спецификатор long, то 4 байта. От количества отводимой под объект памяти зависит множество допустимых значений, которые может принимать объект:

short int - занимает 2 байта, следовательно, имеет диапазон –32768 ..+32767;

long int – занимает 4 байта, следовательно, имеет диапазон –2 147 483 648..+2 147 483 647

Тип int совпадает с типом short int на 16-разрядных ПК и с типом long int на 32разрядных ПК.

Модификаторы signed и unsigned также влияют на множество допустимых значений, которые может принимать объект:

unsigned short int - занимает 2 байта, следовательно, имеет диапазон 0 ..65536; unsigned long int – занимает 4 байта, следовательно, имеет диапазон 0..+4 294 967

2.2.2. Тип char

Значениями этого типа являются элементы конечного упорядоченного множества символов. Каждому символу ставится в соответствие число, которое называется кодом символа. Под величину символьного типа отводится 1 байт. Тип char может использоваться со спецификаторами signed и unsigned. В данных типа signed char можно хранить значения в диапазоне от –128 до 127. При использовании типа unsigned char значения могут находиться в диапазоне от 0 до 255. Для кодировки используется код ASCII(American Standard Code foe International Interchange). Символы с кодами от 0 до 31 относятся к служебным и имеют самостоятельное значение только в операторах ввода-вывода.

Величины типа char также применяются для хранения чисел из указанных диапазо-

2.2.3. Тип wchar_t

Предназначен для работы с набором символов, для кодировки которых недостаточно 1 байта, например Unicode. Размер этого типа, как правило, соответствует типу short. Строковые константы такого типа записываются с префиксом L: L“String #1”.

2.2.4. Тип bool

Тип bool называется логическим. Его величины могут принимать значения true и false. Внутренняя форма представления false – 0, любое другое значение интерпретируется как true.

2.2.5. Типы с плавающей точкой.

Внутреннее представление вещественного числа состоит из 2 частей: мантиссы и порядка. В IBM-совместимых ПК величины типа float занимают 4 байта, из которых один разряд отводится под знак мантиссы, 8 разрядов под порядок и 24 – под мантиссу.

Величины типы double занимают 8 байтов, под порядок и мантиссу отводятся 11 и 52 разряда соответственно. Длина мантиссы определяет точность числа, а длина порядка его диапазон.

Если перед именем типа double стоит спецификатор long, то под величину отводится байтов.

2.2.6. Тип void

К основным типам также относится тип void Множество значений этого типа – пу-

2.3. Переменные

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

Общий вид оператора описания:

[класс памяти]тип имя [инициализатор];

Класс памяти может принимать значения: auto, extern, static, register. Класс памяти определяет время жизни и область видимости переменной. Если класс памяти не указан явно, то компилятор определяет его исходя из контекста объявления. Время жизни может быть постоянным – в течение выполнения программы или временным – в течение блока. Область видимости – часть текста программы, из которой допустим обычный доступ к переменной. Обычно область видимости совпадает с областью действия. Кроме того случая, когда во внутреннем блоке существует переменная с таким же именем.

Const – показывает, что эту переменную нельзя изменять (именованная константа). При описании можно присвоить переменной начальное значение (инициализация). Классы памяти:

auto –автоматическая локальная переменная. Спецификатор auto может быть задан только при определении объектов блока, например, в теле функции. Этим переменным память выделяется при входе в блок и освобождается при выходе из него. Вне блока такие переменные не существуют.

extern – глобальная переменная, она находится в другом месте программы (в другом файле или долее по тексту). Используется для создания переменных, которые доступны во всех файлах программы.

static – статическая переменная, она существует только в пределах того файла, где определена переменная.

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

int a; //глобальная переменная void main(){

int b;//локальная переменная

extern int x;//переменная х определена в другом месте static int c;//локальная статическая переменная a=1;//присваивание глобальной переменной

int a;//локальная переменная а

a=2;//присваивание локальной переменной::a=3;//присваивание глобальной переменной

int x=4;//определение и инициализация х

В примере переменная а определена вне всех блоков. Областью действия переменной а является вся программа, кроме тех строк, где используется локальная переменная а. Переменные b и с – локальные, область их видимости – блок. Время жизни различно: память под b выделяется при входе в блок (т. к. по умолчанию класс памяти auto), освобождается при выходе из него. Переменная с (static) существует, пока работает программа.

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

Имя переменной должно быть уникальным в своей области действия.

Описание переменной может быть выполнено или как объявление, или как определение. Объявление содержит информацию о классе памяти и типе переменной, определение вместе с этой информацией дает указание выделить память. В примере extern int x; - объявление, а остальные – определения.

2.4.Знаки операций в Си++

Знаки операций обеспечивают формирование выражений. Выражения состоят из операндов, знаков операций и скобок. Каждый операнд является, в свою очередь, выражением или частным случаем выражения – константой или переменной.

Унарные операции

& получение адреса операнда

* Обращение по адресу (разыменование)

- унарный минус, меняет знак арифметического операнда

++ Увеличение на единицу:

префиксная операция - увеличивает операнд до его использо-

постфиксная операция увеличивает операнд после его исполь-

int a=(m++)+n; // a=4,m=2,n=2

int b=m+(++n);//a=3,m=1,n=3

уменьшение на единицу:

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

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

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

имеет операнд

имеет две формы

sizeof выражение

sizeof(float)//4

sizeof(1.0)//8, т. к. вещественные константы по умолчанию

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

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

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

Алгоритм, записанный на алгоритмическом языке, должен иметь название. Назва­ние желательно выбирать так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для выделения названия алгоритма перед ним записывают служеб­ное слово АЛГ (АЛГоритм). За названием алгоритма (обычно с новой строки) записывают его команды. Для указания начала и конца алгоритма его команды заключают в пару служебных слов НАЧ (НАЧало) и КОН (КОНец). Команды записывают последовательно.

АЛГ – название алгоритма

серия команд алгоритма

Например, алгоритм, определяющий движение исполнителя-робота, может иметь вид:

АЛГ – в_склад

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

Очень часто при составлении алгоритмов возникает необходимость использования в качестве вспомогательного одного и того же алгоритма, который к тому же может быть весьма сложным и громоздким. Было бы нерационально, начиная работу, каждый раз заново составлять и запоминать такой алгоритм для его последующего использования. Поэтому в практике широко используют так называемые встроенные (или стандартные) вспомогательные алгоритмы, т.е. такие алгоритмы, которые постоянно имеются в распоряжении исполнителя. Обращение к таким алгоритмам осуществляется так же, как и к «обычным» вспомогательным алгоритмам. У испол­нителя-робота встроенным вспомогательным алгоритмом может быть перемещение в склад из любой точки рабочего поля; у исполнителя-языка программирования Бейсик – это, например, встроенный алгоритм «SIN».

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

АЛГ – движение

движение

Алгоритмы, при исполнении которых порядок следования команд определяется в зависимости от результатов проверки некоторых условий, называютразветвляющи­мися. Для их описания в алгоритмическом языке используют специальную составную команду – командуветвления. Применительно к исполнителю-роботу условием может быть проверка нахождения робота у края рабочего поля (край/не_край); проверка наличия объекта в текущей клетке (есть/нет) и некоторые другие:

ЕСЛИ условие ЕСЛИ условие ЕСЛИ край

ТО серия1 ТО серия ТО вправо

ИНАЧЕ серия2 ВСЕ ИНАЧЕ вперед

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

ПРИ условие 1: серия 1

ПРИ условие 2: серия 2

ПРИ условие N: серия N

ИНАЧЕ серия N+1

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

ПОКА условие НЦ

серия ДО условие

Алгоpитм -- точное и понятное пpедписание исполнителю совеpшить последовательность действий, направленных на решение поставленной задачи.

Название "алгоритм" произошло от латинской формы имени среднеазиатского математика аль-Хорезми -- Algorithmi. Алгоритм -- одно из основных понятий информатики и математики.

Исполнитель алгоритма -- это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя хаpактеpизуют:

элементаpные действия;

cистема команд;

Сpеда (или обстановка) -- это "место обитания" исполнителя. Напpимеp, для исполнителя Pобота из школьного учебника сpеда -- это бесконечное клеточное поле. Стены и закpашенные клетки тоже часть сpеды. А их pасположение и положение самого Pобота задают конкpетное состояние среды.

Каждый исполнитель может выполнять команды только из некотоpого стpого заданного списка -- системы команд исполнителя. Для каждой команды должны быть заданы условия пpименимости (в каких состояниях сpеды может быть выполнена команда) и описаны pезультаты выполнения команды. Напpимеp, команда Pобота "ввеpх" может быть выполнена, если выше Pобота нет стены. Ее pезультат -- смещение Pобота на одну клетку ввеpх.

После вызова команды исполнитель совеpшает соответствующее элементаpное действие.

Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.

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

В информатике универсальным исполнителем алгоритмов является компьютер.

Основные свойства алгоритмов следующие:

Понятность для исполнителя -- т.е. исполнитель алгоритма должен знать, как его выполнять.

Дискpетность (прерывность, раздельность) -- т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

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

Pезультативность (или конечность). Это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.

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

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

словесная (записи на естественном языке);

графическая (изображения из графических символов);

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

программная (тексты на языках программирования).

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

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм может быть следующим:

задать два числа;

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

определить большее из чисел;

заменить большее из чисел разностью большего и меньшего из чисел;

повторить алгоритм с шага 2.

Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75.

Словесный способ не имеет широкого распространения по следующим причинам:

такие описания строго не формализуемы;

страдают многословностью записей;

допускают неоднозначность толкования отдельных предписаний.

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

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

В таблице 1 приведены наиболее часто употребляемые символы.

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

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

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

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

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

Он занимает промежуточное место между естественным и формальным языками.

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

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

Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г. Кушниренко и др. "Основы информатики и вычислительной техники", 1991. Этот язык в дальнейшем мы будем называть просто "алгоритмический язык".

Основные служебные слова

Общий вид алгоритма:

алг название алгоритма (аргументы и результаты)

дано условия применимости алгоритма

надо цель выполнения алгоритма

нач описание промежуточных величин

| последовательность команд (тело алгоритма)

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

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

Примеры предложений алг:

алг Объем и площадь цилиндра (арг вещ R, H, рез вещ V, S)

алг Корни КвУр(арг вещ а, b, c, рез вещ x1, x2, рез лит t)

алг Исключить элемент(арг цел N, арг рез вещ таб А)

алг Диагональ(арг цел N, арг цел таб A, рез лит Otvet)

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

алг Замена (арг лит Str1, Str2, арг рез лит Text)

дано | длины подстрок Str1 и Str2 совпадают

надо | всюду в строке Text подстрока Str1 заменена на Str2

алг Число максимумов (арг цел N, арг вещ таб A, рез цел K)

дано | N>0

надо | К - число максимальных элементов в таблице А

алг Сопротивление (арг вещ R1, R2, арг цел N, рез вещ R)

дано | N>5, R1>0, R2>0

надо | R - сопротивление схемы

Здесь в предложениях дано и надо после знака "|" записаны комментарии. Комментарии можно помещать в конце любой строки. Они не обрабатываются транслятором, но существенно облегчают понимание алгоритма.

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

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

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

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

следование,

ветвление,

Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.

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

Для изучения основ алгоритмизации применяется так называемый Русский алгоритмический язык (школьный алгоритмический язык), использующий понятные школьнику слова на русском языке.

Алголо-подобный алгоритмический язык с русским синтаксисом был введён в употребление академиком А. П. Ершовым в середине 1980-х годов, в качестве основы для «безмашинного» курса информатики.

Основные служебные слова алгоритмического языка

Описание алгоритма

  • алг (алгоритм)
  • арг (аргумент)
  • рез (результат)
  • нач (начало) — начало алгоритма
  • кон (конец) — конец алгоритма
  • дано — исходные данные в произвольной форме
  • надо — цель алгоритма

Типы данных:

  • цел (целый)
  • вещ (вещественный)
  • сим (символьный)
  • лит (литера) — строка
  • лог (логический)
  • таб (таблица) — для обозначения массива
  • длин (длина) — количество элементов массива

Обозначение условий

  • если
  • иначе
  • выбор
  • знач

Обозначение циклов

  • нц (начало цикла)
  • кц (конец цикла)
  • пока

Логические функции и значения для составления выражений

Ввод-вывод

  • ввод
  • вывод

Общий вид алгоритма

1
2
3
4
5
6

алг название алгоритма (аргументы и результаты)
| дано условия применимости алгоритма
| надо цель выполнения алгоритма
нач описание промежуточных величин
| последовательность команд (тело алгоритма)
кон

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

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

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

Основные алгоритмические структуры

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

| если условие
| | то действия
| всё

Полная развилка

1
2
3
4
5

| если условие
| | то действия 1
| | иначе действия 2
| всё

Ветвление

1
2
3
4
5
6
7
8

| выбор параметр
| | при знач значение 1
| | | действия 1
| | при знач значение 2
| | | действия 2
| | иначе
| | | действия по умолчанию
| всё

Цикл с предусловием

| нц пока условие
| | действия
| кц

Цикл с постусловием

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

Изучение в школе

Зачастую в школах изучается алгоритмический язык, наиболее известный как учебный. Он получил масштабное распространение благодаря тому, что в нем используются максимально понятные любому ученику слова. Подобный язык с синтаксисом на русском был введен давно, а именно в середине 1980-х годов. Его применяли для того, чтобы дать основу школьникам и преподавать им без компьютера курс информатики. Опубликован данный язык был в 1985 году в одном из учебников. Также его перепечатали несколько раз и для специальных книг, которые предназначались для обучения в 9 и 10 классах. Общий тираж издания составил 7 млн экземпляров.

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

Прежде всего необходимо записать буквосочетание АЛГ. Далее следует название алгоритма. Затем после НАЧ нужно описать серию команд. Оператор КОН означает конец программы.

Описание алгоритма на алгоритмическом языке:

АЛГ Компания

НАЧ

поворот на 90 градусов влево

КОН

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

Составление алгоритмов

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

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

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

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

Алгоритмы, которые имеют определенный порядок следования команд, постоянно могут меняться в зависимости от результатов выполнения специальных частей программы. Такие системы называются разветвляющимися. Для того чтобы их создать, необходимо использовать специальную команду ветвления. Она имеет сокращенную и полную схему написания. Нередко встречаются циклические алгоритмы, которые выполняют особые команды по несколько раз.

E-практикум

Для того чтобы усовершенствовать изучение теории по грамматическому языку, профессионалы мехмата МГУ в 1985 году создали специальный компилятор. Он получил название "E-практикум". С его помощью можно было вводить, изменять и выполнять программы. На следующий год был выпущен определенный комплект исполнителей. Речь идет о «Роботе», «Чертежнике», «Двуногом», «Вездеходе». Это позволило просто и с легкостью реализовывать алгоритмы. Данный компилятор получил огромное распространение, был использован на некоторых компьютерах. Довольно долгое время этот язык программирования дорабатывался и изменялся. В 1990 году его более поздний вариант появился в учебнике.

Кумир

Сейчас школьный алгоритмический язык переживает свое второе рождение, после того как был разработан специальный пакет «Кумир» для Windows и Linux. Система функционирует с несколькими исполнителями. Классическими среди них являются «Робот», «Чертежник». Этот же пакет входит в установочный файл Linux «Школьный». Данная система разработана была специально по заказу Российской Академии наук. Она распространяется бесплатно и свободно. Последние несколько лет описываемый язык активно предлагают использовать в ЕГЭ как один из

Назначение языка

Алгоритмический язык используется для решения довольно большого круга задач. Он подходит для освоения как математических, так и упражнений по другим предметам. Нужно заметить, что он также используется для более простого изучения школьниками подобных тем.

Различия машинного и алгоритмического языков

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

Стандартные функции

Алгоритмический язык имеет специальные стандартные функции, которые получили статус «встроенных». Именно благодаря им можно с легкостью написать многие операции с числами и выражениями, не выполняя рутинных записей. Программа на алгоритмическом языке довольно проста. Штатные функции могут позволить вычислить квадратный корень, логарифмы, модуль и так далее. Наиболее популярными встроенными методами являются следующие:

  • абсолютный модуль abs(X);
  • корень квадратный sqrt(X);
  • натуральный и ln(X), lg(X);
  • минимум и максимум min (X,Y), max (X, Y);
  • тригонометрические функции sin(X), cos(X), tg(X), ctg(X).

Благодаря этому любой программист или просто человек, который обучается работе с алгоритмическим языком, сможет с легкостью написать математическую задачу, не прибегая к изобретению велосипеда. Таким образом, нужно заметить, что данный язык довольно удобный. Он прост в понимании, а также максимально легок в восприятии. Не зря его внесли в школьную программу. Школьники с удовольствием его изучают.

Корпоратив в отеле в Подмосковье.

Понравилась статья? Поделитесь ей
Рекомендуем статьи по теме
Opus bt c3100 v 2.2 охлаждение. Opus bt-c3100 инструкция по эксплуатации. Инструкция по эксплуатации Opus BT-C3100Opus bt c3100 v 2.2 охлаждение. Opus bt-c3100 инструкция по эксплуатации. Инструкция по эксплуатации Opus BT-C3100
Телефон теле2 не включается в чем причинаТелефон теле2 не включается в чем причина
Tele2 mini описание смартфона и способ разблокировкиTele2 mini описание смартфона и способ разблокировки
Посетители сейчас обсуждают
Настройка типов линии для AutoCAD Пунктирная линия в автокаде отображается сплошнойНастройка типов линии для AutoCAD Пунктирная линия в автокаде отображается сплошной Проблемы
Как настроить яркость экрана?Как настроить яркость экрана? Настройка 
Чем открыть файл.FLAC? Что такое расширение файла FLAC? Расширение флакЧем открыть файл.FLAC? Что такое расширение файла FLAC? Расширение флак Советы
Как удалить пробелы в PHP Удаление лишних пробелов phpКак удалить пробелы в PHP Удаление лишних пробелов php Настройка