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


Log in to reply