[C#] Arrays - 17 задача


3

Условие:

17. * Write a program that reads three integer numbers N, K and S and an array of N elements from the console. Find in the array a subset of K elements that have sum S or indicate about its absence.

Мое решение:

http://pastebin.com/cuDGR5Ae




Отговори



0

Аналогично на задача 16 като ако е достигната търсената сума се проверява броя на множителите и ако броя не отговаря на зададения се продължава да се търси друга комбинация от множители
http://pastebin.com/igTSaHxA


от AsenVal (3487 точки)


0

Казах си, че ако този код проработи, ще го публикувам, за да натрупам градивна критика :)))

http://pastebin.com/Km70Cs2B


от vanina_nenova (327 точки)


0
В книгата на Наков 19 глава има раздел "Генериране на подмножества" реализирано с опашка:
http://www.introprogramming.info/intro-csharp-book/read-online/glava19-strukturi-ot-danni-supostavka-i-preporuki/
Остава само да проверим дали броя на елементите е К и дали сумата е търсената:
http://pastebin.com/p9zyY87u

от neofitov (235 точки)


0

Source

подслучай на 16-та задача - тук търся само комбинациите от K елемента.


от Rokata (397 точки)


0

http://pastebin.com/egWWuM1f

Основното решение е като от 16 задача:

Отново генеритаме (в случая побитово) всични комбинации от еденици и нули,

там където имаме единица, използваме съответното число от масива и така правим всички възможни комбинации на числата които имаме.

Разликата е че в крайния изход принтираме решение, само ако има сума от К зададени  брой елементи.

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

http://www.youtube.com/watch?v=Sk0PX0YSHtk


от stanev.plamen (1143 точки)


0
Към тези които слагат флагове: 1. Бихте ли си обосновали флага. 2. Погледанали ли сте там където насочвам в поста. 3. Задавате ли си въпроса защо е този коментар Ако е Да и има проблем, моля за критика а не флаг !!!

от stanev.plamen (1143 точки)

0
Колега, дават ви флагове, защото не се съобразявате с правилата: http://forums.academy.telerik.com//15664 Препоръчвам ви да ги прочетете т.к. ако не редактирате поста си, ще се наложи да го скрия.

от Teodor92 (13062 точки)



0

Едно питане към миналите тази задачка 17.

Гледам, че ползвалите решението с битове слагат ограничение на първи цикъл. Примерно:

int maxSubsets = (int)Math.Pow(2, numberOfElements); - това е от кода на Ивайло Кенов

Ако сложа за K = 3, за N = 4, SUM = 40, array {10, 40, 20, 30}

Тогава броя на комбинациите не се ли изчислява по друга формула http://en.wikipedia.org/wiki/Combination, защото броя им е един при минимум 2 елемента и друг при минимум 3 елемента.

Кое се ползва това:

1. int maxSubsets = (int)Math.Pow(2, numberOfElements);

или

2. int maxSubsets = (int)Math.Pow(K, N);

или

3. Формулата за комбинации.

или

4. В яко заблуждение съм ползва се нещо друго...

 


от deyan.todorov (1019 точки)


0
Струва ми се, че не си схванал съвсем идеята защо до 2 на степен н-1. Пример: Ако редицата ти е от 3 числа, по принцип възможностите ти за суми са всички комбинации измежду 3 числа. Числото ((2 на степен 3) - 1) = 7. Седем в двоичен вид е "111". С други думи, всяко число от 1 до 7 включително, е една възможна комбинация и числата от 1 до 7 изчерпват всички възможни комбинации измежду три бита - едно е "001", две е "010", три е "011" и т.н. Ти въртиш цикъла от 1 до 7 и на всеки бит от първите три, ако е единица, взимаш съотетното число от редицата ти и го добавяш към сумата. Остава ти само проверка дали сумата е равна на тази, която се търси, и дали броя на сумираните числа е равен на к. :)

от varbanoff (2325 точки)

0
Не ми стана ясно защо е 2 на степен нещо си.
Защото проверката е в двоична бройна с-ма или нещо друго?!
Мислех си, че щом говорим за комбинация от минимум 3 числа (примерно) не ме интересуват суми от 2 числа или 1 число.
Т.е. няма нужда да ги проверявам всичките. Гледам примерчета тук http://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html
И по тяхната формула 3 числа и 3 търсени, които могат да се повтарят и реда няма значение са 10 комбинации.

от deyan.todorov (1019 точки)


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



0
Колега, вижте датата на темата и вижте кога е въведено даденото правило, няма как да наказвам теми, появили се преди да бъде въведено дадено правило.

от Teodor92 (13062 точки)

0
Явно съм недогледал, извинявам се :)



0

GitHub

Доста прилича на предната задача, но тук вектора е винаги с определен от нас (К) размер. Чрез помощен масив от bool елементи пазим кои числа сме използвали и генерираме чрез рекурсия всички възможни комбинации от К елемента от елементите от масива. Като сме готови проверяваме дали сбора на елементите им дава търсената от нас сума. Ако не - наново. Понеже ако се намери комбинация която дава търсената сума прекратявам приложението с Environment.Exit(0); съм поставил и едно редче че няма такава сума на края на програмата - ако се стигне до този ред значи наистина няма такава комбинация.


от dzhenko (3893 точки)


0

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


от stambeto09 (425 точки)


0
Колега, връзката ти не е към 17-та задача, а към 1-ва от същото домашно. :)

от Tanya (202 точки)


0

 Здравейте. Снощи 3 часа си блъсках главата да схвана това решение на колега - http://pastebin.com/XEgppsN7

Като цяло го разбрах освен най-важното - какво правят в случая побитовите операции?

 Доколкото разбирам, идеята на решението е да се намерят всички възможни комбинации от елементи, взети от нашия масив. После се пресява кои от тези комбинации имат сумата която търсим, и броя членове, които сме задали. И се печатат тези комбинации

 Но не схващам, как проверката дали числото I има единица на позиция J, помага за определене на комбинациите...


от ivan.mihov1 (4988 точки)


0
Там където имаш единица вземаш това число от масива, което се намира на същия индекс като единицата и правиш сума. Така ако имаш три числа arr = [a, b, c]; arr[0] = a, arr[1] = b, arr[2] = c, възможните суми са: 001(а), 010(b), 011(a + b), 100(c), 110(c + b), 111(a +b +c), където 001, 010 не са индекси от масива а просто числа, които показват коя поред е тази комбинация и кои числа от масива трябва да вземем и кои не. ЕДИТ: Виж сега дали е по-ясно.

от anilak (1134 точки)

0
Отговорът ти ми помогна, но още ми се губи парченце.
Значи всеки от индексите го представяме двоично, и за всеки индекс започваме нова поредица. В битовете на индекса, където имаме единица, вземаме числото на тази позиция от масива и го добавяме към поредицата, отговаряща на съответния индекс...

от ivan.mihov1 (4988 точки)