Contest #1: Fibonacci Zahlen

fr33g

Meine Lösung:

#include <iostream>

using namespace std;

int main()
{
    unsigned int first = 0;
    unsigned int second = 1;
    unsigned int quantity = 18;

    cout << first << endl;
    cout << second << endl;
    for( int i = 0; i < quantity; ++i )
    {
        cout << first + second << endl;
        int temp = first + second;
        first = second;
        second = temp;
    }
}

Allerdings würde ich vorschlagen, dass man die Datei irgendwo hochladen sollte, wo nur der "Chef" Zugriff hat, dieser läd dann nach der Deadline alle Codes hier hoch, bzw jeder darf dann drauf zugreifen. Dies würde vermeiden, dass jemand Code kopiert und dann eventuelle Streitereien enstehen. Man weiß ja nie
Nur so ein Vorschlag:-P

Lg freeG

volkard

314159265358979 schrieb:

Jeder soll in einem gewissen Zeitrahmen ein Programm zur Lösung einer Aufgabe schreiben. Danach wird von den Usern abgestimmt, welches den Contest gewinnt. Es soll das eleganteste Programm bewertet werden, Performance ist nebensächlich.

Am elegantesten ohne Kommentare?

volkard

fr33g schrieb:

Allerdings würde ich vorschlagen, dass man die Datei irgendwo hochladen sollte, wo nur der "Chef" Zugriff hat

Chef hat Mail im Profil ermöglicht.
Ich habe soeben meinen Vorschlag (ohne Kommentare) gemailt.

edit: Mist, war doch mit 8 Zeilen einleitenden Kommentaren. Naja, er soll's löschen, wenn ohne gefordert ist oder drinlassen, wenn mit.

Mit switch Schleife:

#include <iostream> 

class fib
{
public:
	fib():n(20),s(0),a(1){};
	fib(fib const& o)
	:n(o.n-1),a(o.s),s(o.s+o.a)
	{
		std::cout<<o.s<<" ";
		switch( 1 <= n >= 1){
			while(n) {
				default: fib(*this); break;
				case 0:break;
			};
		}
	}
private:
	int s;
	int a;
	int n;
};

int main(){
	fib nacci;
	fib o(nacci);
	return 0;
}

fr33g

volkard schrieb:

fr33g schrieb:

Allerdings würde ich vorschlagen, dass man die Datei irgendwo hochladen sollte, wo nur der "Chef" Zugriff hat

Chef hat Mail im Profil ermöglicht.
Ich habe soeben meinen Vorschlag (ohne Kommentare) gemailt.

edit: Mist, war doch mit 8 Zeilen einleitenden Kommentaren. Naja, er soll's löschen, wenn ohne gefordert ist oder drinlassen, wenn mit.

Oh ok, sorry habe ich überlesen;-)

Lg freeG

@21_00
Schlimmer geht's nicht.

µ schrieb:

@21_00
Schlimmer geht's nicht.

Doch. Hatte den Contest aber erst kurz vor Einsendeschluss gesehen.

Gibts eigentlich noch eine Auswertung wer gewinnt?

volkard

TungAuswert? schrieb:

Gibts eigentlich noch eine Auswertung wer gewinnt?

Am 12 Aug 2011 14:59 hat er den Einsendeschluß verschoben auf Montag 18:00h.

wxSkip

314159265358979 schrieb:

Gut, dann wird die Aufgabe wie folgt abgeändert:
- Der User gibt 2 _beliebig_ große natürliche Zahlen ein, wobei die erste kleiner ist als die zweite.
- Ihr sollt alle Fibonacci Zahlen zwischen diesen beiden Zahlen ausgeben. "zwischen" bedeutet exclusive-exclusive. Bignum-Libraries dürfen nicht verwendet werden.
- Deadline ist Montag 18:00

So, diese Aufgabe habe ich gerade gelöst. Besteht eigentlich noch Interesse an dieser Aufgabenstellung?
Merkmale:
-115 Zeilen
-nicht unbedingt auf Performance ausgelegt, sondern eher auf Eleganz und Erweiterbarkeit.
-Zeit für Ausgabe aller Fibonacci-Zahlen zwischen 0 und Googol: 0.425s (2x2,4GHz)
-Zeit für Berechnung (Ausgabe auskommentiert) aller Fibonacci-Zahlen zwischen 0 und 10^1000: 0.246s

@Pi: Soll ich dir die Lösung per Mail zusenden oder sie hier posten, da sie ja noch bewertet werden muss?

Werner Salomon

314159265358979 schrieb:

Gut, dann wird die Aufgabe wie folgt abgeändert:
- Der User gibt 2 _beliebig_ große natürliche Zahlen ein, wobei die erste kleiner ist als die zweite.
- Ihr sollt alle Fibonacci Zahlen zwischen diesen beiden Zahlen ausgeben. "zwischen" bedeutet exclusive-exclusive. Bignum-Libraries dürfen nicht verwendet werden.
- Deadline ist Montag 18:00

Bitte ein Bit schrieb:

Naja, wie wäre es mit einem Obfuscation Wettbewerb. Oder wir sagen derjenige, der die wenigsten Zeichen Quelltext benötigt, gewinnt.

314159265358979 schrieb:

Klingt wie eine interessante Idee. Dann setzen wir das als Bewertungs-Kriterium fest.

'die wenigsten Zeichen' hin oder her. Zunächst mal sollte das Programm auch '2 _beliebig_ große natürliche Zahlen' als Eingabe verkraften. Selbst wenn man für den Bereich '_beliebig_ groß' nur(!?) die Zahlen von 0 bis std::numeric_limitsstd::size\_t::max() zulässt, sind die dabei entstehenden Fibonacci Zahlen groß genug - wie ich meine.
Hier mein Vorschlag - ohne auf die Anzahl der Zeichen zu achten:

#include <cassert>
#include <algorithm> // transform
#include <functional> // bind2nd
#include <iostream>
#include <iterator> // advance
#include <vector>
#include <boost/operators.hpp> // addable
#include <boost/iterator/iterator_facade.hpp>

class BigInt : public boost::addable< BigInt >
{
public:
    BigInt( std::size_t i = 0 ) : m_digits()
    {
        if( i == 0 )
            m_digits = std::vector< int >( 1, 0 );
        for( ; i > 0; i /= 10 )
            m_digits.push_back( i % 10 );
    }

    BigInt& operator+=( const BigInt& b )
    {
        if( m_digits.size() < b.m_digits.size() )
            m_digits.resize( b.m_digits.size(), 0 );
        std::vector< int >::iterator i = m_digits.begin();
        int carry = 0;
        for( std::vector< int >::const_iterator j = b.m_digits.begin(); j != b.m_digits.end(); ++i, ++j )
        {
            if( (*i += *j + carry) >= 10 )
            {
                *i -= 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        for( ; i != m_digits.end(); ++i )
        {
            if( (*i += carry) >= 10 )
            {
                *i -= 10;
                carry = 1;
            }
            else
                carry = 0;
        }
        if( carry > 0 )
            m_digits.push_back( carry );
        return *this;
    }

    template< typename E, typename Traits > friend
        std::basic_ostream< E, Traits >& operator<<( std::basic_ostream< E, Traits >& out, const BigInt& bi )
    {
        std::transform( bi.m_digits.rbegin(), bi.m_digits.rend()
            , std::ostream_iterator< E >( out ), std::bind2nd( std::plus< E >(), out.widen('0') ) );
        return out;
    }
    friend void swap( BigInt& a, BigInt& b )
    {
        swap( a.m_digits, b.m_digits );
    }
private:
    std::vector< int > m_digits;
};

template< typename T >
class FiboIterator : public boost::iterator_facade< FiboIterator< T >, T, boost::forward_traversal_tag, const T >
{
public:
    FiboIterator() : m_x(0), m_prev(1) {}
    const T dereference() const { return m_x; }
    void increment()
    {
        T next = m_x + m_prev;
        swap( m_prev, m_x );
        swap( m_x, next );
    }
private:
    T m_x, m_prev;
};

int main()
{
    using namespace std;
    cout << "Geben Sie zwei positive Zahlen in steigender Reihenfolge ein" << endl;
    size_t x1, x2;
    if( cin >> x1 >> x2 && x2 > x1 )
    {
        cout << "Die Fibonaccizahlen zwischen F(" << x1 << ") und F(" << x2 << ") sind:" << endl;  
        FiboIterator< BigInt > fibo;
        for( advance( fibo, ++x1 ); x1 < x2; ++x1, ++fibo )
            cout << "F(" << x1 << ") = " << *fibo << endl;
    }
    return 0;
}

Beispiel:

Geben Sie zwei positive Zahlen in steigender Reihenfolge ein
305 312
Die Fibonaccizahlen zwischen F(305) und F(312) sind:
F(306) = 3987795824799770715342824788687062628452272409956636682999616408
F(307) = 6452389184720949856740872794933738025334109298792472139250504213
F(308) = 10440185009520720572083697583620800653786381708749108822250120621
F(309) = 16892574194241670428824570378554538679120491007541580961500624834
F(310) = 27332759203762391000908267962175339332906872716290689783750745455
F(311) = 44225333398004061429732838340729878012027363723832270745251370289

Gruß
Werner

wxSkip

@Werner Salomon:
Ich glaube, er meint, dass wenn du 8 und 54 eingibst, dass dann 13, 21, 34 ausgegeben werden...

314159265358979

Sorry Leute, ich hatte kein Internet bis gerade eben
Dass da dann doch noch so viele interessante Lösungen zur urspünglichen Aufgabenstellung mit geändertem Kriterium kamen, finde ich super

@Werner: Sehr schöne Lösung. Allerdings trifft das von wxSkip genannte zu. Nicht die x-te Fibo-Zahl wird eingegeben, sondern eine Art "Startwert" ab dem gesucht werden soll. (Und natürlich Endwert)

wxSkip

Gibt's auch eine Auswertung?

314159265358979

Gibt doch keine Lösung bisher, was soll ich denn da auswerten?

wxSkip

314159265358979 schrieb:

Gibt doch keine Lösung bisher, was soll ich denn da auswerten?

Meine?

volkard

314159265358979 schrieb:

Gibt doch keine Lösung bisher, was soll ich denn da auswerten?

Ich dachte, ich habe Dir über's Profil eine Lösung geschickt.

314159265358979

Ups, ganz übersehen, sorry.
Poste sie einfach hier in den Thread.

314159265358979

@volkard: dann hätte ich eine email, oder?
Bekommen habe ich keine.

wxSkip

Also gut:

#include <string>
#include <iostream>
#include <sstream>

template<typename T> std::string ToString(T const &in)
{
    std::ostringstream stream;
    stream << in;
    return stream.str();
}

class StringInt
{
    std::string val;

    std::string RemovePendingZeros(std::string const &in);

    public:
    StringInt(int p_val);
    StringInt(std::string p_val);

    StringInt &operator+=(StringInt const &second);
    bool operator==(StringInt const &second);
    bool operator<(StringInt const &second);
    bool operator>(StringInt const &second);

    friend std::ostream &operator<<(std::ostream &stream, StringInt const &val);
};

std::ostream &operator<<(std::ostream &stream, StringInt const &val)
{
    stream << val.val;
    return stream;
}

StringInt::StringInt(int p_val)
  : val(ToString(p_val))
{
}

StringInt::StringInt(std::string p_val)
  : val(RemovePendingZeros(p_val))
{
}

std::string StringInt::RemovePendingZeros(std::string const &in)
{
    size_t first_nonzero = in.find_first_not_of('0');
    if(first_nonzero < in.size()) return in.substr(first_nonzero);
    else return "0";
}

StringInt &StringInt::operator+=(StringInt const &second)
{
    size_t filled_size = std::max(val.size(), second.val.size()) + 1;

    val = std::string(filled_size - val.size(), '0') + val;
    std::string val_2 = std::string(filled_size - second.val.size(), '0') + second.val;

    std::string::reverse_iterator iter_1 = val.rbegin(), iter_2 = val_2.rbegin();

    bool has_add_carry = false;

    for(; iter_1 != val.rend() && iter_2 != val_2.rend(); ++iter_1, ++iter_2)
    {
        int sum = (*iter_1 - '0') + (*iter_2 - '0') + has_add_carry;
        *iter_1 = '0' + sum % 10;
        has_add_carry = sum / 10;
    }

    val = RemovePendingZeros(val);
    return *this;
}

bool StringInt::operator==(StringInt const &second)
{
    return val == second.val;
}

bool StringInt::operator<(StringInt const &second)
{
    size_t filled_size = std::max(val.size(), second.val.size());
    std::string val_2;

    if(filled_size != val.size()) val = std::string(filled_size - val.size(), '0') + val;
    val_2 = std::string(filled_size - second.val.size(), '0') + second.val;

    bool result = val < val_2;
    val = RemovePendingZeros(val);
    return result;
}

bool StringInt::operator>(StringInt const &second)
{
    return !(*this < second) && !(*this == second);
}

template<typename T> void print_fibs_between(T min, T max)
{
    T first_var = 0, second_var = 1;

    while(second_var < max)
    {
        if(second_var > min) std::cout << second_var << "\n";
        first_var += second_var;
        std::swap(first_var, second_var);
    }
}

int main()
{
    std::string min, max;
    std::cin >> min >> max;
    print_fibs_between(StringInt(min), StringInt(max));
}

P.S.: Hast du meine E-Mail in deinem Postfach gesehen? (das war der gleiche Code)