Модул 19

Масиви – типични алгоритми

Типичните алгоритми върху масив в C#: четене на масив от един ред със Split и Select, извеждане със string.Join, броене на елементи по условие, обръщане на място с два индекса, ротация наляво и надясно с остатък по модул, сортиране с Array.Sort и ръчно с метода на мехурчето и пряката селекция. Завършва с комбинирани задачи с масиви и техниката с два индекса.

Теория

Масивът (array) е редица от стойности от един и същи тип под общо име, достъпни по индекс (index) от 0 до Length - 1. Повечето задачи с масиви се решават с няколко типични алгоритъма – кратки шаблони, които се повтарят от задача в задача: прочети, обходи, преброй, обърни, завърти, сортирай, отпечатай. Щом ги владеете, нова задача е просто комбинация от познати парчета. Всичко започва с въвеждането на масива и завършва с неговото извеждане, затова първо ще се научим да четем и пишем масиви бързо и без грешки.

Най-удобно е числата да идват на един ред, разделени с интервал, например 3 8 -2 5. Редът се чете с Console.ReadLine(), разделя се със Split(' ', StringSplitOptions.RemoveEmptyEntries) на отделни низове, всеки низ се превръща в число със Select(int.Parse), а ToArray() събира резултата в int[] (за Select е нужно using System.Linq;). Същото без LINQ прави Array.ConvertAll(parts, int.Parse). Когато всяко число е на отделен ред, първо четем броя n, създаваме new int[n] и с for цикъл запълваме arr[i] = int.Parse(Console.ReadLine()). За извеждане на масив най-краткият правилен начин е Console.WriteLine(string.Join(" ", arr)) – string.Join слепва елементите с избран разделител; ако напишете само Console.WriteLine(arr), ще видите System.Int32[], а не числата.

Броят на елементите по условие е най-простият алгоритъм за обхождане: променлива-брояч int count = 0; преди цикъла и count++ вътре в него, но само когато елементът отговаря на условието. Така броим четните (arr[i] % 2 == 0), отрицателните (arr[i] < 0), елементите в даден интервал или равните на определена стойност. Понякога условието зависи от целия масив – например „колко елемента са над средноаритметичното“ – и тогава трябват две обхождания: първото изчислява средното, второто брои. Няколко брояча могат да работят в един и същ цикъл, а else if гарантира, че всеки елемент попада точно в една група. С LINQ същото се пише на един ред, arr.Count(x => x > 0), но важно е първо да разбирате версията с цикъл, защото тя е в основата на всичко останало.

Обръщането (reverse) на масив разменя първия с последния елемент, втория с предпоследния и така нататък към средата. Най-чистият запис е с два индекса: left тръгва от 0, right от Length - 1, разменяме arr[left] и arr[right] през временна променлива temp и ги движим един към друг, докато left < right. Еквивалентен е цикъл for (int i = 0; i < arr.Length / 2; i++), който разменя arr[i] с arr[arr.Length - 1 - i] – границата е половината, защото ако обходим целия масив, всяка двойка ще се размени два пъти и масивът ще се върне в изходното си състояние. Това обръщане е на място (in place): не създаваме нов масив. Ако искате само да отпечатате елементите отзад напред, без да променяте масива, достатъчен е цикъл от Length - 1 надолу до 0, а готовият метод Array.Reverse(arr) върши цялата работа с един ред.

Ротацията (rotation) „завърта“ масива: при ротация наляво с една позиция първият елемент отива в края, а всички останали се изместват с едно място напред; при ротация надясно последният елемент отива в началото. За една позиция наляво запазваме arr[0] в променлива, изместваме с цикъл arr[i] = arr[i + 1] за i от 0 до Length - 2 и накрая записваме запазената стойност в arr[Length - 1]. За ротация с k позиции най-лесно е да създадем нов масив и да сметнем новата позиция на всеки елемент с остатък по модул: при ротация надясно rotated[(i + k) % n] = arr[i], а при ротация наляво rotated[i] = arr[(i + k) % n]. Операторът % е ключов – той „увива“ индекса обратно в границите на масива и прави излишна отделната обработка на крайните елементи. Преди всичко намалете k с k = k % n: ротация с n позиции връща масива в същия вид, така че ротация с 12 при 5 елемента е същата като с 2.

Сортирането на масив подрежда елементите във възходящ или низходящ ред. В .NET готовият метод Array.Sort(arr) сортира масива на място във възходящ ред и не връща нищо (void); за низходящ ред след него извикваме Array.Reverse(arr). Полезно е обаче да знаете как работи сортирането отвътре. При метода на мехурчето (bubble sort) сравняваме всеки два съседни елемента и ги разменяме, ако са в грешен ред; след първото преминаване най-голямото число „изплува“ в края, затова всяко следващо преминаване може да спре една позиция по-рано, а общо са нужни n - 1 преминавания. При пряката селекция (selection sort) за всяка позиция i търсим индекса на най-малкия елемент в остатъка от i нататък и го разменяме с arr[i]. И двата метода правят около n² сравнения, което е бавно при хиляди елементи; Array.Sort използва много по-бърз алгоритъм, затова в реални програми ползвайте него, а ръчните методи – за да разбирате какво се случва.

При задачи с масиви почти винаги комбинираме шаблоните: четем масива, прилагаме един или няколко алгоритъма и отпечатваме резултата. Търсенето на най-малък или най-голям елемент е брояч от друг вид – пазим текущия най-добър кандидат (и често неговия индекс) и го обновяваме при всяко по-добро число; началната стойност е arr[0], а не 0, защото масивът може да съдържа само отрицателни числа. Двата индекса от обръщането работят и за други проверки: дали масивът е палиндром (arr[left] == arr[right] на всяка стъпка) или дали в сортиран масив има двойка елементи с дадена сума (ако сумата е малка, местим left надясно, ако е голяма – right наляво). Проверката дали масивът е сортиран е един цикъл, който търси съсед arr[i] > arr[i + 1] и спира с break още при първия. Преди да пишете код, разиграйте алгоритъма на хартия с 5–6 числа – така виждате точно кои индекси трябва да се движат и къде свършва цикълът.

Златни правила

Индексите са от `0` до `Length - 1`

Последният елемент е arr[arr.Length - 1], а arr[arr.Length] хвърля IndexOutOfRangeException. Всяка граница на цикъл проверявайте с въпроса: кой е последният индекс, който ще докосна?

Четете със `Split`, печатайте със `string.Join`

Входът от един ред става масив със Split(' ', StringSplitOptions.RemoveEmptyEntries), Select(int.Parse) и ToArray(). Изходът става със string.Join(" ", arr) – Console.WriteLine(arr) печата само името на типа.

Обръщайте само до средата

Цикълът за обръщане на място стига до arr.Length / 2. Пълно обхождане разменя всяка двойка два пъти и връща масива в изходния му вид.

Ротация винаги с `% n`

Преди ротация направете k = k % n, а новата позиция смятайте с (i + k) % n. Така никога не излизате извън масива, колкото и голямо да е k.

`Array.Sort` променя масива и връща `void`

Не пишете int[] s = Array.Sort(arr); – методът сортира arr на място и няма резултат. Ако оригиналът ви трябва, първо направете копие с (int[])arr.Clone().

Бърз справочник

Четене, печат и готови методи за масиви

ИзразКакво правиПримерБележка
Split(' ', StringSplitOptions.RemoveEmptyEntries)Разделя реда на отделни низове"3 8 5".Split(' ', StringSplitOptions.RemoveEmptyEntries) дава 3, 8, 5Без втория аргумент двойният интервал дава празен низ и int.Parse хвърля FormatException
Select(int.Parse).ToArray()Превръща всеки низ в число и прави масивparts.Select(int.Parse).ToArray()Нужно е using System.Linq;
Array.ConvertAll(parts, int.Parse)Същото без LINQint[] arr = Array.ConvertAll(parts, int.Parse);Връща нов масив
string.Join(" ", arr)Слепва елементите с разделителConsole.WriteLine(string.Join(", ", arr));Console.WriteLine(arr) печата System.Int32[]
arr.LengthБрой елементиfor (int i = 0; i < arr.Length; i++)Последният индекс е Length - 1
Array.Sort(arr)Сортира на място възходящоArray.Sort(arr);Връща void, не нов масив
Array.Reverse(arr)Обръща на мястоArray.Reverse(arr);След Sort дава низходящ ред
Array.IndexOf(arr, x)Индекс на първото срещанеint pos = Array.IndexOf(arr, 7);Връща -1, ако го няма
(int[])arr.Clone()Копие на масиваint[] copy = (int[])arr.Clone();int[] b = arr; не е копие – сочи същия масив

Типичните алгоритми в едно изречение

АлгоритъмИдеяКлючов редКолко работа
Броене по условиеБрояч count, увеличава се при вярно условиеif (arr[i] % 2 == 0) count++;Едно обхождане
Най-малък / най-голямПазим текущия най-добър, започваме от arr[0]if (arr[i] > max) { max = arr[i]; maxIndex = i; }Едно обхождане
Обръщане на мястоДва индекса от двата края се разменят и се движат към средатаwhile (left < right) { ...размяна...; left++; right--; }n / 2 размени
Ротация наляво с 1Запазваме arr[0], изместваме останалите, връщаме го в краяarr[i] = arr[i + 1]; и накрая arr[n - 1] = first;Едно обхождане
Ротация с k в нов масивНова позиция с остатък по модулrotated[(i + k) % n] = arr[i]; (надясно)Едно обхождане, преди него k = k % n
Метод на мехурчетоСъседи в грешен ред се разменят; най-големият „изплува“ в краяif (arr[i] > arr[i + 1]) { ...размяна... }n - 1 преминавания, около n² сравнения
Пряка селекцияЗа всяко i намираме най-малкия в остатъка и го слагаме на iif (arr[j] < arr[minIndex]) minIndex = j;Около n² сравнения, най-много n - 1 размени
Проверка за сортираностТърсим съсед, който нарушава редаif (arr[i] > arr[i + 1]) { sorted = false; break; }Едно обхождане
Палиндром с два индексаСравняваме огледалните елементиif (arr[left] != arr[right]) { isPal = false; break; }n / 2 сравнения

Код за анализ и пренаписване

Четене от един ред, броене по условие и обръщане на място

Program.cs
using System;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.Write("Въведете числа, разделени с интервал: ");
        int[] arr = Console.ReadLine()
            .Split(' ', StringSplitOptions.RemoveEmptyEntries)
            .Select(int.Parse)
            .ToArray();

        Console.WriteLine("Масив: " + string.Join(" ", arr));
        Console.WriteLine("Брой елементи: " + arr.Length);

        // Броене по условие: четни и отрицателни числа
        int evenCount = 0;
        int negativeCount = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] % 2 == 0)
            {
                evenCount++;
            }
            if (arr[i] < 0)
            {
                negativeCount++;
            }
        }
        Console.WriteLine($"Четни: {evenCount}, отрицателни: {negativeCount}");

        // Същото броене с LINQ - за проверка
        Console.WriteLine($"Четни (LINQ): {arr.Count(x => x % 2 == 0)}");

        // Обръщане на място с два индекса
        int left = 0;
        int right = arr.Length - 1;
        while (left < right)
        {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
        Console.WriteLine("Обърнат: " + string.Join(" ", arr));
    }
}

Какво се случва тук?

  • Console.ReadLine() връща целия ред като един низ; Split(' ', StringSplitOptions.RemoveEmptyEntries) го нарязва по интервалите и изхвърля празните парчета, ако потребителят е натиснал интервал два пъти.
  • Select(int.Parse) прилага int.Parse върху всяко парче, а ToArray() събира числата в int[] – това е причината за using System.Linq; в началото.
  • string.Join(" ", arr) слепва елементите с интервал между тях – така печатаме масив на един ред, без да пишем цикъл.
  • Броячите evenCount и negativeCount стартират от 0 и всеки се увеличава само когато неговото условие е вярно; двете проверки са отделни if, защото едно число може да е едновременно и четно, и отрицателно.
  • arr.Count(x => x % 2 == 0) е LINQ версията на същото броене – удобна за проверка, че цикълът дава верен резултат.
  • Обръщането използва два индекса: left тръгва от 0, right от arr.Length - 1; на всяка стъпка разменяме двата елемента през temp и ги приближаваме с left++ и right--.
  • Условието left < right спира цикъла в средата – при нечетен брой елементи средният остава на мястото си, а при четен последната размяна е между двата съседни елемента в центъра.

Ротация наляво и надясно, bubble sort и Array.Sort

Program.cs
using System;

class Program
{
    static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 7 };
        Console.WriteLine("Начален:     " + string.Join(" ", arr));

        // Ротация наляво с 1 позиция (на място)
        int first = arr[0];
        for (int i = 0; i < arr.Length - 1; i++)
        {
            arr[i] = arr[i + 1];
        }
        arr[arr.Length - 1] = first;
        Console.WriteLine("Наляво с 1:  " + string.Join(" ", arr));

        // Ротация надясно с k позиции в нов масив
        int k = 7;
        int n = arr.Length;
        k = k % n;
        int[] rotated = new int[n];
        for (int i = 0; i < n; i++)
        {
            rotated[(i + k) % n] = arr[i];
        }
        Console.WriteLine($"Надясно с {k}:  " + string.Join(" ", rotated));

        // Сортиране с метода на мехурчето (bubble sort) върху копие
        int[] bubble = (int[])arr.Clone();
        for (int pass = 0; pass < bubble.Length - 1; pass++)
        {
            for (int i = 0; i < bubble.Length - 1 - pass; i++)
            {
                if (bubble[i] > bubble[i + 1])
                {
                    int temp = bubble[i];
                    bubble[i] = bubble[i + 1];
                    bubble[i + 1] = temp;
                }
            }
        }
        Console.WriteLine("Bubble sort: " + string.Join(" ", bubble));

        // Вграденото сортиране - възходящо и низходящо
        int[] sorted = (int[])arr.Clone();
        Array.Sort(sorted);
        Console.WriteLine("Array.Sort:  " + string.Join(" ", sorted));
        Array.Reverse(sorted);
        Console.WriteLine("Низходящо:   " + string.Join(" ", sorted));
        Console.WriteLine("Оригиналът:  " + string.Join(" ", arr));
    }
}

Какво се случва тук?

  • Ротацията наляво с една позиция първо запазва arr[0] в first, защото следващият ред arr[i] = arr[i + 1] ще го презапише; цикълът спира на arr.Length - 1, за да не прочете несъществуващия arr[arr.Length].
  • Накрая запазеният елемент се записва в arr[arr.Length - 1] – от 5 2 9 1 7 получаваме 2 9 1 7 5.
  • За ротация надясно с k = 7 при n = 5 елемента първо смятаме k = k % n, тоест 2: пет пълни завъртания връщат масива в същия вид, остават само две.
  • В новия масив rotated всеки елемент отива на позиция (i + k) % n: елементът с индекс 3 отива на (3 + 2) % 5 = 0, тоест в началото – модулът „увива“ индекса, и резултатът е 7 5 2 9 1.
  • (int[])arr.Clone() прави истинско копие, за да сортираме, без да променяме arr; простото int[] b = arr; само би дало второ име на същия масив.
  • При bubble sort външният цикъл pass брои преминаванията, а вътрешният стига до Length - 1 - pass, защото след всяко преминаване най-голямото число вече е на мястото си в края.
  • Array.Sort(sorted) подрежда възходящо на място и не връща нищо; Array.Reverse(sorted) веднага след него дава низходящия ред, а последният ред показва, че arr е останал непроменен.

Внимавай! Чести грешки

Грешките, които почти всеки прави в тази тема — виж разликата между грешния и правилния код.

`Console.WriteLine(arr)` не печата елементите

Грешно

int[] arr = { 1, 2, 3 };
Console.WriteLine(arr);
// Извежда: System.Int32[]

Правилно

int[] arr = { 1, 2, 3 };
Console.WriteLine(string.Join(" ", arr));
// Извежда: 1 2 3

Console.WriteLine не знае как да покаже масив и печата името на типа. string.Join слепва елементите с разделител по ваш избор.

Обръщане до края вместо до средата

Грешно

for (int i = 0; i < arr.Length; i++)
{
    int temp = arr[i];
    arr[i] = arr[arr.Length - 1 - i];
    arr[arr.Length - 1 - i] = temp;
}
// Масивът изглежда непроменен!

Правилно

for (int i = 0; i < arr.Length / 2; i++)
{
    int temp = arr[i];
    arr[i] = arr[arr.Length - 1 - i];
    arr[arr.Length - 1 - i] = temp;
}

Пълното обхождане разменя всяка двойка два пъти и масивът се връща в изходния си вид – програмата „работи“, но нищо не се променя. Границата Length / 2 разменя всяка двойка точно веднъж.

Ротация без остатък по модул

Грешно

int[] rotated = new int[n];
for (int i = 0; i < n; i++)
{
    rotated[i + k] = arr[i]; // IndexOutOfRangeException
}

Правилно

k = k % n;
int[] rotated = new int[n];
for (int i = 0; i < n; i++)
{
    rotated[(i + k) % n] = arr[i];
}

Щом i + k достигне n, индексът е извън масива и програмата се срива. Остатъкът % n връща индекса в началото, а предварителното k = k % n обработва и много големи стойности на k.

`Array.Sort` не връща нов масив

Грешно

int[] arr = { 3, 1, 2 };
int[] sorted = Array.Sort(arr); // грешка при компилация
Console.WriteLine(string.Join(" ", sorted));

Правилно

int[] arr = { 3, 1, 2 };
int[] sorted = (int[])arr.Clone();
Array.Sort(sorted);
Console.WriteLine(string.Join(" ", sorted)); // 1 2 3
Console.WriteLine(string.Join(" ", arr));    // 3 1 2

Array.Sort е void и подрежда масива на място, затова резултатът му не може да се присвои. Ако оригиналният ред ви трябва, сортирайте копие.

Задачи за самостоятелна работа

Опитай първо сам — подсказката е там само ако наистина закъсаш.

Броене по условие и средна стойност

Прочетете от един ред масив от цели числа, разделени с интервал. Отпечатайте колко от тях са положителни, колко отрицателни и колко нули. След това изчислете средноаритметичното на масива (с два знака след десетичната запетая) и отпечатайте колко елемента са строго по-големи от него. Ако редът е празен, изведете „Няма числа.“.

Ротация наляво с k и проверка за сортираност

На първия ред се въвежда масив от цели числа, на втория – неотрицателно цяло число k, което може да е по-голямо от дължината на масива. Завъртете масива наляво с k позиции в нов масив и го отпечатайте на един ред. След това проверете дали полученият масив е сортиран във възходящ ред и изведете „Сортиран“ или „Не е сортиран“. Пример: вход 3 4 5 1 2 и k = 3 дава 1 2 3 4 5 и „Сортиран“.

Пряка селекция и двойка с дадена сума

На първия ред се въвежда масив от цели числа, на втория – цяло число target. Сортирайте масива възходящо с метода на пряката селекция (selection sort), без да използвате Array.Sort, и го отпечатайте. След това с два индекса (left от началото и right от края) намерете дали съществуват два различни елемента със сума target. Отпечатайте ги във вид a + b = target или „Няма такава двойка.“.

Мини-тест за проверка

Отговори си наум (или на глас!) и чак тогава разкрий отговора.

1. Защо цикълът за обръщане на масив на място стига само до `arr.Length / 2`, а не до `arr.Length`?

2. Масив с 5 елемента трябва да се завърти надясно с `k = 12` позиции. С колко позиции реално се измества всеки елемент и защо?

3. Какво ще отпечата кодът `int[] arr = { 3, 1, 2 }; Array.Sort(arr); Array.Reverse(arr); Console.WriteLine(string.Join(" ", arr));`?

4. За масива `{ -4, 3, 0, 7 }` колко е `arr.Count(x => x % 2 == 0)` и защо?

Речник на термините

Виж пълния речник на курса
Масив (array)
Редица от стойности от един тип под общо име, достъпни по индекс. Дължината се задава при създаването и не се променя.
Индекс (index)
Номерът на елемент в масива. Първият е 0, последният е Length - 1.
Обръщане (reverse)
Пренареждане, при което първият елемент става последен, вторият – предпоследен и така нататък; на място се прави с два индекса или с Array.Reverse.
Ротация (rotation)
Циклично изместване на елементите: при ротация наляво първият отива в края, при ротация надясно последният отива в началото.
Остатък по модул (`%`)
Остатъкът от целочислено деление. Изразът (i + k) % n дава индекс, който винаги е в границите от 0 до n - 1.
Сортиране (sorting)
Подреждане на елементите във възходящ или низходящ ред. В .NET се прави с Array.Sort, а за низходящ ред – последвано от Array.Reverse.
Метод на мехурчето (bubble sort)
Сортиране чрез многократно сравняване и размяна на съседни елементи, при което най-големият „изплува“ в края след всяко преминаване.
Пряка селекция (selection sort)
Сортиране, при което за всяка позиция се избира най-малкият от останалите елементи и се разменя с елемента на тази позиция.
Два индекса (two pointers)
Техника, при която два индекса се движат от двата края към средата; използва се за обръщане, проверка за палиндром и търсене на двойка с дадена сума в сортиран масив.

Провери знанията

Бърз тест с избор от отговори върху термините на модула — с точки и моментална обратна връзка.

Провери знанията си

9 въпроса върху термините от модула. Показваме определение — ти избираш правилния термин.

Материали от часовете

Задачи и тестове, давани в клас по тази тема.

Препоръки за този модул

  • Разигравайте всеки алгоритъм на хартия с масив от 5–6 числа: записвайте стойностите на i, left, right и съдържанието на масива след всяка стъпка. Повечето грешки с индекси се виждат още на втория ред от таблицата.
  • Пазете си файл с „готови парчета“: четене от един ред, печат със string.Join, размяна през temp, цикъл за обръщане, ротация с модул. При нова задача ги копирате и само ги комбинирате.
  • Тествайте с крайни случаи: празен ред, масив от един елемент, всички елементи еднакви, k по-голямо от дължината, само отрицателни числа. Ако програмата преживее тях, ще преживее и обикновения вход.
  • Пишете първо версията с цикъл, а после – ако знаете LINQ – проверете резултата с Count, Min, Max и Reverse. Когато двете версии дават едно и също, почти сигурно сте прави.

Учебен наръчник — теория, примери, задачи и тестове по предметите от учебния план.

Натисни Ctrl K или / отвсякъде, за да търсиш.