Arrays vertauschen

[jonsen2.0.0.9]

Schreibe eine procedure vertausche( i, j:integer), welche den Inhalt der zwei Arrayelemente i und j eines Arrays zahl vertauscht.

gegeben sei dazu:
a) ein global deklariertes Array zahl.

zahl:Array[1..100] of integer;

dies ist eine aufgabe die ich in der schule bekommen habe.

leider weiss ich und der rest der klasse nicht genug um diese zu lösen.

hoffe ihr habt eine lösung oder tipps für mich.

MFG
Jonsen

[himitsu]

Vertauschen:

- man nehme eine temporäre Variable vom Typ der zu tauschenden Felder
> also var temp: Integer;
- man "kopiere" den Inhalt einen Feldes in diese temporäre Variable
- nun ist das eine Feld frei und kann mit dem Inhal des anderen feldes gefüllt werden
- und nun muß nur noch der zwischengespeicherte Inhalt in das 2. Feld rein

[mkinzler]

Nennt man auch Deieckstausch.

[blink182]

man kanns auch eleganter lösen ;)

Delphi-Quellcode:

a[i]= a[i] xor a[j];
a[j]= a[i] xor a[j];
a[i]= a[i] xor a[j];

kurze erklärung:

a=5
b=7

a=101
b=111

a= a xor b = 101 xor 111 = 010
b= a xor b = 010 xor 111 = 101
a= a xor b = 010 xor 101 = 111

blink

[MStoll]

@blink182:

man mag damit Speicher sparen, ok. Aber es ist a) schwerer zu lesen und b) langsamer als die Standard-Variante, da letztere vom Compiler gut optimiert werden kann.

Von daher bringt es für den TE wohl nichts, da er - wie man an der Fragestellung sieht - sicherlich andere, eher elementare Probleme hat, als sich mit solchen mathematischen Tricks zu befassen.

[himitsu]

Zitat:

Zitat von MStoll

langsamer als die Standard-Variante, da letztere vom Compiler gut optimiert werden kann.

Jupp

Dreieck: 3 Lese- und 3 Schreiboperationen ... optimiert je 2 Lese-/Schreiboperationen

XOR: 6-mal Lesen, 3-mal Verknüpfen und 3-mal Schreiben ... läßt sich im Vergleich nur unwesendlich optimieren und wenn, dann wird's nur nochunübersichtlicher




Also maximal dann geeignet, wenn man viele zusamenhängende Daten tauschen muß und dazu noch Zeit, aber ungenügend Speicher hat.

Aber ein von der Logik her, isses schon irgendwie OK.

[gammatester]

Zitat:

Zitat von blink182

man kanns auch eleganter lösen ;)

Delphi-Quellcode:

a[i]= a[i] xor a[j];
a[j]= a[i] xor a[j];
a[i]= a[i] xor a[j];

kurze erklärung:

a=5
b=7

a=101
b=111

a= a xor b = 101 xor 111 = 010
b= a xor b = 010 xor 111 = 101
a= a xor b = 010 xor 101 = 111

blink

Zusätzlich zu dem was MStoll bereits geschrieben hat:

a und b als nicht arrays zu nehmen ist doch wohl auch nicht sehr sinnreich. Weiter: nimm mal ein arrays
a[0]=3 und a[1]=4. Dann vertausche mit Deinem xorcode die Elemente a[0] und a[0]. Augen reiben, wundern, Erklärung suchen.

[blink182]

Okay vllt nicht sehr rechenzeit optimiert, dafür weniger speicherplatz

ja das macht wenig Sinn... Muss man halt checken, dass j<>i ist.
Aber selbe zahlen kann man ja trotzdem vertauschen ;-)

11 xor 11 = 00
00 xor 11 = 11
00 xor 11 = 11

aber okay, der dreieckstausch ist da sinnvoller. Ist auch das was man normal macht

[mkinzler]

Zitat:

Okay vllt nicht sehr rechenzeit optimiert, dafür weniger speicherplatz

Was bei modernen Rechner ein absolutes Problem ist :mrgreen:

[Sherlock]

Jetzt habt Ihr Jonsen erschreckt...

Sherlock

[jonsen2.0.0.9]

hmmm...DANKE für eure tipps...

er hat die aufgabe ein wenig geändert -.-

jetzt sollen wir array[1..100] mit zufallszahlen von 1-1000 beschreiben.

und dann immer die nebeneinander liegenden tauschen.

hab zu folgender lösung eine frage.

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    ListBox1: TListBox;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  ar:array[1..100] of integer;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
randomize;
end;

procedure fuellen();
Var i:integer;
begin
for i:=1 to 100 do
 ar[i]:=random(1000)+1;
end;

procedure tauschen() ;
Var i,j:integer;
 i2:integer;
 temp:integer;
begin
i:=0;
j:=0;
for i2:=1 to 99 do
 begin
 i:=i2;
 j:=i2+1;
 temp:=ar[i];
 ar[i]:=ar[j];
 ar[j]:=temp;
 end;
end; 

procedure TForm1.Button1Click(Sender: TObject);
Var i:integer;
begin
 fuellen;
 tauschen;
for i:=0 to 99 do
 begin
 listbox1.Items.Delete(i);
 listbox1.items.Add(inttostr(ar[i]));
 end;
end;

end.

dies müssen wir mit den proceduren fuellen und tauschen machen.

diese programm müsste doch wirklich tauschen?

also funktioniern, so wie es soll.

nachdem ich die anderen zwei teilaufgaben gelöst hab werd ich euch wieder schreiben

DANKE nochmal :)

MFG
Jonsen

[Amateurprofi]

Zitat:

Zitat von blink182

Okay vllt nicht sehr rechenzeit optimiert, dafür weniger speicherplatz

ja das macht wenig Sinn... Muss man halt checken, dass j<>i ist.
Aber selbe zahlen kann man ja trotzdem vertauschen ;-)

11 xor 11 = 00
00 xor 11 = 11
00 xor 11 = 11

aber okay, der dreieckstausch ist da sinnvoller. Ist auch das was man normal macht

Nein und nochmal nein.
Das erste Nein zu "Aber selbe zahlen kann man ja trotzdem vertauschen ;-)"
Bei deiner obigen Darstellung
11 xor 11 = 00
00 xor 11 = 11
00 xor 11 = 11
machst du einen Denkfehler. Tatsächlich wird (wenn j=i ist) folgendes gerechnet.
11 xor 11 = 00
00 xor 00 = 00
00 xor 00 = 00
Das zweite Nein zu "dafür weniger speicherplatz"
Die zusätzliche lokale Variable wird überhaupt nicht angelegt, weil (bei eingeschalteter Optimierung) ein CPU-Register für die Zwischenspeicherung verwendet wird. Auch bei ausgeschalteter Optimierung kostet die zusätzliche Variable im Prinzip keinen Speicherplatz, weil sie auf dem Stack angelegt wird, und der ist (unabhängig von lokalen Variablen) eh' schon vergeben.
Aber : bei ausgeschalteter Optimierung ist (in Bytes gemessen) deine Prozedur deutlich länger und das kostet dann tatsächlich Speicherplatz.

[DeddyH]

Und wieder zurück zum Thema *g*. @Jonsen: Du solltest Dir gleich eine nachvollziehbare Einrückung angewöhnen, dann können auch andere Deinen Code besser lesen. Und ich persönlich würde das etwas anders machen:

Delphi-Quellcode:

procedure tauschen(var a, b: integer);
var temp: integer;
begin
  temp := a;
  a := b;
  b := temp;
end;

//der Aufruf könnte dann so aussehen
for i := Low(ar) to High(ar) - 1 do
  tauschen(ar[i],ar[i + 1]);

[jonsen2.0.0.9]

wieso high(ar) -1

wenn ich high richtig verstehe gibt das wenn mein array von 1-100 gehe doch 100 zurück oder?

wieso muss dann die minus eins dahin?

UND

Delphi-Quellcode:

tauschen(ar[i],ar[i + 1]);

so rufst du ja auf.

aber die ar[i],ar[i+1] sind doch dann eigentlich wenn ich ne procedur aufrufe variablen die vorher

Delphi-Quellcode:

procedure tauschen() ;  //in der klammer hinter tauschen stehen müssten
Var i,j:integer;
i2:integer;
temp:integer;
begin
i:=0;
j:=0;
for i2:=1 to 99 do
begin
i:=i2;
j:=i2+1;
temp:=ar[i];
ar[i]:=ar[j];
ar[j]:=temp;
end;
end

stimmt doch oder?

wenn nich...sorry aber so hab ichs gelernt .

DANKE trotzdem

MFG
Jonsen

[implementation]

Zitat:

Zitat von jonsen2.0.0.9

jetzt sollen wir array[1..100] mit zufallszahlen von 1-1000 beschreiben.
[delphi]ar:array[1..100] of integer;

Wer macht denn sowas? :shock:
Smallint/Word reicht doch völlig aus. Die restlichen 2 Byte sind doch überflüssig.

[Valle]

Zitat:

Zitat von implementation

Wer macht denn sowas? :shock:
Smallint/Word reicht doch völlig aus. Die restlichen 2 Byte sind doch überflüssig.

Lediglich fortgebildete Informatiklehrer, die von der Materie nicht viel Ahnung haben und für die eine Zahl par tout gleich "Integer" ist. :zwinker: Das Thema hatten wir hier im Forum schon irgendwo, also bitte nicht den Thread missbrauchen, auch wenn ich gerade dazu eingeladen habe. :angel2:

Liebe Grüße,
Valle

[DeddyH]

Zitat:

Zitat von jonsen2.0.0.9

wieso high(ar) -1

wenn ich high richtig verstehe gibt das wenn mein array von 1-100 gehe doch 100 zurück oder?

wieso muss dann die minus eins dahin?

Richtig, und da wir beim Tauschen um 1 inkrementieren

Zitat:

Delphi-Quellcode:

tauschen(ar[i],ar[i + 1]);

, müssen wir vorher dafür sorgen, dass wir keine Bereichsüberschreitung provozieren ;)