Реализация основных алгоритмических структур на языке программирования.

Блок-схема	Язык Basic
	Вычисление площади треугольника CLS DEFINT A,H DEFDBL S INPUT «Вв. основание тр-ка а=», А INPUT «Вв. высоту тр-ка h=», H S=(1/2)*A*H PRINT «Площадь S=»; S
	CLS PRINT "Вычислите y=1/(x-2) для всех x" INPUT "Введите x=", x IF x = 2 THEN PRINT "При x=2 функция не определена!": END y = 1 / (x - 2) PRINT "y="; y
	CLS FOR X=1 TO 20 PRINT "Привет!" NEXT X

 

Основные этапы разработки программ

Разработка законченного программного продукта в виде компьютерной программы — длительный и трудоемкий процесс. Чтобы окончательный вариант программы работал правильно и содержал как можно меньше ошибок, программисты придерживаются полного цикла разработки программы, состоящего из шести базовых этапов:

1. Постановка и анализ задачи. Четкое определение за­дачи и наборов входных и выходных данных.
2. Разработка алгоритма. Определение зависимости между входными и выходными данными, создание процедуры их преобразования.
3. Разработка пользовательского интерфейса. Определение того, что пользователь должен видеть на экране, как будут вводиться данные, где и в каком формате будут представлены выходные данные.
4. Написание программного кода. Преобразование алгоритма в компьютерную программу на языке высокого уровня.
5. Тестирование и отладка программы. Тестирование - прогон программы на наборе тестов, для которых известен результат, с целью проверки правильности ее работы. Отладка (debug) — процесс выявления и устранения ошибок в программе.
6. Составление документации. Подготовка документов, содержащих описание программы, включая техническое задание, блок-схемы, предположения, список входных и выходных переменных (часто совмещается с программным кодом), руководства пользователя.

 

Технология нисходящего программирования. Разбиение задачи на подзадачи. Процедуры и функции.

 

Технологии программирования

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

Существуют различные технологии программирования.

Технология восходящего программирования («снизу вверх») реализуется так:

1. Вначале создаются и отлаживаются самые элементар­ные подпрограммы (скорее всего используя созданные ранее, хранимые в модулях-библиотеках).
2. Реализуется более крупный блок задачи путем вызова таких подпрограмм.
3. Повторяется пункт 2 до тех пор, пока не реализуется вся задача.

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

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

 

Технология нисходящего программирования — это со­здание программы «сверху вниз». Сначала разрабатывается основная программа (точнее, ее общая структура) и в ней за­писываются обращения к пока еще не написанным вспомогательным подпрограммам; и так далее — до самых простых «неделимых» подпрограмм.

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

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

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

Структурное программирование предполагает, что логическая структура программы может быть выражена комби­нацией трех базовых структур: следования, ветвления и цикла. Эти структуры могут комбинироваться одна с другой, как того требует программа.

Итак, особенности структурного программирования:

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

Этапы решения сложной задачи X сверху вниз:

1. Разбиваем задачу X на несколько функциональных подзадач XI, Х2, ХЗ и т. д., т. е. выполняем ее деком­позицию.
2. Предполагаем, что впоследствии эти части будут разра­ботаны, создаем их спецификации:
   - вид подпрограммы (процедура или функция);
   - ее имя;
   - имена и типы формальных параметров, их порядок;
   - для функции — тип возвращаемого значения;
   - комментарии, описывающие назначение подпрограммы.
3. Пишем программу решения задачи X, заменив каждую из подпрограмм XI, Х2, ХЗ «заглушками», и отлаживаем ее в таком виде.
4. Параллельно работаем с каждой из подпрограмм XI, Х2, ХЗ, при необходимости так же разбивая каждую из них на подзадачи еще более низкого уровня, т. е. используя методику, начиная с п. 1. Каждую подзада­чу можно решать независимо от других.
5. Проводим комплексную отладку постепенно, по одной заменяя заглушки на автономно отлаженные подпрограммы.

Достоинства метода программирования «сверху вниз» — серьезные ошибки с большой вероятностью отыскиваются уже на ранних стадиях проекта; тестирование систематично.

Недостаток — при отладке поглощается больше машин­ных ресурсов. Необходимо снижать трудоемкость тестирова­ния и отладки программы.

 

Процедуры и функции

Подпрограмма (subroutine) — именованная последовате­льность операторов языка, предназначенная для решения некоторой подзадачи. Часто подпрограмма имеет свои пере­менные, не пересекающиеся с переменными других подпрограмм или самой программы (если только переменные не были объявлены специальным образом или переданы под­программе). Каждая подпрограмма имеет имя, по которому к ней можно обратиться. В языке QBasic ме­ханизм подпрограмм реализуется в виде процедур (procedure) и функций (function) с такой же структурой, как и основная программа. Они различаются назначением и способом использования.

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

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

1. не требует многократно повторять в тексте программы аналогичные фрагменты;
2. улучшает структуру, облегчая ее понимание;
3. уменьшает вероятность появления ошибок (отлаживается отдельно);
4. позволяет очень длинную программу разбить на части;
5. позволяет использовать подпрограммы в других программах.

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

 

Описание процедуры

SUB <имя>[(<формальные параметры>)]

<Объявление переменных>

<Тело процедуры>

EXIT SUB

END SUB

Обращение к процедуре

CALL <имя>[(фактические параметры)]

 

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

 

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

 

Функция предназначена для того, чтобы возвращать одно значение, оно и является ее результатом. Описание функции начинается с заголовка, за ним следует имя, а в круглых скобках — список формальных параметров:

 

Описание функции

Function <имя> [(<формальные параметры>)]: <тип результата>

<Объявление переменных>

<Тело функции>

<имя>=<значение>

END FUNCTION

Обращение к функции

Р=<имя>[(<фактические параметры>)]

 

Примечание. <значение> - это результат выполнения арифметичиского выражения.

 

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

 

Структура программы на QBasic:

 

Const — раздел констант

Туре — раздел типов

DEF — раздел переменных

SUB, FUNCTION — раздел процедур и функций

Раздел операторов

END

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

 

Примеры создания и использования процедур и функ­ций:

Задача 1. Написать процедуру возведения в целую степень N некотс рого числа X, N > 0, X > 0. Показать использование процедуры, оба числа вводятся с клавиатуры.

 

DIM Y, К AS INTEGER DIM P AS LONG SUB STEPEN (X, N AS INTEGER, P AS LONG) DEFINT I P=1 FOR I=1 TO N P=P*X NEXT END SUB   CLS INPUT "Введите число Y и степень К "; Y,K CALL STEPEN (Y,К,Р) PRINT "P="; P END

Описание процедуры формальные параметры X, N, P X, N - входные параметры P - выходной параметр I - локальная переменная   конец процедуры   обращение к процедуре с фактическими параметрамиY,K,P

 

 

Структуры данных. Обработка массивов. Поиск в масси­ве. Основные алгоритмы сортировки массивов.

 

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

Основное назначение таких конструкций — упростить описание модели, упорядочить дальнейшую обработку и по­зволить создавать объединения из отдельных переменных.

Самый простой случай такой структуры данных — мас­сив. В компилируемых языках высокого уровня массив определяют как упорядоченный набор однотипных пере­менных. Такой набор переменных объявляется заранее, с указанием типа переменных и их количества — для отведе­ния нужного объема памяти. Переменные в массиве назы­ваются его элементами. Каждый элемент массива имеет ипдекс — целое число, задающее его положение по поряд­ку в массиве.

Основная операция с массивом — обращение к его эле­ментам. Элементы массива используются и изменяются как обычные переменные.

Операция	Бейсик
Объявление массива 10 вещественных элементов	DIM A(10)
Объявление массива 14 целых элементов	DIM В%(14)
Объявление массива 5 строковых элементов	DIM C$(5)
Обращение к элементу	F=C$(2)
Присваивание	C$(3)= C$(1)+ C$(5)

 

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

Часто возникает задача поиска (определения индекса) элемента в массиве по заданному критерию. Простейший способ такого поиска: перебор всех элементов до нахожде­ния нужного. В качестве ответа можно хранить значение, а можно — индекс найденного элемента.

 

Пример — поиск максимального элемента в массиве:

CLS

DEFINT A

DIM A(5)

FOR I = 1 TO 5

A(I) = INT(RND(1) * 100)

PRINT A(I);

NEXT

MAX = 0

FOR I = 1 TO N

IF A(I) > MAX THEN MAX = A(I) ELSE 10

10: NEXT

PRINT "максимальный элемент массива -"; MAX

END

 

Если в массиве выдержан какой-то принцип расположе­ния элементов (упорядочение), то все операции поиска мож­но ускорить. Упорядоченным по неубыванию считается мас­сив, в котором каждый следующий элемент не меньше пре­дыдущего, упорядоченным по невозрастанию — тот, где каждый следующий элемент не больше предыдущего.

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

Алгоритмов сортировки массивов достаточно много, наи­более простой в реализации — метод пузырька. Этот алго­ритм предполагает многократный проход по массиву; на каждом проходе (итерации цикла) циклически обменива­ются местами попарно элементы, стоящие в неправильной последовательности. В результате самый «легкий» элемент (минимальный или максимальный) «всплывает» и занима­ет свое место. На каждой итерации количество обрабатыва­емых элементов уменьшается на единицу. Итерации повто­ряются, пока требуется выполнить хотя бы одну переста­новку:

 

Пример — сортировка элементов массива по возрастанию.

 

CLS

DIM A(10)

FOR I=1 TO 10

A(I) = INT(RND(1)*100)

PRINT A(I);

NEXT

FOR I=1 TO 9

IF A(I) <=A(I+1) THEN 10 ELSE 20

20: R= A(I)

A(I)= A(I+1)

A(I+1)= R

I=0

10: NEXT

PRINT

FOR I=1 TO 10

PRINT A(I);

NEXT

 

 

Основные понятия и операции формальной логики. Зако­ны логики. Логические переменные. Логические выраже­ния и их преобразования. Построение таблиц истинности логических выражений.

 

Основные понятия и операции алгебры логики

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

Логика изучает формы мышления с точки зрения их структуры, законы и правила получения некоторого знания. Формами мышления являются: понятие, суждение, умоза­ключение.

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

Суждение — форма мышления, в которой что-либо утвер­ждается или отрицается о наличии предмета, его свойствах и действиях. Характеризуется содержанием и формой. Со­держанием суждения является его смысл. Форма — способ построения. Суждения бывают истинными и ложными.

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

В своем развитии логика прошла ряд этапов. Современную логику называют математической. Алгебра высказываний (алгебра логики) — раздел математической логики.

Алгебра логики возникла в середине XIX века в трудах Джорджа Буля. Создание алгебры логики представляло со­бой попытку решать традиционные логические задачи алгебраическими методами.

Учение о высказываниях, называемое алгеброй выска­зываний (алгеброй логики), является первой из формаль­ных логических теорий. Объектами алгебры логики явля­ются высказывания.

Алгебра логики имеет приложения при синтезе релейно-контактных и электронных схем. В этой теории отвлека­ются от содержания высказывания, а рассматривают только то его свойство, что оно представляет собой или истину, или ложь. Тогда высказывание можно рассматривать как величину, которая может принимать два значения: «истина» и «ложь». Высказывания обозначаются прописными латин­скими буквами А, В, С, D..., а их значения «Истина» или «Ложь» можно записывать как TRUE и FALSE, или Т и F, или 1 и 0, или И и Л.

Примеры высказываний:

«Луна — спутник Земли».

«Все числа — целые».

 

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

 

Логическое отрицание (инверсия) — это логическая опе­рация, применяемая к одному высказыванию. Высказыва­ние А есть высказывание, которое ложно, когда А истинно, и истинно, когда А ложно. Высказывание называется отри­цанием А.

Возможные обозначения отрицания: A, not А, не А.

 

Логическое умножение (конъюнкция) — это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ис­тинным тогда и только тогда, когда оба исходных высказы­вания истинны.

Возможные обозначения конъюнкции: A И В, А & В, A AND В, А·В, А U В, АВ.

 

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

Возможные обозначения дизъюнкции: А ИЛИ В, A U В, A OR В, А + В, А || В.

 

Логическое следование (импликация) — это высказыва­ние ложно тогда и только тогда, когда А истинно, а В лож­но.

Возможные обозначения импликации: А®В, А => В.

 

Эквивалентность — это высказывание истинно тогда и только тогда, когда А и В оба истинны или оба ложны.

Возможные обозначения эквивалентности: А ~ В, А U В.

 

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

Исходные высказывания могут быть логическими кон­стантами (если имеют постоянное значение «истина» или «ложь») или логическими переменными.

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

Логические операции позволяют каждой формуле при за­данных значениях входящих в нее высказываний приписать одно из двух значений: 0 или 1. Тем самым каждая формула может рассматриваться как некоторый способ задания или реализации функции алгебры логики. Логическая функ­ция — это функция, определенная на множестве значений (истина, ложь) и принимающая значение из того же множе­ства. Например: F1 = А&В, F2 = AUB.

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

 

Таблица простейших логических функций:

 

Отрицание

Конъюнкция

Дизъюнкция

Следование

Эквивалентность

A

А

A

B

A&B

A

B

AUB

A

B

А®В

A

B

АUВ

 

Логические выражения и их преобразования

Будем называть две функции F1 и F2 равносильными, или тождественными, если при любых значениях всех пере­менных, входящих в F1 и F2, эти функции принимают оди­наковые значения. Равносильность обозначается знаком ра­венства (=)

Например:

А ® В = A U В

А U В = (А & В) U (A & В)

 

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

Так можно получать из одной функции другую, равно­сильную ей.

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

1. дей­ствия в скобках
2. инверсия;
3. конъюнкция;
4. дизъюнкция:
5. импликация
6. эквивалентность.

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

 

Законы логики и правила преобразования логических выражений

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

 

 

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

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

Логическая функция называется тождественно ложной, если она принимает значение «ложь» на всех наборах вхо­дящих в нее простых высказываний. Например:

В&А&(В ® А) = В &А & (В UA) = В & ((А & В) U (А & А)) = В & (А & В) U 0 = (А & В & В) = А & 0 = 0.

 

Логическая формула называется тождественно истин­ной, если она принимает значение «истина» на всех наборах входящих в нее простых высказываний (тождественно ис­тинные высказывания часто называют тавтологиями). На­пример:

(А&А) U (В U В) = 0 U 1 = 1.