алгоритмизация и программирование 10 глава

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

int A2[10][3];

Этот оператор описывает двумерный массив, который можно представить как таблицу, состоящую из 10 строк и 3 столбцов.

Таким образом, двумерный массив – это массив, размерность которого равна 2. Визуально, двумерный массив – это обычная таблица, со строками и столбцами или матрица . Фактически двумерный массив – это одномерный массив одномерных массивов. Структура двумерного массива, с именем A, размером m на n показана ниже (см. рис. 8.1).

A[0][0]	A[0][1]	…	A[0][n-1]
A[1][0]	A[1][1]	…	A[1][n-1]
A[2][0]	A[2][1]	…	A[2][n-1]
…	…	…	…
A[m-1][0]	A[m-1][1]	…	A[m-1][n-1]

Рисунок 8.1 – Двумерный массив в виде таблицы (слева) или матрицы (справа)

На рисунке 8.1 m – количество строк двумерного массива;
n – количество столбцов двумерного массива;
m * n– количество элементов массива.

Общий вид описания двумерного массива:

тип_данных имя_массива [количество_строк][количество_столбцов];

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

· тип данных;

· имя массива.

Доступ к значениям элементов многомерного массива обеспечивается через индексы, каждый из которых заключается в квадратные скобки. Например, A2[3][2] - значение элемента, лежащего на пересечении четвертой строки и третьего столбца (помните, что индексы начинаются с 0).

Если многомерный массив инициализируется при его объявлении, список значений по каждой размерности заключается в фигурные скобки. Приведенный ниже оператор объявляет трехмерный массив A3 размерностью 4 на 3 на 2.

int A3[4][3][2] = {{{0,1},{2,3},{4,5}},

{{6,7},{8,9},{10,11}},

{{12,13},{14,15},{16,17}},

{{18,19},{20,21},{22,23}}};

Этот оператор создает массив A3, четыре строки которого являются матрицами вида:

0 1 6 7 12 13 18 19

2 3 8 9 14 15 20 21

4 5 10 11 16 17 22 23

Например, элемент A3[0][1][0] равен 2, элемент A3[3][0][1] равен 19 и т.д.

Если в списке инициализации в какой-то из размерностей не хватает данных, то все дальнейшие не перечисленные элементы считаются равными нулям.

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

В памяти многомерный массив располагается по строкам.

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

К элементу двумерного массива обращаются, указывая номер строки и номер столбца, на пересечении которых он расположен, например:

а[1][4] a[i][j]

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

1. Инициализация двумерных массивов аналогична инициализации одномерных массивов:

а) инициализация:

const int n = 3; // число строк

const int m = 4; // число столбцов

// выделяем память под матрицу с одновременной

// инициализацией элементов

double a[n][m] =

{

{3, -3.1, 4.6, 5.5},

{2, 1.2, -10, -2.5},

{7.6, 3.1, 1.6, 0.5}

};

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

б) ввод данных с клавиатуры:

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

cin >> a[i][j];

В соответствии с приведенным здесь порядком следования циклов элементы массива должны вводиться по строкам.

в) формирование массива с помощью генератора псевдослучайных чисел;

г) непосредственное присваивание (вычисление по формуле):

2. Вывод матрицы надо реализовать в удобном для чтения виде, т.е. чтобы на одной строке экрана располагалась одна строка матрицы. С этой целью в тело внешнего цикла, помимо внутреннего, включается еще оператор cout << endl;, который переводит курсор к началу следующей строки экрана после вывода текущей строки матрицы.

for (i = 0; i < n; i++)

{

for (j = 0; j < m; j++)

cout << a[i][j] << "\t ";

cout << endl;

}

Пример. Дана прямоугольная матрица действительных чисел размером n × m. Пронормировать эту матрицу, т.е. поделить значение всех элементов матрицы на максимальный по модулю элемент.

Возможный текст программы:

# include <iostream>

# include <cmath>

using namespace std;

int main()

{

const int n = 3; // число строк

const int m = 4; // число столбцов

double a[n][m]; // выделяем память под матрицу

int i, j;

double max;

 

// Ввод матрицы с клавиатуры

cout << "Matriza A("<< n << "*" << m << "):" << endl;

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

cin >> a[i][j];

 

// Поиск в матрице максимального по модулю значения

max = fabs(a[0][0]);

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

if (fabs(a[i][j]) > max)

max = fabs(a[i][j]);

cout << "max=" << max << endl;

 

// Нормируем матрицу

for (i = 0; i < n; i++)

for (j = 0; j < m; j++)

a[i][j] /= max;

 

// Вывод матрицы в виде таблицы на экран монитора

for (i = 0; i < n; i++)

{

for (j = 0; j < m; j++)

cout << a[i][j] << "\t ";

cout << endl;

}

return 0;

}

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

Лабораторная работа №8
Двумерные массивы

ЦЕЛЬ РАБОТЫ: приобретение навыков объявления, организации ввода-вывода и обработки двумерного массива.

Выполнение работы: в соответствии с вариантом составить и реализовать программу.

Задание I

1. Составить программу формирования матрицы, число строк и столбцов которой определяется как случайное натуральное число в промежутке [3, 8], а элементы - случайные целые числа от -50 до 50. Заменить неотрицательные числа полученной матрицы единицей, а отрицательные - нулем.

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

3. В квадратной матрице порядка n найти сумму всех тех элементов, сумма индексов которых равна n.

4. Определить, является ли заданная квадратная матрица симметричной относительно главной диагонали. Найти след данной матрицы. Элементы матрицы вводить с клавиатуры.

5. Найти число элементов в каждой из нечетных строк матрицы, равных заданному числу, вводимому с клавиатуры.

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

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

8. Даны вещественные числа a ₁, a ₂, …, a_n и вещественная квадратная матрица порядка n (n > 5). Сформировать вещественную матрицу размером n x (n + 1), вставив в исходную матрицу между пятым и шестым столбцами новый столбец с элементами a ₁, a ₂, …, a_n.

9. Дана вещественная квадратная матрица порядка n. Преобразовать эту матрицу по правилу: строку с номером k сделать столбцом с номером k, а столбец с номером k сделать строкой с тем же номером.

10. В данной вещественной матрице размером n x m (n > 2, m > 2) поменять местами строки с номерами n - 2 и n - 1.

11. Положительные элементы первой строки прямоугольной матрицы умножить на первый элемент этой же строки, а отрицательные - на последний ее элемент; то же самое проделать с остальными строками.

12. Заменить все элементы строки с номером s и столбца с номером k прямоугольной матрицы на противоположные по знаку (элемент, стоящий на пересечении выбранной строки и выбранного столбца, не изменять).

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

14. Дан целочисленный одномерный массив: a ₁, a ₂, …, a_n. Сформировать квадратную матрицу порядка n, у которой элементы, расположенные на главной диагонали, равны соответственно a ₁, a ₂, …, a_n; элементы, расположенные выше главной диагонали, равны единице, а элементы, расположенные ниже главной диагонали, равны минус единице.

15. Даны две прямоугольные целочисленные матрицы А и В одинакового размера m x п. Создать матрицу того же размера, в которой элементы равны 1, если соответствующие элементы матриц А и В имеют одинаковый знак; -1, если соответствующие элементы имеют разные знаки, и нулю, если хотя бы один из соответствующих элементов равен нулю.

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

17. Из прямоугольной матрицы размером m x n удалить строку с номером s и столбец с номером k (0 ≤ s < m, 0 ≤ k < n).

18. Сформировать одномерный массив, каждый элемент которого равен сумме отрицательных элементов соответствующей строки данной целочисленной прямоугольной матрицы.

19. Найти количество элементов в каждом столбце прямоугольной вещественной матрицы, меньших среднего арифметического элементов рассматриваемого столбца.

20. Вывести на экран максимальные элементы каждой строки двумерного массива с указанием их индексов.

21. Задать два двумерных массива, содержащих положительные и отрицательные элементы. Определить, в каком из них больше положительных элементов.

22. Задан массив целых случайных чисел, принадлежащих промежутку [0, 200]. Определить, каких элементов в нём больше: превышающих k 1 или не превышающих k 2.

23. Задан массив целых случайных чисел, принадлежащих промежутку
[-50, 50]. Найти сумму тех элементов массива, которые больше a, но меньше b, а также вычислить количество этих элементов.

24. Поменять местами максимальный и минимальный элемент заданного двумерного массива. Результат вывести на экран в виде матрицы.

25. Дана целочисленная матрица. Сформировать матрицу, получающуюся из данной перестановкой первого столбца с последним, второго - с предпоследним.

26. Из данной матрицы получить другую следующим образом: на место первой строки поместить вторую, на место второй - третью и т.д., на место последней поместить первую.

Задание II

Квадратная матрица A третьего порядка сформирована из вещественных чисел, принадлежащих диапазону [-10, 10]. Найти с точностью до e = 10^-3:

1) матрицу B по заданной формуле вычисления ее элементов b_ij через индексы i и j (i = 1, 2, 3; j = 1, 2, 3);

2) сумму матриц A и B;

3) матрицу, транспонированную матрице A + B;

4) матрицу, обратную матрице A + B;

5) произведение матриц A + B и (A + B)^T.

Вывести, используя вспомагательную функцию, на экран матрицы A, B, A + B, (A + B)^-1, (A + B)^T, (A + B)(A + B)^-1.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15.

16. ;

17. ;

18. ;

19. ;

20. ;

21. ;

22. ;

23. ;

24. ;

25. ;

26. .

Замечание. Обратную матрицу рекомендуется вычислять с помощью присоединенной матрицы, а определитель матрицы – по правилу Саррюса.

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

1. Дайте определение массива.

2. Какие типы данных не допустимы для компонентов массива?

3. Может ли левая граница индексов массива быть отрицательной?

4. Какой массив называется двумерным?

5. Правила описания двумерного массива.

6. Как осуществляется доступ к элементам двумерного массива?

7. Как осуществляется ввод двумерного массива?

8. Какие способы ввода двумерного массива вы знаете?

9. Размещение массива в памяти ЭВМ.

10. Вывод двумерного массива.

11. Может ли инструкция cout<<x; ввести массив х целиком?

Пример выполнения лабораторной работы

Задание. Программа, которая для целочисленной матрицы 3 х 4 определяет среднее арифметическое ее элементов и количество положительных элементов в каждой строке.

Решение

1. Математическая модель

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

Аргументы: целочисленный массив a; целочисленные m и n – количество строк и столбцов.

Результаты: среднее арифметическое элементов sred (вещественного типа); количество положительных элементов в каждой строке n_pos_el (целого типа).

Промежуточные величины: счетчики i, j (целого типа).

2. Алгоритм

3. Программа

Начало   Конец m = 3; n = 4 i=0..m-1 j=0..n-1 a[i, j] i=0..m-1 n_pos_el = 0 = 4 sred = 0 j=0..n-1 sred = sred + a[i, j] a[i,j] > 0 inc(n_pos_el) + – i+1,n_pos_el sred:= sred / m / n sred

#include <iostream> #include <conio.h> #include <math.h>   const int m = 3, n = 4;   using namespace std;   int main() { int a[m][n]; cout<<"Введите элементы массива "<<endl; for(int i=0; i<m; i++) for(int j=0; j<n; j++) cin>>a[i][j];   double sred = 0; int n_pos_el; for(int i=0; i<m; i++) { n_pos_el = 0; for(int j=0; j<n; j++) { sred += a[i][j]; if(a[i][j]>0) n_pos_el++; } cout<<"В "<<i+1<<"-ой строке " <<n_pos_el<<" положительных элементов" <<endl; } sred = sred/m/n;   cout<<"Среднее арифметическое: " <<sred<<endl; _getch();   return 0; } 4. Результат работы программы: Введите элементы массива 1 2 3 4 -2 0 -3 -1 1 1 1 0 B 1-й строке 4 положительных элементов B 2-й строке 0 положительных элементов B 3-й строке 3 положительных элементов Среднее арифметическое: 0.58

9. Алгоритмы решения задач внутренней сортировки и алгоритмы поиска информации

9.1. Сложность алгоритмов

Теория сложности обеспечивает методологию анализа вычислительной сложности различных криптографических методов и алгоритмов.

Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом, и выдающая результат вычислений на выход [4].

Чаще всего, говоря о сложности, имеют в виду временную сложность алгоритма: Т. Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Под элементарными шагами понимают такие базисные операции, как сложение, умножение, замены, безусловные передачи управления и вызовы подпрограмм. Т обычно представляется в виде функции от п,где п - это размер входных данных. Функция времени вычислений – T_A (n).

Обычно вычислительная сложность алгоритма выражается с помощью нотации " О большого", т.е описывается порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4 п²+ 7 п+ 2, то вычислительная сложность порядка n ², записываемая как О (п ²) [4].

Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т = О(п), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т = О(2 ^п), то добавление одного бита к входным данным удвоит время выполнения алгоритма.

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от п: О (1). Алгоритм является линейным, если его временная сложность О (п). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы – полиномиальные, их сложность ­ О (п^m), где m – константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем.

Алгоритмы, сложность которых равна O (t^{f ( n )} ),где t – константа, большая, чем 1, a f (n) – некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О (с ^{f ( n )}), где где с – константа, a f (n)возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным. Алгоритмы, сложность которых равна O (n!), называются алгоритмами с факториальной сложностью. Таким образом, справедливо следующее соотношение:

O (log n) < O (n) < O (n log n) < O (n ²) < O (n ³) < O (2 ⁿ) < O (n!).

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

9.2. Постановка задачи поиска

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

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

Задача поиска в этом случае состоит в отыскании индекса (индексов) элемента по заданному свойству элемента.

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

· поиск оказался удачным, т.е. позволил определить положение элемента в массиве;

· поиск оказался неудачным, т.е. достигнут конец массива, но элемент с заданным свойством отсутствует.

9.3. Последовательный (линейный) поиск

Простейшим методом поиска является последовательный просмотр таблицы, одномерного массива или строки до нахождения элемента с требуемыми свойствами или установления факта, что такого элемента нет. Для массива, данные в котором не упорядочены сортировкой, единственный путь поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным, его позиция в массиве фиксируется. Этот алгоритм называется последовательным, или линейным, поиском. Ядром такого алгоритма является цикл по индексу массива. Так, если в массиве int a[n]нужно найти введенное с клавиатуры целое число х, о котором никакой дополнительной информации нет, то соответствующий цикл можно записать следующим образом:

for (i = 0; i < n; i++) if (a[i] == x) k = i;

Этот способ решения обладает двумя существенными недостатками:

· если значение х встречается в массиве несколько раз, то будет найдено последнее из них;

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

Для устранения этих недостатков необходимо прервать просмотр массива сразу после обнаружения заданного числа. Так как в этом случае число повторений не известно, необходимо использовать цикл с предусловием:

while ((i < n) && (a[i]!= x)) i++;

9.4. Бинарный поиск

Наиболее эффективным и распространенным методом непоследовательного поиска в одномерных упорядоченных массивах является бинарный поиск, который называют также методом половинного деления, методом дихотомии, методом логарифмического поиска или методом деления пополам. Основная идея бинарного поиска состоит в том, что сначала искомый элемент х сравнивается со средним элементом массива а[n]. Результат сравнения либо приводит к решению задачи, либо позволяет определить, в какой части массива – левой или правой – продолжать поиск. После каждой такой итерации область поиска сокращается вдвое и не более чем через [log2n] сравнений мы закончим поиск, то есть либо попадем на элемент х, либо покажем, что х не принадлежит массиву а[n]. Например, при n = 1000 бинарный поиск в 100 раз быстрее последовательного, а при n = 1000000 – в 50000 раз. Разумеется, если массив неупорядоченный, то применить к нему бинарный поиск нельзя. Таким образом, факт упорядоченности элементов в массиве играет ключевую роль при бинарном поиске.

9.5. Постановка задачи сортировки данных

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

Задача сортировки связана со многими важными приложениями, кроме того, служат хорошей иллюстрацией анализа сложности алгоритмов и тем самым позволяют разумно выбирать лучшие среди, казалось бы, равноценных методов. Каждый из алгоритмов сортировки имеет свои достоинства и недостатки, и выбирать алгоритмы нужно, исходя из конкретной постановки задачи. Выбор алгоритма сортировки существенно зависит от структуры обрабатываемых данных, поэтому все методы сортировки подразделяют на два класса: внутренний (сортировка массивов) и внешний (сортировка последовательных файлов). Различие: при внутренней сортировке все данные хранятся в оперативной памяти ЭВМ, а при внешней - во внешней памяти. При внутренней сортировке имеются более гибкие возможности для построения алгоритмов, так как все данные выстроены в виде массива и как бы лежат перед пользователем, он видит каждый элемент и имеет к нему прямой доступ. При внешней сортировке доступ к данным ограничен, поскольку они из-за своего размера в оперативной памяти не помещаются.

Уточним математическую постановку задачисортировки данных [7].

Пусть надо упорядочить п элементов m ₁, m ₂, …, m_n, которые назовем записями. Каждойзаписи m_j поставим в соответствие свой ключ k_j, который и будет управлять процессом сортировки. Помимо ключа запись может содержать и дополнительную информацию, которая не влияет на сортировку, но всегда остается в этой записи. Задача заключается в нахождении такой перестановки , , …, , записей m ₁, m ₂, …, m_n, после которой ключи будут располагаться в неубывающем (невозрастающем) порядке:

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: