Софтуерно Инженерство
Loading...
+ Нов въпрос
djc_bg2015 avatar djc_bg2015 922 Точки

[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
djc_bg2015 avatar djc_bg2015 922 Точки

Браво!

Видях че в книгата Въведение в програмираноето, е подсказано че с бфс става. Аз лично преди да прочета, не се сетих, че може да се реши така, и ми се въртяха разни други неща в галвата. :)

0
lina94 avatar lina94 1 Точки

Здравей, колега!

 

Тъй като нещо го закъсах с 3та задача за longest subsequence, си позволих да ти разгледам решението и да взаимствам някои неща :) Много ми хареса идеята със Skip и Take.

 

Докато тествах, обаче, открих, че при някои входни данни, програмата връща грешен резултат:

вход: 1 2 2 1
резултат: 1 2

вход: 1 2 3 3 1
резултат: 1 2

вход: 1 4 4 2 1
резултат: 1 4

 

След малко дебъгване мисля, че виждам грешката. Във вътрешния цикъл трябва да имаш следното:

for (int j = i + 1; j < nums.Count; j++)
{
    if (nums[j] == currentNum)
    {
        currentLongestCount++;
    }
    else
    {
        break;
    }

}

за да може да излизаш от цикъла, когато числото не е равно на предишното, защото иначе ще сравняваш 3тото с 1вото, 4тото с 1вото и т.н.

Поздрави!

1
djc_bg2015 avatar djc_bg2015 922 Точки

Мдаа, забравил съм брейка, честно да ти кажа до 5 задачка ги написах на бързо и не съм тествал с данни различни от тези от файла.

Фикснах бъга в кода от гитхъб.

0
20/02/2016 18:27:22
Kiril98 avatar Kiril98 66 Точки

Ето и моето решение на 8ма пак със BFS => тук

Малко ми помогна един приятел от телерик :)

ПС: Забравих и класа Cell, който не е нищо сложно => тук

 

1
21/02/2016 22:02:01
iivanov2 avatar iivanov2 10 Точки

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

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

Write a program to test whether the method works correctly.

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

 

0
djc_bg2015 avatar djc_bg2015 922 Точки

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

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

Поздрави!

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

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

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
mishomihaylov avatar mishomihaylov 67 Точки

Хора имам един проблем при Remove на 6та задача. Поглеждаики и вашите задачи, не успях да намеря решението му. Проблема е следния:
Когато махнеш 5 елемента(с for цикъл) от ReversedList не се махат първите 5 елемента. Примерно имаш елементите 10 9 8 7 6 5 4 3 2 1 (съдържащи се в масива в този ред). След for цикъл с 5 итерации (започващ от 0) резултатът е 9 7 5 3 1. Реално по условие това е вярно поведение, но предвид, че примерно при List поведението би било да махне първите 5 как бихме могли да го направим и тук? 

0
24/02/2016 16:03:10
djc_bg2015 avatar djc_bg2015 922 Точки

Здравей,

ако добавим 10 елемента в листа [0-9] как ги пазим вътрешно, няма значение, но ако някой ги поиска с форийч например трябва да върнем: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

и след това ако изтрием първите 5, трябва да имаме следните елементи и индекси:

[0] 4

[1] 3

[2] 2

[3] 1

[4] 0

Защо по условие това да е вярно: След for цикъл с 5 итерации (започващ от 0) резултатът е 9 7 5 3 1 ?

 

0
mishomihaylov avatar mishomihaylov 67 Точки

Ами защото когато подходим с for цикъл махаме първо 0-левия елемент, а в структурата ни автоматично 1-вия става нулев. После когато i се инкрементне, реално вземаме 3тия елемент. Ще дам пример:

Имаме масив с числа 1 2 3 4 5
For i = 0 -> трием елемента на индекс 0, при всички елементи в масива се местят с позиция на долу 
като в този случай масивът става: 2(0), 3(1), 4(2), 5(3)
Когато i се инкрементне то става 1 и взима числото 3 и го трие и по този начин прескача.

По условие това е вярно, защото ти се иска да направиш метод, който трие елемент на дадена позиция. Но когато го използваме във for цикъл имаме различен от очаквания резултат, което аз лично бих искал да разбера как да коригирам.

Тествах също и твоя код, резултатът е същия. Пробвай, ако все още не си разбира се.

ПП: Елегантно решение за Remove() btw

0
24/02/2016 16:19:07
djc_bg2015 avatar djc_bg2015 922 Точки

Ами не мисля, че интерпретираш правилно условието.

Определено не е коректно поведение да модифицираш колекцията докато я итерираш.

Ето какво мисля аз , че е коректно да се случва:

            var reversedList = new ReversedList<int>();
            reversedList.Add(0);
            reversedList.Add(1);
            reversedList.Add(2);
            reversedList.Add(3);
            reversedList.Add(4);

            for (int i = 0; i < reversedList.Count; i++)
            {
                Console.Write(reversedList[i]); // Трябва да върне: [4, 3, 2, 1, 0]
            }

            for (int i = 0; i < reversedList.Count / 2; i++)
            {
                reversedList.Remove(i); // Трябва да изтрие: [4, 3] - остават [2, 1, 0]
            }

Вътрешно как ще имплементираш тази логика си е твоя работа. Аз лично пазя всички елементи в правилен ред, и само когато се поиска някво действие свързано с индексите, викам метод който ми калкулра кой е правилни ревърснат индекс.

 

Поздрави!

0