Домашни от масиви – решения и обяснения. Част втора.

C_Sharp

Задача 7. Sorting an array means to arrange its elements in increasing order. Write a program to sort an array. Use the “selection sort” algorithm: Find the smallest element, move it at the first position, find the smallest from the rest, move it at the second position, etc.

Решение: PasteBin

Обяснение:  Първия сортиращ алгоритъм с който се сблъскваме, един от най-лесните, но и един от най-неефективните. Основанта логика тук е:

Първия и обикаля по всички елементи на цикъла, а втория обикаля всички елементи, започвайки от позицията на брояча на първия цикъл + 1, като с него търсим най-малкия елемент и записваме индекса му в отделна променлива. След като сме намерили най-малкия елемент с помощта на 2рия цикъл правим размяна на елемента с индекс брояча на първия цикъл и най-малкия елемент ( индекса му записахме в отделна променлива.

Накрая отпечатваме сортирания масив.

Допълнителна информация:

  1. Визуализация на търсещите алгоритми
  2. Статия във Wikipedia

Задача 8. Write a program that finds the sequence of maximal sum in given array. Example: {2, 3, -6, -1, 2, -1, 6, 4, -8, 8}  ->  {2, -1, 6, 4} Can you do it with only one loop (with single scan through the elements of the array)?

Решение: PasteBin

Обяснение: Каква хитрина може да използваме за да не е нужно да използваме 2 цикъла ? Просто проверяваме дали текущата сума е паднала под нула. Ето моята логика:

1. С for цикъла обхождаме всеки елемент по-отделно.

2. След това добавяме стойността на текущия елемент към текущата сума.

3. Използваме StringBuilder за да запазим текущата редичка ( може и с начален и краен индекс, но реших да пробвам по друг начин ). Ако не знаете какво е StringBuilder или метода AppendFormat,не ви е познат вижте тук:

StringBuilder: http://www.dotnetperls.com/stringbuilder

AppendFormat: http://www.dotnetperls.com/appendformat

4. Следващата стъпка е да проверим дали, текущата сума е по-голяма, от най-голямата до сега, ако да присвояваме я като най-голяма и превръщаме редичката от StringBuilder – a в най-добрата редичка до сега.

5. Следващата проверка е дали текущата сума е паднала под нула. Ако това е вярно, нулираме текущата сума и изчистваме съдържанието на StringBuilder – a с метода .Clear()

Забележка: Алгоритъма ще работи и при масив със само отрицателни числа. Там най-малката редица е най-малкия отрицателен елемент.

Задача 9. Write a program that finds the most frequent number in an array. Example: {4, 1, 1, 4, 2, 3, 4, 4, 1, 2, 4, 9, 3} -> 4(5 times)

Решение: PasteBin

Обяснение: Ето основните стъпки през който минавам:

1. Ако не знаете какво е речник, потърсете в Интернет. Основната ми идея в задачата се базира в/у тази структура.

Препоръчвам ви да погледнете тук: http://www.dotnetperls.com/dictionary

2. С един цикъл обикалям по всички стойности на масива си ( този който го взимам от входа ). Ако стойността на даден елемент не съществува в речника ми, добавям я с ключ стойност на елемента и стойност към този ключ 1 ( до сега съм я срещнал 1 път ) , а ако съществува просто увеличава стойността на дадения ключ с 1.

Забележка: При работа с речници използвате: TryGetValue(), а не ContainsKey() . Първия е по-бърз. Източник: http://www.dotnetperls.com/trygetvalue

3. След като сме попълнили нащия речник с обикновен foreach обикаляме всичките му елементи и ги сравняваме по стойност (Value) и ако стойноста им е по-голяма от най-голямата срещана до сега я запзваме в отделна променлива. Също така имам и променлива пазеща ключа на най-често срещания елемент в речника ( на често срещания елемент в нашия вход ).

Забелжека: Защо присвоявам на int bestFrequnecy = int.MinValue; ? Ами така се подсигурявам, че при сравнението първия елемент ще бъде присвоен веднага на променливата т.к. което и да е число винаги е по-голямо от най-малката стойност на int.

Задача 10. Write a program that finds in given array of integers a sequence of given sum S (if present). Example:  {4, 3, 1, 4, 2, 5, 8}, S=11 -> {4, 2, 5}

Решение: PasteBin

Обяснение: Основните ми стъпки тук са следните:

1.  Имам 2 цикъла с който генерирам всички възможно суми на последователности на елементи.

2. Редицата я пазя във string, като я конструирам със StringBuilder ( WTF е StringBuilder ? Виж няколко задачи по-горе. )

3. Ако текущата сумата е станала по-голяма от търсената сума – break; – ваме цикъла и изчистваме StringBuilder – a с .Clear().

4. Aко е станала равна на търсената превръщаме редицата в string и я изписваме на конзолата.

Задача 11. Write a program that finds the index of given element in a sorted array of integers by using the binary search algorithm (find it in Wikipedia).

Решение: PasteBin

Обяснение:

Преди да почнем трябва да отбележим, че този алгоритъм трябва да се прилага само в/у сортирани масиви. Какво правя:

1. Създава ме си един метод ( Може и без отделен метод, но така е по-прегледно ) , който приема аргументи – сортирания масив, в който търсим и стойността ( ключа ) на елемента който търсим. Връщаната от него стойност показва индекса, на който се намира елемента или ако върне -1 означава, че няма такъв елемент в масива.

2. Каква е основната логика тук ? Ще се опитам да я обясня с пример.

Има една игричка, която се състой в това да се познае число в дадена рамка, да кажем 0 до 100, като този който си е намислил числото, при наш опит ни казва дали сме познали, дали числото се намира под това което сме казали ( по-малко ), дали над това което сме казали ( по – голямо ). Една игра протича така:

Намислено число: 80 в рамка 0 -100.

1ви опит – 50 -> по-голямо

2ри опит – 75 -> по-голямо

3ти опит – 87 -> по-малко

и т.н. -> винаги определяме дали числото е по-малко или по-голямо и делим дадения интревал 2 за да го стесним 🙂

Ето малко визуално обяснение:

BinSearch

И като цяло това е основата на алгоритъма. Разпишете си го на лист хартия за да видите, колко е лесен 🙂

Ето още един пример, като този е конкретно за имплементацията на алгоритъма в/у масив:

BinSearchOnArray

 

Задача 12. Write a program that creates an array containing all letters from the alphabet (A-Z). Read a word from the console and print the index of each of its letters in the array.

Решение: PasteBin

Обяснение:

Ще приемем, че “а” съответства на позиция 1, а не на 0 в масива с букви, с чисто естетическа цел ( няма нищо грешно да се направи и като 0, зависи как се разбира задачата )

1. Декларираме си char масив за всички букви – малки и големи – с големина 53 т.к. искаме да започва от 1, а не от 0.

2. Пръвия for цикъл пълни масива с малко букви, с помощта на един просто трик -> ‘a’ + 1 = ‘b’ . Като вместо 1 използваме брояча на цикъла.

3. Със втория for попълваме масива със големите букви, пак с трика от предишната точка, но тук декларираме една допълнителна променлива k която се увеличава до 25 т.к. броенето на главния брояч започва от 26 ( това е с цел да започнем попълването на масива от 26та позиция )

4. Сравнението се извършва по елементарен начин – с един цикъл обикаляме по буквите на думата ( най-подходящи според мен тук са for или foreach ) а със втория по масива с букви. Ако има съвпадение изписваме резултата и break; – ваме обхождането по масива с букви. Защо break; – ваме ? Ами една буква може да се среща само 1 път в масива с букви 🙂

Очаквайте скоро следващата порция 🙂

 

Домашни от масиви – решения и обяснения. Част първа.

C-To-Go-300x300

В тази тема ще поместя, част от решенията на задачите от Лекцията за масиви.

Задача 1. Write a program that allocates array of 20 integers and initializes each element by its index multiplied by 5. Print the obtained array on the console.

Решение: PasteBin

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

Задача 2: Write a program that reads two arrays from the console and compares them element by element.

Решение: PasteBin

Обяснение: Относително лесна задача, като първите няколко стъпки са доста праволинейни – попълваме 2 масива, чрез for цикли и четене на отделните елементи от конзолата. Същинската част е след това.

Инициализираме bool променлива която индикира дали дадени два елемента си равни ( началната и стойност е true т.к. двата масива са равни до доказване на противното ). След това обхождаме 2та масива едновременно ( с помощта на индекса на for цикъла, който индикира кореспондиращия индекс в 2та масива ) и ако някой от двата елемента не са равни, то променяме стойността на bool променливата на false и break-ваме цикъла. Защо го break-ваме ? Ами за нас е достатъчно, че 2 елемента са различни за да заключим, че двата масива са различни.

Задача 3: Write a program that compares two char arrays lexicographically (letter by letter).

Решение: PasteBin

Обяснение: Основната логика, тук е – първо проверяваме дали двата масива имат равна дължина, ако не то те не са равни. Ако има равна дължина проверяваме по отделно всеки елемент и ако има даже един различен двата масива не са равни.

Задача 4: Write a program that finds the maximal sequence of equal elements in an array. Example: {2, 1, 1, 2, 3, 3, 2, 2, 2, 1} -> {2, 2, 2}.

Решение: PasteBin

Обяснение: Използвал си 3 променливи, за следните цели:

len – текущата дължина на проверяваната редица.

bestLen – най-голяма дължина срещана до сега;

bestLenElement  – елемента, който се е срещал най-много до сега.

След това обхождам масива си от ляво на дясно и започвам да проверявам дали текущия елемент е равен на следващия ( myArray[i] == myArray[i+1] ). Ако да увеличавам дължината на текущата редичка, ако не проверявам дали дължината на текущата редица е по-голяма от най-голямата до сега. Ако е така, присвоявам bestLen = len; и отбелязван, на кой елемент съм за bestLenElement .

Следващата стъпка е да ресетна len на 1.

И накрая, се подсигурявам, че последната редица не е била, най-голямата т.к. това е случай, който се изпуска от for цикъла ми.

Забележка: Защо len=1; ? Ами понеже елемента който сравняваме със следващия е редичка сам за себе си с дължина 1.

Забележка 2: Не забравяйте при задаване на условието на цъкал то, да е с едно по-малко от максималното ( myArray.Length-1 ) т.к. проверяваме с 1 елемент напред и ако не счетем това ще имаме IndexOutOfRange изключение.

Задача 5:  Write a program that finds the maximal increasing sequence in an array. Example: {3, 2, 3, 4, 2, 2, 4} -> {2, 3, 4}.

Решение: PasteBin

Обяснение: Логиката тук е аналогична с тази от 4та задача, с малки изключения. Условието при което увеличаваме дължината на текущата редица е следващия елемент да е по-голям от текущия и вместо да взимаме на-добрия елемент, взимаме последния елемент от редицата и чрез него си принтваме цялата на-добра редичка, чрез намаляващ for.

Задача 6: Write a program that reads two integer numbers N and K and an array of N elements from the console. Find in the array those K elements that have maximal sum.

Решение: PasteBin

Обяснение: Доста интресна задачка. Основната ми логика тук е:

Първия for цикъл обикаля по отделните елементи на масива.

Когато влезем в този for имаме следната проверка: (i + k > arrayLen) т.е. дали к елемента ( дължината на търсената редица ) напред няма да излезем извън нашия масив т.е. ако е вярно няма смисъл да правим други проверки и за това break; – ваме цикъла.

Следва същинската проверка за сумата с втори for цикъл , който върти до i + k – дължината на търсената ни редица от елемента на който сме.

След това просто имаме проверка дали, текущата сума е по-голяма от най-голямата сума до сега. Ако да заместваме най-голямата сума до сега с нея.

И накрая нулираме текущата сума.

Очаквайте, скоро Част втора от домашната за масиви 🙂