Index an dem Listenelement bis zum Index und ab Index die selbe Summe haben
-
Eine simple Implementierung wäre:
int sum = 0; foreach(int x in list) sum += x; if(split % 2 == 1) return false; int split = sum/2; int temp = 0; for(int i = 0; i < list.length; ++i) { if(temp == split) return true; temp += list[i]; }
Allerdings schützt mich diese Implementierung eindeutig nicht vor Überläufen.
Funktioniert dieser Ansatz:
if(L.length == 1) // no split possible return false int sumleft = 0 int sumright = 0 int ptr1 = &L // ptr to start of list int ptr2 = &L + (L.length - 1) // ptr to end of list while(ptr1 < ptr2) { if(sumleft == 0) { sumleft = *ptr1 ptr1++ } else { sumright = *ptr2 ptr2-- } if(sumleft >= sumright) { sumleft -= sumright sumright = 0 } else { sumleft = 0 sumright -= sumright } } return sumleft == sumright == 0
MfG SideWinder
-
SideWinder schrieb:
Index an dem Listenelement bis zum Index und ab Index die selbe Summe haben
Ich nehme an, gemeint sind die beiden halboffenen Intervalle von 0 bis ausschließlich index und von index bis ausschließlich liste.length
SideWinder schrieb:
Eine simple Implementierung wäre:
int sum = 0; foreach(int x in list) sum += x; if(split % 2 == 1) return false;//sum statt split
SideWinder schrieb:
Funktioniert dieser Ansatz:
Ja.
SideWinder schrieb:
if(L.length == 1) // no split possible return false
Ja, wenn nur positive Zahlen erlaubt sind. Davon gehe ich ab jetzt fest aus.
while(ptr1 < ptr2) //Hier denke ich aber while(ptr1 <= ptr2)
-
Ja, gemeint sind die beiden halboffenen Intervalle von 0 bis ausschließlich index und von index bis ausschließlich liste.length. Ja, die sind nicht-negativ.
@"Oh, doch nur feststellen, OB es eine Teilung gibt.": Ja, der Algorithmus ist nicht für die Praxis sondern nur Teil eines Beweises (eh, der Beweis) um zu zeigen, dass das Problem in LOGSPACE liegt (du weißt ja, in der Komplexitätstheorie gibt man sich damit schon zufrieden ;))
<= stimmt. Ich würde sonst eine Zahl auslassen, danke fürs kontrollieren.
MfG SideWinder