Здравейте,
Опитах се да направя тази задача, но не мога да се оправя. Може ли малко по- подробно някой да ми разясни какъв алгоритъм се изпозва и как действа точно и евентуално да го видя инплементиран в код.
Предварително благодаря!
Moже да кажеш в кое домашно е по-точно.
Това е как аз написах въпросната задача, добавих няколко коментара на бързо, за да можеш да се ориентираш по - лесно, но не съм се впускал в обяснения. Ще се радвам ако съм помогнал по някакъв начин. В случай, че нещо не ти е ясно питай.
Успех!!!
Благодаря ти.
Сега с тази ракурсия ще си запълня уикенда да разбера как става и по този начин :)
Здравей, вчера и аз седнах да я решавам и стигнах до следното решение:
https://gist.github.com/vdonchev/cac01645621b007769c6
Ето това видео ми помогна много да разбера колко и как се формират всички субсетове на сет.
https://www.youtube.com/watch?v=s8FGAclojcs
От горното видео разбрах че даден сет S има точно 2 на степен броя на елементите в S (като това включва и нулевия субсет) субсетове.
Тоест Set{ 1, 2, 3 } има точно 2 на степен 3 субсета (8) и те са:
{,,} {,,3} {,2,} {1,,} {1,2,} {1,,3} {,2,3} {1,2,3}
Относно самото генериране използвах побитова маска, както беше подсказано в условието на домашното.
за създаване на маската въртиш един цикъл до броя на всички субсетове и проверяваш за всяко число къде бита е сетнат, и където е добавяш този елемент от колекцията (суперсета)
Пример със сета 1,2,3:
Цикъл до 8 побитово би изглеждал така:
000 // {,,}
001 // {,,3}
010 // {,2,}
011 // {,2,3}
100 // {1,,}
101 // {1,,3}
110 // {1,2,}
111 // {1,2,3}
А ето и решението на "SortedSubsetSums":
https://gist.github.com/vdonchev/9fb95d82e0defd85d5bb
Надявам се да ме разбереш , че май малко объркно го обясних.
Поздрави!
Благодаря за обянението!
Нещата вече съвсем се изясниха. Трябваше ми съвсем малко за да навържа нещата ,че бях зациклил :)Свързах началото на видеото на телерик
https://www.youtube.com/watch?v=ZVH26zL8WXQ
с част от твоето обяснение и се получиха нещата. Като се прибера с удоволствие ще си реша тази задача.
Видях, че местиш mask bit пъти и после & 1, аз по-скоро си мисля да преместя 1 bit пъти и после & mask, коеото е напълно аналогично, но в главата ми е по разбираемо някак си.
Поздрави!
Колеги, някой може ли да отдели малко от времето си и да ми обясни как се решава тази задача побитово. От 3 дена се опитвам да измисля мой алгоритъм за решението и накрая се отказах. Разбрах, че единственото решение е побитово или рекурсия, но предпочитам да я разбера побитово сега. Четох обясненията по-долу и тръгнах да гледам обяснението на задачата от Телерик, но за съжаление видеото е прецакано и не мога да схвана какво става. Ще съм много благодарен ако някой ми я обясни по Skype задачата.
Ами побитовотоо решение е следното:
За видиш кои подмножества правят определена сума, то в общия случай (ако сметнем, че не си оптимирал нещо) трябва да минеш през всички подмножества.
при множеството {1, -1, 2} възможните подмножества са
{ } празно множество
{ 1 } елемент на позиция [0]
{ -1 } елемент на позиция [1]
{ 2 } елемент па позиция [2]
{ 1, -1 } елементи на позиция [0, 1]
{ 1, 2 } елементи на позиция [0, 2]
{ 1, -1, 2 } елементи на позиция [0, 1, 2]
{-1. 2 } елементи на позиция [1. 2]
Както можем да видим това са 8 (осем) възможности от множество от 3 (три) елемента. Или иначе казано това е 2 на степен 3 (елемента) = 8. Елементите винаги може да са различни, затова ще приемем, че това са N елемента. Можем сейфли да кажем, че комбинациите са 2^N. (2^3 в конкретния случай).
Ако погледнем всички числа от 0 (inclusive) до 8 (exclusive, т.е. до 7). в двоична бройна система те са:
0 => 00000000
1 => 00000001
2 => 00000010
3 => 00000011
4 => 00000100
5 => 00000101
6 => 00000110
7 => 00000111
Ако погледнем оцветените единици в двоичната репрезентация, можем да видим, че те перфектно пасват на това кои елементи правят комбинацията от подмножества. При числото 0 това е празното множество, защото няма елементи. При числото 1, има единица само на нулева позиция т.е. [0]. При числото 2 има единица на 1ва позиция т.е. [1]. При 3 има единица на нулева и първа позиция т.е. [0,1]. При 4 - на втора позиция т.е. [2]. При пет на нулева и втора .е. [0, 2]. При шест на първа и втора т.е. [1,2] и при 7 на нулева, първа и втора т.е. [0,1,2]
Т.е. това което трябва да направиш е да завъртиш цикъл от 0 до 2^N и за всяко число в интервала 0...7 да намериш единиците на кои позиции са, после да сумираш елементите в множеството на тези позиции и да видиш дали правят 0.
Let Set = {1, -1, 2}
for K = 0; K < 2^Set.Length; K++
Let M = K in Binary
Let P = Масив от позициите, на които има единици в M
Let Sum = 0
for Pos in P
Sum += Set[Pos]
if Sum == 0 (или каквато е търсената сума) => Print("подможеството с позиции {P} отговаря на условието")
Като че ли зацепих малко, ама не точно. Например в задачата е даден следният пример: 0 11 1 10 5 6 3 4 7 2, което ако го представя по твоя начин в битове ще изглежда така:
0 => 00000000
1 => 00000001
2 => 00000010
3 => 00000011
4 => 00000100
5 => 00000101
6 => 00000110
7 => 00000111
10 => 00001010
11 => 00001011
Забелязвам примерно, че комбинации от числа като:
1 + 10 = 11
1 => 00000001
10 => 00001010
ако ги съберем с побитово § ще се получат битове колкото на числото 11:
11 => 00001011
Но при други числа като 5 и 6 примерно това не се получава:
5 => 00000101
6 => 00000110
11 => 00001011
Както и при 1 + 2 + 3 + 5 и т.н.
Или побитово трябва да представя всички комбинации на 2^10? Като не ми става ясно ако е така, защо е така при положение, че ще включва много числа, които ние ги нямаме в началния input...
Което означава, че все още не съм разбрал напълно смисълът на задачата :( Ако можеш да отделиш 15мин на Скайп мисля, че на живо ще стане по-лесно и бързо, тъй като ще можем да обсъждаме на момента.
Благодаря!
Ако искаш ми пиши в някой от месинджърите, които съм оставил. Само не и скайп, че е пълна боза последните месеци. Малко съм болен и не ми се говори, по-скоро бих писал.
Има две неща, които не си разбрал от обяснението:
1. Битовите репрезентират позиции в масива, а не числа. Това което трябва да направиш е да вземеш позициите на които са единиците и това де факто са позиции в масива. После събираш на тези позиции масива с обикновен плюс и гледаш дали правят желаната сума, например 0
2. Комбинациите от подмножества в едно множество са точно 2 на N (2^N), където N е броят числа в множеството. Ако числата са 10, то това е 2 на 10та.
Побитовите репрезентации ти дават ВСИЧКИ подмножества. Не ти дават наготово множествата, които дават тази сума. Ти трябва да ги опиташ всичките и да видиш кое от тях дава желаната сума.
Advanced C# ,Homework: Arrays, Lists, Stacks, Queues
Това е моето решение, беше си малко тегава задача и изисква малко математика. Надявам се да можеш да го разбереш, особено този трик с побитовата операция.
https://github.com/DiyanTonchev/SoftUni/blob/master/C%23/CSharpAdvanced/Homeworks/Arrays-Lists-Stacks-Queues/06.SubsetSums/SubsetSums.cs
Благодаря колега!