25-30 вопрос

25. Одномерные массивы: объявление, инициализация, обработка, использование массивов в С/C++.

Массивы – это группа однородных данных, имеющих один и тот же тип и одно и тоже имя.

Объявление: ( тип_имя_кол-во. Элементов) int month или double mas

Инициализация: int mas={1, 2, 3, 4, 5} или с клавиатуры. For(int i=0; i<12; ++i)

Cin>>mas[i]

Обработка: Получение суммы элементов массива

Поиск максимума, минимума и др. задаваемых значений.

Сортировка массива.

Выполнение однотипных действий над всеми элементами массива.

Использование: Массивы используются для обработки большого количества однотипных данных.

25. Одномерные массивы: последовательный поиск элементов в массивах и его организация на языке С/C++

Одномерный массив — массив, с одним параметром, характеризующим количество элементов одномерного массива. Фактически одномерный массив — это массив, у которого может быть только одна строка, и n-е количество столбцов. Столбцы в одномерном массиве — это элементы массива.

Индекс ячейки – это целое неотрицательное число, по которому можно обращаться к каждой ячейке массива и выполнять какие-либо действия над ней (ячейкой).

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

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

// массивы могут быть инициализированы при объявлении:

int a[16] = { 5, -12, -12, 9, 10, 0, -9, -12, -1, 23, 65, 64, 11, 43, 39, -15 }; // инициализация одномерного массива

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

Int a[]={5,-12,-12,9,10,0,-9,-12,-1,23,65,64,11,43,39,-15};//инициализации массива без определения его размера.

25. Алгоритм пузырьковой сортировки и его реализация на языке С/C++

Алгоритм пузырьковой сортировки – это довольно простой в реализации алгоритм для сортировки массивов. Можно встретить и другие названия: пузырьковая сортировка, Buble sortили сортировка простыми обменами – но все они будут обозночать один и тот же алгоритм. Назван так, потому что большее или меньшее значение “всплывает” (сдвигается) к краю массива после каждой итерации, это будет видно в примере.

Сложность этого алгоритма выражается формулой О(n^2) (n в степени 2). Алгоритм работает медленно с большими массивами, а поэтому малоэффективен и на практике используется редко, чаще всего в учебных целях. Для сортировки массивов на практике используют другие более быстрые алгоритмы, один из них –  QuickSort(быстрая сортировка). Функция для быстрой сортировки включена во многие стандартные библиотеки языков программирования, например в языке C функция qsort() из стандартной библиотеки.

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

25. Алгоритмы перестановок элементов массива и их реализация на языке С/C++.

Теория Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным. Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это. Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню. Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место.

Нумерация элементов массива начинается с 0 и заканчивается n-1. 

for(int i=1;i<n;i++) for(int j=i;j>0 && x[j-1]>x[j];j--) // пока j>0 и элемент j-1 > j, x-массив int swap(x[j-1],x[j]); // меняем местами элементы j и j-1

Сортировка вставками имеет сложность n², количество сравнений вычисляется по формуле n*(n-1)/2.

Итак при n=100 количество перестановок равно 4950, а не 10000 если бы мы высчитывали по формуле n². Имейте это ввиду при выборе алгоритма сортировки.

25. Двумерные массивы: объявление, инициализация, использование. Привести пример реализации какого-либо алгоритма обработки и преобразования матриц на языке С/C++.

Двумерные массивы в С++

Допустим, необходимо обработать некоторые данные из таблицы. В таблице есть две характеристики: количество строк и количество столбцов. Также и в двумерном массиве, кроме количества элементов массива, есть такие характеристики как, количество строк и количество столбцов двумерного массива. То есть, визуально, двумерный массив — это обычная таблица, со строками и столбцами. Фактически двумерный массив — это одномерный массив одномерных массивов. Структура двумерного массива, с именем a, размером m на n показана ниже (см. Рисунок 4).

Рисунок 4 — Массивы в С++

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

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

• тип данных;

• имя массива.

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

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

1 2	// пример объявление двумерного массива: int a[5][3];

• a — имя целочисленного массива

• число в первых квадратных скобках указывает количество строк двумерного массива, в данном случае их 5;

• число во вторых квадратных скобках указывает количество столбцов двумерного массива, в данном случае их 3.

1 2	// инициализация двумерного массива: int a[5][3] = { {4, 7, 8}, {9, 66, -1}, {5, -5, 0}, {3, -3, 30}, {1, 1, 1} };

В данном массиве 5 строк, 3 столбца. после знака присвоить ставятся общие фигурные скобочки, внутри которых ставится столько пар фигурных скобочек, сколько должно быть строк в двумерном массиве, причём эти скобочки разделяются запятыми. В каждой паре фигурных скобочек записывать через запятую элементы двумерного массива. Во всех фигурных скобочках количество элементов должно совпадать. Так как в массиве пять строк, то и внутренних пар скобочек тоже пять. Во внутренних скобочках записаны по три элемента, так как количество столбцов — три. Графически наш массив будет выглядеть, как двумерная таблица

Код программы на Visual C++ вода-вывода матрицы будет иметь примерно такой вид:

#include "stdafx.h" #include <iostream> using namespace std; int main() { setlocale (LC_ALL, "RUS"); int i,j,N,M,a[20][20]; cout<<"N="; //ввод количества строк cin>>N; cout<<"M="; //ввод количества столбцов cin>>M; cout<<"Input matrix A \n"; //цикл по переменной i, в которой перебираем строки матрицы for (i=0; i<N; i++) //цикл по переменной j, в котором перебираем элементы внутри строки for (j=0; j<M; j++) cin>>a[i][j]; //ввод очередного элемента матрицы cout<<"matrix A \n"; for (i=0; i<N; i++) { //цикл по переменной i, в котором перебираем строки матрицы for (j=0; j<M; j++) cout<<a[i][j]<<"\t"; //вывод очередного элемента матрицы cout<<endl; //переход на новую строку после вывода всех элементов строки } system("pause"); return 0; }

Теперь, давайте рассмотрим некоторые свойства матриц:

• если номер строки элемента совпадает с номером столбца  (i = j), это означает , что элемент лежит на главной диагонали матрицы;

• если номер строки превышает номер столбца (i > j), то элемент находиться ниже главной диагонали;

• если номер столбца больше номера строки (i < j), то элемент находиться выше главной диагонали;

• элемент лежит на побочной диагонали, если его индексы удовлетворяют равенству i+j+1=n;

• неравенство i+j+1<n характерно для элемента, находящегося выше побочной диагонали;

• соответственно, элементу, лежащему ниже побочной диагонали, соответствует выражение i+j+1>n.

Найти сумму элементов матрицы, лежащих выше главной диагонали 

#include "stdafx.h" #include <iostream> using namespace std; int main() { setlocale (LC_ALL, "RUS"); int S, i, j, N, M, a[20][20]; cout<<"N="; cin>>N; cout<<"M="; cin>>M; cout<<"Введите матрицу А \n"; for (i=0; i<N; i++) for (j=0; j<M; j++) cin>>a[i][j]; for (S=i=0; i<N; i++) for (j=0; j<M; j++) //если элемент лежит выше главной диагонали, то наращиваем сумму if (j>i) S+=a[i][j]; cout<<"S="<<S<<endl; system("pause"); return 0; }

25. Понятие о многомерных массивах. Привести пример инициализации элементов многомерных массивов на языке С/C++.

Многомерные массивы

В языке Си могут быть также объявлены многомерные массивы. Отличие многомерного массива от одномерного состоит в том, что в одномерном массиве положение элемента определяется одним индексом, а в многомерном — несколькими. Примером многомерного массива является матрица.

Общая форма объявления многомерного массива

тип имя[размерность1][размерность2]...[размерностьm];

Многомерные массивы задаются указанием каждого измерения в квадратных скобках, например, оператор

int matr [6][8];

задает описание двумерного массива из 6 строк и 8 столбцов. В памяти такой массив располагается в последовательных ячейках построчно. Многомерные массивы размещаются так, что при переходе к следующему элементу быстрее всего изменяется последний индекс. Для доступа к элементу многомерного массива указываются все его индексы, например, matr[i][j], или более экзотическим способом: *(matr[i]+j) или *(*(matr+i)+j). Это возможно, поскольку matr[i] является адресом начала i-й строки массива.

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

int mass2 [][2] = { {1, 1}, {0, 2}, {1, 0} }: int mass2 [3][2] = {1, 1, 0, 2, 1, 0}

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

#include <stdio.h>

int main(){

   const int nstr = 4, nstb = 5; // размерности массива

   int b[nstr][nstb]; // описание массива

   int i, j;

   for (i = 0; i<nstr; i++) // ввод массива

   for (j = 0; j<nstb; j++) scanf("%d", &b[i][j]);

   int istr = -1, MaxKol = 0;

   for (i = 0; i<nstr; i++){ // просмотр массива по строкам

      int Коl = 0:

      for (j = 0; j<nstb; j++) if (b[i][j] == 0) Kol++;

      if (Ko1 > MaxKol) {istr = i ; MaxKol = Kol;}

   }

   printf(" Исходный массив:\n");

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

      for (j = 0; j<nstb; j++) printf("%d ", b[i][j]);

      printf ("\n");}

   if (istr == -1) printf("Нулевых элементов нет");

   else printf("Hoмep строки: %d", istr);

   return 0;

}