Основы алгоритмизации

REM  Нахождение MAX(X, Y)

INPUT ″Введите значения переменных X,Y ″, X,Y

IF X>Y THEN

Z=X

ELSE

Z=Y

END IF

PRINT ″MAX(X, Y)=″;Z

END

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

Для записи алгоритма решения задачи чаще всего используется графический способ в виде блок-схемы. Менее известен второй способ такого представления алгоритма – диаграмма Насси – Шнейдермана (ее также называют «диаграммой Нэсси – Шнейдермана», «N – S-диаграммой» или «структурограммой»).

В своей статье «Краткая история структурных блок-схем (диаграмм Насси – Шнейдермана)» [1] один из авторов диаграммы Бен Шнейдерман пишет: «Пленительная история и эволюция структурных блок-схем (обычно называемых диаграммами Насси – Шнейдермана, или структурограммами) восходит к 1972 году». Далее он рассказывает, что впервые подумал о создании своих способов записи алгоритмов во время посещения лекции по структурному программированию, когда еще учился в магистратуре. Ему пришло в голову, что если оператор GOTO1 не должен использоваться, то так же не нужны и соединительные линии в старых блок-схемах. Пятнадцать минут вычерчивания привели к первым идеям по оформлению следования, ветвления и циклов. Вместе с аспирантом Исааком Насси, в то время более глубоко знавшим принципы структурного программирования, они написали статью «Технологии блок-схем для структурного программирования» [2], в которой описали свои идеи и представили новый вид графической записи алгоритмов. Статья была опубликована в августе 1973 года.

С тех пор N – S-диаграммы широко используются в ряде стран. Например, в Германии их применение при документировании программ обусловлено требованиями государственного стандарта этой страны.

Очевидные преимущества N – S-диаграмм заключаются в:

      наглядности;

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

      компактности, т.к. даже относительно длинный алгоритм на языке N–S-диаграмм несложно разместить на одной странице;

      простоте использования.

Диаграммы Насси – Шнейдермана строятся с использованием шести элементарных “строительных блоков”: блок действия; блоки с разветвлением; блок множественного выбора; блок цикла с предусловием; блок цикла с постусловием; блок подпрограммы

Алгоритмы линейной структуры

Алгоритм линейной структуры (следование) – алгоритм, в котором все действия выполняются последовательно друг за другом. Такой порядок выполнения действий называется естественным.

Алгоритмы разветвляющейся структуры

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

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

                           полное ветвление                       неполное ветвление

Алгоритмы циклической структуры

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

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

Величина, с изменением которой связано многократное выполнение цикла называется параметром цикла.

Существует 3 вида цикла: цикл с параметром («Для»), цикл с предусловием («Пока») и цикл с постусловием («До»).

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

Здесь x – параметр цикла, x0 – начальное значение параметра цикла, xn – конечное значение параметра цикла, hx – шаг изменения параметра цикла.

Для организации цикло в алгоритмах необходимо предусмотреть:

      подготовку цикла – задание начальных значений переменным цикла перед первым его выполнением;

      тело цикла – действия, повторяемые в цикле для различных значений переменных цикла;

      модификацию/изменение значений переменных цикла перед каждым новым его повторением;

      управление циклом – проверку условия продолжения/окончания цикла и переход на повторение цикла или его окончание.

В зависимости от того, где осуществляется проверка условия продолжения или окончания цикла, последний относят к виду:

      цикла с предусловием, когда цикл начинается с проверки условия продолжения цикла;

      цикла с постусловием, когда условие проверяется после выполнения тела цикла.

Заголовок цикла с параметром включает в себя подготовку цикла (x=x0), изменение параметра цикла при его очередном повторении (x=x+hx), управление циклом – проверку условия его продолжения (x< xn) и переход на продолжение или окончание цикла. Проверка условия x< xn проводится перед каждым, в том числе первым, выполнением цикла, как в цикле с предусловием. И если начальное значение параметра цикла больше конечного, то цикл не выполняется ни разу. Цикл «До» – выполняется хотя бы один раз, т.к. первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено.

Множественный выбор

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

Алгоритмы со структурой вложенных циклов

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

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

Подчиненные алгоритмы

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

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

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

Тема 12. Основные понятия о языках программирования

История развития языка программирования Basic. Алфавит языка QBasic. Переменные и константы. Типы данных. Задание типа данных. Выражения и операции.

История развития языка программирования Basic

Самые первые языки программирования, разработанные в 50-х годах, предназначались, главным образом, для решения сложных математических задач. Разобраться в них «простому смертному» было практически невозможно. Но тогда это не было проблемой, так как компьютеры были только в крупных научно-исследовательских центрах. С развитием электроники, увеличением числа компьютеров, все более широким распространением их в различных областях, сложные языки программирования становятся серьезным препятствием. И вот, в начале 60-х годов в Dartmouth College (США, Т. Куртц и Дж. Кэмени) был создан BASIC. Многие считают, что это английское слово basic – основной. Однако, происхождение этого слова иное – это аббревиатура Beginner's All-purpose Symbolic Instruction Code (BASIC) – многоцелевой код символьных инструкций для начинающих. Ну, или проще и точнее по смыслу – универсальный язык программирования для начинающих.

Первая программа на BASIC, опубликованная Кемени и Куртцем в 1964 г., имела вид.

       10 LET X=(7+8)/3

       20 PRINT X

       30 END

BASIC создавался как язык интерпретирующего типа.

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

В 1975 году появились первые персональные компьютеры «Альтаиры» (MITS Altairs) – началась новая эпоха. Билл Гейтс и Полл Аллен, основатели корпорации Microsoft, создали новую версию Бейсика для Альтаира, способную работать в 4 кб ОЗУ. Эта версия Бейсика стала одной из самых популярных программных продуктов для персональных компьютеров.

Шли годы, Бейсик совершенствовался и развивался. Первые микрокомпьютеры уступили место IBM PC, стандартом для них стал GW-Basic корпорации Microsoft. Впоследствии потребность в более быстром, компактном и простом в работе языке программирования привела к появлению Microsoft QuickBasic. Эта версия подняла Бейсик на уровень технологии 80-х годов, но в компьютерном мире уже намечались большие перемены – был принят стандарт на графический интерфейс пользователя.

В 1979 г. фирмой «Microsoft» была разработана версия языка – MBASIC (распространенное название – BASIC-80), которая получила известность также благодаря созданию компактного интерпретатора и операционной системы MS-DOS, предназначенных для персональных компьютеров фирмы IBM, первая модель которых появилась в августе 1981 г. В этом же году для компьютеров IBM PC фирма «Microsoft» представила расширенную версию BASIC-80 под названием BASIC-A (Advanced – передовой), которая поддерживала текстовой и графические режимы. В 1984 г. в BASIC-A выведены дополнительные возможности, такие, как работы с окном экрана, обработка перерываний от таймера, выполнение команд операционной системы и пр. В этом же году фирма «Microsoft» разработала интерпретатор языка Macintosh BASIC для ПЭВМ Macintosh фирмы «Apple».

Развитием языка BASIC-A стала версия Quick BASIC, включающая подпрограммы и функции с локальными и глобальными переменными, средства поддержки графики и звука, алфавитно-цифровые метки и т.д. К достоинствам языка также следует отнести то, что он:

1.      содержит хороший экранный редактор;

2.      не ограничивает длину программы;

3.      отменяет необходимость нумерации строк;

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

В 1985 г. Т. Куртц и Дж. Кемени разработали для IBM PC версию языка под названием True BASIC.

Алфавит языка QBasic

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

Алфавит языка включает в себя все символы, представленные в кодировочной таблице, которая загружена в ОП или хранится в ПЗУ компьютера. Каждому символу алфавита соответствует индивидуальный числовой код от 0 до 255. Символы с кодами от 0 до 127 представляют собой так называемую основную таблицу кодов ASCII. Их состав и порядок определены американским стандартом на коды обмена информацией.

Набор символов языка QBasic:

      все прописные и строчные буквы латинского алфавита;

      цифры от 0 до 9;

      математические знаки             + – * / = < > ^;

      разделители               , . : ; ‘ _ (подчеркивание), ″ (двойные кавычки);

      символы для объявления типа данных         % ! & # $;

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

      скобки   ( );

      \ ~

Переменные и константы

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

Переменная – это величина, которая может меняться при выполнении программы.

Константа – это заранее объявленные величины, которые не меняются в процессе выполнения программы.

В QBasic константы бывают символьные и числовые.

Символьные константы – последовательность алфавитно-цифровых символов, заключенных в кавычки. Например, ″Грозный″, ″VECTOR″, ″237″.

Числовые константы бывают двух видов: вещественные и целые.

Целая константа представляет собой запись числа без десятичной точки. Например, -432, 1.

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

Например, 123.45=1.2345Е2, (мантисса – 1.2345, основание 10-ой системы счисления – Е, порядок – 2).

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