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

C-To-Go-300x300

След относително голямото прекъсване най-накрая съм свободен ( сесията свърши! 😀 ) да почна отново да пускам решенията на задачите си със обяснение, като ще се постарая да постна всички решения, плюс още няколко полезни статии в близките седмици до изпита 🙂

Задача 13. Write a program that sorts an array of integers using the merge sort algorithm (find it in Wikipedia).

Решение: PasteBin

Обяснение:

Един от по-сложните сортиращи алгоритми. Основната идея зад него е:

  1. Разделяме рекурсивно несортирания масив/лист на N на брой подмасиви/листове с дължина 1 т.к. масив/лист със дължина 1 се счита за подреден ( за тази операция отговаря метода – MergeSortAlg.
  2. Рекурсивно сливаме подлистовте/масивите докато не остане само 1 сортиран масив.

За по-лесна визуализация вижте линка в допълнителна информация

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

  • Графично представяне на сортиращите алгоритми: Цък

Задача 14. Write a program that sorts an array of strings using the quicksort algorithm (find it in Wikipedia).

Решение: PasteBin

Обяснение:

Конкретната реализация, която съм направил аз тук се нарича Simple Quick Sort и по-неефективна от така наречения Inplace Quick Sort ( Ако ви е интересно ви препоръчвам да се пробвате да реализирате нея, лично аз при първа възможност ще го направя ). Основната логика Simple Quick Sort е следната:

  1. Избираме елемент наречен pivot елемент от нашия масив ( Определяме като подаденя масив разделим на 2 )
  2. Подреждаме елементите по-малки от pivot елемента в подлиста lesser, а който са по-големи в подлиста greater
  3. Повтаряме стъпка 2 рекурсивно и добавяме резултата в крайния лист result.

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

  • Графично представяне на сортиращите алгоритми: Цък

Задача 15. Write a program that finds all prime numbers in the range [1…10 000 000]. Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

Решение: PasteBin

Обяснение:

В какво се състой този алгоритъм ? Започваме от 2 и премахваме всички числа който се делят без остатък на 2, след това вземаме следващото число 3 и премахваме всички числа който се делят на това число и т.н. до края.

Как съм го направил в задачата аз ?

  1. Декларирам bool масив с 10 000 000 елемента, като индексите му отговарят на всяко число което искаме да проверим. ( по подразбиране всички елементи са false ).
  2. С първия цикъл обикалям до корен квадратен от всички числа ( може да обикаля до всички числа, но така е по-бързо. Тази оптимизация бе показана в домашните от предишната част на курса )
  3. Проверяваме дали числото е false, ако е влизаме в 2рия цикъл и го инициализираме с j = i*i със стъпка j = j + i. На всяка стъпка променяме стойността на даден елемент на true.
  4. Накрая отпечатваме индексите само на тези елементи, които са false.

П.С. Алгоритъма работи, но докато сe изпише всичко на конзолата, ще пуснете 2 чифта брада 😀

Задача 16.* We are given an array of integers and a number S. Write a program to find if there exists a subset of the elements of the array that has a sum S. Example: arr={2, 1, 2, 4, 3, 5, 2, 6}, S=14 -> yes (1+2+5+6)

Решение: PasteBin

Обяснение:

В основата на това решение, стои решението на задачата за намиране на броя на подмножествата от Примерния изпит за първата част на курса, обяснена на моята група от Николай Костов при подготовката ни за изпит ( Видео от лекцията: http://www.youtube.com/watch?v=Sk0PX0YSHtk  ).

Ето в общи линии в какво се състой решението на задачата:

  1. Попълваме си в един масив всички елементи.
  2. Определяме максимални брой на подмножествата по формулата – 2 на степен броя на елементите ( тук взимаме в предивид и нулевото множество ).
  3. И сега идва ядрото на задачата – как да определим кой са нашите подмножества. В общи лини, това става чрез побитовата репрезентация на числата от 0 до броя на всички възможни подмножества.

Ще ви покажа с пример как може да видим всички подмножества на елементите 1, 2, 3, 4. Всички възможно подмножества тук са – 15.

SubSetSum

Т.е. на всяка единица съответства елемнт от всички елементи.

  1. Реализацията в задачата – с първия for цикъл обхождаме всички възможно комбинация в задачата, а със втория – всички елементи в масива. С помощта на побитови операция проверяваме следното – 0 бит от първия цикъл 1 или нула е ? Ако е 1 взимаме елемента и го добавяме към общата сума, ако не го игнорираме. Същото става и за 1вия бит – ако е 0 го игнорираме, ако не е прибавяме елемента с индекс 1 към текущия сбор.
  2. Текущата редичка си я съхраняваме в обикновен стринг ( със StringBuilder е по-добре, но тук използвах конкитенация )
  3. И последната проверка е дали текущата сума е равна на търсената сума – ако това е вярно, я изписваме на конзолата.

Забележка: При всяка проверка на възможна комбинация трябва да изпразваме string – a където държим редичката си.

ВАЖНО: Този алгоритъм работи, но НЕ е ефективен. Вижте форума на Академията за решения с динамично оптимиране.

Задача 17.* Write a program that reads three integer numbers N, K and S and an array of N elements from the console. Find in the array a subset of K elements that have sum S or indicate about its absence.

Решение: PasteBin

Обяснение:

Основата на задачата е аналогична с тази от 16та. Основаните разлики тук са – от входа взимаме дължината на желаната редичка, правим си още една променлива, която да пази дължината на текущата редичка и само тогава когато тези 2 променливи съвпадат, принтираме редичката си.

Задача 18.* Write a program that reads an array of integers and removes from it a minimal number of elements in such way that the remaining array is sorted in increasing order. Print the remaining sorted array. Example:

{6, 1, 4, 3, 0, 3, 6, 4, 5} -> {1, 3, 3, 4, 5}

Решение: PasteBin

Обяснение: И отново използвам основната логика от 16 задача за да намеря най-дългата нарастваща редица.

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

Задача 20.Write a program that reads two numbers N and K and generates all the variations of K elements from the set [1..N]. Example:

N = 3, K = 2 -> {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}

Решение: PasteBin

Обяснение: Стандартно рекурсивно решение на проблема. Ето графично представяне на извикването на метода VariationsGen(int[] array, int index, int N). Червените методи са дъното на рекурсията.

Arrays.20.variatons

21.Write a program that reads two numbers N and K and generates all the combinations of K distinct elements from the set [1..N]. Example:

N = 5, K = 2 à {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}

Решение: PasteBin

Обяснение: Използвам подхода за генериране на комбинациите от 16та задача. Ако имате време бих ви препоръчал да пробвате да направите рекурсивно решение на задачата 🙂

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