Contest #1: Fibonacci Zahlen

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

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

[314159265358979]

Ah ich seh schon, ich hab hier meine andere Email Addy eingetragen, wo ich selten reinsehe. Ist beides angekommen.

[wxSkip]

314159265358979 schrieb:

Ah ich seh schon, ich hab hier meine andere Email Addy eingetragen, wo ich selten reinsehe.

Wozu gibt es E-Mail-Clients wie Thunderbird?

[volkard]

#include <iostream>
#include <vector>
#include <cassert>
#include <iomanip>
#include <string>
#include <algorithm>

uint32_t const base=1000000000;
size_t const baseMinusOneLen=9;

struct AddResult {
	uint32_t lo;
	bool carry;
};

AddResult add(uint32_t a,uint32_t b,bool carry)
{
	AddResult result;
	result.lo=a+b+carry;
	result.carry=0;
	if(result.lo>=base) {
		result.lo-=base;
		result.carry=1;
	}
	return result;
}

void fiboAddAssign(std::vector<uint32_t>& a,std::vector<uint32_t> const& b)
{
	assert(a.size()==b.size() || a.size()==b.size()-1);
	bool carry=0;
	for(size_t i=0; i!=a.size(); ++i) {
		AddResult r=add(a[i],b[i],carry);
		a[i]=r.lo;
		carry=r.carry;
	}
	if(a.size()!=b.size()) {
		AddResult r=add(*b.rbegin(),0,carry);
		a.push_back(r.lo);
		carry=r.carry;
	}
	if(carry) {
		a.push_back(carry);
	}
}

void fiboWrite(std::vector<uint32_t> const& a)
{
	using namespace std;
	char oldFill=cout.fill('0');
	auto pos=a.rbegin();
	cout<<*pos;
	++pos;
	while(pos!=a.rend()) {
		cout<<setw(baseMinusOneLen)<<*pos;
		++pos;
	}
	cout<<'\n';
	cout.fill(oldFill);
}

std::vector<uint32_t> fiboRead()
{
	using namespace std;
	vector<uint32_t> result;
	string digits;
	if(!(cin>>digits)) {
		throw "A deamon arises and mourns \"All your nose are belong to us.\"";
	}
	reverse(digits.begin(),digits.end());
	while(digits.size()%baseMinusOneLen!=0) {
		digits.append("0");
	}
	for(size_t i=0; i!=digits.size(); i+=baseMinusOneLen) {
		int32_t digit=0;
		for(int j=baseMinusOneLen-1; j>=0; --j) {
			digit=digit*10+digits[i+j]-'0';
		}
		result.push_back(digit);
	}
	return result;
}

bool fiboLess(std::vector<uint32_t> const& a,std::vector<uint32_t> const& b)
{
	if(a.size()<b.size()) {
		return true;
	}
	if(a.size()>b.size()) {
		return false;
	}
	size_t i=a.size();
	do {
		--i;
		if(a[i]!=b[i]) {
			return a[i]<b[i];
		}
	} while(i!=0);
	return false;
}

bool fiboLessOrEqual(std::vector<uint32_t> const& a,std::vector<uint32_t> const& b)
{
	return !fiboLess(b,a);
}

int main ()
{
	using namespace std;
	vector<uint32_t> a;
	a.push_back(0);
	vector<uint32_t> b;
	b.push_back(1);
	vector<uint32_t> lowerBound=fiboRead();
	vector<uint32_t> upperBound=fiboRead();
	while(fiboLessOrEqual(a,lowerBound)) {
		fiboAddAssign(a,b);
		a.swap(b);
	}
	while(fiboLess(a,upperBound)) {
		fiboWrite(a);
		fiboAddAssign(a,b);
		a.swap(b);
	}
}

[314159265358979]

Hab die Addy da nicht eingetragen, da normalerweise Spam-Mail

[wxSkip]

Benchmark: Fibonacci-Zahlen zwischen 0 bis 10^1000 ausgeben:

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <ctime>

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);  //remove pending zeros
    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);
    }
}

clock_t wxSkip()
{
    StringInt min = std::string("0"), max = "1" + std::string(1000, '0');
    clock_t start = clock();
    print_fibs_between(min, max);
    return clock() - start;
}

uint32_t const base=1000000000;
size_t const baseMinusOneLen=9;

struct AddResult {
    uint32_t lo;
    bool carry;
};

AddResult add(uint32_t a,uint32_t b,bool carry)
{
    AddResult result;
    result.lo=a+b+carry;
    result.carry=0;
    if(result.lo>=base) {
        result.lo-=base;
        result.carry=1;
    }
    return result;
}

void fiboAddAssign(std::vector<uint32_t>& a,std::vector<uint32_t> const& b)
{
    assert(a.size()==b.size() || a.size()==b.size()-1);
    bool carry=0;
    for(size_t i=0; i!=a.size(); ++i) {
        AddResult r=add(a[i],b[i],carry);
        a[i]=r.lo;
        carry=r.carry;
    }
    if(a.size()!=b.size()) {
        AddResult r=add(*b.rbegin(),0,carry);
        a.push_back(r.lo);
        carry=r.carry;
    }
    if(carry) {
        a.push_back(carry);
    }
}

void fiboWrite(std::vector<uint32_t> const& a)
{
    using namespace std;
    char oldFill=cout.fill('0');
    auto pos=a.rbegin();
    cout<<*pos;
    ++pos;
    while(pos!=a.rend()) {
        cout<<setw(baseMinusOneLen)<<*pos;
        ++pos;
    }
    cout<<'\n';
    cout.fill(oldFill);
}

std::vector<uint32_t> fiboRead(std::string digits)
{
    using namespace std;
    vector<uint32_t> result;
    reverse(digits.begin(),digits.end());
    while(digits.size()%baseMinusOneLen!=0) {
        digits.append("0");
    }
    for(size_t i=0; i!=digits.size(); i+=baseMinusOneLen) {
        int32_t digit=0;
        for(int j=baseMinusOneLen-1; j>=0; --j) {
            digit=digit*10+digits[i+j]-'0';
        }
        result.push_back(digit);
    }
    return result;
}

bool fiboLess(std::vector<uint32_t> const& a,std::vector<uint32_t> const& b)
{
    if(a.size()<b.size()) {
        return true;
    }
    if(a.size()>b.size()) {
        return false;
    }
    size_t i=a.size();
    do {
        --i;
        if(a[i]!=b[i]) {
            return a[i]<b[i];
        }
    } while(i!=0);
    return false;
}

bool fiboLessOrEqual(std::vector<uint32_t> const& a,std::vector<uint32_t> const& b)
{
    return !fiboLess(b,a);
}

clock_t volkard()
{
    using namespace std;
    vector<uint32_t> a;
    a.push_back(0);
    vector<uint32_t> b;
    b.push_back(1);
    vector<uint32_t> lowerBound=fiboRead("0");
    vector<uint32_t> upperBound=fiboRead("1" + std::string(1000, '0'));
    clock_t start = clock();
    while(fiboLessOrEqual(a,lowerBound)) {
        fiboAddAssign(a,b);
        a.swap(b);
    }
    while(fiboLess(a,upperBound)) {
        fiboWrite(a);
        fiboAddAssign(a,b);
        a.swap(b);
    }
    return clock() - start;
}

int main()
{
    clock_t first = wxSkip(), second = volkard();
    std::cout << "wxSkip ticks: " << first << "\nvolkard ticks: " << second << "\n";
}

Output:
<sehr viele Zahlen>
wxSkip ticks: 6250
volkard ticks: 26979

Tja, volkard: C-Style-Funktionen, umständlich, länger und langsamer...

[314159265358979]

Der Sieger steht im Startpost - Glückwunsch.