Collatz Problem

[lasagne0504]

Hallo,

seit einiger Zeit Programmiere ich jetzt in Delphi, ich bin neu im Forum und habe jetzt mein erstes Problem .
Und zwar programmiere ich gerade ein Programm, welches mit einer Zahl nach dem Algorithmus des Collatz-Problemes verfährt (http://de.wikipedia.org/wiki/Collatz-Problem).
So sieht mein Quellcode aus:

var x,z:integer;


begin
x:=strtoint(edit1.Text);
z:=0;
if (x=0) or (x<0) then begin
showmessage('Die Zahl muss mindestens 1 sein!');
end else begin
while (x>1) do begin
if (x mod 2=0) then begin
x:= x div 2;
z:=z+1;
end else begin
x:=x*3+1;
z:=z+1;
end;
label1.Caption:='Nach '+inttostr(z)+' Schritten kommt 1 heraus.';
end;

end;


end;


Das Programm funktioniert mit (fast) alle Zahlen, die man eingibt, zumindest kam bei jeder Stichprobe das richtige Ergebnis raus. Es funktioniert aber wie gesagt nur bei fast allen Zahlen, bei der Zahl 670617279 funktioniert es nicht (das ist angeblich die Zahl unter einer Milliarde, bei der am meisten Schritte erforderlich sind). Es wird angezeigt, das nur 3 Schritte erforderlich wären, um auf eins zu kommen, wobei es eigentlich 986 sein müssten.
Ich kann mir das nicht erklären, habt Ihr eine Idee?
Vielen Dank

[Volker Z.]

Hallo,

und herzlich Willkommen in der DP.

Mit dem Startwert 670617279 ergibt sich folgende Folge: 670617279, 2011851838, 1005925919, -1277189538
Das Ergebnis 3 * 1005925919 + 1 ist größer als der maximale Integerbreich von -2147483648..2147483647. Deshalb wird das Produkt negativ; also ist Deine Bedingung der while-Schleife nicht mehr erfüllt (nach drei Schritten).

Du kannst es mal mit

Delphi-Quellcode:

var
  x : Int64;
  z : Cardinal;

versuchen. Damit hat es aber auch irgendwann ein Ende.

BTW: Bitte nimm in Zunkunft die Delphi-Tags für Code (Helmsymbol klicken und Deinem Code zwischen die Tags setzen).

Gruß

[schöni]

Ich vermute mal, das der Zahlenbereich Integer zu klein ist für die Zahl 670617279

670617279 * 3 = 2011851837
+1 = 2011851838 -> gerade Zahl noch im Bereich Longint
2011851838 / 2 = 1005925919 -> ungerade Zahl noch im Bereich Longint
1005925919 * 3 = 3017777757 -> nicht mehr im Bereich Longint

[RWarnecke]

Ich habe gerade mal mit diesem Quelltext getestet und bei der Zahl kommt ein Ergebnis bei raus :

Delphi-Quellcode:

procedure TForm13.Btn_1Click(Sender: TObject);
var
  x, z : Int64;
begin
  if TryStrToInt64(edit1.Text, x) then
    x := strtoint(edit1.Text)
  else
    x := 0;
  z := 0;
  if (x = 0) or (x < 0) then
    showmessage('Die Zahl muss mindestens 1 sein!')
  else
  begin
    while (x>1) do
    begin
      if (x mod 2 = 0) then
      begin
        x:= x div 2;
        Inc(z);
      end
      else
      begin
        x := x * 3 + 1;
        Inc(z);
      end;
      label1.Caption := 'Nach ' + inttostr(z) + ' Schritten kommt 1 heraus.';
    end;
  end;
end;

Und habe mir erlaubt Deinen Quelltext noch ein wenig zu verbessern.

[lasagne0504]

Ah ich dachte immer dass Delphi eine Fehlermeldung ausgibt wenn eine Zahl zu groß für eine Integer-Variabel ist. Aber dann ist das Problem ja geklärt, wenn ich int64 benutze klappt das auch.
Danke

[Der schöne Günther]

Zitat von lasagne0504:

Ah ich dachte immer dass Delphi eine Fehlermeldung ausgibt wenn eine Zahl zu groß für eine Integer-Variabel ist.

Das dachte ich auch lange. Leider ist das in der Debug-Fassung nicht die Standard-Einstellung, finde ich auch doof. Du kannst (und solltest?) es in der Debug-Fassung unter Delphi-Compiler->Compilieren->Laufzeitfehler wieder aktivieren (siehe Bild)

[DeddyH]

Auf dem Bild ist die Bereichsprüfung fokussiert, die Überlaufprüfung befindet sich 2 Zeilen tiefer

[Der schöne Günther]

Natürlich, ich hatte noch nicht einmal bewusst etwas angewählt, war immerhin schon nahe dran

[DeddyH]

Ist ja auch kein Beinbruch, die Hilfe sagt sowieso:

Zitat:

Der Schalter $Q wird normalerweise zusammen mit dem Schalter $R eingesetzt, der die Erzeugung von Bereichsprüfungscode aktiviert bzw. deaktiviert. Die Aktivierung der Überlaufprüfung vergrößert und verlangsamt ein Programm. Die aktivierte Überlaufsprüfung verlangsamt und vergrößert Ihr Programm. Sie sollten {$Q+} daher nur für die Fehlersuche verwenden.

[sx2008]

Vereinfacht sieht der Code so aus:

Delphi-Quellcode:

procedure TForm13.Btn_1Click(Sender: TObject);
var
  x : Int64;
  count : Integer;
begin
  x := StrToInt(edit1.Text);
  if x < 1 then
    raise Exception.Create('Die Zahl muss >= 1 sein!');
  count := 0;
  while (x>1) do
  begin
    if x mod 2 = 0 then
      x:= x div 2
    else
      x := x * 3 + 1;
    Inc(count);
  end;
  label1.Caption := 'Nach ' + inttostr(count) + ' Schritten kommt 1 heraus.';
end;