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

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та задача. Ако имате време бих ви препоръчал да пробвате да направите рекурсивно решение на задачата 🙂

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

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# от 2011/2012


Тук ще поместя линкове към условията и моите решения на задачите от C# Fundamentals 2011/2012 Part 1 – Sample Exam . Не претендирам, че решенията ми са най-оптимални, те дават 100/100 в системата BGCoder.

Условията на задачите може да намерите тук:
BGCoder или в Студетската Система на Телерик

Ето и решенията:
Task 1 – Cartesian Coordinate System: Цък
Task 2 – Miss Cat 2011: Цък
Task 3 – Forest Road: Цък
Task 4 – Binary Digits Count: Цък
Task 5 – Subset Sums: Цък

Забележки:
1. В 2 и 5-та задача съм използвал масиви за улеснение. Задачата е напълно възможно да се реше и без тях просто няма да е толкова компактно.
2. Макар, че в задача 3та съм използвал цикли за рисуване по конзолата, по-ефективен начин е: new string () . Ако не знаете как работи ви препоръчвам с 2 ръце, да разберете. Помага много !

Решения на задачите за домашна от лекцията за Цикли

Ето решенията ми на задачите от оследната лекция от Част 1 за програмиране на C# – Цикли.

Условията:
1. Write a program that prints all the numbers from 1 to N.
2. Write a program that prints all the numbers from 1 to N, that are not divisible by 3 and 7 at the same time.
3. Write a program that reads from the console a sequence of N integer numbers and returns the minimal and maximal of them.
4. Write a program that calculates N!/K! for given N and K (1<N<K).
5. Write a program that calculates N!*K! / (K-N)! for given N and K (1<N<K).
6. Write a program that, for a given two integer numbers N and X, calculates the sum S = 1 + 1!/X + 2!/X2 + … + N!/XN
7. Write a program that reads a number N and calculates the sum of the first N members of the sequence of Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …
Each member of the Fibonacci sequence (except the first two) is a sum of the previous two members.
8. Write a program that calculates the greatest common divisor (GCD) of given two numbers. Use the Euclidean algorithm (find it in Internet).
9. In the combinatorial mathematics, the Catalan numbers are calculated by the following formula:

Write a program to calculate the Nth Catalan number by given N.
10. Write a program that prints all possible cards from a standard deck of 52 cards (without jokers). The cards should be printed with their English names. Use nested for loops and switch-case.
11. Write a program that reads from the console a positive integer number N (N < 20) and outputs a matrix like the following:
N = 3 | N = 4
1 2 3 | 1 2 3 4
2 3 4 | 2 3 4 5
3 4 5 | 3 4 5 6
| 4 5 6 7
12. * Write a program1 that calculates for given N how many trailing zeros present at the end of the number N!. Examples:
N = 10  N! = 3628800  2
N = 20  N! = 2432902008176640000  4
Does your program work for N = 50 000?
Hint: The trailing zeros in N! are equal to the number of its prime divisors of value 5. Think why!
13. * Write a program that reads a positive integer number N (N < 20) from console and outputs in the console the numbers 1 … N numbers arranged as a spiral.
Example for N = 4
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

Ето линк към решенията:


П.С. Задачите с факториел стават доста лесни ако изнесете логиката в метод 🙂

Решения на задачите от лекцията – Условни конструкции

Решенията ми на задачите от тази лекция.
Ето условията:
1. Write an if statement that examines two integer variables and exchanges their values if the first one is greater than the second one.
2. Write a program that shows the sign (+ or -) of the product of three real numbers without calculating it. Use a sequence of if statements.
3. Write a program that finds the biggest of three integers using nested if statements.
4. Sort 3 real values in descending order using nested if statements.
5. Write program that asks for a digit and depending on the input shows the name of that digit (in English) using a switch statement.
6. Write a program that enters the coefficients a, b and c of a quadratic equation
a*x2 + b*x + c = 0
and calculates and prints its real roots. Note that quadratic equations may have 0, 1 or 2 real roots.
7. Write a program that finds the greatest of given 5 variables.
8. Write a program that, depending on the user’s choice inputs int, double or string variable. If the variable is integer or double, increases it with 1. If the variable is string, appends “*” at its end. The program must show the value of that variable as a console output. Use switch statement.
9. We are given 5 integer numbers. Write a program that checks if the sum of some subset of them is 0. Example: 3, -2, 1, 1, 8  1+1-2=0.
10. Write a program that applies bonus scores to given scores in the range [1..9]. The program reads a digit as an input. If the digit is between 1 and 3, the program multiplies it by 10; if it is between 4 and 6, multiplies it by 100; if it is between 7 and 9, multiplies it by 1000. If it is zero or if the value is not a digit, the program must report an error.
Use a switch statement and at the end print the calculated new value in the console.
11. * Write a program that converts a number in the range [0…999] to a text corresponding to its English pronunciation. Examples:
0  “Zero”
273  “Two hundred seventy three”
400  “Four hundred”
501  “Five hundred and one”
711  “Seven hundred and eleven”

Ето и линк към решенията:


П.С. Последната задача ( 11-та ) е доста интересна, не толкова сложна колкото, доста обемна за писане. Лично успях да я съкратя с досата с масиви, но е напълно възможно да се нарпави и с условни конструкции + switch.