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

• Anonym. Sich hinsetzen, überlegen, eine Lösungsweg skizzieren, nach 1-2 Tagen(*) vergleichen mit hier gegebenen Auflösung.
• Angemeldet. Man trägt sich unten in die Teilnehmerliste ein. Schickt eine Lösung via E-mail an den Aufgabensteller. Dieser postet nach 1-2 Tagen die Lösungen und verteilt die virtuellen Preise.
• Kommunikativ. Man hat eine Lösung, ist sich aber nicht sicher, ob sie optimal ist (sie ist es wahrscheinlich nicht) und postet sie unten im Diskussionsbereich. Man kooperiert bis die Erleuchtung kommt.
• Unfair. Man postet als Genie die perfekte Lösung sofort hier, erklärt das Problem für trivial und qualifiziert sich somit als Aufgabensteller für die nächste Runde.

Offizielle Teilnehmerliste

• ...... <== hier eintragen
• AndreasBühmann (auch per Mail)
• Ralf Wildenhues (habe email geschickt)
• MichaelSchikora, fast wie Michael Knaup:

#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); } }

• Na ja, es ist wirklich nur "fast" wie Michael. Seine Lösung ist O(M), Deine ist O(M*n). Von Speicherbeadrf, was das Primärkriterium ist, aber sehr effizient. Du brauchst nur einen zusätzlichen Parkplatz, dafür muss Du aber jedes Auto umgefähr n-mal starten. Michael startet jedes Auto im Schnitt unter 2-mal.
• Eine Überlegung von mir war halt, keine weiter Hilfsvariable zu gebrauchen, als die sowieso schon vorgegebenen. Was der Compiler dann wirklich draus macht, mal voellig aussen vor gelassen.

• HelmutLeitner (ich schicke e-mail)
• MichaelKnaup, wie wärs damit - ANSI-C: (Laufzeit: O(m), Speicherverbrauch: inplace für ints bzw. 1 A Objekt für std. swap)

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] ist eine Speicheroptimierung für Ints, nicht für andere Typen (z.B. Autos) Allgemein wäre für Swap also 1 Speicherplatz nötig. (mehr Kommentar am Samstag) Übrigens: man kann den Swap, glaube ich, kompakter schreiben:--gR

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

• Das swappen durch 3-fach xor funktioniert zumindest für alle Arrays die sich auch mittels qsort() sortieren lassen, d.h. für alle Arrays deren Elemente sich ohne Seiteneffekte verschieben lassen. Meiner Meinung nach ist der Sequenzoperator ',' bzw. das ';' notwending. Der Vollständigkeit halber noch eine iterative Variante: (Michael Knaup)

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; } }

• Wieso meinst Du, dass der Operator "," oder das ";" notwendig sind? Sonst hast Du recht, dass man das 3x-XOR in C verwenden kann um beliebige Typen zu vertauschen. In C++ würde sich die Sitaution aber sjon anders darstellen. Man kann da nämlich Typen definieren, die sich zwar problemlos verschieben (und somit vertauschen) lassen, ein XOR aber nicht möglich ist - oder funktioniert nicht so, wie wir es hier brauchen würden. (Z.B. könnte man einen Typ deffinieren, bei dem der 3x-XOR zwar die Werte der Objekte zwar vertauschen würde, nicht aber deren Identität). Da ich davon ausgehe, dass der XOR-Paritätstrick sich bei jeder Methode, bei der 1 Puffervariable benötigt wäre, (z.B. die n-fache Rotation um 1 Element), bewerte ich die Methoden gleich. (Wir können uns darüber unterhalten, ob wir sie alle als eine Inplace- oder 1-Element-Lösung bewerten)
• Ich weiss natürlich nicht, warum Michael Kaup meint, dass ein Sequenzpunkt nötig ist, aber auf jedenfall ist zwischen zwei Wertänderungen ein Sequenzpunkt notwendig. Der Zuweisungsoperator ist kein Sequenzpunkt, der Komma-Operator ist ein Sequenzpunkt.

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

hat in C undefiniertes Verhalten.

A[i] ^= A[j], A[j] ^= A[i], A[i] ^= A[j];

dagegen kann das gewünschte leisten. -- KurtWatzka

• Ich schliesse mich der Meinung von Kurt an, denn der Standard schliesst nicht aus, dass ein Compiler folgenden PseudoAssemblerCode? generiert

load,REG1,A[i] load,REG2,A[j] load,REG3,A[i] xor,REG3,A[j] store,A[i],REG3 xor,REG2,A[i] store,A[j],REG2 xor,REG1,A[j] store,A[i],REG1

MichaelKnaup

• Ich bin kein C-Experte und lasse ich gerne belehren. Mir ist nicht ganz klar, warum

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

  in C undefiniertes verhalten hat. Ist das wirklich so, dass C

  a ^= b ^= a ^= b

  anders als

  a ^= ( b ^= ( a ^= b ))

  auwerten kann? --gR
• Meines erachtens nach ist dein Code äquivalent zu

  a = a ^ (b = b ^ (a = a ^ b))

  Nach dem Standard kann jetzt nicht ausgeschlossen werden dass zunächst das a aus dem äußerstem XOR in ein 1. Register geschrieben wird, das b in ein 2. Register und das a des innersten XORs in ein 3. Register. Dann bleibt das a im 1. Register unverändert (vgl. dazu meinen obigen Pseudo Assembler Code). -- MichaelKnaup
• Danke, jetzt is es mir klar. --gR

• Es geht noch ein wenig eleganter :-): -- MichaelKnaup

void rotate(int *const A, const size_t M, int n) { register int i = 0; assert(A != NULL && M != 0); if (abs(n) > M) /* für beliebige n */ n = (n < 0) ? -(-n % M) : n % M; if (n < 0) n += M; while (i = (i + n) % M) /* Die Rotation */ A[0] ^= A[i], A[i] ^= A[0], A[0] ^= A[i]; }

• Elegant ist es schon, aber funktioniert es auch? Kleiner Test:

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

• Ich denke jetzt so gehts -- MichaelKnaup

void rotate(int *const A, const size_t M, int n) { register int i, j; assert(A != NULL && M != 0); if (abs(n) > M) /* für beliebige n */ n = (n < 0) ? -(-n % M) : n % M; if (n < 0) n += M; /* ggT liefert den größten gemeinsamen Teiler */ for (i = j = 0; j < ggT(M, n); i = ++j) { while ((i = (i + n) % M) != j) A[j] ^= A[i], A[i] ^= A[j], A[j] ^= A[i]; } }

Stolperdrat erkannt und übersprungen :-) --gR

• GerhardHäring, hier die meiner Meinung nach optimale Lösung in SprachePython. Ich beschreib mal schnell den Algorithmus. Wenn n die Anzahl der Schritte ist, nehme man n Mal das letzte Element der Liste und füge es vorne an. Somit funktioniert dieser Algorithmus "in-place" und der Speicherverbrauch ist damit denkbar gering:

def rot(lst, n): if n < 0: n = len(lst) + n for i in xrange(n): lst.insert(0, lst.pop(-1))

• Tja, es kann durchaus sein, dass dies in SprachePython nicht effektiver zu machen ist, aber eine optimale Lösung wäre es nur dann, wenn lst.insert(0, ...) und lst.pop(-1) keine konstante Komplexität hätten. (Was aber durchaus sein könnte, wenn Python Listen als verkette Listen implementiert.) Versuche aber eine Lösung für ein Array zu finden, d.h. Speicher, in dem die Elemente hintereinander liegen. Versuche über den Algorithmus, nicht über eine Implementierung in einer konkreten Sprache nachzudenken. --GregorRayman
• Die Komplexität von lst.insert ist n, die Komplexität von lst.pop ist konstant. Die Implementierung von Listen in Python ist ein zusammenhängender Speicherbereich, in dem Zeiger auf die Objekte liegen (also eine Indirektion). Ok, wenn ich viel Zeit haben sollte, versuch ich noch mal eine Lösung mit array.array (zusammenhängender Speicherbereich fester Größe) --GerhardHäring
• So gesehen entspricht Deine Lösung umgefähr der von MichaelSchikora.

• BerndSchiffer (hab Email geschickt)
• VolkerGlave, eine - nun ja - Lösung folgt hier direkt, eine zweite per E-Mail. Ich verwende die SpracheJ ( http://www.jsoftware.com/download/download.htm). Die Prozedur (der Begriff in J dafür ist: Verb) nenne ich "rot". Es passt gut, dass wir einerseits ein Array und andererseits die Anzahl zu rotierender Elemente als Input haben, so sei "rot" ein dyadisches Verb mit dem Array auf der linken Seite und der Anzahl zu rotierender Elemtente auf der rechten Seite. Also, hier die Lösung: rot=:|.~-. Drei Tests: 1 2 3 4 5 6 rot 2 liefert 5 6 1 2 3 4; 3 1 4 rot 0 liefert 3 1 4; 3 4 5 6 rot _1 liefert 4 5 6 3 (_1 ist J-Notation für "minus Eins"). Sieht gut aus. "Versuche Speicherbedarf zu minimieren.", mhhh, lieber nicht, ich überlass das bis auf weiteres J.
• Ich gebe demütig zu, dass ich SpracheJ nicht kenne. Könntest Du versuchen zu beschreiben, was bei "rot" eigentlich abgeht? Werden neue Arrays erstellt? Wie schätzt Du den Spreicherbedarf und die Zeit ein? --gR
• "rot" verschleiert nur ein wenig den Umstand, dass das Rotieren von Arrays in J ein eingebautes Verb ist. Neben "rot" enthält der gegebene Satz die Bestandteile =: (Zuweisung/Copula), |. (Rotate), ~ (Passive, bewirkt Links-/Rechtsvertauschung der Argumente von Rotate) und - (Negate des rechten Arguments, weil Rotate deiner Vorgabe entgegengesetzt rotiert). Die anderen Fragen kann ich nicht beantworten, kenne J nämlich nur äußerst oberflächlich (und meine Lösung wird ein krude, wenn nicht falsche sein). -- vgl
• Dann ist es aber nicht so richtig eine Lösung der Aufgabe, die Aufgabe wird hier bloss der Programmiestprache überlassen. Wäre die Aufgabe, ein Array zu sortieren, würde ich auch den PHP-Aufruf sort($A) nicht als eine echte Lösung sehen. :-)
• "... nicht so richtig eine Lösung ...": Jedoch in dieser Hinsicht analog den übrigen vorgestellten Lösungen, die alle ebenfalls vorhandene Konstrukte ihrer jeweiligen Programmiersprache nutzen (len, insert, +, ++, --, *, if, for, #define, while, ...). -- vgl
• Gewiss ist das eine Lösung. Leider habe ich in der Aufgabenstellung das Wort Prozedur statt Algorithmus verwendet. Gerade deswegen habe ich, leider erst später, die Bemerkung über das Umparken der Autos hinzugefügt. Aus den oben beschriebenen C-Lösungen und aus den Lösungen, die ich per Mail erhalten habe, geht hervor, wie man bei dem Umparken der Autos vorgehen soll (bis auf die swap-Kleinigkeit). Aus Deiner geht das leider nicht hervor. Aber, wie gesagt, beide sind auch korrekte Lösungen der Aufgabe, wie sie gestellt wurde, wenn auch nicht im Sinne, wie sie gedacht war :-) --gR

• MichaelKnaup, in einer OO-Sprache besteht eine Lösung darin: Eine Klasse zu definieren, die ein Array kapselt und die Rotation einfach durch Index-Arithmetik zu ersetzten. Laufzeit für die Rotation O(1), Speicherverbrauch: Klassenoverhead und eine Variable vom Indextyp für den Rotationsoffset. Der Elementszugriff würde sich allerdings (maximal) um eine Addition und ein Modulo verlangsamen.
• IljaPreuß (konkrete Umsetzung von MichaelKnaups Idee in Java unter Verwendung des ProxyMuster?):

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

• Instanzvariable rotation fehlt noch. Methode get() scheint mir noch nicht richtig zu sein, z. B. get(-1) müsste doch eigtl. eine IndexOutOfBoundsException schmeissen, was sie aber nicht tut, oder? Müsste eigtl. set() nicht definiert sein, sonst könnte ja nach dem Rotieren nur noch lesend in die Liste gegriffen werden? -- vgl
• Ich sehe auch noch einige Probleme, wenn ich mich Richtig erinere ist Modulo für negative Zahlen nicht eindeutig definiert (sollte in Java aber egal sein, da es wohl durch die Sprache standartisiert wird). Weiter sollte die Rotation invers zum obigen Beisiel verlaufen.
• Ja, alles gültige Argumente :-). Wer - im Gegensatz zu mir - gerade die Zeit hat, darf das gerne korrigieren. -- ip

Hier meine minimal version in C++: --MichaelKnaup

template<class T> class MeinArray { T *elemente; std::size_t anzahl; std::size_t offset; public: MeinArray(const std::size_t Anzahl); MeinArray(const MeinArray<T>& Quelle); virtual ~MeinArray(); MeinArray<T>& operator= (const MeinArray<T>& quelle); T operator[] (const std::size_t Index) const; T& operator[] (const std::size_t Index) { return elemente[(Index + offset) % anzahl]; } int size () const; void rotate(const int off) { /* Die Rotation verläuft invers zur Aufgabenstellung */ if (off > 0) offset += (anzahl - (off % anzahl)); else offset += (-off) % anzahl; offset %= anzahl; } };

• MichaelKnaups Idee ist sicherlich die "most sexy", und jeder der z. B. einen zyklischen Puffer mit konstanter Speichergröße implementieren muss, sollte sie in Betracht ziehen. Allerdings entspricht sie nicht der Aufgabenstellung, in der es darum geht, in einem vorhandenen Array die Elemente zu rotieren, und nicht eine neue verbesserte Variante eines Arrays anzuwenden. Allerdings bin ich begeistert von der Vorgehensweise, Probleme umzugehen statt sie zu beseitigen. YouDontNeedIt? :-) --gR
• Ich finde, Michael hat sich den "bunten Zylinder für Querdenker" verdient... ;-) -- IljaPreuß
• Genau. :-) Und für die register und 3xXOR auch noch den WardsWiki:PropellerBeanie. :-) --gR

• Gerson Kurz: Die folgende Lösung basiert auf "unscharfer Programmierung", die in Python 3.0 default sein wird.

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

• Gerson Kurz: Hey, "unscharfe Programmierung" ist /das/ kommende Dinge nach OOP, Eiffel, Patterns, Extreme Programming. Java ist nicht so gut in "unscharfe Programmierung" wie Python, deshalb meine obige Wahl. Eine Erläuterung findest du am Beispiel Quicksort hier http://p-nand-q.com/e/quicksort_lambda.html
• Ich auch sorry, aber hier geht es nicht unbedingt um eine Implementierung in einer konkreten Programmiersprache, sondern um einen Algorithmus. Aus dem obigem Quelltext kann man den Algorithmus nur äusserst schwer ableiten, und um ehrlich zu sein, fehlt mir ein wenig der Bock dies zu tun. Deswegen erlaube ich mir nur eine Kritik an den formellen Punkten Deines Quelltextes.
• Gerson: Es handelt sich um folgenden supersimplen Algorithmus, den bereits oben andere in anderen Sprachen formuliert haben:

def rot(l,m): while m: i = len(l)-1 while i > 0: l[i] ^= l[i-1] l[i-1] ^= l[i] l[i] ^= l[i-1] i -= 1 m -= 1

• Für meinen Geschmack benutzt Du zu viele ausgeschriebene Werte, wie 2, 3, 4, 5 und 6. Mir ist, ohne das Programm zu analysieren, deren Sinn nicht ganz klar. Mein Tipp: Benutze bennannte Konstanten statt ausgeschriebenen Werten.
• Gerson: Konstanten sind Namen für Leute, die Zahlen nicht unterscheiden können. (Ich bin im übrigen problemlos in der Lage, jeden Moment nicht völlig grundlos in eine Philippika über die Geisteslosigkeit von Java auszubrechen, die die bösen #defines durch die guten int consts ersetzt.) Es liegt in der """NATUR""" der Konstante, Konstante zu sein. Im übrigen sind die Zahlen Indizes in ein Array mit Variablen / Funktionen, das in der Funktion selbst aufgebaut wird. Die Funktion funktioniert prima mit listen von sagen wir 1860 elementen. Sechzig!
• Mensch, ich kann mir meine eigene Telefonnummer nicht merken. Und auch eine 69 muss ich mir notieren :-) Früher, als ich jünger war, habe ich auch mit

  copy con > setup.exe

  programmiert, aber wenn man aälter wird, und das Gedächtnis anfängt zu schwächeln...
• In der Aufgabenstellung ist die Rede von M und n. Eigentlich ist es mir gleich, ob Du die Parameter anders nennst, aber bitte, ein kleines l? Wie soll ich es von einer 1 unterscheiden?
• Gerson: Stimmt, ich hätte besser o und O verwenden sollen. Nein, ernsthaft, glaubst du wirklich, wenn man anstelle l->M, m->n schreibt, dann wird der Sourcecode auf einmal sonnenklar?
• Sonnenklar nicht, aber das Licht einer Kerze...

• Wieso hast Du die eine Anweisung auf drei Zeilen umgebrochen? Dem Python-Interpeter mag es egal sein, da die Anweiseung in Klammern steht, aber Menschen wie mich verwirrt es.
• Gerson: Würde ein umbrechen in vier Zeilen helfen? Seid ihr Programmierer oder Wimps?
• Nein, wieso überhaupt umbrechen. Dem Python tut es doch weh. Und sag nie wider Wimp zu mir, erstens weiß ich nicht, was dass ist, zweitens fühle ich mich dadurch beleidigt! :-) --gR

• Dies war eine "unscharfe Kritik" :-) --GregorRayman
• Gerson: Also gut, wenn ihr keinen Spaß versteht, hier ein "paar" Tips zu dem Sourcecode. Anm. Ich habe an zwei offensichtlichen Stellen "[" durch "[]" ersetzt, da das Wiki sonst die Hälfte des Textes abgeschnitten hat :(

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.

• Aua, meinst Du nicht, dass durch die Erklärung der Witz gekillt wird? Sozusagen entschärft? :-) --gR

• DavidSchmitt: Schon etwas zu spät (2002-12-01), aber in der "Shallow Introduction" der SpracheK, habe ich diese Perle gefunden:

  n!''liste''

• ... jedoch wird so genau andersherum rotiert, als laut Aufgabe verlangt. Also noch das Vorzeichen negieren (wie bei obiger SpracheJ-Lösung):

  (-n)!''liste''

  -- vgl

Aufgabensteller der zweiten Runde

• GregorRayman ( MAIL gregor (AT) grayman.de)
• Termin: Samstag 12. Oktober 2002

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

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...

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