3. Contest #1: Fibonacci Zahlen

Contest #1: Fibonacci Zahlen

  • K

    314159265358979 schrieb:

    Aufgabe #1: Gib die ersten 20 Fibonacci Zahlen auf der Standard-Ausgabe aus.
    Deadline: Heute 21:00

    Finde ich ja eine coole Idee mit dem Contest, aber sollte das mit der Standard-Ausgabe nen Witz sein?

    0
  • B

    bmario schrieb:

    Ich nehm' es zurück, SeppJ's ist schöner, Werner hat einen sinnlosen Include 🙂

    Du meinst <ostream>? Ob der sinnlos ist, kommt drauf an, ob man sich an den Standard oder an die Realität hält.

    0
  • 3

    SeppJ schrieb:

    Das war doch klar, du musst schon eine Initiative liefern, warum die Leute das anders machen sollten. 20 zur Compilezeit bekannte Zahlen zu berechnen ist viel zu einfach. Eigentlich ist alles was zur Compilezeit geht trivial, denn dann kann es auch der Programmierer vorher selbst ausrechnen und direkt in's Programm schreiben. Du hättest wenigstens sagen können, dass zwei Zahlen eingegeben werden und diese als Start gelten sollen, anstatt fest 0 und 1 zu nehmen.

    Was eine Lösung über Templates, wie die von bmario, verhindert hätte.

    SeppJ schrieb:

    Und du musst Bewertungskriterien vorher(!) festlegen. Ein Programm um aus zwei vorgegebenen Zahlen eine Fib-Folge zu berechnen scheint einfach, aber ist es gut? Ist es schnell? Kommt es mit Überläufen zurecht? Negative Startwerte? Ist der Code kurz oder umständlich?

    Eleganz definiert jeder anders für sich. Abstimmungen sind per Definition subjektiv, vielleicht hätte ich aber etwas eingrenzen können.

    Kóyaánasqatsi schrieb:

    Finde ich ja eine coole Idee mit dem Contest, aber sollte das mit der Standard-Ausgabe nen Witz sein?

    Nein. Siehe bmarios Lösung.

    Ihr könntet auch einfach Vorschäge machen, wie man es euch Recht machen kann, anstatt zu sagen, dass alles scheiße ist.

    0
  • Mod

    Was eine Lösung über Templates, wie die von bmario, verhindert hätte.

    Na und? Templatemetaprogrammierung nur um ihrer selbst willen ist nun einmal realitätsfern. Man kann ja schicke Sachen damit machen, aber mathematische Konstanten damit zur Compilezeit zu berechnen ist immer nur das Anfängerbeispiel, weil man es besser nachvollziehen kann, als wildes Jonglieren mit Typeninformation. Man kann durchaus Templatemetaprogrammierung auch mit Benutzerinteraktion kombinieren. Ich hatte hier mal so ein Zahlenratespiel, bei dem sämtliche möglichen Pfade die der Benutzer eventuell wählen könnte zur Compilezeit im Voraus berechnet wurden. Der Trick ist eben zu wissen, wann man sie einsetzen sollte und wann nicht.

    Und sofern dein Bewertungsmaßstab nicht "möglichst kompliziert" ist, muss die Aufgabe an sich schon ganz schön schwer sein, damit sich echte TMP lohnt.

    314159265358979 schrieb:

    Ihr könntet auch einfach Vorschäge machen, wie man es euch Recht machen kann, anstatt zu sagen, dass alles scheiße ist.

    Oje, du hast so eine unausgegorene 5 Minutenidee unter der Dusche und wenn man sagt was man da dran besser hätte machen können, dann ist man ein böser Basher der nur motzen kann? Ich halte mich lieber mal raus...

    0
  • 3

    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

    0
  • B
     

    #include <stdio.h>

int main(int, char**)
{
int f[4]={0,0,1,0},&g=f[2],&h=f[3];
for (;*f<20;(*f)++) h=g+f[1],f[1]=g,g=h,printf("%i ",h);
}

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

    Edit:
    Umstellung des Codes auf minimale Zeichenanzahl. #Bytes: 144

    0
  • C
    Mod

    Meine Lösung macht mehr als gefordert (hört nicht nach 20 Zahlen auf), und braucht den meisten Speicher und die längste Zeit zum Compilieren. Ein klarer Gewinner.

    #include <cstddef>
#include <cstdio>
#include <utility>
#include <type_traits>
#include <boost/mpl/at.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/has_key.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/pair.hpp>
#include <boost/mpl/pop_front.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/vector.hpp>

using boost::mpl::at;
using boost::mpl::if_;
using boost::mpl::if_c;
using boost::mpl::front;
using boost::mpl::has_key;
using boost::mpl::identity;
using boost::mpl::map;
using boost::mpl::pair;
using boost::mpl::pop_front;
using boost::mpl::push_front;
using boost::mpl::vector;

constexpr char source[] =
">++++++++++>+>+["
"    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>["
"        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-"
"            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>"
"    ]<<<"
"]"
"This program doesn't terminate; you will have to kill it."
"Daniel B Cristofani (cristofdathevanetdotcom)"
"http://www.hevanet.com/cristofd/brainfuck/";

template <std::ptrdiff_t N> struct mod_ptr_cmd { template <typename Env> static void run(Env& env) { env.ptr += N; } };
template <unsigned char N> struct mod_data_cmd { template <typename Env> static void run(Env& env) { *env.ptr += N; } };
struct get_cmd                                 { template <typename Env> static void run(Env& env) { *env.ptr = std::getchar(); } };
struct put_cmd                                 { template <typename Env> static void run(Env& env) { std::putchar( *env.ptr ); } };
struct block_begin                             { template <typename Env> static void run(Env&) {} };
struct block_end                               { template <typename Env> static void run(Env&) {} };

typedef map<
    pair<std::integral_constant<char, '>'>, mod_ptr_cmd<1>>,
    pair<std::integral_constant<char, '<'>, mod_ptr_cmd<-1>>,
    pair<std::integral_constant<char, '+'>, mod_data_cmd<1>>,
    pair<std::integral_constant<char, '-'>, mod_data_cmd<-1>>,
    pair<std::integral_constant<char, ','>, get_cmd>,
    pair<std::integral_constant<char, '.'>, put_cmd>,
    pair<std::integral_constant<char, '['>, block_begin>,
    pair<std::integral_constant<char, ']'>, block_end>> commands;

template <typename Command, char... Tail> struct fuse;

template <typename Command, typename Next, char... Tail> struct compile
    : compile<Next, void, Tail...>
{
    template <typename Env> static void run(Env& env)
    {
        Command::run( env );
        compile<Next, void, Tail...>::run( env );
    }
};

template <typename Command, char... Tail> struct compile<Command, void, Tail...>
    : fuse<Command, Tail...> {};

template <char... Tail> struct compile<block_begin, void, Tail...>
{
    typedef compile<void, void, Tail...> base;
    typedef typename front<typename base::tails>::type this_tail;
    typedef typename pop_front<typename base::tails>::type tails;
    template <typename Env> static void run(Env& env)
    {
        while ( *env.ptr != 0 )
        {
            base::run( env );
        }
        this_tail::run( env );
    }
};

template <char... Tail> struct compile<block_end, void, Tail...>
{
    typedef compile<void, void, Tail...> base;
    typedef typename push_front<typename base::tails, base>::type tails;
    template <typename Env> static void run(Env&) {}
};

template <typename T, typename U> struct fuse_command
    : pair<T, U> {};
template <std::ptrdiff_t a, std::ptrdiff_t b> struct fuse_command<mod_ptr_cmd<a>, mod_ptr_cmd<b>>
    : pair<mod_ptr_cmd<a+b>, void> {};
template <unsigned char a, unsigned char b> struct fuse_command<mod_data_cmd<a>, mod_data_cmd<b>>
    : pair<mod_data_cmd<a+b>, void> {};
template <typename U> struct fuse_command<void, U>
    : pair<U, void> {};

template <typename Command, char c, char... Tail> struct fuse<Command, c, Tail...>
    : compile<
        typename fuse_command<Command, typename if_<has_key<commands, std::integral_constant<char, c>>, typename at<commands, std::integral_constant<char, c>>::type, void>::type>::first,
        typename fuse_command<Command, typename if_<has_key<commands, std::integral_constant<char, c>>, typename at<commands, std::integral_constant<char, c>>::type, void>::type>::second,
        Tail...> {};
template <typename Command> struct fuse<Command>
{
    typedef vector<> tails;
    template <typename Env> static void run(Env& env) { Command::run( env ); }
};
template <> struct fuse<void>
{
    typedef vector<> tails;
    template <typename Env> static void run(Env&) {}
};

template <char... src> struct program
{
    template <typename Env> static void run(Env& env) { compile<void, void, src...>::run( env ); }
};

// Ein bisschen Hilfsmagie um den String ins Template zu bekommen
// wird irgendwann überflüssig
template <std::size_t... i> struct indexes
    : identity<indexes<i...>> {};

template <typename T, typename U> struct concat
    : concat<typename T::type, typename U::type> {};
template <std::size_t... i, std::size_t... j> struct concat<indexes<i...>, indexes<j...>>
    : indexes<i..., ( j + sizeof... i )...> {};

template <typename T> struct twice
    : concat<T, T> {};

template <std::size_t N> struct make_indexes
    : concat<twice<make_indexes<(N / 2)>>, if_c<(N % 2 == 1),
indexes<0>, indexes<>>> {};
template <> struct make_indexes<0>
    : indexes<> {};

template <typename = typename make_indexes<sizeof source - 1>::type> struct source_to_program;
template <std::size_t... i> struct source_to_program<indexes<i...>>
    : identity<program<source[ i ]...>> {};

struct Environment
{
    unsigned char data[32768];
    unsigned char* ptr;
};

int main()
{
    Environment env = { {}, env.data };
    source_to_program<>::type p;
    p.run( env );
}
    0
  • 3

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

    0
  • V
     

    #include <iostream>

int main()
{
    using namespace std;
    cout << "0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 620 987 1597 2584 4181" << '\n';
}

    Wie Werner, aber endl halte ich für schlecht. Auch, wenn hier das flushen nicht schadet, so habe ich dennoch sicher kein flushen gemeint. Trotzdem habe ich das newline von den Daten abgetrennt.

    0
  • Mod

    Bitte ein Bit schrieb:

    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.

    Eigentlich fand ich die neue Aufgabe langweilig und hätte nicht mitgemacht, aber das klingt interessant.

    Da gerade immer noch Lösungen zum Ursprungsbeitrag eingehen, solltest du dort vielleicht mal editieren (Ok, ich könnte das auch für dich machen, aber ich fände es nicht gut, wenn andere Leute meine Beiträge editieren).

    0
  • ?

    Erster Versuch fuer kurzen Code:

    Zeile 1: 16 Zeichen + 1 Newline
    Zeile 2: 63 Zeichen

    Macht 80 Byte Code. Das sind ~2/3 von der allerersten Lösung von SeppJ.

    Also noch viel Luft für Verkürzungen.

    Link:
    http://codepad.org/yy2fZHrB

    0
  • Mod

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

    0
  • C
    Mod

    nicht besonders kurz, dafür einfach:

    #include<iostream>
#include<math.h>
int main(){auto t=[](int x){return[](int x){return x*x;}(sqrt(x))==x;};int a,b;std::cin>>a>>b;for(;a<=b;++a)if(t(5*a*a+4)||t(5*a*a-4))std::cout<<a<<' ';}

    193 Zeichen

    0
  • ?

    Ich würde eine Regel einführen, dass Whitespaces und Newlines nicht gezählt werden.

    0
  • Mod

    math.h ist länger als cmath 😉 . Auch wenn es nicht Standard ist, so kann man doch ziemlich verlässlich annehmen, dass ein cmath die sqrt auch im globalen Namensbereich auslädt.

    Um solche Konflikte zu vermeiden, sollte man eventuell noch einen oder zwei bestimmten Compiler definieren. Wie wäre es, wenn das Programm entweder auf einem g++ 4.4 oder auf einem MSVC(was immer gerade aktuell ist) compilieren muss?

    0
  • C
    Mod

    SeppJ schrieb:

    math.h ist länger als cmath 😉

    Dafür spar ich mir ein std::

    0
  • Mod

    camper schrieb:

    SeppJ schrieb:

    math.h ist länger als cmath 😉

    Dafür spar ich mir ein std::

    Siehe Rest meines Beitrags. Auch wenn es nicht mehr im Standard liegt, so ist da doch noch Sparpotential.

    0
  • C
    Mod 

    #include<iostream>
int f(int x,int y=0){return y*y==x||y*y<x&&f(x,y+1);}int main(){int a,b;std::cin>>a>>b;for(;a<=b;++a)if(f(5*a*a+4)||f(5*a*a-4))std::cout<<a<<' ';}

    166 Zeichen.
    Mups Code um einen Bereichscheck erweitert dürfte immer noch kürzer sein. Vielleicht hat ja jemand eine Idee, wie nman den square-Test verkürzen könnte.

    0
  • ?

    @camper
    I lol'd 😃

    @Topic
    Gute Idee. Blöde Aufgabe.

    0
  • ?

    Meine angepasste Lösung:

    #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+88 Zeichen == 107 Zeichen

    Allerdings werden hier wirklich nur die Zahlen *zwischen* den Grenzen (exklusive der Grenzen) ausgegeben. Wenn man die Zahlen inklusive Grenzen ausgeben möchte, werden es noch zwei Zeichen mehr.

    0
Anmelden zum Antworten