5.2

[Septic.exe]

K ... ich fang mal an, bei einem Teil bin ich mir noch nicht sicher:

- suche im Feld A[1] ... A[n] jenes mit dem kleinsten key
- addiere jenen key mit dem key aus dem Feld D[1] ... D[n] mit dem selben Index und addiere 5 hinzu (Das komplette Ergebnis speichere in der Variablen zB x.)
- suche im Feld A[1] ... A[n] jenes mit dem "nächstkleineren" Index (Den key hieraus speichere in der Variablen zB y.)
- falls x < y tu nichts
- falls x = y tu nichts
- falls x > y dann erhöhe die Variable m (m wird mit 2 initialisiert.) um 1
- rufe den Algorithmus rekursiv auf mit dem "nächstkleineren" key A[1] ... A[n]
- gib m aus

Jetzt bin ich mir nur noch nicht sicher wie man am besten (und vor allem am einfachsten) ausführt, was der Algorithmus machen soll, wenn zB beim dritten Durchlauf der Tankwagen vom ersten Durchlauf bereits fertig ist (was man natürlich für jede "Kombination" beachten muß). Kann sein, daß das total simpel is und ich auf der Leitung steh ... vielleicht kann mich wer runterheben ;)?

[winterspeck]

und zaw folgendermaßen muss man sich das Vorstellen...
hier mal der Pseudo

Algorithmus Schwechat (A, D, N)
Input: Feld A, Feld, D und N = Anzahl der Flugzeuge
Output: T = Anzahl der benötigten Tankwagen

Initialisiere:
Sortiere zuerst D nach den Schlüsseln von A und dann sortiere A.
i = 0;
z= 0 ;
T = 3;
Betankt[n] == 0 für alle n <= N
tanken (1);

tanken (x);
falls Betankt[x] == 0 & i <= A[x].key dann {
Betankt[x] == 1;
z = z + 1;
i = A[n] + D[n] + 5;
}
falls x = N dann {
falls z = N dann {
Ausgabe T;
} sonst {
T = T+1;
i = 0;
tanken(1);
}
}sonst { tanken (x + 1);}

Hier die hoffentlich ausreichende Erklärung:

Der Funktion tanken basiert auf folgender Idee. Man nehme zuert einmal fix einen Tankwagen und prüft wieviele Flugzeuge dieser eine Tankwagen schafft. und setzt diese FLugzeuge auf Betankt = 1; Ist dieser Tankwagen beim letzten Flugzeug angekommen aber es sind noch immer nicht alle Flugzeuge betankt, braucht noch zusätzlich einen Tankwagen und spielt das ganze von vorne. Für weitere Erklärungen einfach posten,, mag jetzt nimma

[Septic.exe]

Is natürlich auch ned "deppert" ;). Klingt leichter lösbar als mein "Erguss" ;).

[nonamenobody]

Kann man es nicht auch ganz primitiv machen, indem man überprüft, wieviele Tankwagen zu jedem Zeitpunkt (immer dann, wenn ein Flugzeug getankt werden soll) gebraucht werden? Ich hab mir das jetzt nicht genau durchgedacht, vielleicht ist ein Denkfehler dabei.

lg
Philipp

[MrAngel]

Hi Leute!

Ich hab den Ansatz von Winterspeck genommen, und hab da einen Pseudocode geschrieben, wie es für Aufgabe 3 verlangt wird, kann mir jemand sagen, ob ich einen Denkfehler drin hab, weil ich hab nach mehrmaligen korrigierren keinen gefunden.

Ich glaub der Aufwand ist auch nur O(n), kann das sein??

Pseudocode:

Algo Schwechat (A,D,N)

// Initalisierung
AT = 2; // AT...Anzahl Tankwagen (min 2)
Setze für alle Flugzeuge betankt auf false; // betankt[n]
AB = 0; // AB... Anzahl betankter Fluzeuge
i = false; // wird auf true gesetzt, wenn ein
neues flugzeug zum betanken gefunden
wurde
z = 0; // Hilfsvariable

wiederhole solange {
AT++; // Anzahl Tankwagen +1

Für alle ( n<=N ) { // es werden die einzelnen Fluzeuge durchlaufen

Falls ( betankt[n] == false ) dann { // Flugzeug schon betankt??
betankt[n] = true; // falls nein, betankt ja setzen
AB++; // Anzahl betanlter Flugzeuge +1
z = n+1; // Hilfsvariable = n+1

wiederhole solange {
i = false; // i auf false setzen (initialisierung)

Falls ( A[n]+D[n]+5 <= A[z] ) dann { // falls sich zeitlich ausgeht nächstes Flugzeug
i = true; // Flugezug zum betanken gefunden
n = z; } // Nummer des Flugzeug merken
else {
z++; } // falls nein, nächstes Flugzeug
} bis ( z >= N oder i = true ); // solange noch Flugzeuge gibt, oder eines gefunden
}
}
} bis ( AB == N ); // solange nicht jedes Flugzeug betankt wurde


Danke
MFG MrAngel

[templar]

Ich hab mal auch was ähnliches in Java ausprogrammiert, funktioniert nach dem Prinzip: Teste für jeden Tankwagen, welche Flugzeuge er maximal übernehmen kann und füge bei Bedarf zusätzliche Tankwagen hinzu.


int i = 0; //noch keine Flugzeuge aufgetankt
int t = 2; //2 Reservewagen
int[] betankt = new int[n];
for (int j = 0; j < n; j++) {
betankt[j] = 0;
}
while (i < n) { //solange es noch nicht betankte Flugzeuge gibt
t++; //zusätzlicher Tankwagen benötigt
int z = 0; //zu Beginn ist jeder Wagen verfügbar
for (int k = 0; k < n; k++) { //für jedes Flugzeug
if (betankt[k] == 0 && a[k] >= z) { //Tankwagen frei
betankt[k] = t;
z = a[k] + d[k] + 5; //besetzt bis z
i++;
}
}
}

A und D sind vorher aufsteigend nach den Schlüsseln von A sortiert.
i...Zähler für betankte Flugzeuge
t...Anzahl der benötigten Tankwagen
z...gibt an, wann ein Wagen wieder "frei" ist.

Hab in auch schon mit ein paar Werten getestet, dürft halbwegs stimmen, oder? Bei Interesse kann ich auch den ganzen Code posten.

[MrAngel]

zu Templar:

Glaub dein Code passt so, meiner funktioniert auf ähnliche weiße, wenn nicht so gar ganz gleich (nur andere Variablen).

MFG MrAngel

[JackOrlando]

i=n;

für A[i].. A[1] {
j=n; x=1
für A[j].. A[1] {
falls A[j] in nach Mitternacht{
d=D[j] / 2;
} sonst{
d=D[j];
}
falls A[i] >= A[j] UND A[i] < A[j]+d+5 {
x=x+1; //wie viele Wagen brauct man gleichzeitig
}
}
falls wagen < x { wagen = x; }
}

ausgabe wagen;
-----------------------------------------

so ist das algorithmus O(n2)
und ich habe gedacht (der einfachheit halber in minuten nach mitternacht) verursacht diese psuedecode
falls A[j] in nach Mitternacht{
d=D[j] / 2;
} sonst{
d=D[j];
}

wenn ich falsch verstanden habe, bitte schreiben...

[grassi3000]

Edit: schon kapiert

[bosie]

glaube auch net dass dieser code stimmt.
du kontrollierst nämlich nicht ob tankwagen frei sind oder? bzw wie du es kontrollierst kann ja net stimmen

[QN82]

Hi Leute!

Ich hab den Ansatz von Winterspeck genommen, und hab da einen Pseudocode geschrieben, wie es für Aufgabe 3 verlangt wird, kann mir jemand sagen, ob ich einen Denkfehler drin hab, weil ich hab nach mehrmaligen korrigierren keinen gefunden.

Ich glaub der Aufwand ist auch nur O(n), kann das sein??

Pseudocode:

Algo Schwechat (A,D,N)

// Initalisierung
AT = 2; // AT...Anzahl Tankwagen (min 2)
Setze für alle Flugzeuge betankt auf false; // betankt[n]
AB = 0; // AB... Anzahl betankter Fluzeuge
i = false; // wird auf true gesetzt, wenn ein
neues flugzeug zum betanken gefunden
wurde
z = 0; // Hilfsvariable

wiederhole solange {
AT++; // Anzahl Tankwagen +1

Für alle ( n<=N ) { // es werden die einzelnen Fluzeuge durchlaufen

Falls ( betankt[n] == false ) dann { // Flugzeug schon betankt??
betankt[n] = true; // falls nein, betankt ja setzen
AB++; // Anzahl betanlter Flugzeuge +1
z = n+1; // Hilfsvariable = n+1

wiederhole solange {
i = false; // i auf false setzen (initialisierung)

Falls ( A[n]+D[n]+5 <= A[z] ) dann { // falls sich zeitlich ausgeht nächstes Flugzeug
i = true; // Flugezug zum betanken gefunden
n = z; } // Nummer des Flugzeug merken
else {
z++; } // falls nein, nächstes Flugzeug
} bis ( z >= N oder i = true ); // solange noch Flugzeuge gibt, oder eines gefunden
}
}
} bis ( AB == N ); // solange nicht jedes Flugzeug betankt wurde


Danke
MFG MrAngel

Was ist das N in deinem Code?
außerdem verstehe ich den schritt z = n+1 nicht, wofür ist das gut?
wäre echt super wenn du mir das erklären könntest.

lg, qn

[bosie]

mein vorschlag

int n = 5; //Anzahl der FZ
int i = 0; //noch keine Flugzeuge aufgetankt
int t = -1; //Wagen
int[] A = new int[n];
int[] W = new int[n]; //Wagen
int[] D = new int[n];

// setzen der variablen
for (int j = 0; j < n; j++)
{
D[j] = 15;
A[j] = j*5;
W[j] = 0;
}

bool create = true;
while(i < n)
{
int z = 0;
for(z = 0; z < t;z++)
{
if(A[i] > W[z])
{
create=false;
break;
}
}
if(create)
{
t++;
W[t] = A[i]+D[i]+5;
}
else
{
W[z] = A[i]+D[i]+5;
}

i++;
create=true;
}