3. Ganzzahlentyp Unsigned Long als Grenzwert für Fibonacci Folge wählen! Wie?

Ganzzahlentyp Unsigned Long als Grenzwert für Fibonacci Folge wählen! Wie?

  • L

    Hallo Leute 🙂

    Ich habe in diesem Programm die Ausgabe von allen 4 stelligen Fibonacci Zahlen - also Fibonacci Glied 17 - 20 (war meine Aufgabenstellung)!

    So da ... Nun möchte ich gerne noch eine 2. Schleife einbauen die alle Fibonacci Zaheln ausgibt die sich durch einen der Ganzzahlentypen darstellen lassen. Also wenn ich jetzt z.B.: unsigned long hernehme soll die letzte Zahl kleiner gleich 4.294.967.295 sein...

    Das Problem ist wenn ich eine 2. for-Schleife verwende kann ich ich in der ja nur den k Wert (also das k-te Glied verändern) ich hab 2 Funktionen für mein Programm... Bitte um Hilfe!

    Wie würdet Ihr das am besten angehen? 😕

    MFG
    ltseza

    #include <iostream>
#include <iomanip>
#include <climits>

using namespace std;

int fibonacci(int n)
{
    if  (n<=2)
    {
        return 1;
    }

    else
    {
        return fibonacci(n-1) + fibonacci(n-2);
    }

}

int main()
{
    cout << setw(77) << "--------------------------------------------" << endl;
    cout << setw(77) << " Ausgabe aller 4 stelligen Fibonacci Glieder:" << endl;
    cout << setw(77) << "--------------------------------------------" << "\n" << endl;

    for (int k=17; k<=20; k++)

    {

        cout << setw(70) << k << ":\t" << fibonacci(k) << "\n" << endl;

    }

    return 0;
}
    0
  • I
     

    #include <iostream>

bool detectOverflowAdd(unsigned long a, unsigned long b)
{
  if(a + b < a)
   return true;

  else 
   return false;

}

unsigned long fib(int n)
{
 unsigned long n1 = 0;
 unsigned long n2 = 1;
 unsigned long temp = 0;
 for (int i = 0; i < n - 1; ++i)
 {
  if (!detectOverflowAdd(n1,n2))
  {
   temp = n2;
   n2 = n1 + n2;
   n1 = temp;
  }
  else
  {
	  std::cout << "Overflow\n";
	  return -1;
  }

 }
  return n2;
}

int main()
{
  std::cout << fib (48) << '\n';
}
    0
  • S

    IrgendeinName schrieb:

    ...

    Also wenn wir schon einfach was posten dürfen, dann http://ideone.com/JoJZ5A

    0
  • ?

    Statt 40 Zeilen leicht verständlichen Codes 178 Zeilen C++-Wirrwar, der komplexer als das eigentliche Problem ist. Hab mal den Code von IrgendeinName geklaut und leicht geändert.

    #include <iostream>
unsigned long fib(int n){
	unsigned long n1 = 0;
	unsigned long n2 = 1;
	unsigned long temp = 0;

	for (int i = 0; i < n - 1; i++){
		temp = n2;
		n2 += n1;
		if (n2 < n1){ //overflow Bedingung
			std::cout << "Overflow\n";
			return -1;
		}
		n1 = temp;
	}
	return n2;
}

int main(){
	std::cout << fib(48) << '\n';
}

    Wenn man unbedingt möchte kann man die unsigned long ints noch durch einen Template Typ ersetzen, aber das erkenne ich aus der Aufgabenstellung nicht.

    0
  • L

    Also mal danke für eurer Antworten!

    Ich hab mein Program jetzt überarbeitet und ich hab eine letzte Frage:

    Wie schaffe ich es in meiner Bedingung festzulegen dass er ausschließlich die vierstelligen Zahlen ausgibt? Ich will sie nicht selbst festlegen. Das soll das Programm machen. Ich will nur die Grenze setzen. Mit meiner while Schleife hört es zumindest bei den vierstelligen zu zählen auf. Aber ich schaffe es einfach nicht dass er auch erst bei den vierstelligen die Ausgabe beginnt!

    also einfach nur festlege dasa es ab fibonacci(i)>999 zu zählen beginnt.

    Ein Rat täte gut 🙂

    #include <iostream>
#include <iomanip>
#include <climits>

using namespace std;

int fibonacci(int n)
{
    if  (n <= 2)
    {

        return 1;
    }

    else
    {
        return fibonacci(n-1) + fibonacci(n-2);
    }

}

int main()
{
    cout << setw(77) << "--------------------------------------------" << endl;
    cout << setw(77) << " Ausgabe aller 4 stelligen Fibonacci Glieder:" << endl;
    cout << setw(77) << "--------------------------------------------" << "\n" << endl;

    int i = 1;

        while (fibonacci(i) <= 10000)

            {

                cout << fibonacci(i) << endl;
                i++;

            }

    return 0;
}

    MFG Ltseza

    0
  • N

    Du musst alle Folgenglieder berechnen, aber nur die 4-stelligen ausgeben, das kannst du z.B. mit der if Anweisung tun.

    if(fibonacci(i)>999)

    Du musst nur diese eine Zeile einfügen. Überleg dir wo.

    0
  • L

    Super danke 🙂

    hatte es mit if eh schon versucht nur war mir nicht sicher ob da so funktionieren würde und hatte die Verzweigung auch falsch gelegt ^^

    So funktioniert es:

    while (fibonacci(i) <= 9999)

            {
                if (fibonacci(i)>999)

                {
                    cout << fibonacci(i) << endl;

                }

                i++;

            }
    0
  • ?

    Wenn du das auf alle durch unsigned long darstellbaren Fibonacci-Zahlen ausdehnen willst, solltest du den rekursiven Ansatz nochmal überdenken (das solltest du eigentlich sowieso), denn dieser hat exponentielle Laufzeitkomplexität. Auf fib(48) kannst du so seeeeeehr lange warten.

    0
  • S

    seldon schrieb:

    Auf fib(48) kannst du so seeeeeehr lange warten.

    fib(49) hat auf meinem laptop (msvc++2010 im release) auf einem kern meines i7 quadcores etwa 2-3 minuten gedauert (mit Scheme unter DrRacket fast 3 Stunden). Mit tail rekursion wars sofort da in beiden sprachen...

    0
  • I

    seldon schrieb:

    Wenn du das auf alle durch unsigned long darstellbaren Fibonacci-Zahlen ausdehnen willst, solltest du den rekursiven Ansatz nochmal überdenken (das solltest du eigentlich sowieso), denn dieser hat exponentielle Laufzeitkomplexität. Auf fib(48) kannst du so seeeeeehr lange warten.

    Naja, MSVC 2012 Release 15-20 Sek.
    Meine Iterative war instant, also im Hundertstel bis Millisekundenbereich.

    0
  • S

    IrgendeinName schrieb:

    seldon schrieb:

    Auf fib(48) kannst du so seeeeeehr lange warten.

    Naja, MSVC 2012 Release 15-20 Sek.
    Meine Iterative war instant, also im Hundertstel bis Millisekundenbereich.

    die iterative variante geht schnell. aber die standard rekursive dauert und dauert. (2^48 aufrufe oder so)
    LoL

    0
  • ?

    Die rekursive Variante ist, wenn man die Berechnung einer einzelnen Fibonacci-Zahl betrachtet, in Θ(φn), wobei φ ≈ 1,618 der goldene Schnitt ist. Die Anzahl der rekursiven Funktionsaufrufe ist in der gleichen Komplexitätsklasse. Die iterativen und endrekursiven Varianten sind in Θ(n).

    Allerdings: Da das Programm alle Fibonacci-Zahlen unterhalb einer Grenze ausgeben soll, ist es nicht notwendig, jede Fibonacci-Zahl wieder neu von vorne auszurechnen:

    #include <iostream>

int main() {
  unsigned long m, n;

  m = 0;
  n = 1;

  while(m < 10000) {
    std::cout << m << '\n';

    unsigned long next = m + n;
    m = n;
    n = next;
  }
}

    ...so ist die Berechnung der ersten n Fibonacci-Zahlen in Θ(n), mithin die Berechnung jeder einzelnen Zahl in Θ(1). Die gesamte Aufgabenstellung fällt entsprechend mit dem rekursiven Ansatz in Θ(φn) (geometrische Reihe) und mit dem iterativen in Θ(n2).

    Komplexitätstechnisch geht es nicht mehr schneller. Man kann die Berechnung in die Compilezeit verlegen, wenn man lustig ist und die Obergrenze zur Compilezeit feststeht, aber da man immer noch n Zahlen ausgeben muss, ist das Ergebnis immer noch in Θ(n).

    0
Anmelden zum Antworten