Общая форма записи цикла со счетчиком

for i := A to B do begin . . . end;

for i := A downto B do begin . . . end;

Здесь переменная i - управляющая переменная или переменная цикла,

А - начальное значение переменной цикла,

В - конечное значение переменной цикла.

При переходе к обработке оператора цикла for управляющей переменной присваивается заданное начальное значение. Затем в цикле выполняется исполнительный оператор (или составной оператор). Каждый раз при выполнении исполнительного оператора управляющая переменная увеличивается на 1 (для for...to) или уменьшается на 1 (для for...downto). Цикл завершается при достижении управляющей переменной своего конечного значения.

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

for i := 1 to 10 do begin . . . i := i-1; . . . end;

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

20. Форматы Ch, Ch:p. Примеры.

Пример 6: Спецификация Ch.

Ch - начиная с позиции курсора выводится значение Ch.

Значение R	Выражение	Результат
'X'	Write(Ch);	X
'Y'	Write(Ch);	Y
'!'	Write(Ch, Ch, Ch);	_!!!

Пример 7: Спецификация Ch:p.

Ch:p - в крайнюю правую позицию поля шириной "p" выводится значение Ch.

Значение R	Выражение	Результат
'X'	Write(Ch:3);	__X
'Y'	Write(Ch:5);	____Y
'!'	Write(Ch:2, Ch:4, Ch:3);	_!___!__!

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

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

Алгоритм решения задачи:

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

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

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

3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.

4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.

5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.

6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.

7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).

8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

Программа на языке Паскаль:

const m =10; vararr:array[1..m]ofinteger;i, j, k:integer; beginrandomize; write('Исходный массив: ');fori:= 1 to m dobeginarr[i]:=random(256);write(arr[i]:4);end;writeln; writeln; fori := 1 to m-1 doforj := 1 to m-i doifarr[j]>arr[j+1]thenbegink :=arr[j];arr[j]:=arr[j+1];arr[j+1]:= kend; write('Отсортированный массив: ');fori := 1 to m dowrite(arr[i]:4); writeln; readlnend.

Общая форма записи цикла со счетчиком - student2.ru

22. Процедура, определенная пользователем

Функция, определенная пользователем, состоит из заголовка и тела функции.

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

function<имя> (Формальные параметры) :<тип результата>;

const ...

type ...

var

begin

<операторы>

end;

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

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

program DemoFunc; Var М : integer; А,Z,R : real ; {Функция вычисления степени. N - степень, X – число, возводимое в данную степень. N, X – формальные параметры; результат, возвращаемый функцией в точку вызова, имеет вещественный тип} function Step(N : integer; X : real): real; Var I : integer; Y : real; begin Y:=1; for I:=1 to N do {Циклвычисления N–йстепеничисла X} Y:=Y*X; Step:=Y ; {Присваивание функции результата вычисления степени} end; {Конец функции} Begin {Начало основной программы} Write('Введите значение числа А и показатель степени М'); Readln(A,M) ; Z:=Step(5,А) ; {Вызов функции с передачей ей фактических параметров N=5, X=А} Z:=Z+ Step(3,l/A); {Вызов функции с передачей ей фактических параметров N=3, X=1/А} ifM=0 thenR:=l {если число возводится в нулевую степень, то результат всегда равен 1} elseifM>0 thenR:=Step(M,A){Вызов функции Step с передачей ей фактических параметров М, А} elseR:=Step(-M,A); {Вызов функции с передачей ей фактических параметров: - М, отрицательная степень} Z:=Z/(2*R) ; Writeln(' Для А= ',А,'М= ',М,' Значение выражения= ',Z); end.

23. Исполнение алгоритма

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

24. Операции над множествами.

К переменным типа set применимы следующие операции: =, <>, >=, <=, in, +, -, *.

Операции = и <> используются для проверки эквивалентности: два значения переменной типа set считаются равными, если они состоят из одних и тех же элементов.

Пример.

[1, 3] = [3, 1] возвращает true,

[1..3] = [1, 2, 3] возвращает true,

[1] <> [2] возвращает true,

[1, 2, 3] = [1, 4, 3] возвращает false,

[red, blue] = [red, yellow] возвращает false.

Операции >= и <= используются для проверки принадлежности одного множества другому: так, если множество a содержится во множестве b, то a <= bдает true.

Пример.

[1, 2] <= [1, 2, 3] дает true

Пустое множество [ ] содержится во всех множествах, т.е. всегда [ ] <= [b] даетtrue.

Операция in используется для установления наличия определенного элемента в величине типа set. Так, если x есть элемент множества b, то (x in b) дает true. Общий вид:

x in a;

здесь x – величина базового типа, a – величина типа set.

Пример.

red in [red, yellow] возвращает true;

red in [blue, green] возвращает false.

Замечание 1. Чтобы проверить, является ли значение n цифрой, удобно использовать операцию in следующим образом:

if n in [0..9] then …

Замечание 2. Результат операции in может быть неопределенным в некоторых случаях.

Пример. Пусть

a: set of 1..50;

x: integer.

Если заслать в x число, большее максимального значения 50 (например, x := 55), то в этом случае результат операции x in a не всегда false.

К переменным типа set, относящимся к одному и тому же конкретному типу, применимы операции:
+ объединение;
* пересечение;
- дополнение.

Пусть a и b – операнды, имеющие один и тот же конкретный тип. Тогда
a + b представляет собой объединение множества элементов, входящих в a и b(одинаковые элементы не повторяются).
a * b – пересечение множества элементов a и b (только те, которые есть в обоих множествах).
a – b – множество элементов, которые есть в a, но отсутствуют в b.

Пример.

[1, 3] + [1, 4] = [1, 3, 4];

[1, 3] * [1, 4] = [1];

[1, 3] - [1, 4] = [3].

Операция a := a + x добавляет элемент x к множеству a. Если x уже имелся в a, то множество a не меняется. a := a – x исключает x из a. Если x отсутствовал в a, то множество a не меняется.

25. Арифметические процедуры и функции.

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

Таблица 3.1. Стандартные функции

Стандартная функция	Выполняемое действие	Тип
аргумента	результата
abs (x)	\|x\|	real	real
integer	integer
sqr (x)	x²	real	real
integer	integer
sqrt (x)	x^1/2	real	real
integer	real
exp (x)	e^x	real	real
integer	real
ln (x)	ln (x)	real	real
integer	real
sin (x)	sin (x)	real	real
integer	real
cos (x)	cos (x)	real	real
integer	real
arctan (x)	arctg (x)	real	real
integer	real
pi	число Π	-	real

процедура dec(х,n) уменьшает значение целочисленной переменной х на n . Например, х:=10; dec (х, 2); {результат: 8} . При отсутствии необязательного параметра n процедура принимает вид deс(х) , а значение х уменьшается на единицу;

• процедура inc(х,n) увеличивает значение целочисленной переменной х на n. Например, х:=10; inc(х,3);{(результат: 13}. При отсутствии необязательного параметра nпроцедура принимает вид inс (х), а значение х увеличивается на единицу;

Процедура clrscr очищает экран и помещает курсор в его левый верхний угол. Для того чтобы процедура clrscr была доступна программе, в ее начало помещается строка usescrt;.

. В том случае, если нам необходимы вещественные случайные числа из другого диапазона: b>x>=а, мы можем задать его при помощи random*b+a. Перед первым обращением к функции random необходимо с помощью вызова процедуры randomize инициализировать программный генератор случайных чисел. В противном случае при каждом запуске программы датчик будет выдавать одни и те же числа. Эту особенность можно использовать при отладке программы;

26.Линейные алгоритмы

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

Общая форма записи цикла со счетчиком - student2.ru

27. Поиск различных чисел в массиве.

Program DI1ID1;

VAR

A: ARRAY[1..20] OF REAL;

B: ARRAY[1..20] OF REAL;

K: ARRAY[1..20] OF INTEGER;

I,J,N,M: INTEGER;

Begin

Writeln ('Введите нужное количество искомых чисел n'); Read (n);

Writeln ('Введитечисла n');

For i:=1 to n do

Read(A[I]);

M:=0;

FOR I:=1 TO N DO

BEGIN

B[M+1]:=A[I]; J:=1;

WHILE B[J]<>A[I] DO

J:=J+1;

IF J=M+1

THEN

BEGIN M:=M+1; K[M]:=1; END

ELSE K[J]:=K[J]+1;

END;

WriteLn('Количество различных чисел ', M:3);

FOR I:=1 TO M DO

WriteLn('B[',I:2,']=',B[I]:2:0,' K[',I:2,']=', K[I]:2);

END.

28. Оператор выбора case.

Если один оператор if может обеспечить выбор из двух альтернатив, то оператор выбора case позволяет сделать выбор из произвольного числа имеющихся вариантов. Он состоит из выражения, называемого селектором (selection – выбор альтернативы), и списка параметров, каждому из которых предшествует список констант выбора (список может состоять и из одной константы).

Формат записи оператора case:

case<выражение-селектор>of

<список1>: <оператор1; >

<список2>: <оператор2; >

…

<списокN>: <onepaторN>

else<оператор>

end;

Оператор case работает следующим образом. Сначала вычисляется значение выражения-селектора, затем обеспечивается реализация того оператора, константа выбора которого равна текущему значению селектора. Если ни одна из констант не равна текущему значению селектора, выполняется оператор, стоящий за словом else. Если слово else отсутствует, активизируется оператор, находящийся за словом end, т. е. первый оператор за границей case.

program Day_Week;

varDay : byte;

begin

Write ('Введите номер дня недели: ');

Readln(Day) ;

caseDayof {Вычисление значения селектора и выбор}

1: Writeln('Понедельник') ;

2: Writeln('Вторник') ;

3: Writeln('Среда');

4: Writeln('Четверг');

5: Writeln('Пятница');

6: Writeln('Суббота' ) ;

else

Writeln('Воскресенье');

end;

end.

29. Алгоритмы с разветвлением.

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

Общая форма записи цикла со счетчиком - student2.ru

30.Задача о коне на шахматной доске.

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию»

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

Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 ^[1].

Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.

Пример на фигуре(слон)

На шахматной доске слон и фигура. Разработать алгоритм в котором требуется выяснить бьёт ли слон фигуру.

Слон XS. Фигуры XF

Общая форма записи цикла со счетчиком - student2.ru

31 Быстрый последовательный поиск.

Дан массив целых чисел А размерности n (1≤n≤10). Составьте программу, которая будет находить все различные числа в нем и подсчитывать, сколько раз каждое из этих чисел встречается в массиве. Ввод исходных данных организуйте следующим образом:

1-я строка: n;

2-я строка: а₁а₂а₃. . . а_n.

Результат выведите следующим образом:

m (m – найденное количество различных чисел)

Различные числа

b₁b₂b_{3 . . .}b_m

Частота чисел

k₁k₂k₃. . . k_m

Program DI1ID1;

VAR

A: ARRAY[1..20] OF REAL;

B: ARRAY[1..20] OF REAL;