Задача 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рия цикъл правим размяна на елемента с индекс брояча на първия цикъл и най-малкия елемент ( индекса му записахме в отделна променлива.
Накрая отпечатваме сортирания масив.
Допълнителна информация:
Задача 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 за да го стесним 🙂
Ето малко визуално обяснение:
И като цяло това е основата на алгоритъма. Разпишете си го на лист хартия за да видите, колко е лесен 🙂
Ето още един пример, като този е конкретно за имплементацията на алгоритъма в/у масив:
Задача 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 път в масива с букви 🙂
Очаквайте скоро следващата порция 🙂
