Denkfehler bei einfacher Schleife

Naja, was heißt "funktioniert"... Entweder ich sehe was anderes als du oder du hast keine richtige Version gepostet...

Schreib deinen Code doch nochmal sauber auf.

Edit: Oder es ist spät und ich finde nicht mehr durch die Sache durch. 😀
 
Barista hat gesagt.:
Es grenzt schon an Frechheit, die Anforderungen im 41. Posting nachzureichen.

Hier bemühen sich Leute, jemanden zu helfen.

Diese Leute werden durch das Vorenthalten von Infos und schlechte Fragen regelrecht beleidigt.
Zum Vergrößern anklicken....
Wobei ich das hier nicht so hart sehen würde. Mir ist es lieber, jemand schiebt Infos nach, als das jemand die Anforderungen hinklatscht und sagt "Löst mal". Und man muss hier gestehen, hier hat sich eine rege Diskussion ohne den Thread Ersteller entwickelt, so dass die Info zwar sehr spät kam, aber es schaut halt nicht jeder rein.

Bezüglich der Anforderungen ist der Algorithmus im Groben sehr simpel:

Fange mit Index 0 an und schaue, wo das Element hin muss. Mache dann mit dem Element an der Zielstelle weiter und schaue wo das hin muss. Das so lange bis man das Element in der Hand hat, das auf Index 0 gehört.
Wenn dann Index 1 noch nicht bearbeitet wurde, wiederhole das ganze mit dem Element von Index 1.
Dann analog Index 2 usw. bis maximal Index=shift-1

Herausforderung hier ist jetzt zweierlei - und das ist eher ein mathematisches, den ein Programmierproblem:
a) Terminiert der Algorithmus? Komme ich beim verschieben nach dem Algorithmus immer wieder auf der Position an, mit der ich angefangen habe? Ich behaupte ja, aber das wäre zu beweisen, das man da keine Endlosschleife wie Indexe: 0, 3, 6, 2, 5, 2, 5, 2, 5 ... produziert.
b) Wenn ich Index i fertig habe, muss ich dann Index i+1 noch bearbeiten oder wurde das schon bearbeitet? Simples Beispiel: Bei einer gerade Zahl von Elementen im Array und einem Shift von 2 muss ich einmal bei index 0 und einmal bei index 1 starten um alle zu bearbeiten - jeder Durchlauf bearbeitet n/2 Fälle. Die Bearbeitung/Verschiebung ist bei 6 Elementen: 0-> 2 -> 4 -> 0 und 1 -> 3 -> 5 -> 1
Habe ich aber eine ungerade Zahl von Elementen reicht ein durchlauf, weil z.B. bei 5 Elementen die Indexe in der Folgende Reihenfolge bearbeitet werden: 0->2->4->1->3->0

Das ganze hat einiges mit Modulo-Rechnung und evtl. https://de.wikipedia.org/wiki/Restklassenring zu tun. Im Endeffekt braucht man ein Verfahren das einem bei der Eingabe der Array-Länge und Shift ausgibt, wie viele aufeinander folgende Indexwerte man bearbeiten muss. Der Knackpunkt ist die Mathematik - die Umsetzung ist hinterher ziemlich trivial (Ungetestet):

Java: 
public class Test {
    public void shift(char input[], int shift) {

        int anzDurchlaeufe = mathematik(input.length, shift);
        for (int startIndex = 0; startIndex < anzDurchlaeufe; startIndex++) {
            boolean finished = false;
            char element = input[startIndex];
            int workingIndex = startIndex;
            while (!finished) {
                workingIndex = (workingIndex + shift) % input.length;
                char temp = input[workingIndex];
                input[workingIndex] = element;
                element = temp;
                if (workingIndex == startIndex) {
                    finished = true;
                }
            }
        }
    }

    private int mathematik(int length, int shift) {
        if (shift == 2 && length % 2 == 0) {
            return 2;
        } else {
            return 1;
        }
    }

    public static void main(String[] args) {
        Test test = new Test();
        char[] input = "abcdefg".toCharArray();
        test.shift(input, 1);
        System.out.println(input);
        input = "abcdefg".toCharArray();
        test.shift(input, 2);
        System.out.println(input);
        input = "abcdefgh".toCharArray();
        test.shift(input, 2);
        System.out.println(input);
    }
}
Ausgabe:

Code: 
gabcdef
fgabcde
ghabcdef
 
@Barista Du musst dich doch nicht so aufregen. Die Anforderung, nicht rekursiv, ergibt sich eigentlich auch aus dem Eingangsposting, aber so ist es doch nochmal schöner.

@LimDul Vielen Dank, das sieht sehr vielversprechend aus. Ich teste das später.

Ich hab tatsächlich noch eine Seite gefunden, wo so etwas jemand schonmal gemacht hat: https://www.techiedelight.com/right-rotate-an-array-k-times/

Java: 
import java.util.Arrays;
 
class Main
{
    // Function to exchange data of two given indices in an array
    public static void swap(int[] A, int i, int j)
    {
        int data = A[i];
        A[i] = A[j];
        A[j] = data;
    }
 
    // Function to reverse a given subarray
    public static void reverse(int[] A, int low, int high)
    {
        for (int i = low, j = high; i < j; i++, j--) {
            swap(A, i, j);
        }
    }
 
    // Function to right-rotate an array by `k` positions
    public static void rightRotate(int[] A, int k, int n)
    {
        // base case: invalid input
        if (k < 0 || k >= n) {
            return;
        }
 
        // Reverse the last `k` elements
        reverse(A, n - k, n - 1);
 
        // Reverse the first `n-k` elements
        reverse(A, 0, n - k - 1);
 
        // Reverse the whole array
        reverse(A, 0, n - 1);
    }
 
    public static void main(String[] args)
    {
        int[] A = { 1, 2, 3, 4, 5, 6, 7 };
        int k = 3;
 
        rightRotate(A, k, A.length);
        System.out.println(Arrays.toString(A));
    }
}

Wenn ich mich nicht vertue, dann erfüllt das dreimalige reversen mit swappen des Arrays auch die Anforderungen... Ich würde aber die von @LimDul vorgeschlagene "geschlossene" Form bevorzugen...
 
LimDul hat gesagt.:
Fange mit Index 0 an und schaue, wo das Element hin muss. Mache dann mit dem Element an der Zielstelle weiter und schaue wo das hin muss.
Zum Vergrößern anklicken....
Dies verstösst gegen die Anforderung:

zusätzliche Speicherplatzanforderung: O(1)

Das sieht man auch daran, dass zwei temporäre Speicherstellen benötigt werden, element und temp.

Wahrscheinlich klappt es nur mit dem Reverten, da wäre ich nicht drauf gekommen.
 
Barista hat gesagt.:
Dies verstösst gegen die Anforderung:

zusätzliche Speicherplatzanforderung: O(1)

Das sieht man auch daran, dass zwei temporäre Speicherstellen benötigt werden, element und temp.

Wahrscheinlich klappt es nur mit dem Reverten, da wäre ich nicht drauf gekommen.
Zum Vergrößern anklicken....
Wo verstoße ich da. Es ist eine konstante Zahl an lokalen Variablen => O(1).
 
eineNick hat gesagt.:
"geschlossene" Form bevorzugen...
Zum Vergrößern anklicken....
Könnte so funktionieren:
Java: 
public void rotateRight(char[] text, int count) {
    int steps = count % text.length;
    if (steps == 0) { return; }
    int pos = 0;
    int delta = text.length - steps;
    while (delta > 0) {
        swap(text, pos, pos+delta);

        if ((pos+1) % steps == 0) {
             delta = text.length - (pos+1) - steps;
        }
        pos++;
    }   
}

private void swap(char[] text, int ix1, int ix2) {
    char tmp = text[ix1];
    text[ix1] = text[ix2];
    text[ix2] = tmp;
}
 
mihe7 hat gesagt.:
Könnte so funktionieren:
Zum Vergrößern anklicken....

Wunderbar, ich danke dir, @mihe7 , aber ich muss dich gleichzeitig auch enttäuschen: 🙁

Java: 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;

public class Shift {
    public static char[] shiftRight(final char[] txt, final int shift) {
        int steps = shift % txt.length;
        if (steps == 0) {
            return txt;
        }
        int pos = 0;
        int delta = txt.length - steps;
        while (delta > 0) {
            swap(txt, pos, pos + delta);

            if ((pos + 1) % steps == 0) {
                delta = txt.length - (pos + 1) - steps;
            }
            pos++;
        }
        return txt;
    }

    private static void swap(final char[] text, final int ix1, final int ix2) {
        char tmp = text[ix1];
        text[ix1] = text[ix2];
        text[ix2] = tmp;
    }

    /**
     * To test the shiftRight method.
     */
    public static char[] shiftRightConventional(final char[] txt, final int shift) {
        ArrayList<Character> list = String.valueOf(txt).chars().mapToObj(c -> (char) c).collect(Collectors.toCollection(ArrayList::new));
        Collections.rotate(list, shift);
        for (int i = 0; i < list.size(); i++) {
            txt[i] = list.get(i);
        }
        return txt;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 15; i++) {
            System.out.println(i + " a: " + Arrays.toString(shiftRight("Guten Tag".toCharArray(), i)));
            System.out.println(i + " b: " + Arrays.toString(shiftRightConventional("Guten Tag".toCharArray(), i)));
        }
    }
}

Code: 
0 a: [G, u, t, e, n,  , T, a, g]
0 b: [G, u, t, e, n,  , T, a, g]
1 a: [g, G, u, t, e, n,  , T, a]
1 b: [g, G, u, t, e, n,  , T, a]
2 a: [a, g, G, u, t, e, n,  , T]
2 b: [a, g, G, u, t, e, n,  , T]
3 a: [T, a, g, G, u, t, e, n,  ]
3 b: [T, a, g, G, u, t, e, n,  ]
4 a: [ , T, a, g, G, u, t, e, n]
4 b: [ , T, a, g, G, u, t, e, n]
5 a: [n,  , T, a, g, u, t, e, G]
5 b: [n,  , T, a, g, G, u, t, e]
...

Alles hätte so schön sein können. 🙈
 
Java: 
public class Main {

    public static void main(String[] args) {
        for (int i = 0; i < 11; i++) {
            System.out.println(Arrays.toString(shift("Guten Tag!".toCharArray(), i)));
        }
    }

    public static char[] shift(char[] arr, int shift) {
        int steps = shift % arr.length;

        for (int i = 0; i < steps; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                swap(arr, j, j % arr.length + 1);
            }
        }
        return arr;
    }

    public static void swap(char[] arr, int index1, int index2) {
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

}

Die Richtung müsste man noch umkehren und bei O(n) bin ich nicht sicher, da hab ich keine Ahnung davon.

Java: 
[G, u, t, e, n,  , T, a, g, !]
[u, t, e, n,  , T, a, g, !, G]
[t, e, n,  , T, a, g, !, G, u]
[e, n,  , T, a, g, !, G, u, t]
[n,  , T, a, g, !, G, u, t, e]
[ , T, a, g, !, G, u, t, e, n]
[T, a, g, !, G, u, t, e, n,  ]
[a, g, !, G, u, t, e, n,  , T]
[g, !, G, u, t, e, n,  , T, a]
[!, G, u, t, e, n,  , T, a, g]
[G, u, t, e, n,  , T, a, g, !]
 
temi hat gesagt.:
Die Richtung müsste man noch umkehren und bei O(n) bin ich nicht sicher, da hab ich keine Ahnung davon.
Zum Vergrößern anklicken....
Ich würde es als O(n*n) ansehen, denn Du hast O(n*m) mit n Größe Array und m der Schrittweite. Und m geht mit n auch hoch (wenn man alle Möglichkeiten betrachtet, dann hat man ein Schnitt von n/2 ud somit O(n * n / 2) = O (n*n).

Und das ist unter dem Strich auch nur die Implementation, die schon am Anfang als eine Möglichkeit genannt wurde (#2).
 
So könnte es funktionieren. O(n) sollte offensichtlich sein. Hoffentlich sind alle Fälle abgedeckt.
Java: 
import java.util.Arrays;

public class MeniskusShift {

    public static char[] rotateRight(char[] text, int count) {
        int steps = count % text.length;
        if (steps == 0) {
            return text;
        }

        int size = text.length;
        int start = 0;
        int dest = start + steps;
        char temp1 = text[start % size];

        for (int i = 0; i < text.length; i++) {
            char temp2 = text[dest % size];
            text[dest % size] = temp1;
            temp1 = temp2;
            if (dest % size == start) {
                start++;
                temp1 = text[start % size];
                dest = start + steps;
            } else {
                dest += steps;
            }
        }
        return text;

    }

    public static void main(String[] args) {
        for (int i = 0; i < 11; i++) {
            System.out.println(Arrays.toString(rotateRight("Guten Tag!".toCharArray(), i)));
        }
    }

}
 
Sehr schön, es funktioniert alles!!! (bis auf den Fall count = 0, aber das sollte verschmerzbar sein):

Java: 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.stream.Collectors;

public class Shift {
    public static char[] shiftRight(final char[] text, final int shift) {
        int steps = shift % text.length;
        if (steps == 0) {
            return text;
        }

        int size = text.length;
        int start = 0;
        int dest = start + steps;
        char temp1 = text[start % size];

        for (int i = 0; i < text.length; i++) {
            char temp2 = text[dest % size];
            text[dest % size] = temp1;
            temp1 = temp2;
            if (dest % size == start) {
                start++;
                temp1 = text[start % size];
                dest = start + steps;
            } else {
                dest += steps;
            }
        }
        return text;
    }

    /**
     * To test the shiftRight method.
     */
    public static char[] shiftRightConventional(final char[] txt, final int shift) {
        ArrayList<Character> list = String.valueOf(txt).chars().mapToObj(c -> (char) c).collect(Collectors.toCollection(ArrayList::new));
        Collections.rotate(list, shift);
        for (int i = 0; i < list.size(); i++) {
            txt[i] = list.get(i);
        }
        return txt;
    }

    public static void main(String[] args) {
        Random random = new Random(0);
        char[] array = "Guten Tag!".toCharArray();
        for (int i = 0; i < 10000; i++) {
            char[] array2 = new char[random.nextInt(array.length) + 1];
            System.arraycopy(array, 0, array2, 0, array2.length);
            char[] array3 = new char[array2.length];
            System.arraycopy(array2, 0, array3, 0, array2.length);
            int shift = random.nextInt(20);
            shiftRight(array2, shift);
            shiftRightConventional(array3, shift);
            boolean result = Arrays.equals(array2, array3);
            System.out.println(result + " " + Arrays.toString(array2) + " " + Arrays.toString(array3));
            if (!result) {
                System.out.println("OOOPS...");
                break;
            }
        }
    }
}

ich geh nochmal schnell auf @temi ein und, warum seins nicht O(n) ist. Machen wir einen Ausflug in die theoretische Informatik. Man kann den best, worst und average case betrachten. Der best hat offensichtlich O(n) (nur eine Verschiebung), der worst hat aber O((n/2)*n), das ist, wie von Kneitzel bereits richtig beschrieben, O(n²)....

(n/2)*n ist sehr viel. Sagen wir 10 Millionen Elemente, dann braucht die Methode von @Meniskusschaden
10.000.000
und die Methode von @temi braucht
50.000.000.000.000

(oder anders, sie ist 5 Millionen mal langsamer)
Und das ist für einen Computer (bei steigenden n) zu viel.

@mihe7 Kannst du ohne den Ruhm leben? 😀
 
Wobei bei der Lösung @Meniskusschaden ein zweites Array involviert ist 😛 Mich nervt mehr, dass es dafür ja eine Lösung geben muss. Ich hätte auch schon einen Lösungsansatz, bin mir aber noch nicht sicher, dass das so immer funktioniert.
 
mihe7 hat gesagt.:
EDIT: ich konstatiere: mein geistiges Level ist mittlerweile bei einem Pfund Salz angelangt.
Zum Vergrößern anklicken....
Hey, damit lassen sich Lebensmittel konservieren (mit (viel) Zucker allerdings auch...)! @mihe7 sei nicht so wehleidig und traurig, du leistest Großartiges! (In diesem Thema zwar nicht so, aber jeder greift mal ins Klo. 😉 )

Also bitte, mehr Zuversicht, weniger Jammern und beim nächsten mal bist du wieder der Erste. 🙂

Wenn man sich die Beiträge von @Meniskusschaden mal anschaut, sieht man auch schnell, er ist ein harter Hund, mit dem man es nicht unbedingt aufnehmen möchte...

So, jetzt aber Nacht.
 
Darum gehts doch nicht, das ist ja hier kein Wettbewerb. Ich merke einfach, dass ich zurzeit geistig auf einem Tiefpunkt bin (oder mich diesem annähere...) - und das nervt. Vor allem, wenn die Lösung vor einem auf dem Zettel steht und man sie nicht sieht, sich in seinem Ansatz verrennt. Es kommen wieder bessere Zeiten, muss mal den Resetknopf drücken 🙂
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Denkfehler bei for Schleife
Antworten: 2
Denkfehler bei SQL-Befehl
Antworten: 8
Denkfehler? bei Sortiertem einfügen?
Antworten: 4
Pong-Klon. Denkfehler bei kollisionstest
Antworten: 3
Denkfehler bei Interfaces und Casts?
Antworten: 12

Zurück
Oben