Название: Методы программирования - Методические указания (В.П. Хиценко)

Жанр: Информатика

Просмотров: 1167


Методические указания

 

1. Понятие цикла

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

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

a5x5 + a4x4 + ... a1x + a0.  Для сокращения вычислений приведем этот полином к скобочной записи, называемой схемой Горнера: 

(((( a5 x + a4 )x + a3 )x + a2 )x + a1 )x + a0 . Здесь повторяющейся совокупностью действий является умножение на x и сложение с очередным коэффициентом полинома. Чтобы вычислить полином, надо выполнить следующую последовательность действий: p = a5;

 p = p*x + a4;  p = p*x + a3;  p = p*x + a2;  p = p*x + a1;   p = p*x + a0.

С увеличением порядка полинома длина такой последовательности действий может быть очень большой (или даже заранее неизвестной, если порядок полинома задается переменной величиной). Выходом из этой ситуации является такая запись повторяющихся действий (называемая обобщенной записью, т. е. независимой от номера повторного выполнения), которая позволяет, описав эти действия один раз и организовав их повторение столько раз, сколько необходимо вычислить требуемое значение. В данной задаче обобщенная запись может иметь вид p = p*x + k, где k – коэффициент полинома. Перед выполнением этого действия k должна получить значение очередного коэффициента. Или вид p = p*x + ai, здесь ai  также обобщенная запись коэффициента полинома с номером i. Кроме основных действий, называемых телом цикла, цикл содержит дополнительные действия, обеспечивающие повторение тела цикла.

Таким образом, в самом общем виде структурная схема цикла содержит три части:

– действия по подготовке  цикла к первому исполнению;

– действия, являющиеся основным содержанием данного вычислительного процесса – тело цикла;

– действия, отслеживающие повторение тела цикла, – проверка условия продолжения или условия окончания повторений.

Блок-схема алгоритма вычисления значения полинома n–й степени для заданного значения x:

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

 

 

 

 

 

 

         

 

выход из цикла                                                 выход из  цикла

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

2. Циклические управляющие структуры

 – оператор цикла с предусловием:

while ( В )  S;

где B – выражение, определяющее условие выполнения тела цикла; S – оператор (тело цикла).

Структурная схема оператора цикла с предусловием:

Таким образом, тело цикла с предусловием может ни разу не выполнится, если выражение B сразу ложно. Выражение B и оператор S должны быть связаны так, чтобы когда-нибудь выражение стало ложным и, цикл завершился. 

 

– оператор цикла с постусловием:

               do  S  while ( B );

где B – выражение, определяющее условие выполнения цикла; S – оператор (тело цикла).

 

Структурная схема оператора цикла с постусловием:

Таким образом, тело оператора цикла с постусловием всегда, хотя бы один раз выполнится. Выражение B и оператор S должны быть связаны так, чтобы когда-нибудь выражение стало ложным и, цикл завершился.

– оператор пошагового цикла:

         for  (e1; e2; e3)  S;

где e1 – выражение, задающее начальные условия выполнения цикла; e2 – выражение, задающее условие продолжения цикла; e3 – выражение, изменяющее (модифицирующее) условия, заданные выражением e1; S – оператор – тело цикла. Выполнение оператора цикла for состоит из следующих действий:

        e1;

        while  (e2);

           {   S;    e3;

                              }

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

3. Схемы итерационного цикла

1.      v = v0;

while p(v)  { S; f(v) ;}

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

 

,

для всех ,

,

для всех ,

для всех ,

для всех .

 

2.      t = t0; s = t;

while p(s,t) { t = f(t); s += t ;}

Такая схема используется в задачах, реализующих какой-либо процесс последовательных приближений, например вычисление суммы ряда, заканчивающееся при условии, по которому можно судить о погрешности вычислений. При этом если t0, t1, t2,..., tn – последовательность членов ряда, то

 

для всех ,

для всех ,

для всех ,

для всех ,

для всех .

 

Реализуя приближенные вычисления, необходимо помнить, что в памяти ЭВМ действительные числа представляются приближенно и поэтому сравнение действительных значений необходимо производить, задавая уровень точности. Например, необходимо проверить, лежат ли три точки на одной прямой. Для этого в уравнение прямой, проходящей через две точки, необходимо подставить координаты третьей точки. Все точки лежат на одной прямой тогда и только тогда, когда в результате получается нуль. Из-за неточности машинной арифметики для действительных чисел нуль почти никогда не будет получен. Поэтому условие приходится считать выполненным, если полученный при подстановке результат по модулю меньше некоторого предусмотренного разработчиком малого числа, например 10-5, называемого точностью вычислений.

 

Контрольные вопросы

 

1. Понятие цикла.

2. Циклические структуры типа  while,  do,  for – их синтаксис и  семантика.

3. Понятие итерационного цикла.

4. Программирование итерационных вычислений.

5. Структура  программы на языке Си.

6. Простые типы и циклы.

 

ЛАБОРАТОРНАЯ  РАБОТА  № 3

 

Тема. Регулярные типы (массивы). Основные алгоритмы обработки массивов.

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

 

Содержание работы

 

1. Изучить правила задания массивов, их свойства и операции, допустимые над этим типом.

2. Изучить оператор цикла с заданным числом повторений.

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

 

Методические указания

 

1. Понятие сложного типа

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

Сложный тип строится по следующим правилам:

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

б) внутри сложной структуры тип всех элементов может быть

– одинаков – однородная структура,

– различен – неоднородная структура;

в) количество элементов в структуре может быть:

– фиксировано в течение времени существования структуры (структуры фиксированного размера или статические),

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

г) обращение (доступ) к элементам структуры может быть:

– непосредственное (прямое) – вычисляемое (по индексу или месту в структуре) или не вычисляемое (по имени элемента);

– последовательное – характерное для структур переменного размера.

Вид обращения определяется способом объединения компонент в единую структуру;

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

2. Массив

Регулярный тип (массив) – это сложный тип с однородной структурой фиксированного размера и прямым вычисляемым доступом к элементам. Размер структуры фиксируется при описании массива.

Задание регулярного типа  (массива) имеет  вид:

<спецификация типа> <идентификатор> [<константное выражение>]

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

Тип компонентов задается спецификацией типа. Тип компонентов может быть любым (кроме файлового). Если тип компонентов:

– простой, то определяемая структура будет одномерной (линейной);

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

Многомерный массив – это массив, элементы которого типа массив.   

Задание многомерного массива:

<спецификация типа> <идентификатор> [<K1>][K2]…[Kn]

Здесь K1, K2,...,Kn – константные выражения. Причем K1 задает размер массива по первому измерению, K2 – размер по второму измерению, а Kn – по n-му измерению.

Например, описание x[k1][k2] задает двумерный массив x (матрицу), где k1 – размер по первому измерению, т. е. количество строк в двумерном массиве - матрице, k2 – размер по второму измерению, т. е. количество столбцов в матрице. Таким образом, двумерный массив рассматривается как одномерный массив, каждый элемент которого также одномерный массив. Элементы матрицы хранятся по строкам. 

Для обращения к элементам массива необходимо указать имя массива и место (индекс) элемента в структуре:

имя массива [<индекс>]  или

имя массива [<индекс1>][<индекс2>]…[<индекс n>]  соответственно для одномерного и n-мерного массивов.

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

В многомерном массиве можно ссылаться на p-мерный подмассив n-мерного массива (p £ n).

Примеры задания переменных типа массив:

   int vector [10] ;

   float  mas [5] [25];

   char line [80];

   float x[10][10],  y[n1][n2][n3];

Переменная vector это – линейный (одномерный) массив с 10 элементами: vector [0], vector [1], ... , vector [9]. Тип каждого компонента целый.

Переменная mas это двумерный массив из 5 строк и 25 столбцов (т.е. со 125 компонентами):

    mas[0][0], mas[0][1], mas[0][2], ... , mas[0][24],

    mas[1][0],mas[1][1], ... , mas[1][24],

    mas[2][0], ... , mas[2][24], ... , mas[4][0], ... , mas[4][24],  тип компонентa float.

Если указать только один индекс, например mas[0] – это означает одномерный подмассив, т.е. строку матрицы с номером 0. 

Переменная line одномерный массив с 80 компонентами: line [0], line [1], … ,line [79], элементы типа  char.

Тип компонентов переменных x и y – float; x – двумерный массив с 10 строками и 10 столбцами – квадратная матрица размером 10 ´10; y – трехмерный массив размером n1´n2´n3. Здесь n1,n2,n3 –именованные константы, значения которых могут быть определены директивой define или с помощью модификатора const. На элементы массива y можно ссылаться:

y[0], y[1], y[2],…, y[n1-1], где y[i] означает двумерный подмассив с номером i размером n2´n3 ;

элементы более нижнего уровня обозначаются y[0][0], y[0][1], ... , y[0][n2-1], y[1][0], ... , y[n1-1][n2-1], где y[i][j] – одномерный подмассив массива y размером n3;

элементы самого нижнего уровня обозначаются y[0][0][0], y[0][0][1], ... , y[0][0][n3-1], y[0][1][0], ... ,y[0][1][n3-1], ... ,

y[n1-1][0][0], ... , y[n1-1][n2-1][n3-1].

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

Имя массива является константой-указателем на первый элемент массива. Для многомерного массива, определенного, например как «тип» А [n1][n2][n3], имя массива – константа-указатель, поставленная  в соответствие элементам типа «тип» [n2][n3]. Для вышеприведенных примеров, имени массива vector соответствует адрес первого элемента этого массива (т. е. элемента vector[0]), имя line – константа-указатель на элемент line[0]. Имя массива mas – указатель, поставленный в соответствие  элементам типа float mas[25], выражение *(mas+i) – указатель на элемент mas[i];

имя x – указатель, поставленный в соответствие элементам типа float x[10], выражение *(x+i) – указатель на элемент x[i];

имя y – указатель, поставленный в соответствие элементам типа float y[n2][n3], выражение *(y+i) – указатель, поставленный в соответствие элементам типа float[n3].

Увеличивая на единицу значение указателя, получаем адрес следующего элемента (числовое значение адреса при этом увеличивается на размер памяти элемента массива).  Имя vector указывает на первый элемент массива, а выражение vector+i, на i-й элемент после первого (т. е. vector+i – это адрес i-го элемента массива vector). Выражение *(vector+i) – это значение i-го элемента массива vector. Таким образом, записи vector[i] и *(vector+i) эквивалентны. Унарная операция * есть операция косвенной адресации. Ее результатом является значение, на которое указывает операнд – указатель. Если выражение *(mas+i) – это указатель на элемент mas[i] типа float mas[25], то выражение *(mas+i)+j это указатель на элемент mas[i][j]. Выражение *(*(mas+i)+j) – это значение элемента с адресом *(mas+i)+j, т.е. элемента mas[i][j]. Для трехмерного массива y выражение  *(y+i) – указатель на элемент y[i], выражение  *(y+i)+j – указатель на элемент  y[i][j], а выражение  *(*(y+i)+j)+k – указатель на элемент y[i][j][k], выражение *(*(*(y+i)+j)+k) – это значение элемента y[i][j][k].

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

Объявление переменной указателя на значение специфицированного типа:

<спецификация типа> * <идентификатор>;

Пример:

int *pv;

float *py;

Переменная pv – это указатель на значение типа int (т.е. значение pv это адрес области памяти, в которой может храниться число типа int), а py – указатель на значение типа float. Для вышеописанных массивов в результате присваивания pv=vector, pv будет указывать на первый элемент массива, иначе говоря, значение pv – это адрес элемента vector[0];

*pv – это операция косвенной адресации, ее результатом является значение первого элемента массива, что эквивалентно  vector[0];

*(pv+i) – это операция косвенной адресации, результатом которой будет значение i–того элемента массива, что эквивалентно   vector[i], если pv указывает на первый элемент массива (если нет, то на  i-ый после pv, а pv-i  на  i-й перед pv).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

vector:

 

        

 

              vector[0]                                                   vector[9]    

 

Переменную py можно использовать для ссылки на любой из массивов с элементами типа float. Если присвоить py = &mas[0][0], то py равно указателю на mas[0][0], выражение py+i*25+j – это адрес элемента y[i][j]. Если присвоить py = &x[i][j], то py указывает на x[i][j] элемент массива x, если присвоить py = &y[0][0][0], то py – это адрес y[0][0][0], а выражение py+i*n2*n3+j*n3+k – это указатель на элемент  y[i][j][k].

В общем случае для двумерного массива А из m строк и n столбцов указатель на элемент A[i][j] вычисляется по формуле x+i*n+j, где x указатель на первый элемент массива А, т.е. на элемент А[0][0]. (Примечание: числовое значение адреса A[i][j] при этом вычисляется по формуле: (x+i*n+j)*sizeof («тип элемента»).)

Над элементами массива можно выполнять все операции, допустимые для типа элемента.

3. Применение массивов при решении задач

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

Особенностью алгоритмов обработки массивов является то, что все или большинство (или какое-то число) элементов обрабатываются одинаково (по одному алгоритму). Поэтому, решая задачу, приходится в том или ином порядке просматривать (перебирать) элементы массивов. Чтобы осуществить перебор, надо определить правило изменения индекса элементов (для многомерных массивов – индексов). В случае многомерных массивов (если индексы не должны изменяться одновременно) изменение одного индекса должно быть вложено в правило изменения другого. Пример: для матрицы float a [10][5] перебор элементов можно организовать по строкам, столбцам или диагоналям. Если перебор идет по строкам, то первый индекс (индекс строки) изменяется  0£ i £9, второй индекс (индекс столбца) изменяется

0£ j £4 для каждого значения i.

Схема обработки всех элементов матрицы может быть представлена следующим образом:

i := v0;

while (i £ vn )

           {S1;   j := t0;

                         while( j £ tm )

                                         {  S2;  j := j+1 ;}

                         S3;  i := i+1;}

Здесь i принимает последовательно значения v0, v0+1, v0+2, … , vn. Ее можно использовать в операторах    S1, S2, S3  как один из индексов (номер строки или столбца) элемента матрицы. Переменная j принимает последовательно значения t0, t0+1, t0+2, … , tm и ее можно использовать в операторе S2 как второй индекс (номер столбца или строки).

4. Рекомендации

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

for v = a; v £ b; v++) S,                                 (1)

где v – параметр цикла – переменная целого типа; a – начальное значение параметра цикла; b – конечное значение параметра цикла (a и b задаются выражениями, при этом a £ b); S – оператор (тело цикла)

или

for (v =a; v³b; v-- ) S;                                (2)

здесь a ³ b.

Выполнение действий в цикле происходит следующим образом:

в цикле (1):

        v = a;

while (v £ b) {S; v++;}

 

в цикле (2):

          v= a;

       while( v ³ b) {S; v--;}

 

Шаг изменения параметра цикла v может быть (по модулю) и больше единицы.

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

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

# define n 20

# define m 10

main (  )

{

int p,k,i,j,x[n][m];

printf (“ введи размер матрицы”);

scanf(“\%d\%d”, &p,&k);

Тогда ввод значений элементов массива x можно описать:

– по строкам    for (i=0; i<p; i++ )

                          for (j=0; j<k; j++) scanf (“\%f”, &x[i][j]);

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

– по столбцам  for (i=0; i<k; i++ )

           for (j=0; j<p; j++) scanf( “\%f”, &x[j][i]);

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

Контрольные вопросы

1. Понятие сложного типа данных.

2. Понятие типа массив, задание этого типа и операции над типом.

3. Задание многомерного массива.

4. Обращение к элементам массива.

5. Обращение к элементам массива через указатели.

6. Использование массива при решении задач.