Erstellung einer Schleife mit drei Überprüfungen

[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:

Zitat von Delphi.Narium (Beitrag 1489990)

Irgendwie konnte ich es nicht lassen:
Die Fibonacci-Folge kann man doch auch per Schleife berechnen

Ich finde den in #1 gewählten Fibo-Ansatz via MB auch steil. U.a. auch weil für den "berechneten Index" noch gecheckt werden muss, ob's effektiv ein Fibo-Index ist... aber da in #1 auch das schöne Epsilon erwähnt wurde, dachte ich, es MUSS so gelöst werden. Das Epsilon kannst du ja bei Primzahlen schlecht verwenden ;-).
Hausaufgabe erledigt - mo53 und wir alle können die Sonne geniessen! In weniger als einem Monat werden die Tage für uns "NordhalbkugelerInnen" bereits wieder kürzer.


Wobei auch in #13 die Primzahlzwilling Berechnung immer noch sehr abenteuerlich ist ;-).
Zwillinge (3,5), (5,7), (11,13) werden nicht erkannt. Haufenweise Zahlen - wie zum Beispiel 21 mit Primfaktorzerlegung 3*7 - sollen Primzahlzwillinge sein und sind nicht mal prim.

[Michael II]

Zitat:

Zitat von Mo53 (Beitrag 1489974)

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

[Mo53]

@Michael II Vielen Dank dafür:)

[Mo53]

@Delphi.Narium ist echt sehr nett von dir, könntest du vielleicht nochmal kurz erläutern wie du genau die fibonacci überprüfung gemacht hast, ich kann das nicht ganz nachvollziehen.

[Michael II]

Zitat:

Zitat von Mo53 (Beitrag 1490000)

@Delphi.Narium ist echt sehr nett von dir, könntest du vielleicht nochmal kurz erläutern wie du genau die fibonacci überprüfung gemacht hast, ich kann das nicht ganz nachvollziehen.

DelphiNarium berechnet für jede Zahl zahl jedesmal alle Fibonaccizahlen bis zu zahl gemäss der Definition
f[n] := f[n-1] + f[n-2] für alle n>=2
f[0]=0*, f[1]=1

(*Je nach Literatur gibt's ein 0-tes Glied f[0] oder nicht (dann wird mit f[1]=f[2]=1 begonnen). Es ist eine Glaubensfrage: Die Entwicklung der Fibonacci Reihe wird oft mit der Vermehrung von Kaninchen verglichen. Wer glaubt, dass aus 0 und 1 Kaninchen etwas Grosses entstehen kann, nimmt das 0-te Glied 0 dazu.)

Den Code könntest du noch vereinfachen:
1. Vor der zahl Schleife suchst du nach der kleinsten Fibo Zahl f, für welche gilt f >= LOWER_BORDER
2. In der Schleife prüfst du immer auf f=zahl. Wenn f=zahl gibst du "Fibo=TRUE" aus und berechnest mittels f[n] := f[n-1] + f[n-2] die nächstgrössere Fibozahl f.

Vorteil?
Du rechnest so die Fibo-Folge bis UPPER_BORDER insgesamt genau einmal durch.
Im Code von DelphiNarium rechnest du UPPER_BORDER-LOWER-BORDER+1 mal die Fibo-Folge von 0 bis zahl.

Und wie erwähnt: Primzahlzwillinge (3,5), (5,7), (11,13) werden mit diesem Code nicht erkant.

[Delphi.Narium]

Zitat:

Zitat von Michael II (Beitrag 1490002)

Und wie erwähnt: Primzahlzwillinge (3,5), (5,7), (11,13) werden mit diesem Code nicht erkant.

{edit]
Diese Aussage ist so falsch, da hab' ich mich ganz gewaltig geirrt :-(
Es ist ja noch viel schlimmer:

Wenn man Primzahl am Anfang der For-Schleife mit 0 belegt, wird keine Primzahl mehr gefunden.

Die Repeat-Schleife wird beendet, wenn uebrig = 0. Teiler hat dann "irgendeinen" Wert. Ist dieser zufällig = zahl, so wird Primzahl = zahl und bleibt solange unverändert, bis "irgendwann" teiler mal wieder = zahl wird. Mit einer Primzahlberechnung hat das eher nichts zu tuen. Hab's halt aus dem ersten Post einfach mal so übernommen.
Primzahl enthält immer die zuletzt gefundene Primzahl.
[/edit]

Delphi-Quellcode:

    // Überprüfung ob Teil der Fibonacci-Folge:
    a := 0; // Damit fangen wir an.
    b := 1; // a und b sind die ersten beiden Zahlen zur Berechnung.
    c := 0; // c ist ein "Zwischenspeicher".

    // Die Schleife wird beendet, wenn zahl in die Fibonacci-Folge gehört (fib = true)
    // oder a >= zahl geworden ist. 
    while (a < zahl) and not fib do
    begin
      c := a + b; // Zwischenspeicher = Summe von a und b = nächste Zahl für die Fibonacci-Folge.
      a := b; // a wird nun b, da wir immer nur die beiden letzten Zahlen berücksichtigen müssen.
      b := c; // b wird nun der Zwischenspeicher zugewiesen = soeben ermitttelte Zahl für die Fibonacci-Folge,
              // damit enthalten a und b immer die beiden letzten Zahlen, 
              // deren Zugehörigkeit zur Fibonacci-Folge festgestellt wurde. 
      fib := c = zahl; // Stimmen c und zahl überein, so gehört Zahl in die Fibonacci-Folge.
      fib := b = zahl; // Auf b = zahl abzufragen, wäre hier auch korrekt.
    end;

Code:

1. Schleifendurchlauf
c := 0 + 1  // a = 0 plus b = 1
a := 1 // a := b, b = 1
b := 1 // b := c, c = 1

2. Schleifendurchlauf
c := 1 + 1 // a = 1 plus b = 1
a := 1 // a := b, b = 1
b := 2 // b := c, c = 2

3. Schleifendurchlauf
c := 1 + 2 // a = 1 plus b = 2
a := 2 // a := b, b = 2
b := 3 // b := c, c = 3

4. Schleifendurchlauf
c := 2 + 3 // a = 2 plus b = 3
a := 3 // a := b, b = 3
b := 5 // b := c, c = 5

5. Schleifendurchlauf
c := 3 + 5 // a = 3 plus b = 5
a := 5 // a := b, b = 5
b := 8 // b := c, c = 8

6. Schleifendurchlauf
c := 5 + 8 // a = 5 plus b = 8
a := 8 // a := b, b = 8
b := 13 // b := c, c = 13

7. Schleifendurchlauf
c := 8 + 13 // a = 8 plus b = 3
a := 13 // a := b, b = 13
b := 21 // b := c, c = 21

8. Schleifendurchlauf
c := 13 + 21 // a = 13 plus b = 21
a := 21 // a := b, b = 21
b := 34 // b := c, c = 34

9. Schleifendurchlauf
c := 21 + 34 // a = 21 plus b = 34
a := 34 // a := b, b = 34
b := 55 // b := c, c = 55

[Mo53]

@Michael II Es tut mir leid für meine Dummheit aber ich verstehe deinen Lösungsvorschlag für die Primzahlen nach mehrmaligem durchlesen immer noch nicht.
Könntest du den Lösungsansatz vielleicht step by step erklären.

[TurboMagic]

Zitat:

Zitat von Mo53 (Beitrag 1489974)

@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