W
knivil schrieb:
Diese Folge ist die sogenannte Collatz-Folge und endet nach heutigen Kenntnisstand immer mit einer 1.
Kannst du bitte eine Quelle angeben, wo dein immer bewiesen ist. Ansonsten ist der Kenntnisstand: Wir wissen es nicht.
Ich hatte mich ungenau ausgedrückt. Ich meinte natürlich, dass bis heute keine natürliche Zahl bekannt ist, bei der die Collatz-Folge nicht in 4,2,1 mündet. Da schon viele Leute mit viel PC-Power danach gesucht haben, kann man sicher annehmen, dass es für alle Werte gilt, die auf einem normalen PC in ein int passen. Wer da genaueres wissen möchte, folge dem Link oben.
knivil schrieb:
Ausserdem wird es doch erst interessant, wenn man einige Probleme loesen kann. Z.b. welches n<10^8 generiert die laengste Sequenz? Kann diese Frage dein Iterator beantworten?
nun, da es praktisch ein Iterator im Sinne des C++-Standards ist, kann man natürlich mit Hilfe der Algorithmen und boost.bind ...
#include <algorithm> // copy, max_element
#include <iostream>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/bind.hpp>
typedef basic_collatz< int > Collatz; // basic_collatz< int > s.o.
Collatz makeCollatz( int x ) { return Collatz( x ); } // kein bind für Konstruktor
int main()
{
using namespace std;
cout << "Bitte Obergrenze fuer die Suche nach der laengsten Collatz-Folge angeben" << endl;
int n;
if( cin >> n )
{
cout << *max_element( boost::counting_iterator< int >( 1 ), boost::counting_iterator< int >( n+1 ),
boost::bind( &distance< Collatz >, boost::bind( &makeCollatz, _1 ), Collatz( 1 ) )
< boost::bind( &distance< Collatz >, boost::bind( &makeCollatz, _2 ), Collatz( 1 ) )
) << " liefert die laengste Folge im Interval [1," << n << "]" << endl;
}
return 0;
}
Ich nehme an, dass Volkard das wieder lustig findet - aber warum nicht.
Die Ausgabe ist z.B.:
Bitte Obergrenze fuer die Suche nach der laengsten Collatz-Folge angeben
1000
871 liefert die laengste Folge im Interval [1,1000]
Natürlich ist das nicht die performanteste Lösung, aber das war auch nicht die Frage. Ich habe auch einen (sehr) performaten Ansatz mit ähnlicher Vorgehensweise, aber den traue ich mich nicht mehr zu posten - sonst erschlägt 's Volkard.
Gruß
Werner
