Лекции. Основные понятия и определения

• Название: Основные понятия и определения
• Дата: 27.03.2018
• Размер: 1.94 Mb.
• Имя файла: Лекции.docx
• Тип: Контрольные вопросы; #39570
• страница: 14 из 58

5.5. Составная инструкция

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

Формат:

{<инструкция>;[<инструкция>;]...}

Пример. Найти x=max(a, b), y=min(a, b).

if(a>b){

x=a; y=b;

}else{

x=b; y=a;

}

В языке Basic такой инструкции нет по той же причине, что и пустой инструкции.

5.6. Циклы

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

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

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

Дано: {a_i}, i=1...100. Найти сумму(a_i>0) и сумму(a_i<0).

C

u=v=0; i=0; // Инициализация цикла

begin: if(i>=100) goto end; // Условие окончания

if(a[ i ]>0)u+=a[ i ]; if(a[ i ]<0)v+=a[ i ]; // Тело цикла

i++; // Изменение условия

goto begin; // Переход к началу

end: ;

Basic

u=0 : v=0 : i=0 ' Инициализация цикла

begin: If i>=100 ThenGoto konec ' Условие окончания

If a( i )>0 Then u+=a(i) ' Тело

If a( i )<0 Then v+=a(i) ' цикла

i+=1 ' Изменение условия

Goto begin ' Переход к началу

konec: ..................................

Дано: {a_i}, i=1...100. Найти y=max{a_i} и его номер.

С

MaxElem=a[0]; NumbMaxElem=i=1; // Инициализация цикла

Begin: if(i>=100) goto End; // Условие окончания

if(MaxElem

MaxElem=a[ i ]; NumbMaxElem=i+1; //

} // цикла

i++; // Изменение условия

goto Begin; // Переход к началу

End: ;

Basic

MaxElem=a(0) : NumbMaxElem=1 : i=1 ' Инициализация цикла

Begin: If i>=100 Goto Konec ' Условие окончания

If MaxElemThen MaxElem=a(i) : NumbMaxElem=i+1' Тело цикла

i+=1 ' Изменение условия

Goto Begin ' Переход к началу

Konec: ...........................................

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

Пример. Цикл с постусловием.

MaxElem=a(0) : NumbMaxElem=1 : i=1

Begin: If MaxElemThen MaxElem=a(i) : NumbMaxElem=i+1

i+=1

If i<100 Goto Begin

Konec: ...........................................

5.6.1. Циклы с предусловием

Наиболее употребительный тип инструкции цикла. Существует несколько форм таких инструкций и в языке C, и в языке Basic. Назовем их условно циклы while и циклы for.

Циклы while

C

Формат:

while(<условие>)<инструкция>;

Эквивалентная схема:

label: if(<условие>){<инструкция>; goto label;}

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

Замечания.

1. Тело цикла – 1 инструкция. Следовательно, при необходимости выполнения в теле нескольких действий нужно использовать составную инструкцию.

2. Для того, чтобы цикл когда-либо закончился (не произошло зацикливания), необходимо в теле цикла изменять переменные, входящие в условие.

3. Заметим, что задание начальных значений в инструкцию не входит. Следовательно, для этой цели необходимо использовать отдельные инструкции, расположив их перед инструкцией while.

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

Пример. Найти Σxⁿ/n!,n=1,2,..., пока |u_n|>5e-6.

Рекуррентное соотношение: u_n/u_n-1=xⁿ*(n-1)!/x^n-1*n!=x/n →u_n=u_n-1*x/n

s=0;

u=n=1;

while(fabs(u)>5e-6){

u *= x/n; s += u; n++;

}

Basic

Формат:

Do While <условие>

<инструкции>

Loop

Пример. Тот же.

s=0 : u=1 : n=1

Do While Abs(u)>5e-6

u *= x/n : s += u : n += 1

Loop

Допустима другая разновидность этой инструкции:

Do Until <условие>

<инструкции>

Loop

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

Пример.

s=0 : u=1 : n=1

Do Until Abs(u)<=5e-6

u *= x/n : s += u : n += 1

Loop

Есть еще 1 инструкция, более похожая на инструкцию языка C:

While <условие>

<инструкции>

End While

Работает так же, как инструкция Do While ... Loop.

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

- число повторений тела цикла не определено;

- неизвестна закономерность повторений или она сложна.

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

Циклы for

C

Формат:

for([<выражение 1>];[<выражение 2>];[<выражение 3>])

[<инструкция>];

Эквивалентная схема

<выражение 1>;

while(<выражение 2>){

<инструкция>

<выражение 3>;

}

Замечания.

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

2. Тело цикла – одна инструкция, которая может отсутствовать.

Примеры.

Дано: {a_i}, i=1...100. Найти сумму(a_i>0) и сумму(a_i<0).

u=v=0;

for(i=0; i<100; i++){

if(a[ i ]>0)u+=a[ i ]; if(a[ i ]<0)v+=a[ i ];

}

Найти Σxⁿ/n!,n=1,2,..., пока |u_n|>5e-6.

s=0;u=1;

for(n=1; fabs(u)>5e-6; n++){

u *= x/n; s += u;

}

Определить число цифр натурального числа n.

for(k=0; n!=0; n/=10)k++;

Найти первый отрицательный элемент массива. Если его нет, то ответ должен быть равным 0.

for(i=0; i<100 && a[ i ]>=0; i++); // Тело цикла отсутствует

if(i==100){

y=0;

}else{

y=a[ i ];

}

Замечания.

1. Как видно из примеров, почти все циклы используют для своей организации некоторую переменную, которую называют параметром или счетчиком цикла. См. переменные i, n, k, i в порядке следования примеров. Эту переменную не рекомендуется изменять в теле цикла, поскольку логика алгоритма становится запутанной.

2. После окончания цикла параметр сохраняет последнее присвоенное значение. В последнем примере i равно 100, если отрицательных элементов в массиве нет, или равно первому по порядку следования в массиве отрицательному элементу.

3. Это наиболее универсальная форма инструкции цикла.

Basic

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

Формат:

For <счетчик>=<начало> To <конец> [Step <шаг>]

<инструкции>

Next [<счетчик>]

Эквивалентная схема:

<счетчик>=<начало>

Do While <шаг> < 0 And <счетчик> >= <конец> Or _

<шаг> >=0 And <счетчик> <= <конец>

<инструкции>

<счетчик> += <шаг>

Loop

Замечания.

1. <счетчик> - переменная (без индексов!) числового типа, <начало>, <конец>, <шаг> - арифметические выражения.

2. Если опция (часть инструкции) Step отсутствует, то шаг равен 1.

3. Отсутствие <счетчика> в инструкции Next не влияет на работу цикла, являясь, по существу, дополнительным комментарием, особенно при вложенных циклах, о которых речь пойдет ниже.

4. Значение <счетчика> после окончания цикла равно последнему присвоенному значению (как в языке C).

5. Значения <начало>, <шаг> и <конец> вычисляются 1 раз при входе в цикл. Изменение переменных, входящих в эти выражения, в инструкциях тела цикла не влияют на число повторений, поэтому так действовать не следует.

Пример. Дано: {a_i}, i=1...100. Найти сумму(a_i>0) и сумму(a_i<0).

u=0 : v=0

For i=1 To 100

If a(i)>0 Then u += a[i] : If a(i)<0 Then v += a(i);

Next i

5.6.2. Циклы с постусловием

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

C

Формат:

do <инструкция> while <условие>;

Эквивалентная схема:

label: <инструкция>;

if(<условие>)goto label;

Пример. Дано: {a_i}, i=1...100. Найти Σa_i и Πa_i.

s=i=0;

p=1;

do {

s += a[ i ]; p *= a[ i ]; i++;

} while(i<100);

Basic

Формат:

Do

<инструкции>

Loop {While | Until} <условие>

Пример. Тот же.

s=0 : i=0 : p=1

Do

s += a( i ) : p *= a( i ) : i += 1

Loop While i<100

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

Суть: инструкция тела цикла есть другая инструкция цикла.

Примеры.

1.Умножение матриц. C=A*B, где:

{a_ik}, i=1... m, k=1... n; {b_kj}, k=1...n, j=1... l; {c_ij}, i=1...m, j=1...l c_ij=Σa_ik*b_kj

C

for(i=0; i

for(j=0; j

c[ i ][ j ]=0;

for(k=0; k

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ];

}

}

}

Basic

For i=0 To m-1

For j=0 To l-1

c( i, j )=0

For k=0 To n-1

c( i, j ) += a( i, k )*b( k, j )

Next k

Next j

Next i

2.Сортировка по неубыванию элементов массива методом "пузырька".

C

pr=true; // pr – признак наличия перестановки: true - есть перестановка,

// false - нет

while(pr){

pr=false;

for(i=0; i

if(a[ i ]>a[ i+1 ]){ // Сравнение "соседей"

// Выполняется перестановка

b=a[ i ]; a[ i ]=a[ i+1]; a[ i+1]=b; pr=true;

}

}

}

Basic

pr=True ' pr – признак наличия перестановки: true - есть перестановка,

‘ false - нет

Do While pr

pr=False

For i=1 To n-1

If a(i)>a(i+1)) ' Сравнение "соседей"

‘ Выполняется перестановка

b=a( i ): a( i )=a(i+1): a(i+1)=b: pr=True

End If

Next i

Loop
3.Цикл с вещественным(дробным) параметром. Вычислить значение функции P(x)=a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀ при изменении x от 2 до 3 с шагом dx=0.1.

Схема Горнера – вычисление полинома (многочлена): вывод формулы.

a₃x³+a₂x²+a₁x+a₀= (a₃x+a₂)x²+a₁x+a₀= ((a₃x+a₂)x+a₁)x+a₀

C

j=-1;

for(x=2; x<3.05; x+=.1){// Формирование массива значений

j++;

p[ j ]=0; // Вычисление значения полинома для заданного x

for(i=n; i>=0; i--){

p[ j ]=p[ j ]*x+a[ i ];

}

}

Ограничение x 3.05 выбрано из-за возможных ошибок округления дробного значения параметра. Цикл при x=3 выполнится, при x – нет. При ограничении 3.0 нет гарантии выполнения цикла при x=3.

Basic

j=-1

For x=2 To 3.05 Step 0.1 ' Формирование массива значений

j=j+1

p( j )=0 ‘ Вычисление значения полинома для заданного x

For i=n To 0 Step -1

p( j )=p( j )*x+a( i )

Next i

Next x
4. Дана матрица {a_ik}, i,k=1...10. Найти {b_i}, i=1...10, где

1, если в i-й строке диагональный элемент максимален

b_i=

0, если нет

C

for(i=0; i<10; i++){

for(k=0; k<10 && a[ i ][ k ]<=a[ i ][ i ]; k++);

if(k==10){

b[ i ]=1;

}else{

b[ i ]=0;

}

}

Basic

For i=0 To 9

k=0

Do While k<10 And a(i,k)<=a(i,i)

k += 1

Loop

If k=10 Then b(i)=1 Else b(i)=0

Next i