Информатика и ИКТ. Базовый уровень.

Алгоритмы и исполнители. Основы программирования.

Оглавление | Другие разделы: 1 | 2 | 3 | 4 | 5 | 6

Смотрите материалы к разделу в Интернете:

1 | 2 | 3 | 4 | 5 | 6 | 7

Обмен ссылками

© Stepanov & K. 2008

Главная | Разделы | В начало раздела | Другие темы раздела: 1 | 2 | 3 

Алгоритмы и исполнители

            §1. Понятие алгоритма. Исполнители алгоритмов. Свойства алгоритмов.

            §2. Способы описания алгоритмов.

            §3. Типовые алгоритмические структуры.

            §4. Методы разработки сложных алгоритмов.

            §5.  Алгоритмы и процессы управления.

Понятие алгоритма. Исполнители алгоритмов. Свойства алгоритмов.

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

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

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

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

 Для создания алгоритма (программы) необходимо знать:

•  полный набор исходных данных задачи (начальное состояние объекта);

•  цель создания алгоритма (конечное состояние объекта);

•   систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

 Полученный алгоритм  (программа) должен обладать следующим набором свойств:

•          дискретность (алгоритм разбит на отдельные шаги - команды);

•          однозначность (каждая команда определяет единственно возможное действие исполнителя);

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

•          результативность (исполнитель должен решить задачу за конечное число шагов).

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

 Способы описания алгоритмов.

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

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

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

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

 Типовые алгоритмические структуры.

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

Линейная структура (следование).

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

 Ветвление.

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

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

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

 Цикл (повторение).

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

  Циклы «до» - повторение тела цикла до выполнения условия:

 Циклы «пока» - повторение тела цикла пока условие выполняется (истинно):

Циклы со счётчиком (с параметром)  – повторение тела цикла заданное число раз:

Вспомогательный алгоритм (подпрограмма, процедура).

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

Методы разработки сложных алгоритмов.

Существует два метода разработки сложных алгоритмов:

Метод последовательной детализации задачи («сверху-вниз») состоит в том, что исходная сложная задача разбивается на подзадачи. Каждая из подзадач рассматривается и решается отдельно. Если какие-либо из подзадач сложны, они также разбиваются на подзадачи. Процесс продолжается до тех пор, пока подзадачи не сведутся  к элементарным. Решения отдельных подзадач затем собираются в единый алгоритм решения исходной задачи. Метод широко используется, так как позволяет вести разработку общего алгоритма одновременно нескольким  программистам, решающим локальные подзадачи. Это необходимое условие быстрой разработки программных продуктов.

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

 Алгоритмы и процессы управления.

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

В простейшем случае таких объектов два:

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

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

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

 В начало темы

Главная | Разделы | В начало раздела | Другие темы раздела: 1 | 2 | 3

QBASIC

                §1. Алфавит. Величины.

                §2. Встроенные функции.

                §3. Простые операторы.

                §4. Операторы - структуры.

Алфавит QBASIC

Алфавит Qbasic включает следующие наборы символов:

• латинские буквы;

• русские буквы (только для записи комментариев к программе и текстовых констант);

• цифры;

• специальные символы.

 Специальные символы: 

Величины

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

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

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

Массив- совокупность однотипных данных, имеющих общее имя. Массивы позволяют организовать циклы обработки данных в которых параметр цикла указывает на индекс элемента массива. Их классифицируют по типу данных (числовые, строковые, логические) и по размерности (одномерные, двухмерные, трехмерные и т.д.). Каждый элемент массива представляет собой переменную величину. Для указания на элемент массива в программе записывается имя массива и рядом в скобках набор индексов (для одномерных-1 индекс; для двухмерных -2 (строка, столбец) и т.д.), например A(17) - 17й по счету элемент одномерного массива А. Значение, хранящееся в нем, не связано с его номером.

Встроенные функции QBASIC

 Числовые функции 

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

 Строковые функции и функции преобразования типов

 Здесь Х$ - любая текстовая константа, переменная или выражение; N, K, X – числовые константы, переменные или выражения.

Операторы

 Операторы описания и объявления

DIM список - служит для описания переменных и массивов. Обязательно только описание массивов.

DECLARE SUB имя (формальные параметры) - объявляет процедуру.

 Операторы ввода данных.

INPUT “приглашение”; список переменных - служит для ввода данных с клавиатуры, например:

        INPUT”Введите массу и ускорение”; m,a

 Когда в программе встречается такой оператор, компьютер приостанавливает  выполнение программы, выдает на экран текст приглашения и ждет ввода данных. Данные вводятся с клавиатуры пользователем программы. Их количество и тип должны соответствовать списку переменных! Совместно с оператором  INPUT удобно использовать операторы COLOR  LOCATE. Первый регулирует цвет текста, а второй местоположение текста на экране. Например, чтобы вводить данные из центра экрана, а приглашение печаталось красным цветом, можно применить следующий фрагмент программы:

COLOR 4

LOCATE  14, 35

INPUT “Введите массу и ускорение “; m,a

DATA список данных

READ список переменных

Служат для автоматического ввода данных из программы. Оператор  DATA  должен предшествовать оператору (или операторам)  READ. Чтение данных производится последовательно.

Оператор присваивания

 Имя переменной = выражение

Присваивает переменной, имя которой находится слева от знака = (знак присваивания) значение выражения  находящегося справа. Старое значение переменной при этом теряется. Например:

A = A + 1

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

Операторы вывода данных

PRINT список вывода - служит для вывода текстовых и числовых  данных на экран. Список для вывода может включать в себя константы, переменные и выражения. Константы выводятся без изменений, вместо переменных и выражений печатаются их текущие значения. Совместно с PRINT  удобно использовать операторы LOCATE  COLOR. Например:

COLOR 2

LOCATE 15, 35

PRINT  “Сила =”; F; “H”

В результате выполнения программы в центре экрана зелёным цветом будет выведено:

 Сила = 129.81 H

BEEP - выводит звуковой сигнал.

SOUND частота, длительность - выводит звуковой сигнал заданной длительности и частоты.

PLAY”символьное выражение” - позволяет создавать музыкальные фрагменты (см. справку  Qbasic).

SCREEN номер- включает графический режим. Допустимые номера режимов 1,2,8,9,12. Наилучшее качество изображения (640*480 пикселей, 16 цветов) обеспечивает  12 режим.

CLS - очищает экран.

LINE (x1, y1)-(x2, y2), цвет - рисует линию от точки Х1,У1 до Х2,У2 указанным цветом.

LINE (x1, y1)-(x2, y2), цвет, b - рисует рамку с углами в точках Х1,У1 и Х2,У2 указанным цветом.

LINE (x1, y1)-(x2, y2), цвет, bf - рисует закрашенный прямоугольник.

PSET (x, y), цвет - устанавливает точку.

CIRCLE (x, y), радиус, цвет - рисует окружность с центром в точке Х,У указанного цвета и радиуса.

PAINT (x,y), c1, c2 - выполняет заливку начиная с точки Х,У цветом С1. Заливка ограничивается линией цвета С2.

DRAW”символьное выражение” – позволяет создавать сложные рисунки (см. справку  Qbasic).

 Операторы переходов

 GOTO  Метка - передает управление на строку с указанной меткой.

GOSUB Метка - передает управление в подпрограмму, начинающуюся с указанной метки.

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

EXIT - передает управление на строку, следующую за концом текущей структуры.

CALL  Имя (фактические параметры) - передает управление процедуре с указанным именем и фактическими параметрами.

 Оператор конца программы 

END - завершает выполнение программы.

Операторы - структуры

 Операторы ветвлений

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

IF  условие THEN Оператор - если условие – истина, то выполняется оператор после ключевого слова  THEN. Затем управление передаётся на следующую строку программы. Если условие – ложь, то управление сразу передается на следующую строку программы.

IF условие THEN

      Группа операторов

END IF

 - если условие – истина, то выполняется группа операторов между  THEN и END IF. Затем управление передаётся на следующую за END IF  строку  программы. Если условие – ложь, то управление сразу передается на следующую за END IF строку программы.

 Полное ветвление:

IF условие THEN оператор_1 ELSE оператор_2  - если условие – истина, то выполняется оператор1, иначе выполняется оператор2  . Затем управление передаётся на следующую строку программы.

IF условие THEN

        Группа операторов 1

ELSE

        Группа операторов 2

END IF

 - если условие – истина, то выполняется блок операторов 1, иначе выполняется блок операторов 2  . Затем управление передаётся на следующую за  END IF  строку программы. 

Выбор:

SELECT CASE выражение для сравнения

   CASE условие 1

      Группа операторов 1

   CASE условие 2

      Группа операторов 2

………….

   ELSE CASE

      Группа операторов  N

END SELECT

- если  условие 1 - истина, то выполняется блок операторов 1 и осуществляется переход на строку программы, следующую за  END SELECT; если условие 2 - истина, то выполняется блок операторов 2  и осуществляется переход на строку программы, следующую за   END SELECT и т. д., если все условия – ложь, то выполняется блок операторов   N  и осуществляется переход на строку программы, следующую за  END SELECT.

Операторы циклов

 DO  WHILE   условие                         DO                                                 WHILE  условие

Группа операторов                            Группа операторов                     Группа операторов

LOOP                                                     LOOP WHILE  условие               WEND

- выполняет группу операторов, пока условие – истина (такие циклы называются циклами "ПОКА").

DO UNTIL  условие                                  DO

Группа операторов                                  Группа операторов

LOOP                                                          LOOP UNTIL условие

- выполняет группу операторов до выполнения условия (такие циклы называются циклами "ДО").

FOR Параметр = Начальное значение  TO  Конечное значение STEP шаг

Группа операторов

NEXT Параметр

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

Процедуры

SUB Имя (формальные параметры)

  Группа операторов

END SUB

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

В начало темы