Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Технология объектно-ориентированного программирования).pdf

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

Пособие состоит из шести глав.

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

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

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

ГЛАВА I. Основы алгоритмизации

1. 1.1 Понятие алгоритма

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

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

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

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

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

• Результативность. Алгоритм должен приводить к решению задачи или сообщению, что задача решений не имеет за конечное число шагов.

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

• Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма. Например, для решения квадратного уравнения ax 2 +bx+c=0, коэффициенты действительные числа, а ≠ 0, и а, в, с – различные

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

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

а) Словесно-формульный способ. Например, требуется решить квадратное уравнение ax 2 +bx+c=0 в области действительных чисел.

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

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

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

в) Операторный способ (алгоритмический язык). Алгоритм – это задание для исполнителя. Исполнитель выполняет алгоритм, т. е. делает то, что написано в алгоритме. Если исполнитель точно выполнит то, что написано в алгоритме, то он получит результат.

Человек, автоматическое устройство, компьютер – это разные исполнители алгоритмов. Для того чтобы компьютер мог выполнить алгоритм, его надо написать на понятном компьютеру языке. Компьютер понимает машинный язык. Например, равенство х = у на машинном языке имеет вид: 111101110011110111110101.

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

Для того чтобы человек и компьютер понимали друг друга, разработаны специальные языки для записей алгоритмов – алгоритмические языки. Самые известные алгоритмические языки – это Бейсик (Basic), Паскаль (Pascal), Фортран (Fortran).

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

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

Например, можно написать программу решения квадратного уравнения ax ² +bx+c=0 на компьютере. На алгоритмическом языке Бейсик эта программа будет выглядеть так:

REM РЕШЕНИЕ КВАДРАТНОГО УРАВНЕНИЯ

INPUT “введите а,b,c“; А,B,C

D=B-2 - 4*A*C

IF D<0 THEN “РЕШЕНИЙ НЕТ”

Y1=(-B+SQR(D))/(2*A):Y2=(-B-SQR(D))/(2*A)

PRINT “КОРНИ УРАВНЕНИЯ” ;Y1,Y2

1.4. Типы алгоритмов

Алгоритмы бывают линейные, разветвляющиеся и циклические.

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

Линейные алгоритмы в математике – это, например, вычисление площадей фигур.

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

В блок-схемах разветвляющихся алгоритмов всегда есть логический блок.

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

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

ГЛАВА II. Простейшие конструкции языка программирования QBasic

2.1. Алфавит языка

Язык программирования Qbasic (как и любой другой язык) образуют три его составляющие: алфавит, синтаксис и семантика.

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

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

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

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

Алфавит языка включает:

• буквы латинского алфавита от A до Z (строчные и прописные)

• арабские цифры: 0 1 2 … 9

• знаки арифметических операций: + – * / ^ \

• специальные символы объявления типа: % # ! $ &

• круглые скобки ( ) кавычки “ ” апостроф ’ , подчеркивание _

• знаки отношений: < > = < > < = > =

• буквы русского алфавита используются только для записи текстовых констант и комментариев к программе.

2.2. Константы

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

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

Целые константы – это последовательность цифр, перед которой может стоять знак + или – . Например: –567, +29, 29.

Вещественные константы – это числа, имеющие целую и дробную части. Бывают две формы записи вещественных констант: основная и экспоненциальная формы записи. В основной форме записи с фиксированной точкой целая часть числа отделяется от дробной части десятичной точкой, например, -1.012, 3.14159. В экспоненциальной форме записи с «плавающей» точкой число записывается в виде: mE± p, где m – мантисса (число в основной форме), Е – основание 10, р – порядок числа (целая константа, содержащая не более двух цифр).

Например: 2.4Е-05, -2.9Е+07.

Чтобы перейти от экспоненциальной формы к основной, нужно m (мантиссу) умножить на 10 в степени р (порядок).

Например: 2.4Е-5 = 2.4·10-5 = 0.000024, -2,9Е+07 = 2.9·107 = 29000000.

Строковые константы – это набор любых символов длиной, не превышающей 255 символов. Строковая константа заключается в двойные кавычки. Например: “ТАБЛИЦА”, “ALFA_2”,“ Решений нет”.

2.3 Переменные

Переменные – это величины, значения которых могут изменяться в процессе выполнения программы, обозначаются именем (идентификатором). Имя переменной представляется последовательностью не более чем 40 латинских букв и цифр, начинающейся обязательно с буквы и заканчивающейся суффиксом, определяющим тип переменной. Символы типов: % – целый; ! – вещественный; $ – строковый. Если символ типа отсутствует, то переменная по умолчанию считается вещественной. Например: переменные SUM, a, B12, Max, S!, P!, B! – вещественного типа; Z%, D%, A% – целого типа; F$, S$, G$ – строкового типа.

Различают простые переменные и переменные с индексом. Простая переменная определяется только именем. Переменная с индексом является элементом массива, определяется именем и индексами, которые задают 23 местоположение элемента в массиве. Индексы записываются в скобках через запятую после имени переменной. Например: Х(10), А(5,6).

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

2.4. Функции

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