Loading...
KatyaMarincheva avatar KatyaMarincheva 572 Точки

[Homework] Advanced C# - Arrays, Lists, Stacks, Queues - Problem {7} *Sorted Subset Sums

Здравейте, колеги :)

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

Това е решението ми: https://github.com/KatyaMarincheva/SoftUni/blob/master/SoftUni-Homeworks/Advanced%20C%23/01.%20Arrays-Lists-Stacks-Queues-Homework/07.%20Sorted-Subset-Sums/SortedSubsetSums.cs

Благодаря предварително :)

Тагове:
9
C# Advanced 07/05/2015 23:18:45
Filkolev avatar Filkolev 4482 Точки
Best Answer

Здравей,

Първо поздравления за добре структурираното (отново) решение :) 

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

  • Принтирането може да стане със string.Join(), така няма да мислиш какви са размерите и къде какво да сложиш.
  • Смятането на сума в колекция може да стане с LINQ - .Sum().
  • Зачистването на повтарящи се сетове може да стане в началото като се елиминират повтарящите се елементи в подадения масив. Така се спестяват и малко ненужни итерации.

Задачата е със звезда, понеже изисква малко повече работа с функционално програмиране. Алтернативата е n на брой цикли и доста по-тежки сметки, иначе както виждаш не е кой знае колко сложна.

 

1
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Здравей Fil,

Страшно благодаря за съветите - веднага ще опитам да си направя ново оптимизирано решение :)

Какво имаш предвид под "добре структурираното (отново) решение"?

0
Filkolev avatar Filkolev 4482 Точки

Имам предвид, че решенията ти винаги са разбити на методи и подредени. По този начин доста лесно става ориентирането в кода, както и промените (например да замениш някой твой метод с вграден такъв, като .Sum()). На мен ми трябваше доста време да се отърва от навика да пиша задачите като един чаршаф отначало до край :D Но се надявам след ООП и КПК курсовете мнозинството колеги да пишат по подобен начин.

1
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Благодаря :)

Моят лош навик, от който още се опитвам да се отърва, е че в "една друга академия" ни забраняваха да използваме вградена функционалност, та оттам ми е останал този навик без да забележа дори за Sum() да използвам собствен метод..... Това беше и основната цел на въпроса ми - сигурна бях че пак съм включила излишен собствен метод.

0
04/05/2015 13:31:59
GogoK avatar GogoK 80 Точки

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

0
GalyaGeorgieva avatar GalyaGeorgieva 88 Точки

https://gist.github.com/alagalia/279df40c1a3a15abc2a3

Кате, това е моя вариант. Минава нулеви тестове. (макар, че съм използвала на едно място изтриване с \b), което в juge няма да мине.

Спокойна вечер от мен.

4
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Здравей Галя,

Мноого оригинално решение, особено побитовата част и сортирането на subsets.

Благодаря :)

0
EBojilova avatar EBojilova 330 Точки

Здравей Катя,

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

Относно оптимизацията- аз много обичам краткия код, че даже понякога и залитам в тази посока :) Празните редове ме разсейват и ги махам :) Ето го и оптимизирания от мен твой код:

https://gist.github.com/EBojilova/a564663f16d1af39848e 

Итерацията служи за дъно на рекурсията.

Печатам от метода. В книгата на Наков са дадени примери с печатане в метода, докато от други колеги съм чувала, че не е добре да се печата, но тепърва предстои да учим добри практики.

Премахвам повтарящите се числа още в началото. Поне така го разбирам по условие.

Резултата е същия, както преди да оптимизирам, така, че работи :), но е доста по-кратко. По-опитните колеги да кажат дали е ок.

Добавила съм 2 закоментирани реда, за да видя как работи рекурсията.

2
04/05/2015 20:04:29
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Здравей Елена,

Благодаря :)

Ето този пример за функционално програмиране (както го нарече Светлин Наков тази вечер на лекцията) много ми харесва:

 numbers = Console.ReadLine().Split(' ').Select(int.Parse).Distinct().ToArray();

и печатането също е мноооого хитро:

Console.WriteLine(" {0} = {1}", string.Join(" + ", subset), N);

За 6-та задача е необходимо точно това.

За 7-ма задача обаче май не можем да избегнем да пълним тези subsets в един List<List<int>> - за да ги сортираме по number of operands и после и по стойност на първия елемент.

    static List<List<int>> subsets = new List<List<int>>();

        var sorted = subsets.OrderBy(list => list.Count).ThenBy(list => list[0]);

И аз много искам да пиша кратък код, тъй че - страшно благодаря за идеите :)

0
05/05/2015 00:19:47
EBojilova avatar EBojilova 330 Точки

Аз съм решавала точно 6 задача :). Докaто съм скролвала домашното и на нея съм попаднала. От къде да предположа, че има 2 почти еднакви задачи :). Това ми подсказва, че трябва да седна вече и да напиша домашното.

Ето я и 7ма- сортирах числата в самото начало и после подреждах само по размер на листа преди разпечатване. Така се получи перфектно сортиране и по следващите числа.

https://gist.github.com/EBojilova/c307351703302abc668f 

Най-голямата трудност в тези задачи си е рекурсията :). Сега ще разгледам и как става с маска и побитово решаване на Галя. Подобна задача Longest Non Decreasing Sequence ме измъчи преди и единствено нея не я реших преди изпита. Сега ще пробвам да я реша и с рекурсия и с маката с побитово решаване.

1
05/05/2015 11:59:27
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Здравей пак Елена,

Наистина страхотно решение е станало - честно казано е бих се сетила че сортиран в началото list би дал сортирани subsets! И накрая сортираш само по subset.Count!

Наистина разбираш от кратки решения :)

 

0
malkstor avatar malkstor 348 Точки

Здравейте :)

Понеже задачи 6 и 7 са свързани, ще пиша направо тук за решението, което успях да напиша за 6-та задача. Направи ми впечатление коментара след примерите в заданието "Hint: Search how to generate subsets of elements with a bitwise mask.". Потърсих в нета и намерих това и по-точно - пример 7.

С негова помощ успях да подкарам задачата с доста по-малко редове. Лошото обаче е че все още не ми е много ясно как точно работи :D

Ето го и решението ми: http://pastebin.com/EZtQ6FAX

Сега се опитвам да го адаптирам за задача 7, но ще ми трябва още време да си изясня какво точно е и как работи Enumerable колекцията. Надявам се ще го учим по-късно в този курс.

5
Filkolev avatar Filkolev 4482 Точки

Enumerable ще се разгледа по-подробно в ООП курса. За момента просто може да смяташ, че това е колекция, която може да обхождаш с foreach.

По принцип методите от LINQ връщат подобни гадости, затова просто ползвай някой от методите ToArray() или ToList(), за да си превърнеш колекцията в нещо, с което знаеш как да боравиш.

4
Innos avatar Innos 419 Точки

Таман се чудех как може да се направи с LINQ тази задача, благодаря за линка колега. Седнах да чета Basic LINQ Query операциите -  интересна работа.

0
Inspix avatar Inspix 51 Точки

Здравей!

Eто и моето решение, различава се до някъде от всички други, а до колко е оптимално не зная, но направих няколко "тестове" , особено генерирането на subset по моя(странен) начин е доста по-бързо от колкото,ако ги гинерираме само с Linq. Там идва решението дали да напишем по-дълъг код, за да спечелим по-бързи резултати, или да го съкратим за сметка на performance-a :) (стига тестовете ми да не са кофти и да си въобразявам, че правя нещо като хората :D)

SortedSubsetSums

 
Поздрави!

2
09/05/2015 02:47:36
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Здравей Inspix,

наистина много интересен подход!

0
Filkolev avatar Filkolev 4482 Точки

На първо четене две препоръки:

(int)Math.Pow(2, numbers.Length) - това е хубаво да се изведе в променлива. Слагането като условие на цикъл не е оптимално, защото всеки път се смята наново.

Другото е, че за повдигне на степен на 2 няма нужда да се ползва Math.Pow, този израз е аналогичен на: 1 << numbers.Length. Ако си спомняш изместването веднъж наляво е еквивалентно на умножение по 2.

3
KatyaMarincheva avatar KatyaMarincheva 572 Точки

@Filkolev,

Така обяснено звучи гениално просто!

0
S.Iliev avatar S.Iliev 47 Точки

Здравейте,

 

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

Защо при печатане на изхода ми дава нули?

http://pastebin.com/P3Qsefxn

 

Благодаря предварително.

1
09/05/2015 13:24:31
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Здравей Светославе,

на този ред си взел инпут стринга и си го разцепил на масив от стрингове:

string[] arrayA = input.Split(' ');

На този ред обаче създаваш нов масив от числа и не пълниш нищо в него, само обявяваш, че ще има дължината на масива от стрингове arrayA, и понеже инициализираш масив, а не пълниш никакви стойности в него - всички негови елементи са равни на нула, затова ти печата нули:

int[] numbers = new int[arrayA.Length]

Вместо да използваш междинен масив, можеш да направиш това:

        string input = Console.ReadLine();
        int[] numbers = input.Split(' ').Select(int.Parse).ToArray();

обяснено на части в горния ред се случва следното:

input.Split(' ') // взема string input и го разцепва на масив от strings

.Select // взема всеки елемент от масива от strings за да го превърне в нещо друго, в друга форма

.Select(int.Parse) // означава че всеки string от масива от strings ще се превърне в число от тип int,

и всички получени числа ще образуват IEnumerable<int> - това е колекция от числа, но абстрактна, не е List, не е array - не е нищо конкретно и реално съществуващо, само абстрактна колекция от числа

.ToArray() // това превръща горната абстрактна колекция от числа в реално съществуващa, конкретна  колекция от числа - array

        int[] numbers = input.Split(' ').Select(int.Parse).ToArray();

Като цяло този ред е превърнал string input в масив от числа, който вече можеш да сортираш, печаташ и т.н.

Твърде нашироко го обясних - предполагам че празният ти масив е бил по-скоро резултат от разсеяност - т.е. предпоставка да станеш страхотен програмист :)

 

 

 

1
09/05/2015 14:28:00
S.Iliev avatar S.Iliev 47 Точки

Здравей Катя,

Ето това обяснение търсих доста време. С Bubble sort algorithm-a се запознахме и там ми стана ясно как сортира, но тези вградените функционалности все още ми бягат, а хелп-а на Майкрософт ме потриса. :D

Обяснението ти е страхотно.

 

Още веднъж Благодаря. 

1
09/05/2015 14:51:11
KatyaMarincheva avatar KatyaMarincheva 572 Точки

Хелп-а на Microsoft e "специален" - прав си :)

Но като имаш въпрос - казвай, и ще се справим :)

0
09/05/2015 16:19:54
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.