Классификация и примеры алгоритмических структур

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

- алгоритмы линейной структуры;

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

- алгоритмы циклической структуры.

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

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

Заданы радиусы оснований R1 и R2, длина образующей L и высота h прямого усеченного конуса. Найти площадь поверхности и объем усеченного конуса.

Постановка задачи.

Входные данные:

R1 – радиус нижнего основания конуса;

R2 – радиус верхнего основания конуса;

h – высота усеченного конуса.

Выходные данные:

S – площадь поверхности усеченного конуса;

V – объем усеченного конуса.

Метод решения: вычисление значений V и S по формулам:

– объем прямого усеченного конуса:

площадь поверхности усеченного конуса:

где

– образующая конуса.

Алгоритм. Вычисление значений V и S.

Входные данные.

СКАЛЯР R1 – вещественное число.

СКАЛЯР R2 – вещественное число.

СКАЛЯР h – вещественное число.

Выходные данные.

СКАЛЯР V – вещественное число.

СКАЛЯР S – вещественное число.

Промежуточные данные.

СКАЛЯР L – вещественное число.

Начало

ввод(R1,R2,h)

вывод(V,S)

Конец

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

Вывод V,S

		Рис 3.10

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

Вычислить значение функции в зависимости от условия по формуле:

Постановка задачи.

Входные данные:

X – аргумент вычисляемой функции.

Выходные данные:

Y – значение функции[k1] .

Метод решения: проверка условия и вычисление функции по соответствующей формуле.

Алгоритм. Вычисление значения функции Y.

Входные данные.

СКАЛЯР X – вещественное число.

Выходные данные.

СКАЛЯР Y – вещественное число.

Начало

ввод(X)

ЕСЛИ (X>=1) ТО

Y=ln(X)

ИНАЧЕ

ЕСЛИ (X<1) и (X>-1) ТО

Y =1

ИНАЧЕ

Y=e^X

КОНЕЦ_ЕСЛИ

КОНЕЦ_ЕСЛИ

вывод(Y)

конец

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

Ввод (X)

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

Пример 1. Определить сумму заданного числа членов последовательности:
1, 1/4, 1/9, …… 1/n².

Постановка задачи.

Входные данные:

К – число членов последовательности.

Выходные данные:

S – сумма заданного числа членов последовательности [k2] .

Метод решения:

- инициализация S=0;

- вычисление значений K членов последовательности и суммирование.

Алгоритм. Вычисление суммы заданного числа членов последовательности.

Входные данные.

СКАЛЯР K – целое число.

Выходные данные.

СКАЛЯР S – вещественное число.

Промежуточные переменные

СКАЛЯР I – целое число.

Начало

ввод(K)

S=0

ЦИКЛОТ I=1 ДО K

S=S+1/(I*I)

КОНЕЦ_ЦИКЛА

вывод(S)

конец

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

Ввод(K)

Вывод(S)

Пример 2. Определить, какое минимальное количество членов последовательности

1, 1/4, 1/9, …… 1/n²

надо суммировать, чтобы сумма была больше заданного числа R.

Постановка задачи.

Входные данные:

R – заданное значение суммы членов последовательности.

Выходные данные:

N – число членов последовательности [k3] .

Метод решения:

- инициализация S=0; N=0;

- пока сумма S<=R, вычисление очередного номера N и суммы S.

Алгоритм. Вычисление числа членов последовательности.

Входные данные.

СКАЛЯР R – вещественное число.

Выходные данные.

СКАЛЯР N – целое число.

Промежуточные данные.

СКАЛЯР S – вещественное число.

Начало

ввод(R)

S=0

N=0

ЦИКЛПОКА S<=R

N=N+1

S=S+1/(N*N)

КОНЕЦ_ЦИКЛА

вывод(N)

конец

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

Ввод(R)

Вывод(N)

Пример 3. Определить, какое минимальное количество членов последовательности

1, 1/4, 1/9, …… 1/n²

надо суммировать, чтобы сумма была больше заданного числа.

Постановка задачи.

Входные данные:

R – заданное значение суммы членов последовательности.

Выходные данные:

N – число членов последовательности [k4] .

Метод решения:

- инициализация S=0; N=0;

- вычисление очередного номера N и суммы S до тех пор, пока сумма S<=R.

Алгоритм. Вычисление числа членов последовательности.

Входные данные.

СКАЛЯР R – вещественное число.

Выходные данные.

СКАЛЯР N – целое число.

Промежуточные данные.

СКАЛЯР S – вещественное число.

Начало

ввод(R)

S=0

N=0

ЦИКЛ

N=N+1

S=S+1/(N*N)

ДО S>R

вывод(N)

конец

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

Ввод(R)

Вывод(N)

Основы языка программирования Паскаль

Алфавит и лексемы

Язык Паскаль, как и любой язык программирования имеет свой алфавит, синтаксис и семантику. Алфавит ¾ это набор допустимых в языке символов. Синтаксис ¾ это совокупность правил образования предложений языка. Синтаксические правила определяют требования к записи операторов языка программирования. Семантика ¾ это множество правил, определяющих смысл предложений языка. Семантические правила определяют, какие действия и в какой последовательности должна выполнить ЭВМ, выполняя программу на языке Паскаль.

Алфавит языка Паскаль является подмножеством набора символов кода ASCII и включает следующие символы:

§ прописные и строчные буквы латинского алфавита и символ подчеркивания;

§ арабские цифры;

§ специальные знаки: # $ ’ ( ) * + - , ; : . / < = > @ [ ] ^ { }

§ символ пробела;

§ управляющие символы.

Из символов алфавита формируются лексемы. Лексема ¾ это минимальная, смысловая единица текста программы. Классификация лексем языка Паскаль приведена на рис. 1.

Специальные символы ¾ это знаки операций, скобки и разделители.

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

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

and goto program

asm if record
array implementation repeat
begin in set
case inherited shl
const inline shr

	лексема

		Рис. 4.1

constructor interface string
destructor label then
div library to
do mod type
downto nil until
else not unit
end object uses
exports of var
file or while
for packed xor
function procedure

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

Метки в Паскале могут относиться к оператору или его части ( в операторе case) и бывают числовыми или символьными. Метка отделяется от оператора двоеточием (:).

Числа в программах на Паскале используются целые и вещественные. Целые числа могут быть представлены в десятичной и шестнадцатеричной системах счисления. Целые десятичные числа записываются, как в математике, и должны находится в диапазоне от –2147483648 до +2147483647. Примеры: 35, -64, 0.

Для обозначения целых шестнадцатеричных чисел используется знак доллара ($), который записывается перед числом. Например, $A01, $0. Допустимый диапазон целых шестнадцатеричных чисел от $00000000 до $FFFFFFFF.

Вещественные числа записываются в виде десятичной дроби (вещественное число с фиксированной запятой) и в экспоненциальной форме (вещественное число с плавающей запятой). Примеры вещественных чисел с фиксированной запятой : 35.26; –90.5; 0.097. Во втором способе записи указываются мантисса и порядок числа, разделенные буквой ‘Е’:
<мантисса>E<порядок>. Например, 0.272Е+02, это означает

0.272 х 10²= 27.1 .

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

‘Н. Вирт – автор языка Паскаль’

‘Borland Pascal 7.0’

‘’ –пустая строка.

Строка, состоящая из одного символа, называется символьной константой. Например, ‘Z’ – символьная константа.

Управляющие символы используются в строках и записываются в виде десятичного числа, перед которым ставится знак ‘#’. Например,

#7 – символ «звонок»,

#10– символ «перевод строки»,

#13 – символ «возврат каретки».

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

Особым случаем является комментарий, после открывающейся скобки которого стоит знак доллара $. Такой комментарий называется псевдокомментарием или директивой компилятора. Например, {$N+ } – в программе необходимо использовать математический сопроцессор, {$I-} - отключить автоматическую обработку ошибок ввода-вывода.