Week 06

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

Същност

• Подобно на едномерните масиви, представляват хиперкуб с елементи
• Данните представляват множество от множество от ... множество от елементи
• Масиви с размерност повече от 3 практически са неприложими, освен за моделиране на големи данни и невронни мрежи
• Най-лесната аналогия на двумерен масив е таблицата (матрица от алгебрата)
• В курса многомерен масив с размерност над 3 няма да е необходим

Декларация на двумерен масив

// 2d array
<type> <identifier>[<size>][<size>];

int arr1[4][3];
int arr2[][2] = {{1,2},{5,6},{7,8}}
std::cout << arr2[0][1];

Note

Може да пропуснем размера само на първото измерение. Това е така защото компилатора трябва да знае колко място да задели за останалите елементи и е необходимо за да изчислява мястото в паметта

Important

За размерност на масивите отново се ползват само константи

Принцип на работа

• Двумерните масиви в паметта са разполагат като едномерни масиви. Благодарение на размерността при инициализация, компилаторът изчислява как да си достъпи адреса в паметта.
• На практика ако имаме двумерен масив arr, то arr[0] ни връща указател към масива, представляващ второто измерение за конкретната стойност от първото измерение
• Може да си го мислим като масив от масиви
• На практика в паметта се разлога като една последователност и липсва тази концепция за разграничаване на отделните масиви (това е вярно само за статичните масиви)

Note

arr[i][j] е същото като да достъпим arr[i * n + j]

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

int logicalTwist[2][3][4][5][6];
int arr[3][4][5];
int arr2[][2][2] = { {{1,2},{3,4}}, {{5,6},{7,8}} };
arr2[0][1][0] = 42;

Работа с двумерен масив

Всички операции с двумерни масиви се основават на обхаждането на матрицата. Това носи и своите особености

• Обхождане по редове
• Обхождане по колони
• Обхождане по диагонали

// Обхождане на диагонал, успореден на главия,
// минаващ през елемент matrix[startRow][startCol]
for(size_t i = startRow, j = startCol; i <= n && j <= m; i++; j++){ }

// Обхождане на диагонал, успореден на втория диагонал,
// минаващ през елемент matrix[startRow][startCol],
// отдолу нагоре
for(int i = startRow, j = startCol; i >= 0 && j <= m; i--; j++){ }

• Обхождане по спирала

Подаване на двумерен масив във функци - с особеностите на декларацията - може да пропуснем само първата размерност

Important

Когато обхождаме масив отзад напред, трябва променливата да е от тип със знак, защото операция -- приложена над елемент от тип size_t със стойност 0 ни дава отново положително цяло число

Ефективност на алгоритмите

• За да може да избираме един алгоритъм пред друг, ни трябва някаква мярка
• Пример за такава мярка може да е дали алгоритамът винаги завършва, дали винаги намира решение, дали винаги намира оптимално решение и т.н.
• Като за начало може да въведем понятието сложност на алгоритъм - броят операции, необходими за завършването на алгоритъма
• Тази метрика има своите нюанси, но нека разгледаме сложност в най-лошия случай, тоест броят операции, необходими за изпълнение на алгоритъма при възможно най-неприятни за него входни данни - това може да значи например масив сортиран точно наобратно
• Нотацията за сложност на алгоритъм ползва като параметър N - големината на входните данни - може да си го мислим като броя елементи в масива
• Тогава ако искаме да обходим един масив, то ще имаме условно N елемента над които да минем
• Като търсим елемент в едномерен масив сложността на алгоритъма ще казваме, че е в най-лошия случай N, понеже трябва да обходим целия масив с N елемента, ако търсения е последен
• Аналогично ако искаме да обходим квадратна матрица, ще имаме сложност N*N, ако N е размерността ѝ
• Big O notation?

Основна задача

Да се провери дали даден масив е трион - тоест всеки негов елемент е по-малък(или равен) или по-голям(или равен) едновременно от двамата си съседи (arr[k] <= arr[k+1] <= arr[k+2] или arr[k] >= arr[k+1] >= arr[k+2] за произволно k)

Сложна задача за упражнение

Дадено е число $n \in [3,10]$ - брой на числата $x_i$. Всяко число $x_i$ има минимум 1 и максимум 10 цифри. Създаваме нулева квадратна матрица, която попълваме по следните правила:

• Ако цифрите на числото $x_i$ образуват трион, слагаме числото на ред $i$, подравнено вляво, като всяка цифра е отделен елемент
• Ако горното условие не е изпълнено, но четните цифри на числото $x_i$образуват трион, слагаме числото на ред $i$, подравнено вляво, като всяка цифра е отделен елемент
• Ако горните условия не са изпълнени, слагаме числото, получено от текущото като напишем цифрите му в обратен ред, на ред $i$, подравнено вляво, като всяка цифра е отделен елемент

За така получената матрица образуваме ново число, получено по следните правила: - Обхождаме матрицата спираловидно по посока на часовниковата стрелка отвън навътре - Ако предходната цифра от обхождането е нечетна, добавяме текущата цифра към новото число отзад - Ако предходната цифра от обхождането е четна, то ако сумата на елементите от диагонала, успореден на главния, който минава през текущия елемент, е нечетна, то добавяме текущата цифра към новото число - Ако новото число надвиши 10 цифри, махаме цифра от началото на числото

Да се отпечата новополученото число, ако се прочитат от конзолата $n$ и $x_i$.