Erstellung einer Schleife mit drei Überprüfungen

[Michael II]

Fibonacci.

Da machst du diverse Fehler.

Du willst für die Berechnung offenbar Moivre-Binet (MB) verwenden. Mit MB kannst du die n-te Fibonacci Zahl ermitteln.
D.h. du musst bei deiner Überprüfung von "zahl" ein n finden, für welches f(n) = zahl gilt. Dann ist "zahl" Fibonacci Zahl.

Du verwendest in deiner Formel Power(a,b), was a^b entspricht. Schau dir noch einmal die Formel von MB an, dann siehst du, dass du in deinem Programm bei Power(a,b) Basis und Exponent vertauscht hast.

Näherung: Der zweite Power Therm in MB ist bereits für kleine n klein und (da ¦Basis¦ < 1) konvergent lim(n->unendlich) = 0. Du kannst auf den zweiten Therm verzichten und rechnen:

Delphi-Quellcode:

    sqrt5 := sqrt(5);
    fib := trunc( 1/sqrt5 * Power((1+sqrt5)/2,n) + 0.5 );

Noch einmal: Du musst (Code oben) nach einem n suchen, für welches fib=zahl.

Du suchst: Gegeben eine Zahl zahl. Gesucht: Gibt es ein n für welches gilt fib(n)=zahl. zahl := trunc( 1/sqrt5 * Power((1+sqrt5)/2,n) + 0.5 ) kannst du auflösen nach n: (zahl-0.5)*sqrt5=((1+sqrt5)/2)^n. => n = log(zahl-0.5)/log((1+sqrt5)/2).
Für grössere Werte von Zahl kannst du das 0.5 auch weglassen (dies ist ja die Abschätzung für ((1-sqrt)/2)^n in MB und dieser Funktion konvergiert gegen 0).
Bleibt zu prüfen, ob der gefundene Wert n (ist eine real Zahl) effektiv Index einer Fibonacci Zahl ist.

(Mit einem ε machst du mathematisch nix falsch, in einem Programm musst du aber i.A. im Auge behalten, wie beim von dir verwendeten Zahlentyp Werte abgespeichert werden. Die "reelle Zahlenwelt" im Computer weist mehr Löcher als Werte (nur endlich viele voneinander verschiedene Werte speicherbar, jedoch R überabzählbar) auf: Du findest zu einem abgespeicherten real Wert x locker ein ε für welches im (mathematischen) Intervall [x-ε,x+ε] alle Werte als x gespeichert werden.)

Nebenbei und für Uni (1. Jahr, Lineare Algebra, Differentialgleichungen) interessant: Du kannst für Folgen vom Typ a[n+1] = f*a[n] + g*a[n-1], Startwerte a[0], a[1] gegeben
eine Formel (wie jene von MB für Fibo) für a[n] berechnen. Wenn du dir die Herleitung von MB anschaust, dann siehst du sofort wie das geht. (Du betrachtest im R^2 die lineare Abbildung (a[n],a[n-1]) = A(a[n-1],a[n-2]) => (a[n+k],a[n+k-1]) = A^(k)(a[n],a[n-1]), Du suchst für A die Eigenvektoren und kannst so leicht A^(k) berechnen. Fertig.)

[TurboMagic]

Hallo,

evtl. ist es auch sinnvoll, suerst mal die gerade/ungerade und primzahlen AUfgabenteile zu lösen, damit man
dafür eine saubere Grundstruktur des Programmes bekommt und danach dan das Fibonnaci Problem anzugehen.

Grüße
TurboMagic

[Mo53]

@KodeZwerg
Vielen Dank für die Mühe, ich hatte aber vergessen zu erwähnen das wir noch keine arrays verwenden dürfen.

[Mo53]

Leute könnt ihr mir vielleicht sagen warum nach dem compilen die Ausgabe nur für die Zahl Null ausgegeben wird, hänge da schon Stundenlang dran.

Delphi-Quellcode:

{$APPTYPE CONSOLE}
{$R+,Q+,X-}

uses
  System.SysUtils, System.Math;

const
  LOWER_BORDER = 0;
  UPPER_BORDER = 50;
  Epsilon = 1E-100;

var
  even: boolean;
  fib: extended;
  fibo: extended;
  twinprim: boolean;
  zahl: integer;
  Primzahl: integer;
  teiler: integer;
  uebrig: integer;
  n: real;

begin
  for zahl := LOWER_BORDER to UPPER_BORDER do
  begin
    // Überprüfung ob gerade
    if zahl > 1 then
    begin
      even := (zahl mod 2 = 0);
    end
    else
      even := FALSE;

    // Überprüfung ob Primzahl
    if zahl > 1 then

      teiler := 1;
    repeat
      teiler := teiler + 1;
      uebrig := zahl mod teiler;
    until (uebrig = 0);

    if (teiler = zahl) then
      Primzahl := zahl;

    // Überprüfung ob Primzahlzwilling
    if zahl >= 1 then
    begin
      while zahl = Primzahl do
        twinprim := (zahl + 2 or zahl - 2 = Primzahl);
    end;

    writeln(zahl, ' even: ', even, ' twinprim: ', twinprim);
  end;
  readln;

end.

[Delphi.Narium]

Dashier führt zu einer Endlosschleife, wenn zahl = Primzahl.

Delphi-Quellcode:

   // Überprüfung ob Primzahlzwilling
    if zahl >= 1 then
    begin
      while zahl = Primzahl do
        twinprim := (zahl + 2 or zahl - 2 = Primzahl);
    end;

In der Schleife werden weder Zahl noch Primzahl verändert, so dass hier nie ein Schleifenabbruch geschehen wird.

Diese Zuweisung wird vermutlich auch nicht das gewünschte Ergebnis bringen:twinprim := (zahl + 2 or zahl - 2 = Primzahl);
Das könnte eher mit twinprim := (zahl + 2 = Primzahl) or (zahl - 2 = Primzahl); erreicht werden.

Auch wenn Du irgendwo noch eine While-Schleife unterbringen musst, erschließt sich mir hier nicht, wie eine sinnvolle Nutzung an dieser Stelle möglich sein könnte.

Delphi-Quellcode:

    // Überprüfung ob Primzahlzwilling
    if (zahl >= 1) and (zahl = Primzahl) then
      twinprim := (zahl + 2 = Primzahl) or (zahl - 2 = Primzahl)
    else
      twinprim := false;

[Michael II]

Ein Tipp: Du kannst dein Programm in die Delphi IDE laden und dann Zeile für Zeile durchsteppen und schauen, wo dein Programm durchläuft und welche Werte momentan in der Variablen gespeichert sind. Wenn du das tust, dann geht's schneller - hoffentlich hast du die vielen Stunden wenigstens an der Sonne programmiert .

Zu deiner Prüfung, ob Primzahl oder nicht.

Deine Variable teiler lässt du in 1er Schritten von 2 bis zahl laufen.
Prüfe doch auf teilbar durch 2 und danach nur ob teilbar durch 3,5,7,9,11,...
Du sparst etwa die Hälfte der Abfragen: Faktor 2 schneller.
Das hier kennst du wahrscheinlich aus der Grundschule 7. Klasse Mathe führt aber wahrscheinlich punkto Delphi noch zu weit.

Du testest etwas viele "teiler" durch. Prüf doch nur bis zu sqrt(zahl) und hör dann auf. Statt zum Beispiel 1'000'000 "teiler Checks" führst du dann nur etwa 1'000 durch. Faktor 1'000 schneller.

Primzahlzwilling. Den Code musst du etwas überdenken.

[Mo53]

@Michael II kannst du das vielleicht mehr erläutern ggf. mit einem beispiel

[Delphi.Narium]

Irgendwie konnte ich es nicht lassen:

Da es ja vorwiegend um die korrekte Nutzung von Schleifen gehen soll und die Verwendung einer For-, eine Repeat-Until und einer While-Schleife gefordert ist, dachte ich mir. "Die Fibonacci-Folge kann man doch auch per Schleife berechnen (statt durch 'hötere Mattetik'."

Dabei rausgekommen ist dann folgendes:

Delphi-Quellcode:

program ueb04;

{$APPTYPE CONSOLE}
{$R+,Q+,X-}

uses
  System.SysUtils;

const
  LOWER_BORDER = 0;
  UPPER_BORDER = 50;

var
  even     : boolean;
  fib      : boolean;
  twinprim : boolean;
  zahl     : integer;
  Primzahl : integer;
  teiler   : integer;
  uebrig   : Integer;
  a        : Integer;
  b        : Integer;
  c        : Integer;
begin
  for zahl := LOWER_BORDER to UPPER_BORDER do
  begin
    // Alles auf Anfang, damit nicht irrtümlicherweise die Ergebnisse der vorherigen Zahl genutzt werden.
    even     := false;
    fib      := false;
    twinprim := false;

    if zahl > 1 then
    begin
      // Überprüfung ob gerade:
      even := (zahl mod 2 = 0);

      // Überprüfung ob Primzahl:
      teiler := 1;
      repeat
        teiler := teiler + 1;
        uebrig := zahl mod teiler;
      until (uebrig = 0);

      if (teiler = zahl) then
        Primzahl := zahl;
    end;

    // Überprüfung ob Primzahlzwilling:
    if zahl >= 1 then
      twinprim := (zahl + 2 = Primzahl) or (zahl - 2 = Primzahl);

    // Überprüfung ob Teil der Fibonacci-Folge:
    a := 0;
    b := 1;
    c := 0;
    while (a < zahl) and not fib do
    begin
       c := a + b;
       a := b;
       b := c;
       fib := c = zahl;
    end;
    WriteLn(zahl, ' even: ', even, ' fib: ', fib, 'twinprim: ', twinprim);
  end;
  readln;
end.

Das Ergebnis sieht so aus:

Code:

00, even: false, fib: false, twinprim: false
01, even: false, fib: true,  twinprim: false
02, even: true,  fib: true,  twinprim: false
03, even: false, fib: true,  twinprim: false
04, even: true,  fib: false, twinprim: false
05, even: false, fib: true,  twinprim: false
06, even: true,  fib: false, twinprim: false
07, even: false, fib: false, twinprim: false
08, even: true,  fib: true,  twinprim: false
09, even: false, fib: false, twinprim: true
10, even: true,  fib: false, twinprim: false
11, even: false, fib: false, twinprim: false
12, even: true,  fib: false, twinprim: false
13, even: false, fib: true,  twinprim: false
14, even: true,  fib: false, twinprim: false
15, even: false, fib: false, twinprim: true
16, even: true,  fib: false, twinprim: false
17, even: false, fib: false, twinprim: false
18, even: true,  fib: false, twinprim: false
19, even: false, fib: false, twinprim: false
20, even: true,  fib: false, twinprim: false
21, even: false, fib: true,  twinprim: true
22, even: true,  fib: false, twinprim: false
23, even: false, fib: false, twinprim: false
24, even: true,  fib: false, twinprim: false
25, even: false, fib: false, twinprim: true
26, even: true,  fib: false, twinprim: false
27, even: false, fib: false, twinprim: false
28, even: true,  fib: false, twinprim: false
29, even: false, fib: false, twinprim: false
30, even: true,  fib: false, twinprim: false
31, even: false, fib: false, twinprim: false
32, even: true,  fib: false, twinprim: false
33, even: false, fib: false, twinprim: true
34, even: true,  fib: true,  twinprim: false
35, even: false, fib: false, twinprim: false
36, even: true,  fib: false, twinprim: false
37, even: false, fib: false, twinprim: false
38, even: true,  fib: false, twinprim: false
39, even: false, fib: false, twinprim: true
40, even: true,  fib: false, twinprim: false
41, even: false, fib: false, twinprim: false
42, even: true,  fib: false, twinprim: false
43, even: false, fib: false, twinprim: false
44, even: true,  fib: false, twinprim: false
45, even: false, fib: false, twinprim: true
46, even: true,  fib: false, twinprim: false
47, even: false, fib: false, twinprim: false
48, even: true,  fib: false, twinprim: false
49, even: false, fib: false, twinprim: true
50, even: true,  fib: false, twinprim: false

[Michael II]

Zitat von Mo53:

@Michael II kannst du das vielleicht mehr erläutern ggf. mit einem beispiel

Falls du damit den Teil meinst bis sqrt(zahl) auf Teilbarkeit checken:

Jede Zahl lässt sich wie du weisst in Primfaktoren zerlegen oder eben nicht.

Du suchst mit deinem Test von 2 an aufwärts (bis zahl) nach einer Zahl p, welche echter Teiler von zahl ist.

Wenn es eine solche Zahl p < zahl gibt, dann kannst du zahl zerlegen in

zahl = p*q

Du weisst bei dieser Zerlegung, dass q nicht kleiner als p sein kann. Grund: Du suchst ja von 2 aufwärts und bist zuerst auf p gestossen. (Wäre q kleiner als p wärst du bei deiner Suche zuerst auf q gestossen.)

Es gilt also p <= q [Wichtig, dass du diesen Schluss begreifst.]

=> Bleibt zu überlegen, wie gross p maximal sein kann.
Da p kleiner als q ist, ist p im Fall p=q maximal =>
p <= sqrt(zahl)

Zahlenbeispiel?
Teste 41
Du prüfst momentan /2 /3 /4 /5 /6 /7 /8.... /41
Es reicht, nur /2 /3 /4 /5 /6 zu testen. Tests ab /7 lohnen sich nicht mehr, da wir oben gezeigt haben, dass der kleinste echte Teiler von zahl kleiner oder gleich sqrt(zahl) ist; also hier p <= sqrt(41) sein muss.

- Sobald du einen Teiler gefunden hast, kannst du deine Berechnung abbrechen und auf "nicht prim" entscheiden.
Du berechnest ja "übrig" - wenn dein "übrig=0" hast du einen Teiler von Zahl gefunden => Zahl ist nicht prim, Abbruch => Abbruchbedingung übrig=0.

Wie früher erwähnt: Wenn 2 nicht Teiler von Zahl ist, dann musst du die anderen geraden Zahlen 4,6,8,... nicht mehr checken. Grund: Bei deinem Test wärst du ja bereits bei /2 fündig geworden und hättest auf nicht prim entschieden.

[TurboMagic]

Zitat von Mo53:

@Michael II kannst du das vielleicht mehr erläutern ggf. mit einem beispiel

Was davon?
Das Steppen?

Dazu einfach mit F5 in der Zeile ab der man steppen möchte einen Breakpoint
setzen, das Programm dann ausführen. Es wird am Breakpoint stoppen und
ab da mt F7 Schritt für Schritt ausführen.

Nach jedem Schritt kannst du die Lokalen und globalen Variablen links
vom Editor aufgelistet sehen und deren Werte.

Grüße

TurboMagic