pascal_lections

Введение

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

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

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

За математической постановкой и разработкой метода решения следует реализация метода на ЭВМ

– Процесс программирования.

Процесс программирования состоит из двух частей: 1) составление блок-схемы программы – графического изображения последовательности действий; 2) написание программы на языке, понятном ЭВМ.

Контроль за выполнением программы включает в себя отладку и получение результатов. Отладка – процесс обнаружения и устранения ошибок программирования.

Последний этап решения задачи – обработка результатов.

Понятие алгоритма и свойства алгоритма

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

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

Слово «алгоритм» происходит от латинской формы написания имени узбекского математика 9-го века аль-Хорезми. Он впервые сформулировал правила выполнения арифметических действий с использованием арабских цифр.

свойства алгоритма:

1)свойство конечности – алгоритм должен заканчиваться после конечного числа шагов

2)свойство определенности – каждый шаг алгоритма должен быть точно и однозначно определять характер действий

3)свойство эффективности – результат должен быть получен за наименьшее число наиболее простых операций

4)алгоритм должен иметь некоторое число исходных данных (кол-во исх.дан. м.б.=0), т.е. величин, заданных до начала работы алгоритма

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

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

1.Указание формулы или последовательности формул

Пример: вычислить объем круглого конуса, пользуясь формулой V 13 r 2 h . При заданных

размерах r и h , эта формула дает однозначное предписание исполнителю.

2. Словесное описание алгоритма

1

Пример: через точку А, расположенную вне прямой а, в пространстве провести прямую b, параллельную прямой a.

а) через прямую а и точку А провести плоскость М

б) в плоскости М провести прямую b, параллельную прямой а

3. Представление в виде блок-схемы Блок-схема – графическое представление хода решения задачи.

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

Запись программы на алгоритмическом языке.

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

-алфавит (словарь исходных символов)

-синтаксис (грамматика языка)

-семантика

Синтаксис языка – система правил, по которым из символов алфавита образуются правильные конструкции языка.

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

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

-каждый описываемый алгоритм должен иметь собственное название, раскрывающее смысл алгоритма

-при записи следует обозначать начало и конец алгоритма

-необходимо указать величины, которые будут входными при работе алгоритма

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

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

ПРИМЕР АЛГОРИТМА

S v0t at 2 / 2

А. описание с помощью формулы Алгоритм: Вычисление Пути

Описание величин: v0 , t, a – аргументы; S – результат

Начало

S v0 t a t t / 2

Конец.

Б. описание на языке программирования PL/1

P: PROCEDURE OPTIONS (MAIN);	- начало алг и заголовок
DECLARE (V0, T, A, S) DECFIXED (2,0); - описание данных
S=V0*T+A*T*T/2;	- вычисление
END P;	- конец описания алг

2

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

Существует три основных типа алгоритмов:

-линейный

-разветвляющийся

-циклический

И, естественно, более-менее сложный алгоритм является комбинацией трех базовых типов алгоритмов.

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

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

Пример. Составить алгоритм и программу вычисления площади прямоугольника.

1.Построение математической модели.

a, b – длины сторон прямоугольника (исходные величины), S – площадь прямоугольника (результат)

Sa *b

2.Блок-схема алгоритма.

начало

ввод

данных a, b

S = a * b

вывод

результата

S

конец

3. Реализация алгоритма на языке программирования Pascal

Program LinAlgor; Var a, b, s: real; Begin

Write(‘введите длину первой стороны : ’);

Readln(a);

Write(‘введите длину второй стороны : ’);

Readln(b);

s:=a*b;

Writeln(‘площадь прямоугольника равна : ’,s); End.

3

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

Полная форма разветвления

					условие
		ДА							НЕТ
					истинно ?
действие 1								действие 2

Сокращенная форма разветвления

	условие	ДА
	истинно ?
		действие

Пример. Даны целые числа X, Y. Определить, принадлежит ли точка с координатами X, Y кругу радиуса R, при условии что центр круга совпадает с началом координат. Вывести на экран сообщение "Принадлежит" или "Не принадлежит".

1.

Построение математической модели

Уравнение окружности: R2 X 2 Y 2

Точка с координатами X,Y принадлежит

заданной

области (кругу), если выполняется условие:

X 2 Y 2 R2 .

2.

Блок-схема алгоритма

начало

ввод

данных

X, Y, R

X2 + Y2 <= R2

ДА

НЕТ

точка (Х,У)

точка (Х,У) не

принадлежит

принадлежит

кругу радиуса

кругу радиуса

R

R

конец

4

3. Программа на языке Pascal

Program VetvAlg; Var X,Y,R: real; Begin

Write(‘введите координату Х : ’);

Readln(X);

Write(‘введите координату У : ’);

Readln(Y);

Write(‘введите радиус круга R : ’);

Readln(R);

If sqr(X)+sqr(Y)<=sqr(R) then Writeln(‘принадлежит’)

Else

Writeln(‘не принадлежит’)

End.

Циклический алгоритм

Цикл - это многократно повторяющиеся действия с разными значениями исходных данных.

Циклы.

Существует 3 классических управляющих конструкции циклов:

1.цикл с предусловием

2.цикл с постусловием

3.цикл параметром (цикл со счетчиком)

Так же существует безусловный (бесконечный) цикл, который выполняется постоянно, пока не произойдет принудительной остановки выполнения.

цикл с предусловием

while

условие

do

оператор

оператор while позволяет многократно выполнять одни и те же действия в зависимости от некоторого условия, которое должно быть булевского типа, то есть принимать только значения true или false.

Сначала при входе в цикл вычисляется условие. Если оно равно false, то цикл не выполняется и управление передается оператору следующему за оператором цикла. Если условие равно true, то происходит вход в цикл и выполнение оператора (операторов) тела цикла. Как только достигнут конец тела цикла, управление опять передается в заголовок, где снова вычисляется условие. Если условие равно true, то происходит вход и т.д., пока условие не станет false.

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

Const n=20; Begin

...

Summa:=0;

I:=1;

While I<=n do Begin

Summa:=Summa+A[I];

5

I:=I+1;

End;

...

end.

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

repeat

оператор(ы)

until

условие

Цикл repeat является не столь универсальным универсальным, как цикл while, поскольку его условие располагается в конце цикла и тело цикла будет выполнено хотя бы один раз.

Цикл будет продолжаться пока условие равно false и заканчивается, когда условие становится равным true.

Const n=20; Begin

...

Summa:=0;

I:=1;

Repeat Summa:=Summa+A[I]; I:=I+1;

Until I>N;

Цикл с параметром (цикл со счетчиком)

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

for	управляющая	:=	исходное
	переменная		значение
	to
		конечное	do	оператор
		значение
	downto

1)счетчик наращивает свое значение

for переменная := начальное_значение

to конечное_значение do оператор

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

2)счетчик уменьшает свое значение

for переменная := начальное_значение

downto конечное_значение do оператор

6

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

Begin

...

Summa:=0;

For I:=1 no n do Summa:=Summa+A[I];

...

end.

Шаг изменения счетчика циклов может быть только +1 (to) или –1 (downto).

Бесконечный цикл.

repeat оператор until false;

while true do оператор;

Типы данных

Понятие типа данных в Турбо Паскаль

Для обработки ЭВМ данные представляются в виде величин и их совокупностей. С понятием величины связаны такая важная характеристика, как ее тип.

Тип определяет:

возможные значения переменных, констант, функций, выражений, принадлежащих к данному типу;

внутреннюю форму представления данных в ЭВМ;

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

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

Иерархия типов в языке Паскаль такая:

(См на следующей стр.)

7

типы данных

Turbo Bascal

Простые				Структурированн		Указатели
				ые

Порядковые		Вещественные		Массивы

Строки

Целые

Логические

Множества

Символьные

Записи

Перечисляемые

Интервальные

Файлы

Простые типы данных (БАЗОВЫЕ)

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

	Идентификатор	Длина	Диапазон значений	Операции
		(байт)
	Целые типы
	integer	2	-32768..32767	+, -, /, *, Div, Mod, >=, <=, =,
				<>, <, >
	byte	1	0..255	+, -, /, *, Div, Mod, >=, <=, =,
				<>, <, >
	word	2	0..65535	+, -, /, *, Div, Mod, >=, <=, =,
				<>, <, >
	shortint	1	-128..127	+, -, /, *, Div, Mod, >=, <=, =,
				<>, <, >
	longint	4	-2147483648..	+, -, /, *, Div, Mod, >=, <=, =,
			2147483647	<>, <, >
	Вещественные типы
	real	6	2,9x10-39 ..	+, -, /, *, >=, <=, =, <>, <, >
			1,7x1038
	single	4	1,5x10-45 ..	+, -, /, *, >=, <=, =, <>, <, >
			3,4x1038
	double	8	5x10-324 ..	+, -, /, *, >=, <=, =, <>, <, >
			1,7x10308
	extended	10	3,4x10-4932 ..	+, -, /, *, >=, <=, =, <>, <, >
			1,1x104932

8

Логический тип

boolean		1	true, false	Not, And, Or, Xor, >=, <=, =, <>,
				<, >
Символьный тип
char		1	все символы кода	+, >=, <=, =, <>, <, >
			ASCII

Дополнительные сведения о типах данных...

Порядковые типы, выделяемые из группы простых типов, характеризуются следующими свойствами:

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

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

к любому порядковому типу могут быть применены стандартные функции Pred и Succ, которые возвращают предыдущее и последующее значения соответственно;

к любому порядковому типу могут быть применены стандартные функции Low и High, которые возвращают наименьшее и наибольшее значения величин данного типа.

Вязыке Паскаль введены понятия эквивалентности и совместимости типов. Два типа Т1 и Т2 являются эквивалентными (идентичными), если выполняется одно из двух условий:

Т1 и Т2 представляют собой одно и то же имя типа;

тип Т2 описан с использованием типа Т1 с помощью равенства или последовательности равенств.

Например: type

T1 = Integer;

T2 = T1;

T3 = T2;

Менее строгие ограничения накладываются на совместимость типов. Так, типы являются совместимыми, если:

они эквивалентны;

являются оба либо целыми, либо действительными;

один тип - интервальный, другой - его базовый;

оба интервальные с общим базовым;

один тип - строковый, другой - символьный.

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

Имя_Типа(переменная или значение)

Напрмер, Integer('Z') представляет собой значение кода символа 'Z' в двухбайтном представлении целого числа, а Byte(534) даст значение 22, поскольку целое число 534 имеет тип Word и занимает два байта, а тип Byte занимает один байт, и в процессе приведения старший байт будет отброшен.

Переменные и константы Переменная – элемент программы, который предназначен для хранения, коррекции и передачи

данных внутри программы. Все переменные программы должны быть объявлены в разделе описания переменных (см. далее).

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

9

В Турбо Паскаль применяется несколько стандартных видов констант:

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

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

Символьные константы. Могут быть определены посредством некоторого символа (заключенного в апострофы).

Строковые константы. Могут быть определены последовательностью произвольных символов (заключенных в апострофы).

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

Const

year: integer = 2001; symb: char = '?'; money: real = 57.23;

Выражения

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

типы операций: математические, логические и операции отношений.

Математические операции

В таблице приведены основные математические операции Турбо Паскаль.

Символ операции		Название операции					Пример
*		умножение			2*3	(результат: 6)
/		деление		30/2 (результат: 1.5E+01)
+		сложение			2+3	(результат: 5)
-		вычитание			5-3	(результат: 2)
div		целочисленное деление		5	div	2	(результат: 2)
mod		остаток от деления		5	mod	2	(результат: 1)

Логические операции

Над логическими аргументами в Турбо Паскаль определены следующие операции:

NOT - логическое отрицание ("НЕ")

AND - логическое умножение ("И")

OR - логическое сложение ("ИЛИ")

XOR - логическое "Исключающее ИЛИ"

Результаты выполнения этих операций над переменными А и В логического типа приведены в таблице истинности.

A		B		not A		A and B		A or B		A xor B
true		true		false		true		true		false
true		false				false		true		true
false		true		true		false		true		true
false		false				false		false		false

10