Существуют два вида подпрограмм: функции и процедуры.

Билет №1

Алгоритм и его свойства

Подпрограммы-функции. Пример описания и использования

Алгоритм

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

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

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

• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

 

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

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

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

Такая трактовка понятия “алгоритм” является неполной и неточной.

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

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

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

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

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

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

Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.

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

На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.

Требования, предъявляемые к алгоритму

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

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

3. Детерминированность — повтор результата при повторе исходных данных.

4. Корректность — способность алгоритма давать правильные результаты решения задачи при различных исходных данных.

5. Конечность — решение задачи должно быть получено за конечное число шагов алгоритма, "зацикливание" недопустимо.

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

Функции

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

Подпрограммы-функции

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

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

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

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

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

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

Описание функции имеет вид:

function имя(список формальных параметров): тип возвращаемого значения;
раздел описаний
begin
операторы
end;

Пример опсиания

function Add(a,b: real): real;

Пример использования:

function Add(a,b: real): real;
begin
Add:= a + b;
end;

БИЛЕТ №2

№2 1. Теорема о структурировании

Подпрограммы-процедуры. Пример описания и использования

2.1

Одним из наиболее ощутимых результатов этих исследований была разработка в 1971 году Никлаусом Виртом языка программирования Pascal. Pascal, названный в честь математика и философа семнадцатого столетия Блеза Паскаля, был разработан для изучения структурного программирования в академической среде и вскоре стал наиболее предпочитаемым языком программирования во многих университетах.

Структурный алгоритм

 

Подпрограммы-процедуры.

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

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

БИЛЕТ №3

3.1

Type

Rainbow = (RED, ORANGE, YELLOW, GREEN, LIGHT_BLUE, BLUE, VIOLET);

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

Описание переменных, принадлежащих к скалярным типам, которые объявлены в разделе описания типов, производится с помощью имен типов. Например:

type Traffic_Light= (RED, YELLOW, GREEN);

var Section: Traffic_Light;

Это означает, что переменная Section может принимать значения RED, YELLOW или GREEN.

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

var Section: (RED, YELLOW, GREEN);

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

К переменным перечисляемого типа может быть применим оператор присваивания:

Section:= YELLOW;

Упорядоченная последовательность значений, составляющих перечисляемый тип, автоматически нумеруется, начиная с нуля и далее через единицу. Отсюда следует, что к перечисляемым переменным и константам могут быть применены операции отношения и стандартные функции Pred, Succ, Ord.

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

Ограниченный тип данных.

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

Например,

Var a: 1..25; ch: 'a'..'z';

 

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

Переменная ограниченного типа сохраняет все свойства переменных базового типа.

Для чего вводится ограниченный тип данных? Использование ограниченного типа делает программу наиболее понятной и наглядной. Например, если в программе переменная b может принимать только значения 3, 4, 5, 6, 7, 8, то лучше описать её следующим образом: Var b: 3..8;, чем Var b: Integer; так как в случае выхода значения b за диапазон 3..8 в первом случае будет выдано диагностическое сообщение, которое поможет найти ошибку. Во втором случае будет получен неправильный результат, что затруднит поиск ошибки. Таким образом, второй вариант описания переменной следует использовать в тех случаях, когда диапазон значений заранее неизвестен либо занимает весь допустимый интервал значений для рассматриваемого типа.

 

БИЛЕТ №4

Параметры-значения подпрограмм. Пример использования

Параметры значения

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

имя: тип;

Например, передача в процедуру Р величины целого типа записывается так:

procedure P(x: integer);

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

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

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

Например, если в вызывающей программе описаны переменные

var x: integer;

c: byte;

y: longint;

то следующие вызовы подпрограммы Р, заголовок которой описан выше, будут синтаксически правильными:

P(x); P(c); P(y); P(200); P(x div 4 + 1);

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

Параметры-переменные

Признаком параметра-переменной является ключевое слово var перед описанием параметра:

var имя: тип;

Например, передача в процедуру Р параметра-переменной целого типа записывается так:

procedure P(var x: integer);

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

ВНИМАНИЕ При вызове подпрограммы на месте параметра-переменной может находиться только ссылка на переменную точно того же типа.

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

Пример.

var a, b, c, d, e: word;

procedure X(a, b, c: word; var d: word);

var e: word;

Begin

c:= a + b; d:= c; e:= c;

writeln ('Подпрограмма:');

writeln ('c = ', c, ' d = ', d, ' e = ', e);

end;

Begin

a:= 3; b:= 5;

x(a, b, c, d);

writeln ('Главная программа:');

writeln ('c = ', c, ' d = ', d, ' e = ', e);

End.

Результаты работы этой программы приведены ниже:

Подпрограмма:

c = 8 d = 8 e = 8

Главная программа:

c = 0 d = 8 e = 0

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

Прямой код

Прямой код двоичного числа совпадает по изображению с записью самого числа. Значение знакового разряда для положительных чисел равно 0, а для отрицательных чисел 1.

Пример. В случае, когда для записи кода выделен один байт, для числа +1101 прямой код 0,0001101, для числа -1101 прямой код 1,0001101.

Обратный код

Обратный код для положительного числа совпадает с прямым кодом.

Для отрицательного числа все цифры числа заменяются на противоположные (1 на 0, 0 на 1), а в знаковый разряд заносится единица.

Пример.

Для числа +1101 прямой код 0,0001101; обратный код 0,0001101.

Для числа -1101 прямой код 1,0001101; обратный код 1,1110010.

БИЛЕТ №5

Параметры-переменные подпрограмм. Пример использования

Массивы

С понятием "массив" приходится сталкиваться при решении научно-технических и экономических задач обработки совокупностей большого количества значений.

Одномерные массивы

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

Массив в Паскале

<имя массива>:= array [<количество элементов>] of <тип переменной>;

Каждый элемент массива в общем виде описывается как А[I], где

А - имя массива,

I - номер или индекс массива (0<=I<=N, но практически употребляется 1<=I<=N)

A[I] - значение элемента массива.

Действия над массивами

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

Например, если массивы А и В описаны как

var А, В: array[1..20] of real; то применение к ним допустимых операций даст следующий результат:

Выражение Результат

А=В True, если значение каждого элемента массива А равно соответствующему значению элемента массива В

А<>В True, если хотя бы одно значение элемента массива А не равно значению соответствующего элемента массива В

А:=В Все значения элементов массива В присваиваются соответствующим элементам массива А. Значения элементов массива В остаются неизменны.

Двумерные массивы

Двумерным называется массив, элемент которого зависит от его местоположения в строке и в столбце. В общем виде элемент матрицы обозначается как A(I,J), где А — имя массива, I — индекс (номер) строки,

J — индекс (номер) столбца.

Описание матрицы на языке Паскаль

Матрицу можно задать двумя способами:

<имя матрицы>: array [<количество строк>] of array [<количество столбцов>] of <тип переменной>;

<имя матрицы>: array [<количество строк >,<количество столбцов>] оf <тип переменной>].

.

 

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

Примечание:

Для использования случайных чисел в TP используются операторы random:real - генерирует случайные числа в диапазоне 0...0.99.

random(i:word):word — генерирует случайные числа в диапазоне 0...1.

randomize - изменение базы генератора случайных чисел.

program mas1;

var

a: array [1..10] of integer;

i: integer;

begin

randomize;

for i:=1 to 10 do

begin

a[i]:=random(20);

write('a(', i, ')=', a[i], ' ')

end;

readln

end.

 

 

БИЛЕТ №6

Метод простой итерации

Бесконечное произведение

Бесконечное произведение представляет собой произведение бесконечного числа сомножителей:

.

Если такое произведение стремится при i ®¥ к некоторому пределу P, то P называют значением бесконечного произведения. Если P конечно и отлично от нуля, то произведение называют сходящимся, в противном случае - расходящимся. Если бесконечное произведение сходится, то . Именно это обстоятельство можно использовать для прекращения циклических вычислений частичных произведений, а именно когда очередной сомножитель станет отличаться от 1 на величину меньше заданной погрешности e. Разберем правила решения данной задачи на конкретном примере.

БИЛЕТ №7

№7 1. Процедурный тип данных. Пример его использования

2. Сортировка символьных данных. Пример

Процедурный тип данных

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

Объявление процедурного типа похоже на заголовок подпрограммы (см. п. 10): пишется слово procedure или function, за которым в круглых скобках записывается список формальных параметров; для функции после списка формальных параметров через двоеточие указывается тип функции. В отличие от заголовка подпрограммы здесь не указывается имя подпрограммы.

Пример.

type

Proc1 = procedure; {процедура без параметров}

Proc2 = procedure(var X,Y: Integer);

{процедура с двумя параметрами-переменными целого типа}

Func1 = function(X: Real): Real;

{функция вещественного типа с одним параметром-значением}

Далее можно ввести переменные этих типов:

var

Р1: Proc1;

Р2: Proc2;

F1: Func1;

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

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

они должны компилироваться с ключом компилятора {$F+} или иметь директиву far для получения полного адреса подпрограмм;

они не должны быть стандартными процедурами и функциями;

они не должны объявляться внутри других процедур и функций;

они не должны быть типа inline или interrupt (пп. 10.5.5 и 10.5.6).

Пример.

{$F+}

procedure Swap (var A, B: Byte);

var

Temp: Byte;

begin

Temp:=A; A:=B; В:= Temp

end;

function Tan(Angle: Real): Real;

begin

Tan:=Sin(Angle) / Cos(Angle)

{проверка, что Cos(Angle)<>0, осуществляется в основной программе}

end;

{$F-}

В этом случае процедурным переменным, введенным ранее, можно присвоить значения:

Р2:= Swap;

Fl:= Tan;

а вызовы P2(I,J) и F1(X) эквивалентны соответственно Swap(I,J) и Таn(Х).

Так же как и указатель, процедурная переменная занимает 4 байта памяти, в которых помещается полный адрес подпрограммы (поэтому подпрограммы необходимо компилировать с ключом {$F+}).

 

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

 

Сортировка символьных данных. Пример.

Сортировка пузырьковым методом

Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пузырька:

{ сортировка пузырьковым методом}

procedure Bubble(var item: DataArray; count:integer);

var

i,j: integer;

x: DataItem;

begin

for i:= 2 to count do

begin

for j:= count downto i do

if item[j-1]>item[j] then

begin

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

end;

end;

end; {конец сортировки пузырьковым методом}

В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.

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

Эта версия сортировки пузырьковым методом может сортировать символьный массив в порядке возрастания значений элементов. Например, следующая короткая программа сортирует строку, которая считывается с дискового файла "test.dat". Эта же программа может использоваться с другими подпрограммами сортировки, которые приводятся в этой главе.

program SortDriver;

{эта программа будет считывать 80 или меньше символов

дискового файла "test.dat", отсортирует их и

выдаст pезультат на экран дисплея }

type

DataItem = char;

DataArray = array [1..80] of char;

var

test: DataArray;

t, t2: integer;

testfile: file of char;

{ сортировка пузырьковым методом}

procedure Bubble(var item: DataArray; count:integer);

var

i,j: integer;

x: DataItem;

begin

for i:= 2 to count do

begin

for j:= count downto i do

if item[j-1]>item[j] then

begin

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

end;

end;

end;

 

begin

Assign(testfile, 'test.dat');

Reset(testfile);

t:= 1;

 

{ считывание символов,которые будут сортироваться.}

 

while not Eof(testfile) do begin

read(testfile, test[t]);

t:= t+1;

end;

t:= t-2; {скорректировать число считанных элементов }

 

Bubble(test, t); { сортировать массив }

 

{ выдать отсортированный массив символов }

for t2:= 1 to t do write(test[t2]);

WriteLn;

end.

 

Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":

 

- исходное положение: d c a b;

- первый проход: a d c b;

- второй проход: a b d c;

- третий проход: a b c d.

При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/ 2 (n**2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу.

Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n**2-n), а для наихудшего случая будет равно 3/2 (n**2-n) раз. Вывод этих формул выходит за пределы этой книги. Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива.

Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет пять секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет небольшой телефонный справочник) потребовала бы 5000000 секунд или около 1400 часов (т.е. два месяца непрерывной работы).

Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab")

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

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

{ челночная сортировка является улучшенной версией сортировки пузырьковым методом }

procedure Shaker(var item: DataArray; count:integer);

var

j, k, l, r: integer;

x: DataItem;

begin

l:= 2; r:= count; k:= count;

repeat

for j:= r downto l do

if item[j-1] then

begin { обмен }

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

k:= j;

end;

 

l:= k+1;

 

for j:= l to r do

if item[j-1]>item[j] then

begin { обмен }

x:= item[j-1];

item[j-1]:= item[j];

item[j]:= x;

k:= j;

end;

 

r:= k-1;

until l>r

end; { конец челночной сортировки }

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

БИЛЕТ №8

1. Нетипизированные параметры подпрограмм. Явное приведение типа

2. Операторы циклов с постусловием и предусловием. Пример

Нетипизированные параметры

В Borland Pascal допускается использовать параметры, тип которых не указан. Такие параметры могут передаваться в подпрограмму только по ссылке, так как в этом случае в подпрограмму реально передается адрес параметра.

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

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

1Автоопределенное преобразование типов;

2 Наложенное описание переменной определенного типа.

При автоопределенном преобразовании типов тип выражения указывают явно, например:

Procedure Proc (Var: а);

b: = Integer (a) + 10;

Для наложения переменной определенного типа используют описание с absolute, например:

Procedure Proc (Var: а);

Var r: real absolute a;

При этом переменная r оказывается в памяти размещенной в том же месте, что и нетипизированный параметр а, и, соответственно, любое изменение r приведет к изменению а.

2.2 Цикл с постусловием “Repeat Untill” цикл повторяется до тех пор пока не будет выполнено условие… и цикл While do повторяется До тех пор пока выполняется условие.

 

 

БИЛЕТ №9

1. Структурограмма как способ записи алгоритма

2. Логический тип и операции с ним

Существуют еще формы записи, которые можно отнести к графическим.

Одной из таких форм является построение структурограмм.

 

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

 

Рассмотрите блок-схему и структурограмму алгоритма.

БИЛЕТ №10

1. Алгоритмизация: основные понятия смотри Билет №6 1 вопрос

2. Операторы условного перехода и варианта. Пример

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

if условие then оператор 1 else оператор 2;

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

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

else - часть в операторе if может отсутствовать:

if условие then оператор 1;

Тогда в случае невыполнения логического условия управление сразу передается оператору, стоящему в программе после конструкции if.

Следует помнить, что синтаксис языка допускает запись только одного оператора после ключевых слов then и else, поэтому группу инструкций обязательно надо объединять в составной оператор (окаймлять операторными скобками begin... end). В противном случае возникает чаще всего логическая ошибка программы, когда компилятор языка ошибок не выдает, но программа тем не менее работает неправильно.

 

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

Тема: Оператор выбора CASE. Решение задач.

 

Ранее Вы познакомились с условным оператором If, который позволяет программе выполнять переходы на ту или иную ветвь по значению булева условия. Используя несколько операторов If, можно производить ветвление по последовательности условий. В приведенном фрагменте показано, как при помощи ряда операторов If можно преобразовать целое число (в диапазоне 0-9) к его словесному представлению:if Ziphra = 0

then

write (‘Нуль‘);

if Ziphra = 1

then

write (‘Единица‘);

if Ziphra = 2

then

write (‘Два‘);

 

 

и т.д.

 

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

 

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

 

Общая форма записи следующая:case выражение of

значение1: оператор (группа операторов);

значение2: оператор (группа операторов);

......................

значениеN: оператор (группа операторов)

else оператор (группа операторов);

end;

 

 

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

 

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

 

Например,case NUMBER mod 2 of

0: writeln (NUMBER, ‘- число четное‘)

else: writeln (NUMBER, ‘- число нечетное‘);

end;

 

 

Если один оператор выполняется при нескольких значениях, то их можно перечислить через запятую.case MONTH of

1, 2, 3: writeln (‘Первый квартал‘);

4, 5, 6: writeln (‘Второй квартал‘);

7, 8, 9: writeln (‘Третий квартал‘);

10, 11, 12: writeln (‘Четвёртый квартал‘);

end;

 

 

Оператором может являться не только простой оператор, но также составной и пустой операторы.case CODE of

1: for i:= 1 to 5 do

writeln (‘*******‘);

2: begin {составной оператор}

x:=sqr(y-1);

writeln (x);

end;

3: {пустой оператор}

end;

 

 

Любому заданному значению селектора соответствует лишь один вход в списке операторов. Константы должны принадлежать тому же типу, что и селектор. Если селектор принимает значение, которому не соответствует ни один вход, то будет выполняться оператор, следующий за словом else. Если же этого оператора нет, то никакие альтернативы не будут выполняться.

 

Если оператор должен выполняться при нескольких значениях селектора следующих друг за другом, образуя некоторый промежуток, то это можно записать в более сжатой форме. Например,case Chislo of

0..9: write (‘Это число является цифрой‘);

 

 

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

 

Задача. Написать программу преобразования цифр в слова.Program Number1;

Var

a, b, c: integer;

Begin

writeln(‘Введите цифру ‘);

readln(a);

if (a<0) or (a>9)

then

writeln (‘Это число не является цифрой‘)

else

case a of

0: writeln (‘ноль‘);

1: writeln (‘один‘);

2: writeln (‘два‘);

3: writeln (‘три‘);

4: writeln (‘четыре‘);

5: writeln (‘пять‘);

6: writeln (‘шесть‘);

7: writeln (‘семь‘);

8: writeln (‘восемь‘);

9: writeln (‘девять‘);

end;

readln;

End.

БИЛЕТ №11

1. Алгоритмы сложных циклических процессов

2. Битовые операции в TP

Битовые операции

Если необходимо обрабатывать отдельные биты некоторой константы, то це