Професионална програма
Loading...
djc_bg2015 avatar djc_bg2015 923 Точки

[Homework] Linear Data Structures Lists - Февруари 2016

Здравейте колеги, споделям моите решения  на задачите от домашното.

https://github.com/vdonchev/LinearDataStructures-Lists-Homework

На 6 и 7 задача написах някой друг юнит тест, от 1 до 5 съм използвал само листове а 8ма я реших с BFS.

Тагове:
3
Структури от данни и алгоритми 24/02/2016 12:56:45
iivanov2 avatar iivanov2 10 Точки

За 3-ти проблем не си написал програма, която да тества метода ти LongestSubsequence

В условието се казва:

Write a program to test whether the method works correctly.

Това не ми е ясно как трябва да се подходи.

 

0
djc_bg2015 avatar djc_bg2015 923 Точки

Ами с юнит тестове трябва да стане (поредното нещо, което съм проспал в условието),

сега ще напиша и ще ги кача в гитхъб.

Поздрави!

0
24/02/2016 08:09:28
djc_bg2015 avatar djc_bg2015 923 Точки

Тестовете са готови, може да ги видиш тук:

https://github.com/vdonchev/LinearDataStructures-Lists-Homework/blob/master/03.LongestSubsequence.Tests/LongestSubsequenceTests.cs

Относно това, как се пишат UNIT тестове, може да научиш повече от лекциите на Наско и Иван от курса по качествен програмен код:

https://softuni.bg/trainings/1286/high-quality-code-december-2015 (Компонентно тестване).

 

С две думи, прави се нов проект от тип Unit Test Project. Реферира се проекта чиито методи и класове ще тестваш и се пишат тест методи, които тестват функционалността.

Поздрави!

 

0
mishomihaylov avatar mishomihaylov 67 Точки

Не е нужно да се правят Unit тестове макар, че е силно препорачително. В условието има да се напише метод и после програма с която да тестваме. Реално можеш да тестваш метода в main(), резултатът е същия.

0
djc_bg2015 avatar djc_bg2015 923 Точки

Съгласен съм с теб :)

Но не пречи и с методчета в мейна да се направи

0
iivanov2 avatar iivanov2 10 Точки

Не ми харесва четвъртата ти задача направил си алгоритъма със сложност O(n*n) експоненциална сложност, а би могло да е линейна O(2*n)

0
djc_bg2015 avatar djc_bg2015 923 Точки

Варианти много, сетих се за първия и го направих.

Сподели твоето решение, да погледна как си подходил.

Поздрави

0
iivanov2 avatar iivanov2 10 Точки

    Получавам линейна сложност около 5n, прав си че има различни варианти, но нали трябва да избягваме експоненциалните алгоритми, това повтарят постоянно  на  лекциите.

    static void Main(string[] args)
        {
            Console.Write("Enter your string:\n");
            String str1 = Console.ReadLine();

            String[] strNums = str1.Split(' ');

            int[] nums = Array.ConvertAll<string, int>(strNums, int.Parse);

            int biggestNum = 0;
            int counter1 = 0;
            foreach(int item in nums)
            {
                if(item > biggestNum)
                {
                    biggestNum = item;
                }
                counter1++;
            }

            bool[] numbers = new bool[biggestNum+1]; //false default;flase means even or 0
            foreach (int item in nums)
            {
                if(numbers[item]==false) 
                {
                    numbers[item] = true;
                }
                else
                {
                    numbers[item] = false;
                }
            }

            foreach (int item in nums)
            {
                if (numbers[item] != true)
                {
                    Console.Write(item + " ");
                }

            }

            //keep console opened
            Console.ReadLine();
        }

0
26/02/2016 18:16:25
djc_bg2015 avatar djc_bg2015 923 Точки

Браво, интересно решение. Ще помисля и аз за нещо по оптимизирано и ако ми хрумне ще постна тук.

Поздрави

0
Filkolev avatar Filkolev 4482 Точки

За да бъдем коректни - O(n^2) е квадратична сложност, не експоненциална. Също така при смятане на асимптотична сложност константите се игнорират - О(n) е единственото, което има смисъл, дали е 2n или 3n е без значение. Идеята на такъв тип анализ е да се направи бърза преценка какво е поведението на даден алгоритъм.

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

2