[Java] Wat is er mis met algoritme?

[Verwijderd]

Ik ben bezig met een algoritme die moet bepalen hoeveel waarden uit een willekeurige array (alle gehele gatallen) er groter zijn dan al hun voorgangers. Volgens mij ben ik op de goede weg, maar de uitkomst is niet goed. Als ik bijvoorbeeld een array van 10 waardes heb, dan geeft hij nog wel eens een uitkomst als 12. Dat kan natuurlijk niet. Mijn vraag is wat gaat hier fout?

code:

    public void biggerThanPre() {
        int[] arrayFinal = getArray(); //De array waar de berekening op uitgevoerd wordt
        int biggerNumbers = 0; //Waarde +1 als alle voorgangers kleiner zijn
        boolean bigger;


        for (int i = 1; i < arrayFinal.length; i++) {
            bigger = true;
            for (int j = 0; j < arrayFinal.length; j++) {

                if (arrayFinal[i] <= arrayFinal[j]) {

                    bigger = false;
                    break;
                }
                if (bigger) {
                    biggerNumbers++;
                }
            }
        }

        System.out.println("Number of values bigger than predecessors: " + biggerNumbers);
        
    }

[mandroid]

Moet de variable j in de tweede lus niet itereren tussen 0 en i?

[BCC]

Dat is er toch altijd 1?
[1,2,3] => 1, namelijk 3
[3,2,1] => 1, namelijk 3
[1,2,3,1,2,3] => 1 namelijk de eerste 3.

[ Voor 66% gewijzigd door BCC op 07-09-2008 20:07 ]

[danslo]

Zie:

cls in "[Java] Wat is er mis met algoritme?"

[ Voor 87% gewijzigd door danslo op 07-09-2008 20:21 ]

[FireWood]

Ik zie de fout niet zo snel, maar ik zou sowieso het iets anders opbouwen.
BTW ik weet de precieze syntax van java niet meer, dus code is onder voorbehoud.

code:

    public void biggerThanPre() {
        int[] arrayFinal = getArray(); //De array waar de berekening op uitgevoerd wordt
        int biggerNumbers = 0; //Waarde +1 als alle voorgangers kleiner zijn

        for (int i = 1; i < arrayFinal.length; i++) {
                if (arrayFinal[i] > arrayFinal[i-1]) {
                    biggerNumbers++;
                }
            }
        
        System.out.println("Number of values bigger than predecessors: " + biggerNumbers);
        
    }

Iets simpeler opgebouwd.

edit: Damn you cls, to late (en ik zag ook nog een foutje in mijn code. )

[ Voor 5% gewijzigd door FireWood op 07-09-2008 20:10 ]

[Verwijderd]

Nee, dan geeft hij bij een array van 10 waarden nog steeds antwoorden groter dan 10.

[Onbekend]

Je kijkt 2x door die array. Je kan maximaal 10x10 = 100 als resultaat hebben omdat je 2 for-loops in elkaar hebt staan.

[RSpliet]

Twee loops is inderdaad niet nodig:

Hij moet groter zijn dan _alle_ voorgaande elementen. Dus: groter zijn dan de grootste van de voorgaande elementen, immers, dat is de grootste.
Hou dus bij de grootste die je tot nu toe bent tegengekomen. Pak je het volgende element, dan zijn er 2 mogelijkheden:
1. Het genomen element is groter. Je verhoogt je biggerNumber teller met 1, en maakt dat je nieuwe grootste getal
2. Het genomen element is gelijk of kleiner. Je verhoogt je teller niet, en houdt ook de grootste gelijk.

Ik ga het niet voor je in Java uitwerken, maar ik denk dat dat zo'n 8 regels code is ;-)

[DrClaw]

code:

public void biggerThanPre() {
        int[] arrayFinal = getArray(); //De array waar de berekening op uitgevoerd wordt
        int biggerNumbers = 0; //Waarde +1 als alle voorgangers kleiner zijn
        boolean bigger;


        for (int i = 1; i < arrayFinal.length; i++) {
            bigger = true;
            for (int j = 0; j < i; j++) {

                if (arrayFinal[i] <= arrayFinal[j]) {

                    bigger = false;
                    break;
                }
            }
            if (bigger) {
                biggerNumbers++;
            }
        }

        System.out.println("Number of values bigger than predecessors: " + biggerNumbers);
        
    }

zo, je if(bigger) uit de inner loop gehaald... en de condition in de 2e loop aangepast.

[ Voor 3% gewijzigd door DrClaw op 07-09-2008 20:18 ]

[FireWood]

Gevonden:

code:

                if (bigger) {
                    biggerNumbers++;
*                   break;
                }

Toch zal ik het in 1 loop houden zoals cls en ik al eerder op hebben getypt.

[Verwijderd]

Het is dus de bedoeling hij bijvoorbeeld bij de volgende array als antwoord 4 geeft, omdat -3 heeft geen voorganger, dus is hij groter. En 0 is groter dan -3, dus groter dan voorganger. Dan -1 niet, omdat 0 groter is en 3 en 4 wel omdat die groter zijn dan al hun voorgangers.

Volgens mij heb je dus wel 2 for loops nodig. h.edink werkt helaas niet.

Array nr.: 0 Value: -3
Array nr.: 1 Value: 0
Array nr.: 2 Value: -1
Array nr.: 3 Value: 3
Array nr.: 4 Value: 4

[danslo]

Zie nu pas wat de OP bedoelt

Je moet zoiets doen:

code:

bool bigger = true;
for (int i = 1; i < arrayFinal.length; i++) {
    for(int j = 0; j < (i-1); j++) {
        if(arrayFinal[i]<=arrayFinal[j]) {
            bigger = false;
            break;
        }
    }
    if (bigger) {
        biggerNumbers++;
    }
    bigger = true;
}

De fout zat hem in het feit dat je de tweede loop door moet laten gaan naar (i-1), en dus niet naar de grootte van de array. Ook moet je die boolean resetten na elk nummer.

[ Voor 25% gewijzigd door danslo op 07-09-2008 20:22 ]

[RSpliet]

h.edink schreef op zondag 07 september 2008 @ 20:14:
Toch zal ik het in 1 loop houden zoals cls en ik al eerder op hebben getypt.

Jou oplossing controleert alleen maar de directe voorganger. Wat nou als je de volgende array hebt?
[i-2] = 12
[i-1] = 8
[i] = 10

Juist, dan geeft hij een false positive 't Kan met één loop, maar dan moet je vergelijken met "de grootste", niet met de eerst voorgaande.

[Confusion]

Verwijderd schreef op zondag 07 september 2008 @ 20:16:
Volgens mij heb je dus wel 2 for loops nodig. h.edink werkt helaas niet.

Als je iedere waarde 1 keer bekijkt, kan je telkens bijhouden wat de grootste voorgaande waarde was. Je weet dus bij iedere nieuwe waarde die je bekijkt wat de grootste voorgaande waarde was. Dat kan dus prima in 1 loop. Als je het in twee loops doet en telkens alle voorgaande waarden opnieuw gaat bekijken, dan herhaal je vergelijkingen waarvan je de uitkomst allang weet.

[danslo]

Op deze manier dus:

code:

int biggest = arrayFinal[0];
int biggerNumbers;
for (int i = 1; i < arrayFinal.length; i++) {
    if (arrayFinal[i] > biggest) {
        biggest = arrayFinal[i];
        biggerNumbers++;
    }   
}

[RSpliet]

cls schreef op zondag 07 september 2008 @ 20:24:
Op deze manier dus:

code:

int biggest = arrayFinal[0];
int biggerNumbers;
for (int i = 1; i < arrayFinal.length; i++) {
    if (arrayFinal[i]>biggest) {
        biggest = arrayFinal[i];
        biggerNumbers++;
    }   
}

Bijna. Geef maar eens een getal aan dat een voorganger is van arrayFinal[0], én groter is. Die is er niet, dus arrayFinal[0] moet ook een "groter dan alle voorgangers" zijn. Met andere woorden, biggerNumbers moet op 1 worden geinitialiseerd .

[Verwijderd]

Bedankt cls. Jouw oplossing werkt. Seven of nine heeft ook gelijk. biggerNumbers op 1 initialiseren en het werkt perfect. Tnx

[WormLord]

Seven of Nine schreef op zondag 07 september 2008 @ 20:27:
Bijna. Geef maar eens een getal aan dat een voorganger is van arrayFinal[0], én groter is. Die is er niet, dus arrayFinal[0] moet ook een "groter dan alle voorgangers" zijn. Met andere woorden, biggerNumbers moet op 1 worden geinitialiseerd .

Daar ben ik het niet mee eens. Geef jij maar eens een getal dat een voorganger is van arrayFinal[0] en dat kleiner is. Als een getal geen voorgangers heeft, kan het gewoon niet groter zijn dan al zijn voorgangers.
Natuurlijk zijn beide keuzes voor het eerste getal (wel tellen of niet tellen) te verdedigen. Welke keuze het beste is, is afhankelijk van het doel dat Overflow88 heeft voor het algoritme.

[RSpliet]

WormLord schreef op maandag 08 september 2008 @ 10:14:
[...]


Daar ben ik het niet mee eens. Geef jij maar eens een getal dat een voorganger is van arrayFinal[0] en dat kleiner is.

Ik durf veilig te stellen dat alle getallen die er voor staan kleiner zijn dan arrayFinal[0], dat dat een eigenschap is van de verzameling van voorgangers. Evenzogoed durf ik te stellen dat alle getallen _die ervoor staan_ groter zijn dan arrayFinal[0]. Geef maar een tegenvoorbeeld!
Beide stellingen gelden, tegelijkertijd, en dat kan alleen maar omdat het een lege verzameling is.
D'r staat nergens in Overflow88's definitie dat ik werkelijk zo'n getal moet kunnen geven. Alleen dat als er getallen voor staan (alle voorgangers, al zijn dat er 0), dat die kleiner moeten zijn dan arrayFinal[i]. En daar durf ik mijn hand voor in 't vuur te steken

Tuurlijk hangt het af van het praktisch nut wat je programmeert, maar dit staat er gedefinieerd .

[ Voor 7% gewijzigd door RSpliet op 08-09-2008 14:02 ]

[redfox314]

idd dat is wat er staat
Een inductieve definitie.
Zij x₁---x_n een geordende verzameling getallen dan is het resultaat van de functie
Basis:
voor n=0 het resultaat=0
voor n=1 het resultaat is 1
Inductie: i>1
resultaat=|{x_i: x_j<x_i,j<i}|

bij dit soort inductieve dingen moet je goed uitkijken wat je met je basis doet. Op de totale ordening van < kan je niet rekenen a<a is niet waar.

[ Voor 4% gewijzigd door redfox314 op 08-09-2008 14:58 ]

[roy-t]

... laat maar, niet helder.

Maar ik zou een recursief algoritme voorstellen.

Edit: ik zie nu ook het stukje van CLS (dacht dat het een stukje voorbeeld was, maar het is de hele oplossing al) werkt perfect zo te zien en lekker weinig instructies + zoals Oisyn al zei O(n) complexiteit.

Ik snap eigenlijk niet waarom je ooit met een dubbele loop kwam, kun je die keuze is uitleggen?

[ Voor 156% gewijzigd door roy-t op 08-09-2008 17:08 ]

[.oisyn]

Wat er mis aan is is dat dat algoritme O(n²) is, terwijl de laatste oplossing van cls maar O(n) is (en een stuk minder code)

[Grijze Vos]

Euhm, als je dit nou gewoon zoals het hoort berekent dan zat je niet met deze vragen. Nooit gehoord van invarianten en aanverwante zaken?

[BCC]

offtopic:
Lazy evaluation :)!