Алгоритмы. Способы записи алгоритмов

Алгоритм — точное предписание исполнителю (человеку или автомату) выполнить последовательность действий, направленных на достижение поставленной цели.



Алгоритм всегда составляется для конкретного исполнителя, т. е. для человека или автомата, который может его исполнить.

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

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

• Дискретность. Алгоритм состоит из отдельных команд, которые выполняются последовательно, начало и конец их выполнения строго фиксированы.

« Понятность. Команды алгоритма должны быть полностью понятны исполнителю.

• Точность. После выполнения каждой команды точно известно, завершено ли выполнение алгоритма или нужно перейти к следующей команде.

• Результативность. Алгоритм завершается либо достижением цели, либо обнаружением невозможности решения задачи.

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

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

Для того чтобы алгоритм мог выполняться автоматом, его надо записать в той форме, в которой автомат его сможет «читать». Для ЭВМ такой формой является двоичный код.

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

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

Конкретные виды блоков будут упоминаться вместе с соответствующими частями программ.

Язык программирования — формализованный язык, предназначенный для описания алгоритмов решения задач на ЭВМ.

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

Язык программирования низкого уровня — язык программирования, структура команд которого определяется системой команд процессора и архитектурой ЭВМ. Часто эти языки называют языками ассемблера.

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

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

Языки высокого уровня — языки программирования, средства которых допускают описание алгоритма в наглядном виде, т. е. не на основе команд процессора, а на основе слов естественного языка.

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

-

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

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

Существует два вида трансляторов: интерпретаторы и компиляторы.

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

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

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

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

Языки высокого уровня. Basic

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

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

Значение переменной — фактическое значение, находящееся в этой области памяти.

Тип переменной — вид данных, которые переменная может хранить. Каждый тип переменных хранится и обрабатывается по определенным правилам. Тип переменной еще определяет, сколько памяти займет переменная.

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

Оператор — команда, воспринимаемая транслятором как единое целое.

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

Далее основные понятия языков высокого уровня изложены на примере языка Basic (точнее, Microsoft QuickBasic v.4.5).

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

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

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

Тип переменной в языке Basic определяется с помощью последнего символа имени (суффикса). Используются следующие типы переменных:

• ! — дробное число с одинарной точностью;

• # — дробное число с двойной точностью;

• % — целое число;

• & — длинное целое число;

• $ — строка.

Ниже приведены примеры переменных.

Имя

Тип

Norma

Число с плавающей точкой, одинарная точность

Bint%

Целое число

S$

Строка

A#

Число с плавающей точкой, двойная точность

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

В зависимости от типа вычисляемого в выражении итогового результата, говорят о типе выражения.

Числовые выражения — выражения, результатом вычисления которых является число.

Математические операции, доступные в языке Basic

Знак

Операции

Операция

Пример

+

Сложение

А+В

Вычитание

А-В

Умножение

А*В

/

Деление

А/В

Деление нацело

АВ

Mod

Нахождение остатка от деления

A mod В

Л

Возведение в степень

АЛВ

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

В выражениях можно использовать встроенные математические функции:

• sin(x) — синус числа х;

• cos(x) — косинус числа х;

• tan(x) — тангенс числа х;

• atn(x) — арктангенс числа х;

• abs(x) — модуль числа х;

• sqr(x) — корень квадратный из числа х.

В тригонометрических функциях аргумент

Выражается в радианах.

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

Примеры записи числовых выражений

Математическая запись

Запись на языке Basic

А + Ь + 4,5 cd

А + b + 4.5*c*d

A + b cb

(а + Ь)/(с * Ь)

Х5 + sin2 х • cos у2

ХЛ5 + (sin(x)A2) * (cos(y"2))

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

Для составления строковых выражений можно использовать:

• строки-константы, записанные в двойных кавычках;

• функции, возвращающие строки;

• операцию «склеивания» (конкатенацию) двух строк (записывается как сложение).

Строковые функции

Len(A$)

Длина строки A$. Внимание: длина строки А$ — число!

Left$(A$,N)

Первые N символов строки А$

Right$(A$,N)

Последние N символов строки А$

Mid$(A$,P, N)

N символов строки А$, начиная с символа номер Р

Str$(N)

Строка, содержащая запись числа N

Val(S$)

Число, записанное в строке S$

Примеры строковых выражений

"Привет!"

«Привет!»

Left$("npHBeT’3)

«При»

МЮ$("12345",3,2)

«34»

"Вася"+сЬг$(32)+”Синицын"

«Вася Синицын»

Логические выражения в языке Basic строятся из элементарных условий с помощью обычных логических операций, результат — значения ИСТИНА или ЛОЖЬ.

Элементарными называют условия, сравнивающие выражения между собой.

Примеры условий

А>=0

А — неотрицательно

(А>=10)AND(A< 15)

А 6 [10,15)

(XO0)AND(X<0.5)

X - 0, X меньше 1/2

(X<2)AND(X>5)

Противоречивое условие.

Всегда имеет значение «ложь».

Основные операторы и синтаксические конструкции

Присваивание. В результате выполнения этого оператора переменной присваивается (иногда говорят —
записывается) некоторое значение. Значение может быть предварительно вычислено.

Пример 1. Записать в переменную А значение 15, умноженное на содержимое переменной В.

Пример 2. Увеличить значение в переменной А на единицу.

Блок-схема

Basic

1

А = А + 1

А = А + 1

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

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

Условие (ветвление). Так называется ситуация выбора одного из двух путей продолжения действий, как правило, в случае выполнения некоторого условия.

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

Оператор условия в краткой форме

Пример 4. Если А > О, то вывести сообщение о том, что значение этой переменной положительно.

Basic

подпись: basicБлок-схема

Оператор условия в полной форме

_

подпись: _Пример 5. Если А> 0, то вывести сообщение о том, что это значение неотрицательное; иначе — сообщение о том, что оно положительное.

Basic

подпись: basic

Блок-схема

подпись: блок-схемаIf А >= 0 then Print

"A — неотрицательное" Else Print "A — отрица тельное"

End if

Вывод «А — отрицательное»

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

В зависимости от вида условия циклы делятся на два основных типа:

• Цикл «Пока» (с предусловием). Цикл выполняется, пока условие истинно. Как правило, условие проверяется перед выполнением тела цикла.

• Цикл «До» (с постусловием). Цикл выполняется, пока условие ложно. Как правило, условие проверяется после тела цикла

Важный частный случаи цикла — определенный цикл.

Определенным циклом считается цикл, в котором условие наложено на количество повторений цикла, т. е. определенный цикл повторяется заданное количество раз. Переменная, которая отслеживает количество повторений называется счетчиком цикла.

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

Оператор цикла «Пока» (с предусловием)

Basic

подпись: basicП р и м е р 6. Повторять ввод строки в переменную а$, пока там не появится значение пароля. Если в переменной уже есть это значение, то цикл не выполнится.

Блок-схема

Оператор цикла «До» (с постусловием)

Пример 7. Повторять ввод строки в переменную а$, до появления в ней значения пароль. Цикл выполнится хотя бы один раз.

Запись на языке Basic.

Do Input "Пароль?";а$ Loop until a$ = "пароль".

Оператор цикла с параметром (определенный цикл)

Пример 8. Вывести на экран числа от 1 до 10.

Запись на языке Basic.

For I = 1 to 10 Print I Next I.

Ниже приводится пример законченной программы на языке Basic.

Решение квадратного уравнения

Любое квадратное уравнение может быть записано в виде ах2 + Ьх + с = 0. Количество его решений зависит от значения дискриминанта

D = Ъ2 - 4ас.

Если дискриминант положителен (D > 0), то уравнение имеет два действительных корня:

_-b±J3

Если дискриминант равен нулю (D = 0), то

Решение одно: х = ^ .

Если дискриминант отрицателен (D < 0), то действительных корней это уравнение не имеет.

Rem Программа решения квадратных уравнений Input "Коэффициент А"; А Input "Коэффициент В"; В Input "Коэффициент С"; С D = В*В - 4*А*С If D > 0 then Х1 = (-b-sqr(d))/(2*a)

Х2 = (-b+sqr(d))/(2*a)

Print "Х1 = "; Х1 Print "Х2 = "; Х2 Else If D = 0 then

Print "X = "; - b/(2*a)

Else

Print "Нет действительных корней."

End if End if End




See also: