Software Denk Sport 2
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Dies ist nur eine kleine Übung.

Aufgabenstellung:

Schreibe eine Prozedur, die die Elemente eines Arrays mit M Elementen um n rotiert. -M < n < M

Beispiel: M = 6, n = 2. Vorher: {1, 2, 3, 4, 5, 6} Nachher: {5, 6, 1, 2, 3, 4}

Versuche Speicherbedarf zu minimieren.

Eine nachträgliche Bemerkung:

Es geht hier nicht um eine konkrete Implementierung in eine konkreten Sprache, eher geht es um den Algorithmus. Versuche es Dir so vorzustellen. Auf einer Straße parken M Autos nebeneinander. Rotiere sie um n, zusammen sollten die Autos nach dem rotieren den selben Platz belegen, wie vorher. Alle Autos sind gleich groß und belegen gleich große Parkplätze. Nur Du darfst die Autos fahren - eins auf einmal. Versuche den Algoritmus so zu gestalten, dass Du ein Minimum an zusätzlichen Parkplätzen brauchst. Autos dürfen nur auf einem Parkplatz stehenbleiben.

Wie kann man dieses Training absolvieren

(*)Nicht Wochen wie in SoftwareDenkSport 1, weil diese Aufgabe ziemlich leicht ist.

Offizielle Teilnehmerliste

#define xor(A,x,y) A[x] ^= A[y]
#define Ix (n+1)%M
#define Iy (n)%M
void rot( int* A, int M, int n )
{
   n=n*(M-1);
   while( n-- )
   {
 xor(A,Ix,Iy);xor(A,Iy,Ix);xor(A,Ix,Iy);
   }
}
 void rotate(int * const A, const int m, int n)
 {
  if (A != NULL && m && n && abs(n) < m) {
   register int  i, j;;
   if (n < 0)
    n = m + n;
   for (i = n; i < m; ++i) {
    j = i % n;
    /* Speicheroptimierter swap für ints. */
    A[i] ^= A[j], A[j] ^= A[i], A[i] ^= A[j];
   }
   rotate(A, n, n - 1 - j);
  }
 }

 A[i] ^= A[j] ^= A[i] ^= A[j]

 void rotate(int *const A, int m, int n)
 {
  register int i, j = -1;

  assert(A != NULL && m && abs(n) < m);

  if (n < 0)
   n = m + n;
  while(n -= (j + 1)) {
   for (i = n; i < m; ++i) {
    j = i % n;
    /* Speicheroptimierter swap für ints.   */
    A[i] ^= A[j], A[j] ^= A[i], A[i] ^= A[j];
   }
   m = n;
  }
 }

 
   A = {0, 1, 2, 3, 4}; n = 2; M = 5;
   i = 0; nach i = (i + n) % M ist i = 2;  ==> {2, 1, 0, 3, 4}
   i = 2; nach i = (i + n) % M ist i = 4;  ==> {4, 1, 0, 3, 2}
   i = 4; nach i = (i + n) % M ist i = 1;  ==> {1, 4, 0, 3, 2}
   i = 1; nach i = (i + n) % M ist i = 3;  ==> {3, 4, 0, 1, 2}
   i = 3; nach i = (i + n) % M ist i = 0; FERTIG. {3, 4, 0, 1, 2} ist eine korrekte Lösung.
Test bestanden. Machen wir aber noch einen Test:
 
   A = {0, 1, 2, 3}; n = 2; M = 4;
   i = 0; nach i = (i + n) % M ist i = 2;  ==> {2, 1, 0, 3}
   i = 2; nach i = (i + n) % M ist i = 0;   ==> FERTIG. Erwartete Lösung {2, 3, 0, 1}
Test fehlgeschlagen :-( Der Ansatz ist richtig, aber es fehlt noch was :-) --gR

  def rot(lst, n):
      if n < 0: n = len(lst) + n
      for i in xrange(n):
          lst.insert(0, lst.pop(-1))
public class RotatedList extends AbstractList {
  private List originalList;

  public RotatedList(List originalList, int rotation) {
    this.originalList = originalList;
    this.rotation = rotation;
  }

  public Object get(int index) {
    int rotatedIndex = (index + rotation) % size();
    if (rotatedIndex < 0) {
      rotatedIndex += size();
    }
    return originalList.get(rotatedIndex);
  }

  public int size() {
    return originalList.size();
  }
}

Oder ist das eher das DekoratorMuster?? Ich habe häufig Schwierigkeiten, die beiden auseinander zu halten... :-o

def rot(l,m):
    v=[m,len(l)-1,0,lambda x,i,j:(j(i,x[i]^x[i-1]),j(i-1,x[i]^x[i-1]),j(i,x[i]^x[i-1])),
       lambda:v[2]>0 and(v[3](l,v[2],l.__setitem__),v[5](2,v[2]-1),v[4]()),0,
       lambda:v[0] and(v[5](2,v[1]),v[4](),v[5](0,v[0]-1),v[6]()) ]
    v.__setitem__(5,v.__setitem__) or v[6]()

Sorry, aber ich erkenne den Algorithmus hieraus nicht. Könntest Du diesen Code bitte kommentieren oder erläutern? --bs

nur halt etwas lambdaisiert, aufgemotzt und tiefergelegt. Benötigt eine zusätzliche Variable; löscht den Aufrufparamter m.
def rot(l,m):
    v = [] m, # v[0] ist die Anzahl rotierungen
         len(l)-1, # v[1] ist die Anzahl der Listenelemente minus 1         
         0, # v[2] ist eine lokale Variable, noch blutjung & unbenutzt
       # das nächste lambda hier ist die xor swap-funktion. Die Parameter sind x=Liste, 
       # i=zu vertauschende Position, j=zugriffsfunktion.
       # Die Zugriffsfunktion schaut so aus: "liste.__setitem__(index,wert)"  was "liste[index]=wert" entspricht.
       # die Funktion ist total simpel, nur dank der Lambdarestriktionen (in python) auf den ersten hieb unübersichtlich. 
       
       lambda x,i,j:(j(i,x[i]^x[i-1]),j(i-1,x[i]^x[i-1]),j(i,x[i]^x[i-1])),

       # das ist, wie unschwer erkennbar, eine WHILE-Schleife in Lambda. Beachte, daß es sich um v[4] handelt, und v[4] rekursiv
       # am Ende ("tail-recursiv" für Fachwortfetischisten) aufgerufen wird; sofern die while-bedingung (v[2]>0) erfüllt ist.
       # der loop-body ruft v[3] auf (swap) und dekrementiert die Variable v[5]. Was ist v[2] -> siehe nächstes lambda.

       lambda:v[2]>0 and (v[3](l,v[2],l.__setitem__),v[5](2,v[2]-1),v[4]())

       # v[5] ist eine lokale Variable
       0,

       # noch eine while-schleife, über ... guess what ... die anzahl rots (v[0]). Wieder wird v[6]=selbst am ende aufgerufen.
       # der body setzt v[2]=v[1], ruft v[4] auf, zählt v[0] um 1 runter. 

       lambda:v[0] and(v[5](2,v[1]),v[4](),v[5](0,v[0]-1),v[6]()) []

    # na, das findest du selber raus, oder ? 
    v.__setitem__(5,v.__setitem__) or v[6]()

mit ein bischen scharf ansehen hätte man z.b. das xor-ding gut erkennen können; und dann muß man nur noch den lambda-while-ersatz kennen.
Aufgabensteller der zweiten Runde

Fragen

Soll die Lösung als Funktion in einer beliebigen Sprache formuliert werden, oder genügt eine Beschreibung des Algorithmus?

Es reicht eine Beschreibung des Algoritmus. --gR

Ist n aus der Menge der natürlichen Zahlen einschließlich 0? Und ist M eine nichtleere Menge? Und ist die Anzahl der Elemente in M immer größer oder gleich n? --bs

Siehe oben: -M < n < M, aber eigentlich reicht es, den Algorithmus für 0 < n < M zu beschreiben, denn -n ist hier äquivalent M-n, und für 0 ist es trivial.

Okay, nun verstehe ich das auch. Aber ist es nicht mathematisch unkorrekt, wenn man schreibt: -M < n < M? Müßte es nicht eher heißen card -M < n < card M, da die Kardinalität gemeint ist?
Aber nochmal konkret: soll nun 0 < n < card M betrachtet werden oder die ursprüngliche Aufgabe. Wie klein auch immer die Änderung wäre, so muß der Algorithmus doch auf jeden Fall entsprechend angepasst werden, und auch bei einer trivialen 0...:-) --bs

Wenn du dir die Aufgabe oben mal richtig durchliest, merkst du vielleicht, dass M _nicht_ das Array bezeichnet. -- vgl

Hmm, warum dann ein großes M und kein kleines? Find ich etwas mißverständlich, obgleich Du recht hattest, daß ich nicht genau hingeschaut habe :-) Na, mir soll's so recht sein. Ist denn nun 0 die untere Grenze oder -M, und wenn 0 trivial ist, warum dann nicht 1? -- bs

Mea culpa mit dem großem M. Und wie schon gesagt, eine Lösung für n < 1 läßt sich von der Lösung n >= 1 ableiten. Es reicht also eine Lösung für n >= 1. --gR

Großbuchstaben als Platzhalter für Obergrenzen/Maximalwerte u. ä. zu benutzen, ist in der Mathematik durchaus üblich...

Kleine Anmerkung: IMO ist geringstmöglicher Speicherverbauch und maximale Performance nicht unbedingt gleichzusetzen. Man _kann_ natürlich mit nur einem temporären Speicherplatz und ziemlich vielen Vertauschoperationen auskommen. Ok, aber um Performance geht's ja hier nicht ;-) -- GerhardHäring

Na ja, wir haben hier schon Lösungen, die im Speicherbedarf optimal sind (ich zähle hier nur Platz für die Elemente des Arrays, nicht die Variablen für Indizes und auch nicht die Stackgröße.*) Also bleibt bei der Bewertung der Algorithmen Eleganz, Einfachkeit und Performance ein Kriterium. Aber hier geht es, zumindest ich sehe es so, nicht umbedingt um den Gewinner, sondern um den Spaß an Algorithmen :-)

Stackgröße wird hier nicht berücksichtigt, weil alle bisherigen Lösungen, die Rekursion anwenden, eine TailRecursion anwenden. Die Größe der Variablen, die nicht für Elemente des Arrays verwendet werden, würde sicherlich in einer konkreten Implementierung für konkrete Elementtype eine Rolle spielen. --gR


/Auswertung
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 22. Mai 2003 18:15 (diff))
Suchbegriff: gesucht wird
im Titel
im Text