Loading...
achkata avatar achkata 17 Точки

[Homework] C# Conditional Statements {12} Zero Subset

Страхотна задача.

Ето, който иска да почете малко повече по въпроса.

http://en.wikipedia.org/wiki/Subset_sum_problem

Тук представям рекурсивно решение. Пропуснал съм частта с въвеждането на числата от конзолата, за 5-та седмица, предполагам това е тренирано вече от всички.

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

Ето рекурсивно решение : тук

Mod Edit: Моля, спазвайте правилата на форума.

 

Тагове:
2
Programming Basics 07/12/2014 17:16:39
HPetrov avatar HPetrov 822 Точки

Здравей колега. Интересно решение имаш, хареса ми :) Ето го и моето решение. Малко е мармалад кода ми се струва, но веднъж схване ли се логиката лесно се проследява. Очаквам критики!

0
achkata avatar achkata 17 Точки

Здравей,

В момента го гледам през телефона и ме съмнява , че има логическа грешка.

Няма как да го дебъгна в момента, но според това , което виждам :

int combinations = (int)Math.Pow(2, N);

.

.

.

for (int i = 1; i < combinations; i++)

Тук ти е до 2^N-1. Не успявам да видя, дали правиш нещо с останалата една комбинация.

 

0
HPetrov avatar HPetrov 822 Точки

По принцип кобинациите не са 32 ами 31, като целта е да се избегне случай, в който една от цифрите ти е всъщност желаната кобинация. В останалите 31 комбинации също влизат подобни случай но тях съм ги адресирал с една проверка за бройката на елементите в List накрая. Идеята е да се представят в броичен вид комбинациите и примерно комбинация 7 в броичен вид е 00111. Взимаме единиците и събираме числата на тези индекси и т.н. Не мисля, че ако всъщност си брой до 32 вместо до 31 ще ми даде грешно решение, но просто си преизползвам кода от решението на друг проблем :)

1
achkata avatar achkata 17 Точки

Тук вече е въпрос на преценка (или на условие).

Когато числото е равно на търсената сума, това пак си е subset с дължина 1-ца. Вече дали да влиза в решението си е въпрос на преценка.

1
aslv1 avatar aslv1 304 Точки

Между другото, задачата има много хитро решение.

В цикъл се завъртат числата от 1 до 25-1 и всяко едно се превръща в двоична бройна система.

Примерно, ако имаме числото 12 = 01100(2) проверяваме дали сумата на второто и третото число == 0. Ако имаме 15 = 01111(2), проверяваме дали сумата на второто, третото, четвъртото и петото число ==0.

Нали разбирате идеята? От представянето на всяко число правим такова подмножество, че където има 1, вземаме числото, а където няма - не го вземаме. Това гарантира, че ще изчерпим всички случаи и няма да пропуснем нито един.

П. П. Вижте тук - задача 5 от упражненията.

2
aslv1 avatar aslv1 304 Точки

Ето го и решението!

2
ZvetanIG avatar ZvetanIG 907 Точки

Само бих добавил, че взимането или прескачането на дадно число става много лесно. Просто умножаваме i-я бит с i-то число.

Когато бита е 0, числото няма да се взима предвид, когато бита е 1 - числото ще се взима предвид.

1
aslv1 avatar aslv1 304 Точки

Разбрах ти идеята.

Хитро!

0
YaneYo avatar YaneYo 40 Точки

Ето го и моето спартанско решение... :Р

 

using System;
class ZeroSubset
{
static void Main()
{
Console.WriteLine("Enter five integer numbers");

int a = int.Parse(Console.ReadLine());
int b = int.Parse(Console.ReadLine());
int c = int.Parse(Console.ReadLine());
int d = int.Parse(Console.ReadLine());
int e = int.Parse(Console.ReadLine());

if (a + b == 0)
Console.WriteLine("{0} + {1} = 0", a, b);
if (a + c == 0)
Console.WriteLine("{0} + {1} = 0", a, c);
if (a + d == 0)
Console.WriteLine("{0} + {1} = 0", a, d);
if (a + e == 0)
Console.WriteLine("{0} + {1} = 0", a, e);
if (b + c == 0)
Console.WriteLine("{0} + {1} = 0", b, c);
if (b + d == 0)
Console.WriteLine("{0} + {1} = 0", b, d);
if (b + e == 0)
Console.WriteLine("{0} + {1} = 0", b, e);
if (c + d == 0)
Console.WriteLine("{0} + {1} = 0", c, d);
if (c + e == 0)
Console.WriteLine("{0} + {1} = 0", c, e);
if (d + e == 0)
Console.WriteLine("{0} + {1} = 0", d, e);
if (a + b + c == 0)
Console.WriteLine("{0} + {1} + {2} = 0", a, b, c);
if (a + b + d == 0)
Console.WriteLine("{0} + {1} + {2} = 0", a, b, d);
if (a + b + e == 0)
Console.WriteLine("{0} + {1} + {2} = 0", a, b, e);
if (a + c + d == 0)
Console.WriteLine("{0} + {1} + {2} = 0", a, c, d);
if (a + c + e == 0)
Console.WriteLine("{0} + {1} + {2} = 0", a, c, e);
if (a + d + e == 0)
Console.WriteLine("{0} + {1} + {2} = 0", a, d, e);
if (b + c == 0)
Console.WriteLine("{0} + {1} = 0", b, c);
if (b + d == 0)
Console.WriteLine("{0} + {1} = 0", b, d);
if (b + e == 0)
Console.WriteLine("{0} + {1} = 0", b, e);
if (b + c + d == 0)
Console.WriteLine("{0} + {1} + {2} = 0", b, c, d);
if (b + c + e == 0)
Console.WriteLine("{0} + {1} + {2} = 0", b, c, e);
if (b + d + e == 0)
Console.WriteLine("{0} + {1} + {2} = 0", b, d, e);
if (c + d == 0)
Console.WriteLine("{0} + {1} = 0", c, d);
if (c + e == 0)
Console.WriteLine("{0} + {1} = 0", c, e);
if (c + d + e == 0)
Console.WriteLine("{0} + {1} + {2} = 0", c, d, e);
if (d + e == 0)
Console.WriteLine("{0} + {1} = 0", d, e);
if (a + b + c + d == 0)
Console.WriteLine("{0} + {1} + {2} + {3} = 0", a, b, c, d);
if (a + b + c + e == 0)
Console.WriteLine("{0} + {1} + {2} + {3} = 0", a, b, c, e);
if (a + b + d + e == 0)
Console.WriteLine("{0} + {1} + {2} + {3} = 0", a, b, d, e);
if (a + c + d + e == 0)
Console.WriteLine("{0} + {1} + {2} + {3} = 0", a, c, d, e);
if (b + c + d + e == 0)
Console.WriteLine("{0} + {1} + {2} + {3} = 0", b, c, d, e);
if (a + b + c + d + e == 0)
Console.WriteLine("{0} + {1} + {2} + {3} + {4} = 0", a, b, c, d, e);
else
Console.WriteLine("no zero subset");
}
}
13
aslv1 avatar aslv1 304 Точки

БРАВО! По принцип това се искаше в задачата, да се упражнят if-овете.

Бих те посъветвал да слагаш отстъп пред Console.WriteLine, за да е ясно, че се изпълняват в зависимост от някакво условие.

Например:

if (c + e == 0)
    Console.WriteLine("{0} + {1} = 0", c, e);

а пък по принцип най-добрият вариант е

if (c + e == 0)
{
    Console.WriteLine("{0} + {1} = 0", c, e);
}
0
beBoss avatar beBoss 507 Точки

Тук форумът му форматира кода така(подрежда го в ляво).

2
bangelova avatar bangelova 48 Точки

Няма майтап, май само твоето работи със 100%-това точност. Браво за търпението :D

0
coaster avatar coaster 412 Точки

Хора, въртях, мислих, писах, суках, и пак не изкарах 32 if-а както гласи подсказката в условието. При всички случаи възможните комбинации са 26. Бъркам ли нещо?
Задачата работи и така: <ЦЪК>

1
achkata avatar achkata 17 Точки

Здравей,

Като добавиш и всяко число да ти е търсената сума, получаваш всички вариации.

Нямаш грешка в if-овете, които си описала.

 

Поздрави.

0
ViValDam avatar ViValDam 15 Точки

И аз започнах да пиша 32 if-аsurprised , но някъде към средата някъде се досетих ,че Наков се е пошегувал с нас и реших да си изнамеря по-мързеливо решение от едночасово писане на  if-ове surprised 

smile

 

-1
ViValDam avatar ViValDam 15 Точки

Какво и е пък , чак толкоз страхотното на 12 задача ?smile

На мен 10 - тази с бирата по-ми хареса !wink

Ето го моето решение :

int sum ;
bool found = false;
int[] number = new int[5];

for (int i = 0; i < 5; i ++)
{
      Console.Write("\n\nEnter a value for number " + (i+1) + " : ");
      number[i] = int.Parse(Console.ReadLine());
}
Console.WriteLine();

//creating the sums

for (int onStart = 0; onStart < 5; onStart ++)
{
       sum = 0; //seting every time sum to 0 , when starting to calculate the next sum 
       for (int onEnd = onStart; onEnd < 5; onEnd ++)
       {
             //suming
             sum = sum + number[onEnd];
             if (sum == 0)
            {

                  found = true;
                  //printig zero subset       
                  Console.WriteLine();
                  for (int i = onStart; i < onEnd; i++)
                  {
                        Console.Write("{0} + ", number[i] );
                  }
                  Console.Write(number[onEnd]);
                  Console.Write(" = 0\n\n");
            }
        }
}
if (found == false)
{
     Console.WriteLine();
     Console.WriteLine("no zero subset\n\n");

}

 

 

0
IvanKrastev avatar IvanKrastev 0 Точки

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

 

0
zontak avatar zontak 457 Точки

След грешката си.. като видях задачата ми.. е същата като на YaneYo. Сори за спама.. не беше нарочно ;с Край..

3
ViValDam avatar ViValDam 15 Точки

Зонтак , дал си някаква друга задача , не е 12

-1
zontak avatar zontak 457 Точки

Даа.. дал съм задачата за пресмятане колко нули има накрая на даден факториел.. ;д Сега ще поправя линка ;д Дал съм 18-та от Лоопс ;д Край..

3
achkata avatar achkata 17 Точки

@VivalDam

 

Интересното на задачата е, че предлага различни начини за решение.

В уикипедия е написано доста по-въпроса.

И най-важното е, че това си е чисто мое мнение.

Решението, което ти предлагаш е грешно. Сега ако тръгнеш да го оправяш, може да ти стане и по-интересно. :)

За да спестя 2-3 коментара:

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

Нямаш прескачане на числа. В твоя случай, ако въведем : 4, 1, 6, -4, -1 изкарва, че няма събсетс, които да отговарят на условиете. 

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

Успех!

 

П.С. Интересно, че никой не ти е драснал по този повод, а даже и са те воутнали :)

5
ScreeM avatar ScreeM 19 Точки

Много добро решение на задачата. Моето е по-аматьорско, но все пак бих искал да го споделя с Вас: http://pastebin.com/YUt4fs3v

1
g.stoyanov avatar g.stoyanov 776 Точки

Ето още едно решение, да обогатим колекцията :). Ползвам побитова маска, StringBuilder и Linq.

4
ViValDam avatar ViValDam 15 Точки

Най-хубави са побитовите решения smile елегантни, бързи и кратки !

3
zornitza_gencheva avatar zornitza_gencheva 28 Точки

Здравейте,

според мен това е една от най-трудни задачи досега и една от най-интересните.

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

 

 

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