Contest #1: Fibonacci Zahlen

[volkard]

SeppJ schrieb:

Aber die neue Aufgabe ist, alle Fib-Zahlen zwischen zwei benutzergegebenen Zahlen auszugeben

Ich habe in der Tat angefangen damit. Bin jetzt bei 122 Zeilen und das Prog schweigt sich einfach aus und zeigt mal gar nichts an. Wiedermal sowas, wo man den Debugger anmachen möchte. Aber nein, ohne ist es viel spannender und schärft den Blick.

[SideWinder]

Ich schlage einen neuen Ansatz vor: Die ausdrucksstärkste Implementierung.

Vorschläge?

MfG SideWinder

[volkard]

SideWinder schrieb:

Ich schlage einen neuen Ansatz vor: Die ausdrucksstärkste Implementierung.
Vorschläge?
MfG SideWinder

Ausdrucksstärke ist Effekt pro Token? Das wird doch gerade parallel gemacht.

[SideWinder]

Nein, ich denke da eher an ausdrucksstärke des Codes = Lesbarkeit.

MfG SideWinder

[Mups]

SeppJ schrieb:

@Mups: Du kannst dir noch zwei Klammern sparen.

Und coole Nullinitialisierung

Ich hatte gerade einen ganz ähnlichen Ansatz gebastelt, dank expliziter Initialisierung aber länger. Hat sich nun wohl erledigt, kürzer als deines (minus die Klammern), bekomme ich es vorerst nicht mehr

Stimmt, das mit den Klammern ist mir erst zu spät auf dem Nachhauseweg im Bus eingefallen

#include<iostream>
int a,b=1,x,y;int main(){std::cin>>x>>y;for(;a<y;b+=a,a=b-a)if(a>x)std::cout<<a<<" ";}

18+1+86 Zeichen == 105 Zeichen

Doof gefragt: Wie zähle ich die Tokens?

int a,b=1,x,y;

Sind das "int" "a" "," "b" "=" "1" "," "x" "," "y" ";" also 11 Token?

[seldon]

µ schrieb:

http://upload.wikimedia.org/math/1/6/e/16ea0dee516003a472c75c4e0b8b4154.png

Der zweite Term wird mit hohem n immer kleiner, und auch bei kleinen kommt man mit einer Rundung davon. Zwei Methoden in einem (zu Vergleichszwecken):

#include <iostream>
#include <cmath>

int main() {
  int fib[] = { 0, 1 };

  for(int i = 0; i < 20; ++i) {
    std::cout << fib[i % 2] << ' ';
    fib[i % 2] = fib[0] + fib[1];
  }
  std::cout << '\n';

  for(int i = 0; i < 20; ++i) {
    std::cout << static_cast<int>(1 / std::sqrt(5) * std::pow((1 + std::sqrt(5)) / 2, i) + .5) << ' ';
  }
  std::cout << '\n';
}

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

[21_00]

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

[Gast]

@21_00
Schlimmer geht's nicht.

[21_00]

µ schrieb:

@21_00
Schlimmer geht's nicht.

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

[TungAuswert?]

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?