+1 Daumen
2,8k Aufrufe

Aufgabe:

Fibonacci numbers are the integers in the following sequence: $$0,1,1,2,3,5,8,13,21,...$$

Each number is the sum of the two previous numbers.

Fibonacci primes are Fibonacci numbers that are also prime numbers. Write a program that asks the user for an integer \(m\)
and then computes and prints all Fibonacci primes between
\(0\) and \(m\) (m including). Print each number on a new line.

Finally, on a new line print the total number of Fibonacci primes found.

Was ging bisher ? 

Der Fall m = 0 
Gibt die Zahlen \(0\) aus
Totale Zahl der Primzahlen = 0. 

Der Fall m = 1
Gibt die Zahlen \(0,1,1\) aus.
Totale Zahl der Primzahlen = 0. 

Das habe ich so vordefiniert, eventuell wertet man das auch als Hardcoding. 

Der erste Fehler
Der Fall m > 2

Wenn ich eine Fibonaccizahl für m eingebe, printet es alle Fibonaccizahlen bis dort hin aus.
Das Funktioniert. Wenn ich zb: 5 eingebe ist der output: 0,1,1,2,3,5.

Wenn ich aber eine Fibonaccizahl + 1 eingebe, Printet es alle Zahlen bis dort hin aus und eine Fibonaccizahl Plus!
Zb wenn ich 6 eingebe ist der Output: 0,1,1,2,3,5,8. 


Der zweite Fehler,

für den Fall m>2

Ich sollte herausfiltern was die Primzahlen in dieser Fibonacci-Folge sind. Da habe ich keine Idee wie! 
Für die Fälle m < 2 ist es klar, da gibt es 0 Fibonacci Primes. 


Der Code: (Oder per Link:

)

//Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
//1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
//By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

#include <iostream>

int a = 1;
int b = 1;
int c = 0;
int sum = 0;
int primes_printed;
int m = 0;

int main(){
 
  //Type in a number m
  std::cout << "Type in a number: " << std::endl;
  std::cin >> m;
  ///std::cout << "The entered number is: " << m << "." << std::endl;
 
  if(m==0 && m<1){
    std::cout << 0 << std::endl;
    primes_printed = 0;
    std::cout << "Number of printed primes = 0" << std::endl;
  }
  if((m != 0) && (1>=m)){
    std::cout << 0 << std::endl;
    std::cout << 1 << std::endl;
    std::cout << 1 << std::endl;
    primes_printed = 0;
    std::cout << "Number of printed primes = 0" << std::endl;
  }
 
 
  if(m!=0 && m != 1){ // 1. Step: Run Loop as long as term a or term b is less than 4 million.
      std::cout << 0 << std::endl;
      std::cout << 1 << std::endl;
      std::cout << 1 << std::endl;
     
     
      do {
        c = a + b;
        std::cout << c << std::endl;
        a = b;
        b = c;}
        while (c<m && m>1);
     
     

  }
    // Final: Print the sum of all even Fibonacci numbers.
 
   
    return 0;
}



von

2 Antworten

0 Daumen
 
Beste Antwort

Hallo Limonade,

Es gibt eine Sache, die beim Erstellen von Programmen essentiell ist:

divide et impera

Heißt 'Teile und Herrsche', heißt beim Programmieren: zerlege das Problem in möglichst kleine Einheiten und zwar derart, dass diese möglichst wenig miteinander zu tun haben. mathe53 hat dies in seiner Antwort schon gezeigt, in dem er den Algorithmus zur Primzahlprüfung in eine Funktion Ist_Primzahl verpackt hat. Das nennt man übrigens 'Kaspelung'.

Dieses Prinzip ist deshalb so wichtig, da man bei mittleren bis größeren Programmen ansonsten völlig den Überblick verlieren würde, und am Ende nur noch Chaos produziert. Und bei kleinen Programmen kann man das schon mal üben ..

Eine Konsequenz dieses Prinzip ist es auch, auf globale Variablen möglichst zu verzichten. Die Variablen oberhalb von 'int main {' sollten und brauchen da gar nicht stehen!

Weiter: bennen die Variablen und auch alles andere sinnvoll. Also nicht 'a' oder 'b', sondern besser 'fib_i_minus_1' und 'fib_i' für die Fibonaccizahlen \(f_{i-1}\) und \(f_i\).

Kommen wir mal zur Kapselung der Fibonaccizahlen. Das ist ein schönes Beispiel für eine kleine Klasse. Um eine Fibonaccizahl zu berechnen benötigt man zwei auf einander folgende. In einer Klasse sähe das so aus:

class Fibo {
private:
    int m_fib_i;
    int m_fib_i_minus_1;
};
Das 'm_' steht für Member, und das 'm_fib_i' ist die i'te Fibonaccizahl \(f_i\) sowie der Vorgänger 'm_fib_i_minus_1' \(f_{i-1}\). Und die sind 'private', weil sie sollten von außerhalb nicht verändert werden. Wir möchten natürlich die aktuelle Zahl haben, also braucht man noch ein 'get':

class Fibo
{
public:
    int get() const {
        return m_fib_i;
    }
private:
    int m_fib_i;
    int m_fib_i_minus_1;
};

Jetzt wollen wir natürlich auch zur nächsten Fibonaccizahl übergehen, dazu implementiere ich eine Funktion 'next'

class Fibo
{
public:
    int get() const {
        return m_fib_i;
    }
    void next() {
        int fib_i_plus_1 = m_fib_i + m_fib_i_minus_1;
        m_fib_i_minus_1 = m_fib_i;
        m_fib_i = fib_i_plus_1;
    }

private:
    int m_fib_i;
    int m_fib_i_minus_1;
};

Oben siehst Du die bekannte Gleichung \(f_{i+1} = f_i+ f_{i-1}\). Anschließend geschieht der Übergang von \(i\) nach \(i+1\). Das aktuelle \(i\) ist um \(1\) erhöht.

Am Anfang - nach Erstellen eines Objekts der Klasse 'Fibo' - soll \(i=0\) sein und das 'get()' natürlich eine \(f_0=0\) liefern. Das \(f_{(-1)}\) berechnet sich aus$$f_1 = f_0 + f_{(-1)} \implies f_{(-1)} = f_1 - f_0 = 1-0=1$$und damit ist klar, wie die Member der Klasse initialisiert werden müssen. Im folgenden gleich das ganze Programm:

#include <iostream>

class Fibo
{
public:
    Fibo()
        : m_fib_i(0)          // f_0 = 0
        , m_fib_i_minus_1(1)  // f_(-1) = 1
    {}
    int get() const {
        return m_fib_i;
    }
    void next() {
        int fib_i_plus_1 = m_fib_i + m_fib_i_minus_1;
        m_fib_i_minus_1 = m_fib_i;
        m_fib_i = fib_i_plus_1;
    }

private:
    int m_fib_i;
    int m_fib_i_minus_1;
};

int main() {
    using namespace std;
    for(int m; cout << "Type in a number: ", cin >> m; ) {
        cout << "Fibonacci numbers up to " << m << endl;
        for(Fibo f; f.get() <= m; f.next() ) {
            cout << f.get() << " ";
        }
        cout << "\n" << endl;
    }
    return 0;
}
Dieses Programm gibt alle Fibonaccizahlen bis zu einer Obergrenze 'm' aus. Und nun sollte es kein Problem sein, den Primzahltest von mathe53 hinzu zu fügen. Das erweiterte 'main' sähe so aus:

int main() {
    using namespace std;
    for(int m; cout << "Type in a number: ", cin >> m; ) {
        cout << "Fibonacci primes up to " << m << endl;
        for(Fibo f; f.get() <= m; f.next() ) {
            if(Ist_Primzahl(f.get())) {  // ist es eine Primzahl?
                cout << f.get() << " ";  // ... nur dann ausgeben
            }
        }
        cout << "\n" << endl;
    }
    return 0;
}

Bem.: 'Ist_Primzahl' von mathe53 enthält einen kleinen Fehler. Oben muss es 'aZahl < 2' statt 'aZahl <= 2' heißen. Die 2 ist auch eine Primzahl!

Da Du das std::sqrt nicht nutzen darfst (so ein Quatsch!), schnitze Dir ein eigenes.

namespace limonade {      // namespace != std, um Verwechslungen zu verhindern
    double abs_(double a) {
        if( a < 0)
            return -a;
        return a;
    }
    int sqrt(int a) {
        assert(a >= 0);  // Eingangsbedingung prüfen
        if( a < 2 )
            return a;
        double x_prev;
        double x = a/2.;  // 1. Schätzung
        do {
            x_prev = x;  // bisheriges x merken
            x = (x_prev + a/x_prev)/2;
        } while( abs_(x_prev - x) > 0.5 );
        return int(x);
    }
}

und füge es so in die Funktion Ist_Primzahl ein

bool Ist_Primzahl( int zahl ) {
    if ( zahl < 2) {
        return false;  // Primzahlen beginnen erst mit 2
    }
    int max_teiler = limonade::sqrt(zahl);
    for ( int teiler=2; teiler <= max_teiler; ++teiler) {
        if( zahl % teiler == 0) {
            return false;  // keine Primzahl; 'teiler' ist Teiler von 'zahl'
        }
    }
    return true; // Primzahl
}
falls Du noch Fragen hast, nur heraus damit ;-)

Gruß Werner

von
+1 Daumen

Hier der geänderte Code. Wesentliche Fehler:

- Variable a falsch initialisiert

- do-while Schleife gibt Zahlen über dem festgelegten Limit aus


#include <iostream>
#include <math.h>

using namespace std;

int a = 0;
int b = 1;
int c = 0;
int sum = 0;
int primes_printed = 0;
int m = 0;

bool Ist_Primzahl( int aZahl );

int main()
{
  //Type in a number m
  cout << "Type in a number: " << endl;
  cin >> m;
  ///cout << "The entered number is: " << m << "." << endl;
 
  if(m==0)
  {
    cout << 0 << endl;
  }
 
  else
  {
    cout << 0 << endl;
    cout << 1 << endl;
     
    while (c <= m)
    {
      c = a + b;

      if ( c <= m )
      {
        if ( Ist_Primzahl(c) )
        {
            cout << c << "(Primzahl)" << endl;
            primes_printed++;
        }
        else
          cout << c << endl;
      }

      a = b;
      b = c;
    }
  }

  cout << "Number of printed primes " <<  primes_printed << endl;

  return 0;
}

bool Ist_Primzahl( int aZahl )
{
  int teiler;

  if ( aZahl <= 2)
  {
    // keine Primzahl
    return false;
  }

  // sqrt(aZahl) siehe "Sieb des Eratosthenes"
for ( teiler=2; teiler <= sqrt(aZahl); teiler++)
  {
    if( aZahl % teiler == 0)
    {
      // keine Primzahl
      return false;
    }
  }

  // Primzahl
return true;
}

von

Es gibt die Restriktion dass \(math.h\) nicht verwendet werden darf.

Es gibt die Restriktion dass math.h nicht verwendet werden darf.

Na ja !? ... darf #include <cmath> verwendet werden? ;-)

auch nicht :-(

Dann

#include <math.h>
weglassen und
for ( teiler=2; teiler <= sqrt(aZahl); teiler++) 
ändern in
for ( teiler=2; teiler < aZahl; teiler++

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community