Loading...
Xzahn avatar Xzahn 34 Точки

[Homework] Programming Basics - Conditional Statements - Problem {12} - ZeroSubset

Здравейте,

Започнах да решавам задачата по ТОЗИ начин, обаче вече изключих напълно и не мога да доизмисля. Знам, че има други решения, но искам да я завърша така като съм я започнал, ако е възможно разбира се. Затова не искам да използвам побитови операции или Linq. Възможно ли е да се реши така и ако може, какво ми липсва?

В момента проверява само част от подмножествата, като при {3, -2, 1, 1, 8} няма да изведе {-2, 1, 1}. Няма да ги намери и ако са в края.

П.С. Четвъртия цикъл е грешен и няма да изведе множествата правилно (беше за предишна версия на програмата и забравих да ги оправя).       

0
Programming Basics 19/07/2015 22:11:01
tilchev92 avatar tilchev92 Trainer 128 Точки

Ако разбирам правилно идеята ти, за да работи ще ти трябват няколко поредици с няколко вложени for-a всяка (зависимост от колко числа се образува множеството, т.е. 2, 3, 4 и 5) и отделна проверка за нулите. Нещо такова

Това не е мое решение, взех го от форума. Не съм го тествал, но предполагам нещо такова се опитваш да направиш и мисля, че може да ти е от полза.

1
19/07/2015 23:13:25
TonislavAtanasov avatar TonislavAtanasov 86 Точки

Тази задача можеш да я решиш и с помощта на битове. В конкретния случай, за да намериш всички под-множества, чиито сбор е 0, трябва да намериш всички под-множества, които се състоят от 1 число (те са 5 в случая), всички под-множества от 2 числа, от 3, 4 и 5 (от 5 е само едно под-множество). Пример с 3 числа (1,2,3):

Под-множества на множеството [1, 2, 3], всяко множество е в [ ]

Празно множество: [ ]

От едно число: [1] [2] [3]

От две числа: [1, 2] [1, 3] [2, 3]

Oт три числа: [1, 2, 3]

Ето горе-долу какво можеш да опиташ:

1. Броят на комбинациите между n на брой числа е 2^n (^ = степен). В този случай са 32 (2 на 5-та). Хинт: Пусни си един цикъл от 0 до 32 и отпечатай всички числа в двоичен вид. Разгледай къде са единиците в числата. Веднага ще се сетиш, че това са всички комбинации, които ти трябват.

2. Пускаш един цикъл от 1 до броя на комбинациите (без включително) и на всяка итерация събираш числата, които се намират на индекс в масива, който съответства на индекса на битовете със стойност 1 в итератора. Това ще рече, че ти трябва вложен цикъл, който да обхожда битовете на всяка стойност на итератора и да проверява къде те имат стойност 1. 

Пример: В цикъла си дефинираш променлива, която да е равна на итератора на външния цикъл (да кажем int index = i;) Така на всяко завъртане тя ще се инициализира наново с коректната стойност. После правиш вътрешен цикъл, който е от 0 до 32 (за да обходиш битовете) и проверяваш каква им е стойността. Ако стойността на съответния бит е 1 към текущата сума добавяш numbers[currentBitPosition]. Нещо такова (във вътрешния цикъл, да кажем че итераторът там е currentBitPosition): 

if (index & 1 == 1) { currentSum += numbers[currentBitPosition]; index >>= 1; } //на един ред е само за да спестя място

После проверяваш дали стойността на това под-множество е 0 и ако е нула отпечатваш числата на съответните индекси от масива в какъвто формат ти трябва.

Хинт: Ако започнеш от 0 ще включиш и празното множество и това може да ти създаде проблем, тъй като при него сумата ще е 0, a всъщност не включва никакви числа.

Пример: На първото завъртане итераторът е със стойност 1, значи това ни е едно под-множество от 1 число, което е със стойност равна на стойността на числото на нулевия индекс в масива (1 в двоичен вид). На 5-тото завъртане стойността на итератора е 5 (не забравяй, че в този случай броим от 1). 5 в двоичен вид е 101, т.е. от масива с числата събираме тези на индекс 0 и индекс 2 и това ни е едно под-множество от две числа и т.н.

Ако пък много забиеш: http://pastebin.com/Had1qkUi (имай предвид, че съм го писал без .NET и Visual Studio и може да има някоя грешка. Но логиката би тярбвало да е вярна. Дебъгни го ако се наложи и донагласи нещата.

Поздрави!

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