18 svar
91 visningar
Koya_The_Koala2.0 är nöjd med hjälpen!
Koya_The_Koala2.0 36
Postad: 9 dec 2020

Hur ska metoden skapas?

Hej!

Jag försöker skapa en metod som hittar tre element vars totala summa är noll. Den skall sedan lägga in de här tre elementen i en array och returnera den. Jag håller på att skissa hur metoden skall se ut, det här är det jag har:

- Deklarera variablen för summan (int sum = 0) och arrayen(int [] sum2Zero = new int [3])

- skapa en loop

- någon form av if sats

-??

Jag vet inte hur jag skall fortsätta efter det. Jag tänker att jag är i behov av en while-loop, men hur länge skall den hålla på? Hur skall if-satsen fungera? Jag behöver lite tips på hur jag kan tänka.

Laguna 12476
Postad: 9 dec 2020

Hur hittar du talen? 

Koya_The_Koala2.0 36
Postad: 9 dec 2020

Kanske med en for-loop för att söka igenom arrayen, men hur ska jag göra med elementen.? T.ex om jag har arrayen int arr = {0,1,2,3,4,5} och jag  har arr[0], vad gör jag sen? Jag vet inte hur if-satsen ska vara så att den kan hitta rätt element.

Eller tre nästlade for-loopar som löper igenom alla kombinationer av tre tal i listan och bryter när summan blir noll?

Laguna 12476
Postad: 9 dec 2020

Jaha, du har ett antal givna tal i en array från början? 

Koya_The_Koala2.0 36
Postad: 9 dec 2020
Lindehaven skrev:

Eller tre nästlade for-loopar som löper igenom alla kombinationer av tre tal i listan och bryter när summan blir noll?

Hur blir det med for-looparna? Den största arrayen innehåller 8 element, alltså blir det 83= 56st sätt att välja ut tre element. Räcker det inte med en for-loop som ser ut såhär??

for(int i = 0; i<combinationsOfthree; i++){...}
Koya_The_Koala2.0 36
Postad: 9 dec 2020
Laguna skrev:

Jaha, du har ett antal givna tal i en array från början? 

Ja, men jag har 4st arrays som metoden ska fungera på. Den största har 8 element, den minsta har 3 element.

Laguna 12476
Postad: 9 dec 2020

Med så små arrayer spelar det ingen roll vilken metod man väljer, men det går att hitta en algoritm som är bättre än O(n3) (vilket betyder att tiden det tar är proportionell mot kuben på antalet element). Hur bra kan man få den?

Står det i uppgiften att du ska göra något försök att optimera?

Koya_The_Koala2.0 36
Postad: 9 dec 2020

Det står inte att man ska optimera utan man ska skriva metoden från grunden.

Koya_The_Koala2.0 skrev:
Lindehaven skrev:

Eller tre nästlade for-loopar som löper igenom alla kombinationer av tre tal i listan och bryter när summan blir noll?

Hur blir det med for-looparna? Den största arrayen innehåller 8 element, alltså blir det 83= 56st sätt att välja ut tre element. Räcker det inte med en for-loop som ser ut såhär??

for(int i = 0; i<combinationsOfthree; i++){...}

Det blir snarare såhär (vilket är av komplexitet  O(n3)):

for (int x = 0; x < n-2; x++)
    for (int y = x+1; y < n-1; y++)
        for (int z = y+1; z < n; z++)
            // more code
Koya_The_Koala2.0 36
Postad: 10 dec 2020

Vad betyder "O(n3)): "?

Att algoritmen i värsta fall kräver n^3 operationer för en array med n element. Det är en relativt ineffektiv algoritm. Därav frågorna om eventuell effektivisering.

Koya_The_Koala2.0 36
Postad: 10 dec 2020
Lindehaven skrev:

Att algoritmen i värsta fall kräver n^3 operationer för en array med n element. Det är en relativt ineffektiv algoritm. Därav frågorna om eventuell effektivisering.

Aha, tack!

Koya_The_Koala2.0 36
Postad: 10 dec 2020

Det här är koden jag nu har skrivit:

int[] sum2Zero = new int[3];

    int[] getThreeSum(int[] arr1) {
        int i = 0;
        boolean found = false;
        for (int x = 0; x < arr1.length - 2; x++) {
            for (int y = 0; y < arr1.length - 1; y++) {
                for (int z = y + 1; z < arr1.length; z++) {
                    if (arr1[x] + arr1[y] + arr1[z] == 0) {
                        found = true;
                        sum2Zero[i] = arr1[x];
                        i++;
                        sum2Zero[i] = arr1[y];
                        i++;
                        sum2Zero[i] = arr1[z];
                    }
                    else if (arr1[x] + arr1[y] + arr1[z] < 0){
                        y++;
                    }
                    else{z--;}
                }

            }
            if (found = false){
                out.println("No triplets available");
            }
        }
        return sum2Zero;
    }

Problemet är att det kommer inte upp något på skärmen. Jag testade debugga den och den fastnade i en loop när z = 5. Hur kan jag fixa det här?

Laguna 12476
Postad: 10 dec 2020

Det där z-- ser riktigt konstigt ut. Om du nånsin kommer dit så kommer loopen att fortsätta med det värde på z som du hade nyss, så det kommer att hålla på med det värdet på z i evighet.

y++ ser också udda ut, men den kanske är vettig. 

Laguna har rätt.

Dessutom finns ett klassiskt fel med tilldelning istället för jämförelse här:

            if (found = false){
                out.println("No triplets available");
            }
Koya_The_Koala2.0 36
Postad: 10 dec 2020

Jag ändrade koden till det här

int[] getThreeSum(int[] arr1) {
        int i = 0;
        boolean found = false;
        for (int x = 0; x < arr1.length - 2; x++) {
            for (int y = 0; y < arr1.length - 1; y++) {
                for (int z = y + 1; z < arr1.length; z++) {
                    if ((arr1[x] + arr1[y] + arr1[z] == 0) && ((arr1[x] != arr1[y]) && (arr1[x] !=arr1[z])&& (arr1[y] != arr1[z]))) {
                        found = true;
                        sum2Zero[i] = arr1[x];
                        i++;
                        sum2Zero[i] = arr1[y];
                        i++;
                        sum2Zero[i] = arr1[z];
                    }
                    else if (arr1[x] + arr1[y] + arr1[z] < 0){
                        y++;
                    }
                    else{z++;}
                }

            }
            if (found = false){
                out.println("No triplets available");
            }
        }
        return sum2Zero;
    }

Men nu skriver den ut [0,0,0] på skärmen vilket inte är rätt. 

Din kompilator sätter alla element i sum2Zero till noll

int[] sum2Zero = new int[3];

Vilken indata använder du till arr1?

Varför inte prova de tips du fått?

Varför ändra i for-looparna?

Varför de extra villkoren i if-satserna?

Koya_The_Koala2.0 36
Postad: 10 dec 2020
Lindehaven skrev:

Din kompilator sätter alla element i sum2Zero till noll

int[] sum2Zero = new int[3];

Vilken indata använder du till arr1?

Varför inte prova de tips du fått?

Varför ändra i for-looparna?

Varför de extra villkoren i if-satserna?

Förlåt, jag försökte kombinera eran lösning med en som jag hittade på nätet. Jag använde tipsen ni gav mig ooch nu funkar programmet. Tack!

Svara Avbryt
Close