Erstellung einer Schleife mit drei Überprüfungen

[Mo53]

Hallo,

Ich muss ein Programm für die Uni erstellen das überprüft ob in einer Schleife gerade Zahlen, Fibonacci Zahlen, oder Primzahlzwillinge vorhanden sind, und dann bei der Zahl jeweils TRUE oder FALSE anzeigen. Die Ausgabe sollte dann so aussehen:

0 even: TRUE fib: TRUE twinprim: FALSE
1 even: FALSE fib: TRUE twinprim: FALSE
2 even: TRUE fib: TRUE twinprim: FALSE
3 even: FALSE fib: TRUE twinprim: TRUE
4 even: TRUE fib: FALSE twinprim: FALSE
5 even: FALSE fib: TRUE twinprim: TRUE
6 even: TRUE fib: FALSE twinprim: FALSE
7 even: FALSE fib: FALSE twinprim: TRUE
8 even: TRUE fib: TRUE twinprim: FALSE
9 even: FALSE fib: FALSE twinprim: FALSE
10 even: TRUE fib: FALSE twinprim: FALSE
11 even: FALSE fib: FALSE twinprim: TRUE
12 even: TRUE fib: FALSE twinprim: FALSE
13 even: FALSE fib: TRUE twinprim: TRUE
14 even: TRUE fib: FALSE twinprim: FALSE
15 even: FALSE fib: FALSE twinprim: FALSE
16 even: TRUE fib: FALSE twinprim: FALSE
17 even: FALSE fib: FALSE twinprim: TRUE
18 even: TRUE fib: FALSE twinprim: FALSE
19 even: FALSE fib: FALSE twinprim: TRUE
20 even: TRUE fib: FALSE twinprim: FALSE
21 even: FALSE fib: TRUE twinprim: FALSE
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: FALSE

Nun habe ich ein Problem mit Gleitkommawerten und wollte dies mit Epsilon lösen also 1E - 100, so hatten die uns das in der Vorlesung erklärt, jedoch funktioniert das nicht ganz ohne weiteres und ich finde im Internet auch nix brauchbares dazu. Im Programm muss dazu noch jeweils ein for, while und repeat vorkommen und ich weiß nicht wo ich das while integrieren soll.
Sorry für die dummen Fragen, ich bin noch blutiger Anfänger, habe vor einem Monat mit dem Programmieren angefangen.
Freue mich über jede Hilfe und danke im voraus.

Hier mein Quellcode:

Delphi-Quellcode:

// Schleife zum überprüfen ob gerade Zahl, Primzahl oder Fibonacci Zahl.
program ueb04;

{$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: boolean;
  twinprim: boolean;
  zahl: integer;
  Primzahl: integer;
  teiler: integer;
  übrig: integer;

begin

  for zahl := 1 to 50 do
  begin
    // Überprüfung ob gerade
    even := (zahl mod 2 = 0);
    // Überprüfung ob Fibonacci
    fib := ((1 / sqrt(5)) * (Power(zahl, ((1 + sqrt(5)) / 2)) - (Power(zahl,
      ((1 - sqrt(5)) / 2)))));
    fibo := (zahl = (fibo - Epsilon));
    // Überprüfung ob Primzahl
    if zahl > 0 then
    begin
      teiler := 1;
      repeat
        teiler := teiler + 1;
        übrig := zahl mod teiler;
      until (teiler = 0);
      if (teiler = zahl) then
        Primzahl := zahl
    end;

    // Überprüfung ob Primzahlzwilling
    twinprim := (Primzahl + 2 = Primzahl);

    writeln(zahl, ' even: ', even, ' fib: ', fib, ' twinprim: ', twinprim);

  end;
  readln;

end.

[TurboMagic]

Hallo,

keine Ahnung, aber mal 2 Anmerkungen:

1. uebrig bekommt bei dir zwar einen Wert zugewiesen aber den verwendest du nie.

2. dein Test ob es ein Primzahlzwilling ist kann nicht funktionieren.
Eine Zahl x kann niemls die selbe Zahl wie x + 2 sein!

Grüße
TurboMagic

[KodeZwerg]

Zitat:

Zitat von Mo53 (Beitrag 1489949)

Im Programm muss dazu noch jeweils ein for, while und repeat vorkommen und ich weiß nicht wo ich das while integrieren soll.

Erstelle für Input ein Array of "Datentyp" zum abarbeiten.
Erstelle für Output ein Array of String für die Ausgabe.

In einer "For"-Schleife über Input Array überprüfst Du auf gerade Zahlen und schreibst das Ergebnis in das Output Array.
In einer "While"-Schleife über Input Array überprüfst Du auf Fibonacci Zahlen und schreibst das Ergebnis in das Output Array.
In einer "Repeat"-Schleife über Input Array überprüfst Du auf Primzahlzwillinge und schreibst das Ergebnis in das Output Array.

Somit wären diese Pflichten erledigt.

Nun musst Du Dir überlegen wie Du es auswertest mit dem True/False da ich nicht verstanden habe was True/False bedeuten soll.

Ich hoffe es bringt Dich ans Ziel.

Ps: Ich würde mir für das Überprüfen jeweils eine Eigene Methode erstellen, "IsEven, IsFibo, IsPrimePair" um in den Schleifen einfacher darauf zugreifen zu können.


//edit grober pseudo code der verdeutlichen soll wie ich es meine, etwaige fehler und lücken müssen noch bearbeitet werden.

Delphi-Quellcode:

program hausaufgabe;

uses Units;

function IsEven(const AValue: {Datentyp}): Boolean;
begin
//code
end;

function IsFibo(const AValue: {Datentyp}): Boolean;
begin
//code
end;

function IsPrimePair(const AValue: {Datentyp}): Boolean;
begin
//code
end;

var
  input: Array of {Datentyp};
  output: Array of string;
  i, maxI: Integer;
begin
  Writeln('Hausaufgabe');
  Writeln('');

  Randomize;
  maxI := Random(666);
  SetLength(input, maxI);
  SetLength(output, maxI);
  for i := 0 to maxI do
    input[i] := Random(666);

  for i := 0 to High(input) do
    if IsEven(input[i]) then
      output[i] := 'IsEven, '
      else
      output[i] := 'IsNotEven, ';

  i := 0;
  while True do
  begin
    if IsFibo(input[i]) then
      output[i] := output[i] + 'IsFibo, '
      else
      output[i] := output[i] + 'IsNotFibo, ';
    if i < Length(input) then
      Inc(i, 1)
      else
      Break;
  end;

  i := 0;
  repeat
    if IsPrimePair(input[i]) then
      output[i] := output[i] + 'IsPrimePair'
      else
      output[i] := output[i] + 'IsNotPrimePair';
    Inc(i, 1);
  until i > Length(input);

  for i := 0 to High(output) do
    Writeln('#' + IntToStr(i) + ': "' + DatentypToStr(input[i]) + '" = ' + output[i];

  Readln;
end.

[himitsu]

"Überprüfung ob Primzahl" kann nicht stimmen.
* die Repeat-Schleife wird nur bei 0 verlassen
* das was in der Schleife ist, ist komplett sinnlos, weil niemals damit etwas gemacht wird
* "Zahl" kann sowieso niemals 0 sein

und bezüglich "Primzahlzwilling"
* man nehme das vorherige Ergebnis "IsPrime"
* und wenn ja, dann Zahl+2 und Zahl-2 prüfen, ob einwas davon auch eine Primzahl ist

Delphi-Quellcode:

  for zahl := 1 to 50 do
  begin
    ...
    if zahl > 0 then
    begin

Und überleg auch mal, ob diese Prüfung irgendeinen Sinn haben kann.

Oder andersrum, schau dir an, was die Ausgabe im ersten Post mit deiner Schleife nicht gemeinsam hat. :wink:

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

Delphi-Quellcode:

twinprim := (zahl + 2 or zahl - 2 = Primzahl);

Das könnte eher mit

Delphi-Quellcode:

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:

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

[Michael II]

Zitat:

Zitat von Mo53 (Beitrag 1490024)

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

Für zahl = 2 gibst du prim aus.

Du fragt wegen allen anderen Primzahlen. Hier Code.

Delphi-Quellcode:

var teiler, pruefebis, zahl : integer;
    ist_prim : boolean;
....

  zahl := 91;

  ist_prim := true;
  teiler := 3;
  pruefebis := trunc(sqrt(zahl));
  while ist_prim and ( teiler <= pruefebis ) do
  begin
    ist_prim := zahl mod teiler <> 0;
    inc( teiler, 2 ); // teiler := teiler + 2;
  end;

Lade den Code in der IDE und steppe durch wie TurboMagic geschrieben hat.

Zum Code:

Wir nehmen zuerst ist_prim:= TRUE an und werden vielleicht später (in der while Schleife) das Gegenteil beweisen.

zahl ist im Beispiel 91.
Du weisst, dass es einen echten Teiler von 91 <= sqrt(91) geben muss, wenn 91 nicht prim ist.
Wir prüfen also für teiler mit den Werten 3,5,...9, ob zahl durch teiler teilbar ist.
Wenn dem so ist, wird ist_prim in der while Schleife FALSE. => Die Schleife wird wegen der Abbruchbedingung (while ist_prim and ( teiler <= pruefebis ) do) verlassen.

Am Ende der while Schleife ist ist_prim TRUE, wenn zahl eine Primzahl ist, sonst FALSE



Da ihr wahrscheinlich keine "function" benutzen dürft, ist die Aufgabe mit den Primzahlzwillingen etwas aufwändig [und ohne die Verwendung von "function" vielleicht auch ein wenig nutzlos ;-)].

[himitsu]

F7 ist, Dank der bescheuert standardrdmäßig aktiven Option "Debug-DCUs", seit zuvielen Jahren nicht mehr so toll.

also F8

oder in den Projektoptionen die Debug-DCUs deaktivieren,
es sei denn jemandem macht es Spaß, wenn er die VCL/RTL/System-Units ebenfalls debuggen will.

[Mo53]

@Michael II ist es möglich das ganze auch in einer repeat schleife zu verpacken?
Wie mach man das jetzt mit dem Primzahlzwilling, da istprime ja boolean ist klappt es in der nächsten überprüfung nichtmehr mit zahl+2 = istprime

[Michael II]

Dieser Code gibt dir aus, ob eine Zahl gerade ist, ob fibo, ob prim, ob zwillingsprim.

Da du sicher keine function istprim(zahl) verwenden darfst, merken wir uns halt in zwei booleschen Variablen, ob die letzte ungerade Zahl (zahl-2) prim war (letzte_warprim) und ob die nächste ungerade (zahl+2) es sein wird (naechste_istprim). So müssen wir jede zahl nur einmal auf prim prüfen.

Die "Spezialwerte" 0,1,2 geben wir direkt aus. (Man müsste den Code durch diese drei "Sonderfälle" aufblähen. - Tun wir nicht.)

Was macht das Programm?

Fibo: Für fibo berechnen wir am Anfang die kleinste Fibo-Zahl f, welche >= LOWER_BORDER ist. Dann geht's ab in die while Schleife. Sobald zahl=f wissen wir "fibo!". Wir setzen im fibo Fall istfibo:=TRUE und müssen das nächste Glied f der Fibofolge berechnen. Bei der Berechnung von f=f[n] greifen wir auf die gespeicherten Werte von f[n-1] und f[n-2] zurück.

Gerade: istgerade := zahl mod 2 = 0; und das war's bereits.

Primzahlen und deren Zwillinge: Für Zahlen, welche ungerade sind, prüfen wir auf prim. Wir prüfen dabei nicht die aktuelle Zahl, sondern "zahl+2". Grund: Wir müssen für die Bewertung "zahl ist Zwilling oder nicht" wissen, ob die nächste ungerade Zahl "zahl+2" prim ist. Wir speichern in naechste_istprim ab, ob "zahl+2" prim ist. In letzte_warprim merken wir uns, ob die letzte ungerade Zahl prim war. In diese_istprim steht, ob zahl prim ist. diese_istprim berechnen wir dabei nicht via Faktorzerlegung von zahl: Wir wissen ja dank letzte_warprim, ob zahl prim ist oder nicht. "zahl" ist Teil eines Primzahlzwillings, wenn
primzwilling := diese_istprim and ( letzte_warprim or naechste_istprim );

Fertig - Viel Spass beim Denken.

Delphi-Quellcode:

var teiler, sqrt_n, naechste, zahl, fn_1, fn_2, f : int64;
    primzwilling, istfibo, istgerade, letzte_warprim, naechste_istprim, diese_istprim : boolean;

const
  LOWER_BORDER = 0;
  UPPER_BORDER = 50;

begin
  if ( LOWER_BORDER = 0 ) then writeln( '0 even: TRUE fib: TRUE prim: FALSE twinprim: FALSE' );
  if ( LOWER_BORDER <= 1 ) and ( 1 <= UPPER_BORDER ) then writeln( '1 even: FALSE fib: TRUE prim: FALSE twinprim: FALSE' );
  if ( LOWER_BORDER <= 2 ) and ( 2 <= UPPER_BORDER ) then writeln( '2 even: TRUE fib: TRUE prim: FALSE twinprim: FALSE' );
  if ( LOWER_BORDER mod 2 = 0 ) then zahl := LOWER_BORDER-3 else zahl := LOWER_BORDER-4;

  if ( zahl < 3 ) then
  begin
    zahl := 3;
    naechste_istprim := true; // 3 ist Primzahl
  end;

  fn_1 := 1;
  fn_2 := 1;
  f := 2;
  while ( f < zahl ) do // berechne die kleinste Fibo-Zahl f, welche >= LOWER_BORDER
  begin
    f := fn_1 + fn_2;
    fn_2 := fn_1;
    fn_1 := f;
  end;

  while ( zahl <= UPPER_BORDER ) do
  begin
    istfibo := f = zahl;
    if istfibo then 
    begin // die nächste Fibozahl wird berechnet
        f := fn_1 + fn_2;
        fn_2 := fn_1;
        fn_1 := f;
    end;

    istgerade := zahl mod 2 = 0;

    if not istgerade then
    begin
      diese_istprim := naechste_istprim; // in durchlauf "zahl-2" haben wir berechnet, ob "zahl" prim ist
      naechste := zahl + 2; // die nächste ungerade zahl nach "zahl" auf prim prüfen
      sqrt_n := trunc(sqrt(naechste)); // bis zu diesem wert suchen wir nach möglichen teilern von naechste
      teiler := 3;
      naechste_istprim := true; // wir nehmen mal an, "naechste" sei prim
      while naechste_istprim and ( teiler <= sqrt_n ) do
      begin // und prüfen, ob dem so ist
        naechste_istprim := naechste mod teiler <> 0;
        inc( teiler, 2 );
      end; 
      // naechste_istprim = true, wenn naechste=zahl+2 prim ist
      // wir prüfen, ob "zahl" zu einem Zwilling gehört
      primzwilling := diese_istprim and ( letzte_warprim or naechste_istprim );
      letzte_warprim := diese_istprim; // wir merken uns für runde "zahl+2", ob "zahl" prim ist
    end
    else
    begin
      diese_istprim := false; // "zahl" ist gerade also nicht prim
      primzwilling := false;  // ..und damit auch nicht Teil eines Zwillings
    end;

    if ( zahl >= LOWER_BORDER ) then // Ausgabe
    writeln(zahl, ' even: ', istgerade, ' fib: ', istfibo, ' prim: ', diese_istprim, ' twinprim: ', primzwilling );
    inc( zahl );
  end;

  readln;

[Mo53]

Das sieht sehr gut aus, ich habe in der zwischenzeit auch meinen code bearbeitet, jedoch wird auf einmal nur bis 1 ausgegeben.
Bevor ich die zwei neuen repeat schleifen eingefügt hab hat es bis 50 geklappt, siehst du vielleicht woran es liegt.

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;
  NextPrim: boolean;
  PrevPrim: boolean;
  zahl: integer;
  Primzahl: boolean;
  teiler: integer;
  uebrig: integer;
  a: integer;
  b: integer;
  c: integer;

begin
  for zahl := LOWER_BORDER to UPPER_BORDER do
  begin
    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);

      Primzahl := (zahl = teiler);
    end;

    if Primzahl then
    begin
      Teiler:= 1;
      repeat
        teiler := teiler + 1;
        uebrig := zahl + 2 mod teiler;
      until (uebrig = 0);
      NextPrim := (zahl + 2) = teiler;
    end;

    if Primzahl and (zahl > 3) then
    begin
      Teiler:= 1;
      repeat
        teiler := teiler + 1;
        uebrig := zahl - 2 mod teiler;
      until (uebrig = 0);
      PrevPrim := (zahl - 2) = teiler;
    end;

    twinprim := Primzahl and (NextPrim or PrevPrim);

    // Ü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.

[Michael II]

uebrig := zahl - 2 mod teiler; ist nicht das, was du willst.

mod wird vor +*-/ ausgewertet.

Was du willst ist
uebrig := ( zahl - 2 ) mod teiler;

In deinem Code berechnest du in jeder Runde drei Mal, ob eine Zahl (du rechnest für zahl-2, zahl und zahl+2) prim ist. Wie du gesehen hast geht es auch mit einer Berechnung pro Runde: Du könntest dir jeweils prim oder nicht für zahl und zahl+2 merken. In der nächsten "ungeraden zahl Runde" kannst du dann auf diese Werte zurückgreifen und musst nur für "zahl+2" rechnen.

Wie besprochen: Ausser 2 ist keine Primzahl gerade. Überprüfe also nur ungerade teiler.
teiler := teiler + 2;

Wie besprochen: Prüfe nur für ungerade Teiler von 3 bis sqrt(zahl).

Delphi-Quellcode:

  ist_prim := true;
  teiler := 3;
  pruefebis := trunc(sqrt(zahl));
  repeat
    ist_prim := zahl mod teiler <> 0;
    inc( teiler, 2 );
  until not ist_prim or ( teiler > pruefebis );

Fibo müsstest du nicht für jede Zahl immer neu berechnen. Es reicht, wenn du dir immer die nächste Fibo-Zahl f > zahl merkst und dann in jeder Runde auf f=zahl prüfst.
Das spielt hier keine grosse Rolle - aber Effizienz in Schleifen ist wichtig ;-).