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

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, наз-ся собственным подполем. Ясно, что всякое подполе яв-ся полем.

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