Теория
Масивът (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) | Същото без LINQ | int[] 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 намираме най-малкия в остатъка и го слагаме на i | if (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 сравнения |
Код за анализ и пренаписване
Четене от един ред, броене по условие и обръщане на място
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
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 3Console.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 2Array.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)` и защо?
Речник на термините
Виж пълния речник на курса0, последният е Length - 1.Array.Reverse.(i + k) % n дава индекс, който винаги е в границите от 0 до n - 1.Array.Sort, а за низходящ ред – последвано от Array.Reverse.Провери знанията
Бърз тест с избор от отговори върху термините на модула — с точки и моментална обратна връзка.
Провери знанията си
9 въпроса върху термините от модула. Показваме определение — ти избираш правилния термин.
Материали от часовете
Задачи и тестове, давани в клас по тази тема.
Препоръки за този модул
- Разигравайте всеки алгоритъм на хартия с масив от 5–6 числа: записвайте стойностите на
i,left,rightи съдържанието на масива след всяка стъпка. Повечето грешки с индекси се виждат още на втория ред от таблицата. - Пазете си файл с „готови парчета“: четене от един ред, печат със
string.Join, размяна презtemp, цикъл за обръщане, ротация с модул. При нова задача ги копирате и само ги комбинирате. - Тествайте с крайни случаи: празен ред, масив от един елемент, всички елементи еднакви,
kпо-голямо от дължината, само отрицателни числа. Ако програмата преживее тях, ще преживее и обикновения вход. - Пишете първо версията с цикъл, а после – ако знаете LINQ – проверете резултата с
Count,Min,MaxиReverse. Когато двете версии дават едно и също, почти сигурно сте прави.