Базовые алгоритмические структуры

3. Следование и ветвление

4. Команды повторения

4) Цикл со счётчиком

5) Цикл с условием

6) Вложенный цикл

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

Базовая структура ветвление. Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведёт к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

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

Структура ветвление существует в четырёх основных вариантов:

- если-то

- если-то-иначе

- выбор

- выбор-иначе

Команды повторения

Цикл со счётчиком

Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Циклические алгоритмы бывают двух типов: циклы со счётчиком, в которых тело цикла выполняется определённое количество раз, циклы с условием, в которых тело цикла выполняется до тех пор, пока выполняется условие.

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

нц для i от i1 до i2

тело цикла (последовательность действий)

кц

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

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

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

Цикл типа пока

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

Цикл с послеусловием сначала предписывает выполнение цикла, а затем проверку условия, и в этом случае команды тела цикла выполняются один раз обязательно.

Вложенные циклы

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

3. Заполнить таблицу размерности n*n:

1 2 3 … n-1 n

0 1 2 … n-2 n-1

……….

0 0 0 … 1

program gg;

var

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

i,j,n,k:integer;

begin

writeln('Enter n:');

readln(n);

writeln('Array:');writeln;

for j:=1 to n do

for i:=1 to n do

a[i,j]:=0;

for i:=1 to n do begin k:=1;

for j:=i to n do

begin

a[i,j]:=k;

k:=k+1;

end;end;

for i:=1 to n do begin

for j:=1 to n do begin

write(a[i,j]:3,' ');end;

writeln;

end;

readln;

end.

БИЛЕТ №30

1. Группы (подгруппы), поля и кольца.

Алгебра Е=<G,*,’> называется группой, если ее главные операции удовлетворяют условиям (аксиомам):

1) бинарная операция * ассоциативна, т.е. для любых эл-ов a, b, c из G а*(b*c)=(f*b)*c;

2) в G имеется правый нейтральный элемент относительно операции *, т.е. такой элемент е, что а*е=а для всякого эл-та а из G;

3) для любого Эл-та а из G а*а’=е.

ОПР: Группа Е=<G,*,’> называется абелевой или коммутативной, если бинарная операция группы * коммутативна, т.е. для любых a, b из G a*b=b*a.

ОПР: Порядком группы Е=<G,*,’> называется число Эл-ов основного множ-ва G группы, если G конечно. Если G – бесконечное множество, то группу Е называют группой бесконечного порядка.

При мультиплмкативной записи бинарную операцию группы наз-т умножением и пишут a∙b (ab) вместо а*b, называя Эл-т ab произведением Эл-ов а и b. При аддитивной записи бинарную операцию группы наз-т сложением и пишут a+b вместо а*b, называя Эл-т а+b суммой Эл-ов a и b. Эл-т, симметричный Эл-ту а, обозначают (-а) и называют противоположным Эл-ту а. Нейтральный Эл-т относительно сложения обозначают символом 0 или 0Е и называют нулевым Эл-ом или нулем группы.

П-р: Пусть Q – множ-во всех рациональных чисел с обычным сложением и унарной операцией -, операцией перехода от числа а к противоположному числу (-а). Алгебра Q=<Q,+,-> является группой. Она называется аддитивной группой рациональных чисел.

Подгруппой группы Е называется любая подалгебра этой группы.

Алгебра Н=<Y, ○, ^-1> типа (2,1) называется подгруппой группы Е=<G, ▪, ^-1>, если Н?G и тождественное отображение множ-ва Н в G мономорфизмом алгебры Н в Е, т.е. выполняется усл-я:

1) a○b= a∙b доля любых a,b из Н;

2) а^-1=a^-1 для а Н.

Теорема: Любая подгруппа группы является группой. Нейтральный элемент группы является нейтральным элементом любой ее подгруппы.

Пример1. Множество положительных чисел R₊ является группой относительно умножения чисел. Единицей этой группы явля­ется число 1

Пример2. Множество R вещественных чисел — абелева группа относительно сложения; число ноль является единицей этой группы. Множество Z целых чисел - дискретная подгруппа группы R.

Пример3. Абелевой группой является линейное пространст­во Rⁿ=R*R*...*R. Любое линейное (векторное) про­странство является в первую очередь непрерывной абелевой группой относительно сложения векторов. В ней введено ум­ножение элементов на числа.

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

Пример. Группа всех подстановок над n элементами.

ОПР: Кольцом называется алгебра К=<K,+,-,∙,1>, главные операции которой удовлетворяют следующим усл-ям:

1) алгебра <K,+,-> есть абелева группа;

2) алгебра <K,∙,1> есть моноид;

3) умножение дистрибутивно относительно сложения, т.е. для любых Эл-ов a,b,c из К (a+b)∙c=a∙c+b∙c, c∙(a+b)=c∙a+c∙b.

ОПР: Группа <K+,-> называется аддитивной группой кольца К. Нуль этой группы, т.е. нейтральный эл-т относительно сложения, наз-ся нулем кольца и обозначается ч/з 0 или 0К.

ОПР: Моноид <K,∙,1> называется мультипликативным моноидом кольца К. Эл-т 1, обозначаемый также ч/з 1 , являющийся нейтральным относительно умножения, называется единицей кольца К.

Кольцо К наз-ся коммутативным, если a∙b=b∙a для любых эл-ов a,b кольца. Кольцо К наз-ся нулевым, если |К|={0K}.

ОПР: Кольцо К наз-ся областью целостности, если оно коммутативно, 0 ≠1 и для любых a,b R из a∙b=0 следует а=0 или b=0.

ОПР: Эл-ты а и b кольца К наз-ся делителями нуля, если а≠0, b≠0 и ab=0 b или ba=0.

ПОЛЯ

ОПР: Эл-т а кольца К наз-ся обратимым эл-ом кольца, если в кольце сущ-т такой Эл-т b, что ab=ba=1 . при этом эл-ты a и b наз-ся взаимно обратными.

ОПР: Полем наз-ся коммутативное кольцо, в котором нуль отличен от 1, 0 ≠1 , и всякий ненулевой Эл-т яв-ся обратимым эл-ом кольца.

ОПР: Пусть F=<F,+,-,∙,1> - поле. Группа <F,+,-,1> наз-ся аддитивной группой поля. Ей нейтральный Эл-т наз-ся нулем поля и обознач-ся символом ноль при 0 . Эл-т 1, нейтральный относительно умножения,наз-ся ед-ей поля и обозн-ся так же символом 1 .

ОПР: Под полем поле F наз-ся подкольцо поля F, в котором всякий ненулевой Эл-т обратим. Подполе поля F, отличное от F, наз-ся собственным подполем. Ясно, что всякое подполе яв-ся полем.

ОПР: Поле наз-ся простым, если оно не имеет собственных подполей