Алгоритмизация и основы программирования
Одним из важнейших этапов решения задачи на компьютере после того, как поставлена задача и выбран метод решения, является этап разработки алгоритма. Это самый трудный этап, но и самый интересный и творческий, здесь есть работа для ума. Последующий этап написания программы по разработанному алгоритму уже не требует особых усилий, если, конечно, знать, как это делается.
Понятие алгоритма.
В своей повседневной жизни люди встречаются с различными практическими задачами, например, нужно ли сегодня идти в университет и как до него проехать, как найти нужную аудиторию или перевод нужного слова в словаре, что съесть на завтрак и т.д. Успех любой деятельности человека зависит от того, насколько хорошо продуманы его действия, рассмотрены ли все возможные варианты и выбран ли наилучший в данном конкретном случае, в какой последовательности эти действия будут выполняться. С целью успешного решения какого-либо класса задач выработаны системы предписаний, поведенческие алгоритмы. Например, для успешной сдачи экзамена по информатике необходимо посещать занятия и выполнять все предлагаемые задания. Алгоритмом можно считать и рецепт приготовления праздничного пирога.
Кроме того, алгоритмизация – основной метод кибернетики, рассматривающей процессы управления в различных системах как реализацию определенных алгоритмов.
Что же такое алгоритм вычислительный?
Согласно ГОСТ19781-74 “Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату”.
Свойства алгоритма:
Дискретность,
Понятность,
Детерминированность,
Множественность,
Результативность.
Рассмотрим их более подробно.
Дискретность – разбиение процесса решения задачи на строгую последовательность отдельных шагов (команд, предписаний). Всякая последующая команда выполняется только после завершения предыдущей.
Понятность – ориентированность на определенного исполнителя, т.е. алгоритм может включать команды только из системы команд данного исполнителя.
Детерминированность (определенность) – один и тот же алгоритм, выполняемый разными исполнителями, должен давать один и тот же результат, т.е. алгоритм не должен содержать неоднозначно трактуемых команд.
Множественность (массовость) – возможность алгоритма обеспечивать решение всего класса задач данного типа.
Результативность – алгоритм должен давать решение задачи за конечное число шагов и при этом должен быть получен правильный ответ.
Алгоритмы бывают трех типов:
линейный,
разветвляющийся,
циклический.
Основные способы описания алгоритмов:
словесное описание,
графическое представление в виде блок-схем, элементы которых соответствуют выполняемым предписаниям и представляют собой геометрические фигуры, определенные ГОСТ19781-74.
Реализация алгоритма на языке программирования – это программа. Мы будем рассматривать реализацию алгоритмов на простейшем языке программирования языке BASIC.
Основы языка программирования BASIC.
Символы языка.
Также как изучение любого языка человеческого общения, например, английского, начинается со знакомства с алфавитом, освоение языка программирования требует знания символов, которые применимы в этом языке. Итак символы:
буквы – латинские строчные и прописные, буквы русского алфавита допустимы только в текстовых константах и комментариях;
цифры – только арабские от 0 до 9;
знаки арифметических операций: сложение (+), вычитание (-), умножение (*), деление (/), возведение в степень (^ );
знаки логических операций:
a OR b – «или», логическое сложение, равно «Истина», если истинно a или b
a AND b– «и», логическое умножение, равно «Истина», если и a и b истинны
a XOR b– «исключающее или», равно «Истина», если истинно только a или только b,
NOT b логическое отрицание;
знаки операций отношения:
a>b (больше),
a<b (меньше),
a<=b (меньше или равно),
a>= b (больше или равно),
a=b (равно)
a<>b (не равно);
разделители – ограничители:
знак операции сцепления - +;
встроенные, стандартные функции языка
Константы – «слова» текста программы, интерпретирующиеся как числа (например, 12 или 13.4, обратите внимание на десятичный разделитель) или строки, например, “Строка”. Константы бывают числовые, текстовые (строковые) и логические.
Переменная – это величина, которая в процессе выполнения программы может изменять свое значение, которое хранятся в ячейки памяти. Чтобы обратиться к ячейке памяти нужно в программе указать ее имя. Имя переменной (идентификатор )– это имя ячейки памяти. Идентификаторы могут состоять только из букв латинского алфавита, цифр (цифра не первая), символов подчеркивания. Прописные и строчные буквы считаются одинаковыми. Значением переменой является константа. Переменные, имена которых заканчиваются на знак $, содержат символьные значения, а заканчивающиеся на % (например, К%), содержащих только целые значения.
Типы данных – типы переменных.
Итак мы уже сказали, что константы бывают числовые, текстовые (строковые) и логические. Числовые константы, в свою очередь, делятся на вещественные (действительные) и целые. Вещественные константы могут быть представлены в двух формах записи: в форме с фиксированной точкой, например: 1.25; 0.64; .0085 и в форме с плавающей точкой, т.е. в виде мантиссы и порядка, например: 0.125Е1; 0.85Е-2;
Максимальный размер порядка +32, минимальный –32.
Целочисленная константа состоит только из цифр и предшествующих им знаков « – « или необязательный «+». Максимальный размер целочисленной константы +32768, минимальный - -32768.
Операция – действие, выполняемое процессором с операндами. Операндами могут быть переменные или константы.
Выражения бывают арифметические, логические и символьные.
Арифметическое выражение - это запись, состоящая из имен переменных, числовых констант, встроенных функций, соединенных знаками арифметических операций. Порядок действий такой же как в арифметике: сначала выполняется операции возведения в степень, потом умножения и деления (слева направо), а затем – сложения и вычитания. В арифметическом выражении для изменения естественной последовательности выполнения операций используются скобки, но здесь, в отличии от арифметики, только круглые. Примеры записи арифметических выражений:
(а-с)/5;
(а-с)/(5*а + b/с);
ехр(х) – sin(x^2)/cos(x)^3 + 854.6;
b/((а-с)*64) – это тоже самое, что b/(а-с)/64, но совсем не b/(а-с)*64. Понятно почему? Правильно, порядок действий.
Логическое выражение это запись, состоящая из имен переменных, числовых констант, арифметических выражений, соединенных знаками логических операций и операций отношения. Порядок вычисления логических выражений – сначала вычисляются арифметические выражения, затем выполняются операции отношения, затем логические операции. Круглые скобки могут изменить этот порядок. Примеры записи логических выражений:
a>b OR c=0;
a>10 AND a<100;
(а-с)/5>b^3
Текстовое выражение это запись, состоящая из текстовых констант, текстовых переменных, соединенных операцией сцепления. Примеры записи текстовых выражений:
«Здравствуй» + «Маша» + «!»;
«У меня по информатике» + «5».
Результатом вычисления логического выражения являются логические константы «Истина» (True) или «Ложь» (False).
Оператор – это запись действия на языке программирования. В результате выполнения оператора в ячейку памяти записывается значение, или изменяется ход выполнения программы, или происходит вызов подпрограммы, или иные действия. Об операторах мы будем подробно говорить при изучении алгоритмов, т.к. они являются средством реализации алгоритмов в программе.
Комментарии не вызывают никаких действий в программе. Будучи записаны на родном языке программиста, они полезны для пояснения программы. Компилятор игнорирует их при создании программного модуля. Комментарии начинаются с букв REM или с символа ‘ (апостроф), причем, REM нужно писать только в начале строки, а апостроф можно применить и после оператора, например:
REM начало программы
Или
A=St*Days ‘ расчет стоимости тура.
Строки программы могут быть пронумерованы, это бывает полезно при нелинейной программе
Линейный алгоритм
Алгоритм линейной структуры – алгоритм, в котором команды выполняются последовательно друг за другом в естественном порядке и независимо от каких бы то ни было условий. Для записи линейных программ используются операторы:
ввода; вывода; присваивания; конца программы.
Примером линейного алгоритма может служить, например, простейший диалог, состоящий из оператор ввода, вывода, присваивания и конца программы.
Если, например, вводимые значения переменных будут:
P$ - “Добрый день”; O$ - “ дорогая “; NN$ - “Машенька!”, то в результате выполнения операций сцепления переменной XX$ будет присвоено значение “Добрый день, дорогая Машенька!”, что и будет выведено на экран.
Рис. 1. Линейный алгоритм формирования и вывода приветствия.
Какие операторы языка Basic необходимо знать, чтобы написать линейную программу?
Оператор присваивания
Синтаксис:
Имя переменной = выражение
Оператор присваивания работает следующим образом - вычисляется значение выражения, записанного справа от символа присваивания «=» и результат пересылается в ячейку памяти, имя которой записано слева от символа присваивания.
Например,
Х=10 ‘ в ячейке памяти Х будет записано число 10
М= М- 5 ’От значения М отнимается 5 и результат записывается в М
В=(Х/М)^2 ’ в ячейке В будет записано число 4
A$=”Здравствуй,“+” Федя!” ‘ в ячейке А – текст “Здравствуй, Федя!”
Оператор ввода данных с клавиатуры
Синтаксис:
Input список ввода, где элементами списка ввода могут быть константа (текстовая записывается на первом месте и служит как подсказка) и имена переменных, значения которых должны быть заданы. Элементы списка ввода разделяются запятыми. Например:
INPUT “Введите три числа”, А, В, С
На экран будет выдан запрос: «Введите три числа», а затем программа остановится, ожидая ввод. Чтобы продолжить программу, надо последовательно ввести в одну строку три числа через запятую. При вводе символа, который не может быть числом, программой будет выдано сообщение об ошибке.
Оператор вывода на экран монитора
Синтаксис:
PRINT [список вывода]
где элементами списка вывода могут быть константы, переменные, арифметические или символьные выражения. Если список вывода отсутствует, то выводится пустая строка. Элементы списка вывода могут разделяться запятой или точкой с запятой, что определяет количество пробелов между ними при выводе. Если после последнего элемента списка вывода нет запятой или точки с запятой, то следующий оператор Print выводит свой список на новую строку печати, если есть, то на ту же самую.
Оператор физического окончания программы End.
Программная реализация линейного алгоритма рис.1.:
INPUT “Введите приветствие”, P$
INPUT “Форма обращения”, O$
INPUT “Имя”, NN$
XX$ = P$+”,”+O$+NN$
PRINT XX$
END