close

Вход

Забыли?

вход по аккаунту

?

LR5 ukr

код для вставкиСкачать
Лабораторна робота №5
Одновимірні масиви
Ціль завдання:
1) Розробка програми в IDE (MS VS, Dev C++, C++Builder, Codeblock) 2) Надбання навичок у роботи з одновимірними масивами
Теоретичні відомості
Массивы - это однородные данные (т.е. данные одного типа), расположенные в последовательных ячейках оперативной памяти. Так как все элементы таких данных имеют одинаковую длину, то для идентификации любого элемента достаточно знать его порядковый номер в последовательности и адрес первого элемента массива. Это позволяет использовать общее групповое имя для всех элементов массива и выделять каждый из них лишь индексом (или индексами), соответствующим порядковому номеру элемента.
В простейшем случае для так называемых одномерных массивов (векторов ) индекс массива и его порядковый номер совпадают. Так как в языках C, C++ принято отсчитывать индексы от 0, то обозначениеxy[2] соответствует третьему элементу массива с именем xy. Если элементы этого массива имеют тип double и начальный элемент xy[0]расположен в оперативной памяти с адресом 0x02000000, то для вычисления адреса элемента xy[2] достаточно выполнить пару операций - 0x02000000+2*8. Естественно, что такого рода операции перекладываются на компилятор, а программист может записывать алгоритм обработки элементов массива, манипулируя с индексами его элементов. Это приближает запись программы к общепринятым математическим обозначениям ( xy[j]соответствует элементу xyj ) и позволяет писать достаточно компактные программы, близкие по идеологии к формулам, принятым в математике. Например, определение суммы элементов массива xy, содержащего 20 компонент, выглядит следующим образом:
for(s=0,j=0; j<=19; j++) s=s+xy[j];
Элементы двумерных массивов ( матриц ) характеризуются двумя индексами w[i][j], где i представляет номер строки, а j - номер столбца матрицы, на пересечении которых находится элемент wi,j. В системах программирования на базе языка C принято располагать в памяти элементы матриц по строкам - w[0][0], w[0][1], w[0][2],..., w[0][n], w[1][0], w[1][1],.... Поэтому для вычисления адреса элемента w[i][j]необходимо подсчитать значение выражения:
address(w[0][0])+(i*n+j)*size_w
Здесь
* address(w[0][0]) - адрес начала массива w в оперативной памяти
* size_w - длина в байтах каждого элемента массива w.
По сути дела, выражение i*n+j, где n - количество элементов в строке, определяет порядковый номер элементаw[i][j] в матрице w и носит название приведенного индекса. Обозначения элементов массива, более привычные для программиста, компилятор преобразует в выражения с указателями по правилам приведения индекса:
a[6] эквивалентно *(a+6)
b[1][2] эквивалентно *(*(b+1)+2)
Эти преобразования основаны на следующих соглашениях языка C. Имя одномерного массива a одновременно является указателем на его первый элемент, т.е. значением, доступным по адресу *a, является элемент массиваa[0]. Имя двумерного массива b одновременно является указателем на указатель его первой строки, т.е. значением, доступным по адресу **b, является элемент массива b[0][0]. Указатель b+1 "смотрит" на указатель, определяющий адрес первого элемента второй строки массива b. Смысл подобного рода преобразований заключается в повышении эффективности программы, т.к. операции с указателями выполняются намного быстрее. Иногда к такого рода преобразованиям прибегают и программисты, например, сводя обработку двумерного массива к одномерным приведенным индексам.
Объявление и инициализация массивов.
Объявление массива сводится к указанию типа его элементов и количества элементов по каждому измерению:
#define Nmax 50
char a1[20],a2[2][80];
int b1[25],b2[Nmax];
По такому объявлению компилятор будет знать, сколько места в оперативной памяти понадобится для хранения такого массива. Для глобальных массивов место в памяти будет выделено в момент запуска программы, а для локальных - в момент вызова соответствующей функции.
Объявление массива можно совместить с его инициализацией, т.е. с присвоением начальных значений всем элементами массива или только нескольким первым элементам:
char a[7]="Привет";
char b[7]={'П','р','и','в','е','т',0x0};
char c[]="Привет";
float d[10]={1.,2.,3.,4.};
int q[2][3]={{1,2,3},
{4,5,6}};
Обратите внимание на инициализацию символьных массивов a, b и c. В первом случае значения элементов массива совпадают с символами указанной строковой константы. Хотя значащих символов там 6, не следует забывать и о невидимом признаке конца строки - байте с нулевым значением. В случае инициализации массива bкаждый его элемент задан символьной константой, не забыт и признак конца строки. Самый удобный способ использован при инициализации массива c - вместо того, чтобы указывать количество элементов, здесь заданы пустые скобки. Компилятор по заданному значению текстовой константы сам определит нужное количество байтов. Это позволяет избежать ненужных ошибок при подсчете количества символов в достаточно длинных строках.
При инициализации массива d вместо десяти значений заданы только четыре. Это означает, что указанные величины будут присвоены только первым четырем элементам. Остальные элементы не инициализированы. В случае если d является глобальным массивом, значения этих элементов будут равны 0 (память, выделяемая глобальным данным, предварительно чистится). Если массив d локализован в какой-то функции, то значения его элементов, начиная с d[4], предсказать невозможно - там будет находиться "мусор", который при повторных вызовах функции может оказаться разным.
Инициализация двумерных массивов выглядит более естественно, если значения элементов строк располагать друг под другом (так как это сделано в инициализации массива q ).
Использование двумерных массивов для хранения строковых данных - не всегда лучшее решение:
char spisok[][20]={"Иванов","Петров-Водкин","Репин"};
Для хранения элементов такого массива компилятор выделит 3*20=60 байт. Вместо этого можно было бы завести 3 указателя на соответствующие строковые константы:
char *sp[]={"Иванов","Петров-Водкин","Репин"};
В этом случае понадобилось бы 3*4=12 байт для хранения элементов массива sp и 27 байт для хранения строковых констант, т.е. почти в полтора раза меньше памяти. Дополнительный выигрыш может быть получен при дальнейшей обработке. Например, при сортировке строковых значений вместо перестановки фамилий могли бы меняться местами только четырехбайтовые указатели.
Некоторые приемы обработки числовых массивов
Для изучения некоторых приемов обработки числовых массивов рассмотрим несколько конкретных задач.
Пример Переворот одномерного целочисленного массива - перестановка его элементов в обратном порядке. Выделим в отдельную функцию процедуру инвертирования:
void invert(int *a,int n)
{ for(int j=0,tmp; j<n/2; j++)
{ tmp=a[j]; a[j]=a[n-j-1]; a[n-j-1]=tmp; }
}
Для проверки ее работоспособности можно воспользоваться следующей программой:
#include <stdio.h>
#include <conio.h>
#define N 20
void invert(int *a,int n);
void main()
{ int j,a[N];
printf("Before reverse:\n");
for(j=0; j<N; j++)
{ a[j]=j+1; printf("%3d",a[j]); }
invert(a,N);
printf("\nAfter reverse:\n");
for(j=0; j<N; j++) printf("%3d",a[j]);
getch();
}
//=== Результат работы ===
Before reverse:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
After reverse:
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Пример Перестановка головы и хвоста массива без использования промежуточного массива. Алгоритм этой процедуры был опубликован много лет тому назад в книге Дж. Бентли "Жемчужины для программистов". Заключается он в том, что надо последовательно выполнить 3 инвертирования - головы массива, хвоста массива и всего массива целиком. Для этой цели мы и воспользуемся модификацией ранее написанной процедурой invert:
void invert1(int *a, int k, int n)
{//k - индекс первого элемента инвертируемого фрагмента массива
//n - количество инвертируемых элементов
int j,tmp;
for(j=k; j<k+n/2; j++)
{ tmp=a[j]; a[j]=a[2*k+n-j-1]; a[2*k+n-j-1]=tmp; }
}
Для проверки описанного выше алгоритма можно воспользоваться следующей программой:
#include <stdio.h>
#include <conio.h>
#define N 20
#define M 15
void invert1(int *a, int k, int n);
void main()
{ int j,a[N];
printf("Before reverse:\n");
for(j=0; j<N; j++)
{ a[j]=j+1; printf("%3d",a[j]); }
invert1(a,0,M);
printf("\nAfter reverse head:\n");
for(j=0; j<N; j++) printf("%3d",a[j]);
invert1(a,M,N-M);
printf("\nAfter reverse tail:\n");
for(j=0; j<N; j++) printf("%3d",a[j]);
invert1(a,0,N);
printf("\nAfter reverse all:\n");
for(j=0; j<N; j++) printf("%3d",a[j]);
getch();
}
//=== Результат работы ===
Before reverse:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
After reverse head:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16 17 18 19 20
After reverse tail:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 20 19 18 17 16
After reverse all:
16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Пример Вывод целочисленной матрицы в заданном окне. Договоримся о следующих обозначениях параметров нашей процедуры вывода:
* *c - указатель на первый элемент матрицы;
* n - количество строк матрицы;
* m - количество столбцов матрицы;
* w - ширина каждой колонки матрицы при выводе на экран ( w <= 9 );
* row, col - экранные координаты, определяющие позицию верхнего левого знакоместа окна, в котором должна быть размещена матрица.
Тогда функция printa, которая выводит заданную целочисленную матрицу в указанном окне, может быть оформлена следующим образом:
void printa(int row,int col,int w,int *c,int n, int m)
{ int j,k;
char f[4]="%0d";//заготовка для форматного указателя
f[1] += w;//формирование форматного указателя %wd
for(j=0; j<n; j++)
for(k=0; k<m; k++)
{ gotoxy(col+k*w,row+j);//переход в позицию элемента c[j][k]
printf(f,c[k+j*m]);
}
}
Отметим три особенности приведенной выше программы. Во-первых, для вывода числовых данных в поле, содержащем w позиций, удобно воспользоваться функцией printf с форматным указателем %wd. Но w - это числовой параметр, передаваемый программе printa. Поэтому строку с форматным указателем можно сформировать. Именно для этой цели заведена строковая константа f, второй байт которой (символ f[1] ) формируется как сумма кода цифры 0 с числом w. Затем сформированная строка используется в функции printf, первым аргументом которой может быть не только литеральная константа, но и ссылка на строку. Во-вторых, вместо того, чтобы перебирать элементы матрицы c[j][k] как элементы двумерного массива, в программе printaиспользуются приведенные индексы ( k+j*m ). Наконец, для перевода курсора в позицию, соответствующую началу поля элемента c[j][k] используется функция gotoxy.
Работа функции printa может быть проверена с помощью следующей программы:
#include <stdio.h>
#include <conio.h>
void main()
{ int a[3][4]={{1,2,3,4},
{10,20,30,40},
{100,200,300,400}};
int b[4][4]={{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};
printa(5,5,4,(int *)a,3,4);
printa(5,40,5,(int *)b,4,4);
getch();
}
Результат ее работы приведен на рис. 8.1. Обратите внимание еще на одну деталь: поскольку имена матриц являются указателями не на первый элемент матрицы, а на ее первую строку, то при обращении к функции printaпотребовалось преобразовать указатель к типу ( int * ). Прибавление 1 к преобразованному указателю позволит с помощью указателя c перебирать элементы матрицы, а не ее строки.
Рис. Вывод числовых матриц в заданных окнах
Следует отметить, что можно обойтись и без формирования переменного формата в функции printf, если воспользоваться сравнительно редко применяемым форматным указателем *:
printf("%*d",w,c[k+j*m]);
Значение переменной w в данном случае не выводится на экран, а замещает символ * в форматном указателе"%*d".
Создание программ для обработки одномерных массивов на языках C, C++ особых проблем не вызывает. Чтобы это доказать, продемонстрируем несколько функций, реализующих стандартные операции над векторами.
Пример Вычисление нормы вектора.
#include <stdio.h>
#include <math.h>//здесь находится прототип функции sqrt
#include <conio.h>
double norm(double *a, int n)
{ double s=0;
for(int i=0; i<n; i++) s += a[i]*a[i];
return sqrt(s);
}
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
printf("norm=%f",norm(v1,5));
getch();
}
//=== Результат работы ===
norm=7.416198
Функцией norm можно воспользоваться и для того, чтобы вычислить "норму" любого фрагмента вектора - достаточно вместо первого аргумента задать адрес начальной компоненты (например, &v1[2] ), а в качестве второго аргумента количество обрабатываемых компонент.
Пример Нормирование вектора.
#include <iostream.h>
#include <math.h>//здесь находится прототип функции sqrt
#include <conio.h>
void norm_vec(double *a, int n)
{ double s=0;
for(int i=0; i<n; i++) s += a[i]*a[i];
s= sqrt(s);
for(int i=0; i<n; i++) a[i] /= s;
}
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
norm_vec(v1,5);
for(int i=0;i<5;i++)
cout << v1[i]<< " ";
getch();
}
//=== Результат работы ===
0.13484 0.26968 0.40452 0.53936 0.6742
Пример Вычисление скалярного произведения двух векторов.
#include <stdio.h>
#include <conio.h>
double scal_prod(double *a, double *b,int n)
{ double s=0;
for(int i=0; i<n; i++) s += a[i]*b[i];
return s;
}
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
printf("scal_prod=%f",scal_prod(v1,v1,5));
getch();
}
//=== Результат работы ===
scal_prod=55.000000
Пример Сумма векторов.
#include <stdio.h>
#include <conio.h>
void sum_vec(double *a,double *b,double *c,int n)
{ for(int i=0; i<n; i++) c[i]=a[i]+b[i]; }
void main()
{ double v1[5]={1.,2.,3.,4.,5.};
double v2[5]={1.,0.,1.,0.,1.};
double v3[5];
sum_vec(v1,v2,v3,5);
for(int i=0;i<5;i++)
printf("%3.0f",v3[i]);
getch();
}
//=== Результат работы ===
2 2 4 4 6
ВаріантЗавдання1В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) суму від'ємних елементів масиву;
б) добуток елементів масиву, розташованих між максимальним і мінімальним елементом.
Впорядкувати елементи масиву за зростанням. Результати всіх розрахунків і перетворень масиву вивести на консоль.2В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) добуток додатніх елементів масиву;
б) суму елементів масиву, розташованих до мінімального елементу.
Впорядкувати за зростанням окремо елементи, що стоять на парних місцях, і елементи, що стоять на непарних місцях. Результати всіх розрахунків і перетворень масиву вивести на консоль.3В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) добуток від'ємних елементів масиву;
б) суму додатніх елементів масиву, розташованих до максимального елементу.
Змінити порядок слідування елементів у масиві на протилежний. Результати всіх розрахунків і перетворень масиву вивести на консоль.4В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість елементів масиву, менших за деяке число С;
б) суму цілих частин елементів масиву, розташованих після останнього від'ємного елементу.
Перетворити масив таким чином, щоб спочатку розташовувались усі елементи, що відрізняються від максимального не більше, ніж на 20%, а потім - усі інші. Результати всіх розрахунків і перетворень масиву вивести на консоль.5В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість додатніх елементів масиву;
б) суму елементів масиву, розташованих після останнього елементу, рівного нулю.
Перетворити масив таким чином, щоб спочатку розташовувались усі елементи, ціла частина яких не перевищує 1, а потім - усі інші. Результати всіх розрахунків і перетворень масиву вивести на консоль.6В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість від'ємних елементів масиву;
б) суму модулів елементів масиву, розташованих після мінімального за модулем елементу.
Замінити всі від'ємні елементи масиву їх квадратами і впорядкувати елементи масиву за зростанням. Результати всіх розрахунків і перетворень масиву вивести на консоль.7В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість елементів масиву, більших за деяке число С;
б) добуток елементів масиву, розташованих після максимального за модулем елемента.
Перетворити масив таким чином, щоб спочатку розташовувались усі від'ємні елементи, а потім - усі додатні (елемнти, що дорівнюють 0, вважати додатніми). Результати всіх розрахунків і перетворень масиву вивести на консоль.8В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість елементів масиву, рівних 0;
б) суму елементів масиву, розташованих після мінімального елемента.
Упорядкувати елементи масиву за зростанням модулів елементів. Результати всіх розрахунків і перетворень масиву вивести на консоль.9В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість від'ємних елементів масиву;
б) суму модулів елементів масиву, розташованих після мінімального за модулем елементом.
Замінити всі від'ємні елементи масиву їх квадратами та упорядкувати елементи масиву за зростанням. Результати всіх розрахунків і перетворень масиву вивести на консоль.10В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) кількість елементів масиву, що лежать в діапазоні від А до B;
б) суму елементів масиву, розташованих після максимального елемента.
Упорядкувати елементи масиву за убуванням модулів елементів. Результати всіх розрахунків і перетворень масиву вивести на консоль.11В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) номер максимального за модулем елемента масиву;
б) суму елементів масиву, розташованих після першого додатнього елемента.
Перетворити масив таким чином, щоб спочатку розміщувались усі елементи, ціла частина яких лежить в інтервалі , а потім - усі інші. Результати всіх розрахунків і перетворень масиву вивести на консоль.12В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) номер мінімального за модулем елемента масиву;
б) суму модулів елементів масиву, розташованих після першого від'ємного елемента.
Стиснути масив, видаливши з нього всі елементи, величина яких знаходиться в інтервалі . Звільнені в кінці масиву елементи заповнити нулями. Результати всіх розрахунків і перетворень масиву вивести на консоль.13В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) мінімальний за модулем елемента масиву;
б) суму модулів елементів масиву, розташованих після першого елемента, рівного нулю.
Перетворити масив таким чином, щоб у його першій половині розміщувались елементи, що стоять у парних позиціях, а в другій половині - елементи, що стоять у непарних позиціях. Результати всіх розрахунків і перетворень масиву вивести на консоль.14В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) максимальний за модулем елемента масиву;
б) суму елементів масиву, розташованих між першим і другим додатніми елементами.
Перетворити масив таким чином, щоб елементи, що дорівнюють нулю, розміщувались після всіх інших. Результати всіх розрахунків і перетворень масиву вивести на консоль.15В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) номер мінімального елемента масиву;
б) суму елементів масиву, розташованих між першим і другим від'ємними елементами.
Перетворити масив таким чином, щоб спочатку розміщувались усі елементи, модуль яких не перевищує 1, а потім - усі інші. Результати всіх розрахунків і перетворень масиву вивести на консоль.16В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) номер максимального елемента масиву;
б) добуток елементів масиву, розміщених між першим і другим нульовими елементами.
Перетворити масив таким чином, щоб у першій його половині розміщувались елементи, що стоять у непарних позиціях, а у другій половині - елементи, що стоять у парних позиціях. Результати всіх розрахунків і перетворень масиву вивести на консоль.17В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) мінімальний елемента масиву;
б) суму елементів масиву, розташованих між першим і другим додатніми елементами.
Перетворити масив таким чином, щоб спочатку розміщувались усі елементи, рівні нулю, а потім - усі інші. Результати всіх розрахунків і перетворень масиву вивести на консоль.18В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) максимальний елемента масиву;
б) суму елементів масиву, розташованих до останього додатнього елемента.
Стиснути масив, видаливши з нього всі елементи, модуль яких знаходиться в інтервалі . Звільнені в кінці масиву елементи заповнити нулями. Результати всіх розрахунків і перетворень масиву вивести на консоль.19В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) суму елементів масиву з непарними номерами;
б) суму елементів масиву, розташованих між першим і останнім від'ємними елементами.
Стиснути масив, видаливши з нього всі елементи, модуль яких не перевищує 1. Звільнені в кінці масиву елементи заповнити нулями. Результати всіх розрахунків і перетворень масиву вивести на консоль.20В одномірному масиві, що складається з n дійсних елементів, розрахувати:
а) добуток елементів масиву з парними номерами;
б) суму елементів масиву, розташованих між першим і останнім нульовими елементами.
Перетворити масив таким чином, щоб спочатку розміщувались усі додатні елементи, а потім - усі від'ємні (елементи, що дорівнюють 0, вважати додатніми). Результати всіх розрахунків і перетворень масиву вивести на консоль.Зміст звіту
1) Постановка задачі (загальна й конкретного варіанта).
2) Формули, використовувані при розв'язку задачі (математична модель).
3) Програми для розв'язку задач мовою С/C++.
4) Опис стандартних функцій, що використовуються у програмі.
5) Система тестів для перевірки правильності роботи програми й результати виконання тестів.
Документ
Категория
Рефераты
Просмотров
52
Размер файла
104 Кб
Теги
lr5, ukr
1/--страниц
Пожаловаться на содержимое документа