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

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 път в масива с букви 🙂

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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s