3. Programmierwettbewerb

Programmierwettbewerb

  • F

    Hi,

    jefff: Lösungen sehe ich noch gar keine. Die kommen, wenn der Abgabetermin überschritten wurde. Interessant sind die Aufgaben allemal. Wollen wir uns nicht zusammensetzen und abkassieren? *BG*

    Die Schrifterkennung hat es wirklich in sich. Hat jemand sowas schon einmal gemacht? Wie geht man an so ein Problem dran?

    freedy

    0
  • J

    Hehe bin leider weder Schweizer noch Schueler.
    Ja die Schrifterkennung macht mir auch zu schaffen.. fuzzy logic, mehr faellt mehr dazu nich ein , muss mich ma schlau machn.

    0
  • D

    Naja ich bin Schweizer aber es würde mir nichts bringen, wenn ihr auch hier den Quellcode postet 🙄 , denn zur 2. Runde muss man an die ETH Zürich. Dort kann einem niemand mehr helfen.

    Grüsse Raphael

    PS: Die Aufgaben des BwInf sind um einiges schwieriger 🙂

    [ Dieser Beitrag wurde am 04.03.2003 um 13:22 Uhr von darkpenguin editiert. ]

    0
  • J

    die handyaufgabe ist ein standardproblem und lässt sich in zur anzahl handys proportionaler zeit lösen... die brute force lösung ist inpraktikabel (das merkt man spätestens wenn man die letzte datei mit den 50 handys testet :D)

    0
  • F

    Hi,

    geht das Handy-Problem dann nicht sogar schon in Richtung Travelling-Salesman-Problem??? Okay, es ist etwas vereinfacht... aber vom Prinzip. Die suchen bestimmt nur jemanden, damit sie den Nobelpreis kriegen. :-)))

    freedy

    0
  • J

    lesd mal ein gutes algorithmen buch dort steht drinn das man das in lenarer zeit lösen kann...
    eigentlich isses pseudoplynomial oder so... d.h. es ist von der zu erreichenden länge (indem fall 1000)
    und der anzahl handys abhängig...
    meine lösung braucht zum lösen der aufgabe mit 50 handys 30 mikrosekunden... aber das is ja eigentlich irrelevant weil das programm wenn mans richtig macht den grossetil der zeit mit daten lesen und schreiben verbringt...

    0
  • ?

    mein Handschrifterkennungsprogramm kann scohn 95% aller Wörter (Buchstaben) erkennen! Mit Training hab ich es von 0% auf 70 auf 80 auf 90 auf 95 geschaft, und jetzt werd ich noch weiter mit ihm trenieren, bis es mindestens 99.9% schafft! war ga nicht sooo schwer...

    0
  • ?

    und ich hab nur 26KB Zusatzdateien.
    Nur das mit der variablen Größe muss ich noch hinkriegen. Wird aber sicher nicht so schwer, dann muss ich halt vielleicht mit 50KB Zusatzdateien aufwarten 🙂
    wer will, sagt mir seine email und ich schick ihm den Code zum lernen 😃 😉

    0
  • ?

    Jo bitte

    derchefe@gmx.net

    Danke

    0
  • A

    Hi,
    mir auch:

    sulfrian@gmx.net

    Danke

    Alexander Sulfrian

    PS: Ich mach beim BWInf mit! Is eigentlich garnicht so schwer!

    0
  • ?

    Original erstellt von japro:
    meine lösung braucht zum lösen der aufgabe mit 50 handys 30 mikrosekunden...

    sicher doch! MIKRO-SEKUNDEN?!?!?!?!?!?! blödsinn! du hast keine ahnung

    0
  • ?

    ich poste es lieber hier:
    helfer.h:

    #ifndef INCLUDE_HELFER_H
#define INCLUDE_HELFER_H

#include <vector>

namespace Helfer {

    extern const int hoehe, breite;
    extern const int min, max, mittel;

    class error {};
    class equality_error : public error {};
    class letter_error : public error {};
    class helfer_error : public error {};
    class input_error : public error {};

    double compare (const std::vector<int> &memory, const std::vector<int> &input);
    void open (std::vector<int> &x, const char *filename);
    void add (std::vector<int> &memory, const std::vector<int> &input);
    int diff (int mem, int in);
}

#endif

    (Haut mich nicht wegen den extern's)

    helfer.cpp

    #include "helfer.h"
#include <fstream>

using namespace Helfer;
using namespace std;

const int Helfer::hoehe = 8;
const int Helfer::breite = 10;
const int Helfer::min = 1;
const int Helfer::max = 100;
const int Helfer::mittel = (Helfer::min + Helfer::max) / 2;

namespace {
    double equality (int a, int b) {
        if (a < Helfer::min || a > Helfer::max) {
            throw equality_error();
        }

        if (a < mittel) {
            return b ? 0 : (Helfer::max-Helfer::min+1) * a/100.0;
        } else if (a > mittel) {
            return b ? (Helfer::max-Helfer::min+1) * a/100.0 : 0;
        } else if (a == mittel) {
            return 100;
        }

        return 0;
    }

    template <class T>
    T absolut (T a) { return a < 0 ? -a : a; }

}

double Helfer::compare (const vector<int> &memory, const vector<int> &input) {
    double ret = 0;

    for (unsigned int i = 0; i < memory.size(); ++i) {
        double tmp = equality (memory[i], input[i]);
        ret += tmp;
    }

    return ret / memory.size();
}

void Helfer::open (vector<int> &x, const char *filename) {
    ifstream fin (filename);
    if (fin)
        for (int tmp; fin >> tmp;) {
            x.push_back (tmp);  
        }

    else
        for (int i = 0; i < hoehe*breite; ++i) x.push_back(mittel);
}

void Helfer::add (vector<int> &memory, const vector<int> &input) {
    for (unsigned int i = 0; i < memory.size(); ++i) {
        memory[i] += input[i] == 1 ? 3 : -2;
        if (memory[i] < Helfer::min) memory[i] = Helfer::min;
        else if (memory[i] > Helfer::max) memory[i] = Helfer::max;
    }
}

int Helfer::diff (int a, int b) {
/*  if (a < mittel) return a-1;
    else return a+1;
*/
    return a;
}

    diff ist noch nicht ausgereift, und würde den lernvorgang durcheinanderbringen
    so. das ganze noch in die klassen gepackt:

    letter.h

    #ifndef INCLUDE_LETTER_H
#define INCLUDE_LETTER_H

#include <vector>
#include <string>

namespace Letter {

    class input;
    class letter {
        std::string let;
        std::string filename;

    protected:
        std::vector<int> repr;
        letter ();

    public:
        letter (const char *filename, const std::string &letter_);
        ~letter ();
        operator const std::string & () const { return let; }

        double compare (const input &l2) const;
        friend double compare (const letter &l1, const input &l2) { return l1.compare(l2); }

        void add (const input &i);
        //void diff (const letter &l);
    };

    class input : public letter {
        using letter::repr;
    public:
        void init ();
    protected:
        void push_back (int);
        virtual void doInput (int hoehe, int breite) = 0;
    };

    class input_maker {
    public:
        input &getInput ();
    protected:
        virtual input &doGetInput () = 0;
    };

    //inline void diff (letter &l1, letter &l2) { l1.diff(l2); l2.diff(l1); }

}

#endif

    und
    letter.cpp

    #include "letter.h"
#include "helfer.h"
#include <fstream>

using namespace Helfer;
using namespace Letter;
using namespace std;

letter::letter (const char *filename_, const string &letter_)
 : let(letter_), filename(filename_) { open(repr, filename_); }

letter::letter () : let(""), filename("") {
    //for (int i = 0; i < hoehe*breite; ++i) repr.push_back(0);
}

letter::~letter () {
    if (filename == "") return;

    ofstream fout(filename.c_str());
    for (unsigned int i = 0; i < repr.size(); ++i) {
        if (repr[i] < Helfer::min) repr[i] = Helfer::min;
        else if (repr[i] > Helfer::max) repr[i] = Helfer::max;

        fout << repr[i] << ' ';
        if ((i % breite) == (unsigned int)breite-1) fout << '\n';
    }
}
/*
void
letter::diff (const letter &l) {
    for (unsigned int i = 0; i < repr.size(); ++i) {
        repr[i] = Helfer::diff(repr[i], l.repr[i]);
    }
};
*/

double
letter::compare (const input &l2) const
{ return Helfer::compare(repr, l2.repr); }

void letter::add (const input &i) {
    Helfer::add (repr, i.repr);
}

void input::init () { doInput(Helfer::hoehe, Helfer::breite); }

void
input::push_back (int x) {
    repr.push_back(x);
}

input &
input_maker::getInput () {
    input &tmp = doGetInput ();
    tmp.init();
    return tmp;
}

    So. das ganze drumherum könnte ZUM BEISPIEL so ausschauen:

    main.cpp

    #include <iostream>
#include <fstream>
#include <string>
#include <map>
#include "letter.h"
#include "helfer.h"
using namespace Letter;
using namespace std;

int main () {
begin:
    {
    input in(8, 10);

    map<letter*, double> com;
    map<double, char> com2;

    for (char c = 'A'; c <= 'Z'; ++c) {
        string filename = "C:\\writelite\\";
        filename += c; filename += ".let";

        letter *tmp = new letter(filename.c_str(), c);
        try {
            com[tmp] = compare (*tmp, in);
            com2[compare(*tmp, in)] = *tmp;
        } catch (Helfer::equality_error &) {
            cout << "Es gibt einen Fehler: Mein Gedaechtnis ist defekt!" << endl;
        }

    }

    map<double,char>::iterator end = com2.end(); --end;
    char geraten = end->second;
    cout << "Ich glaube, du hast ein \'" << geraten << "\' eingegeben " << endl;

    cout << "Was hast du wirklich eingegeben?\n"; char c; cin >> c;
    if (c != geraten) {

        cout << "Ich habe mich also geirrt...\nIch hoffe, ich mache diesen Fehler nicht noch einmal!" << endl;

        char g = geraten;
        map<letter*, double>::iterator richtig, geraten;
        for (richtig = com.begin(); *richtig->first != c; ++richtig);
        for (geraten = com.begin(); *geraten->first != g; ++geraten);

        diff(*geraten->first, *richtig->first);

        cout << "Danke, dass du mich korrigiert hast!" << endl;
    } else {
        cout << "Cool, ich hab richtig gelesen!!!" << endl;
    }

    for (map<letter*, double>::iterator i = com.begin(); i != com.end(); ++i) {
        if (*(i->first) == c) (i->first)->add(in);
        delete i->first;
    }

    cout << "Moechtest du noch sehen, was ich mir gedacht habe (Schreib \'j\' oder \'n\') ?\n";
    char ci;
    cin >> ci; if (ci != 'j') return 0;

    int xxx = 0;
    for (map<double, char>::reverse_iterator i = com2.rbegin(); i != com2.rend(); ++i, ++xxx) {
        cout << i->second << ": " << i->first << '%' << '\t';
        if (xxx % 2 == 1) cout << '\n';
    }
    cout << endl;
    }

    cout << "\nNochmal\n"; goto begin;
}

    bla. qed

    0
  • ?

    sieht aus wie java :o

    0
  • ?

    wieso? lug nicht!

    0
  • ?

    Original erstellt von <was>:
    wieso? lug nicht!

    weil das ein java- oder c-cast ist.

    0
  • ?

    eben keine warnungen :p

    0
  • B

    Hat jemand von euch an so einem Bewerb schonmal teilgenommen?

    0
  • ?

    und werde ich auch nicht. das programm (weiter oben) hab ich zum spaß gemacht, nur die idee hat mir dieser wettbewerb gegeben.

    0
  • J

    Original erstellt von <greeeg>:
    **
    sicher doch! MIKRO-SEKUNDEN?!?!?!?!?!?! blödsinn! du hast keine ahnung**

    jo wenn ich schreibe mikrosekunden dann meine ich das so... nenn mir mal nen grund warum es nicht so schnell gehen sollte (nur weil du nicht weisst isses noch lang nicht unmöglich)

    0
  • ?

    ich mag keine aufgaben, wo man mathematisches Grundwissen braucht :p 😃
    verrat uns wie's geht, bitte

    [raten=on]
    btw. kann es sein, das du diesen algorithmus verwendest?
    [/raten]

    0
Anmelden zum Antworten