random-shuffle algorithmus implementieren!!



  • hallo, ich muss bis montag einen "RANDOM SHUFFLE" algorithmus implementieren, könnt ihr mir da bitte helfen?? ich hab gar kein plan!

    danke
    info student, 1. semester



  • Schau dir doch den aus der STL an.



  • um dir ma ne etwas bessere antwort zu geben:
    (und da mir gerad langweilig ist)

    für nen statisches array:

    #include <algorithm> //hier ist std::random_shuffle zu finden
    #include <iostream> //std::cin, std::cout und std::endl
    
    const int MAX (10 /*wie lang soll das array sein?*/);
    int a[MAX];
    for (int i (0); i != MAX; ++i)
     {
      a[i] = i*123; //^^
     }
    std::cout << "a[] vor dem shuffle" << std::endl;
    for (int i (0); i != MAX; ++i)
     {
      std::cout << a[i] << "\t";
     }
    std::random_shuffle (a[0], a[MAX]);
    std::cout << "a[] nach dem shuffle" << std::endl;
    for (int i (0); i != MAX; ++i)
     {
      std::cout << a[i] << "\t";
     }
    std::cin.get (); //oder ne tollere lösung um die konsole offen zu lassen ^^
    

    für nen beliebiges array:

    #include <algorithm>
    #include <iostream>
    
    int MAX (0);
    std::cin >> MAX;
    int *a = new int[MAX];
    /*befüllen und ausgabe wie gehabt*/
    std::random_shuffle (a[0], a[MAX]);
    /*ausgabe wie oben*/
    delete []a; //freigeben des speichers nicht vergessen
    

    die "richtige" C++ - Lösung:

    #include <algorithm>
    #include <iostream>
    #include <vector> /*entweder, du nimmst vector (wie ich hier oder list oder irgend nen anderen std-container
    irgendwann hatte ich da auch mal ne tolle seite mit ner darstellung, wann welcher containier wann am besten wäre - aber naja >.<*/
    
    std::vector <int /*deinen datentyp hier reinschreiben - das nennt man template*/> array;
    
    //eingabe über std::cin
    do
     {
      int /*oder halt nen anderen datentyp nehmen - je nach dem, was du oben eingesetzt hast ^^ */ temp;
      std::cin >> temp;
    //eingabe überprüfen
      array.push_back (temp); //eingabe einfach hinten ans array 'einfügen' (eigtl das falsche wort, aber ich denke, push_back ist aussagekräftig genug ^^
     } while (/*kein plan, wie lang oder so...*/);
    /*alternativ könnte man das auch so machen:
    for (;/*bedingung* /;)
     { /*bla* / };*/
    
    //ausgabe, wie du sie kennst:
    const size_t l (array.size ()); //size_t ist nen unsigned int, also nen positiver integer - findest du auch oft so: std::size_t, ist aber eigtl nicht im namespace std
    for (size_t i (0); i != l; ++i) //man sollte allgemein immer preincrement nehmen, wenn es geht - auch, wenn der compiler (hier noch) das postincrement (i++) eh rausoptimieren würde
     {
      std::cout << array[i] << "\t";
     }
    
    /*das ganze hat aber ein problem: array[i] ist nicht sehr perfomant: das geht intern (stark vereinfacht) jedes mal so in etwa:
    template <class T>
        T std::vector::operator [] (const size_t /*&* /pos) //so überlädt man operatoren
        { //ich nehm einfach mal an, dass das array an sich so gespeichert ist: T *array_data;
            T *temp; //ein zeiger auf das erste element
            for (size_t i (0); i != pos; ++i) //der hier nach hinten verschoben wird - so ne for schleife wird allerdings eher anders geschrieben
            {
                ++temp;
            }
    //nämlich so: for (size_t i (0); i != pos; ++i, ++temp);
            return *temp;
        }
    
    deshalb löst man den zugriff auf arrays besser über pointer - in den std-containern werden die iteratoren genannt
    -->*/
    #include <iterator> //std::iterator </*viel zu viel ^^ sry*/> bzw. std::vector <T>::iterator
    
    std::vector <int /*nat. gleicher datentyp wie oben*/>::iterator begin (array.begin ()); //der übersichtlichkeit hab ich das mal nicht erst in der for-schleife initialisiert
    const std::vector <int /*...*/>::iterator end (array.end ());
    
    /*konstrukte á la:
    for (std::vector <T>::iterator begin (array.begin ()); begin != array.end (); ++begin);
    solltest du vermeiden, weil hier bei jedem schleifendurchlauf wieder die funktion end () aufgerufen wird
    
    kommen wir zum thema zurück ^^:*/
    
    for (/*deklariert und initialisert haben wir scho alles*/; begin != end /*sind wir schon am ende?*/; ++begin)
     {
      std::cout << *begin << "\t"; //sch... ich hätte es doch, wie immer iter statt begin nennen sollen ^^ naja, der var.-name ist bissl unglücklich gewählt
     }
    
    /*das eigentliche Thema:*/
    std::random_shuffle (array.begin (), array.end ());
    
    std::cout << "Feld nach dem random-shuffle" << std::endl;
    //ich mach einfach ma nen neuen scope auf, damit die variablen danach nich noch ewig "leben", mach ich normalerweise aber nicht... hier aber auch, um die gleichen variablen-namen zu nehmen ^^
    {
    const std::vector <int>::iterator end (array.end ());
    for (std::vector <int>::iterator iter (array.begin); iter != end; ++iter)
     {
      std::cout << *iter << "\t";
     }
    }
    //endlich fertig ^^ war doch mehr, als gedacht : D
    

    nachtrag für die nicht-so-richtig-c++-lösung:

    //nat. kann man auch hier über pointer gehen, ich nehm einfach ma die gleichen var.-namen wie oben ^^:
    //int *array;
    
    int *begin (array);
    int *end (&array[MAX]);
    
    for (/*done...*/; begin != end; ++begin)
     {
      std::cout << *begin << "\t";
     }
    //hier fehlt jetzt noch das letzte element, weil in nem "normalen eigenen" array das letzte element nicht NULL oder so ist sondern halt noch dazu gehört ^^ also entweder noch so:
    std::cout << *end << std::endl;
    //oder gleich so:
    do
     {
      std::cout << *begin << "\t";
     } while (++begin != end);
    

    bb - ich hoffe, es hat dir etwas gebracht : )

    PS: Is alles so hingeschrieben und nich probiert, aber sollte alles so funktionieren - hoff ich ^^

    edit1: da hab ich es scho x-ma durchgelesen bevor ich auf absenden geklickt hab - und trotzdem noch nen /* vergessen gehabt ^^

    edit2:
    hmm... hab gerad noch ma deinen post durchgelesen... wahrscheinlich darfst du den aus der stl nich nehmen... ^^
    also versuchen wir es mal so:
    (und ändern und vereinfachen den aus der stl ^^ der wird dann zwar ne so toll sein, aber das is ja au egal)

    #include <windows.h> //GetTickCount ()
    #include <cstdlib> //srand (), rand ()
    
    namespace my
     {
      template <class T>
       void swap (T &a, T& b)
        {
         T temp (b);
         b = a;
         a = temp;
        }
    
      template <class T>
       size_t diff (T first, const T &last)
        {
         size_t l (0);
         for (; first != last; ++first, ++l)
         return l;
        }
    
      template <class T_iter> 
       void random_shuffle (T_iter first, T_iter last)
        {
         srand (static_cast <unsigned int> (GetTickCount()); //den zufallsgenerator initialisieren - ich würd die uptime nehmen - weiß nicht genau, ob der cast sein muss oder nicht - aber schaden kann er nicht ^^
    
         size_t difference (diff (first, last));
         for (; first != last; ++first, --difference)
          {
           const size_t posi (((rand () + 1)*difference) % difference);
    /*rand: 0 ... 32767
    rand+1 => 1 ... 32768
    das mit difference multipliziert, damit es auch geht, wenn die differenz größer ist, als 33000 ^^
    und dann modulo difference, damit wir im feld bleiben ^^
    vll geht das au besser, kein plan ^^*/
           swap (first, first + posi);
          }
        }
     };
    

    vieles davon ist auch in der STL zu finden, aber kein plan, was du verwenden darfst und was nich ^^

    3.edit:
    hab die includes ma noch rausgesucht und au sonst noch bissl was rumgeschrieben ^^

    das wars jz aber wirklich - es sei denn, du hast noch fragen

    bb : )



  • Bitte bitte, wir brauchen einen "Oh mein Gott, Hand an Kopf klatsch"-Smilie.



  • Programmieren besteht nicht aus CTRL+C und CTRL+V und nix verstehen.



  • unskilled schrieb:

    um dir ma ne etwas bessere antwort zu geben:

    deine antwort ist nicht besser, sondern die denkbar schlechteste. man tut niemandem einen gefallen, wenn man seine hausaufgaben für ihn erledigt.



  • ich will ma den sehen, der das (so wies is) kopiert und abgibt xD
    wenn er sich das durchliest, dann versteht er es mit sicherheit auch 😛

    und wenn er faul (und nicht dumm) ist und keine ahnung von c/c++ hat, dann hätte er es ohnehin nicht selbst gemacht sondern iwen gefunden.

    wenn er nicht faul ist und vll doch versucht den ganzen quatsch zu verstehen, dann versucht er mit sicherheit auch, hinter den sinn zu steigen

    und wie habt ihr programmieren gelernt?
    die meisten mit nem buch und tutorials vermut ich mal...

    so gesehen, glaube ich kaum, dass es eine schlechte antwort war : P

    bb

    edit:
    btw wird es so eh nich funktionieren : P
    wer den fehler findet, bekommt nen keks - ok nen virtuellen ^^





  • baaaaaaaaaa schrieb:

    Bitte bitte, wir brauchen einen "Oh mein Gott, Hand an Kopf klatsch"-Smilie.

    Ein Kopf->Wand smiley würde schon genügen 🙂

    @unskilled der sinn einer solchen aufgabe ist, dass die schüler/studenten/whatever lernen wie man sich einen algorithmus ausdenkt. das ist eine methodik, die man *nicht* durch code lesen lernt.

    Wie mach ich das? Wo fang ich an? Wie gehts weiter? all solche fragen stellen sich bei so einer komplettlösung nicht mehr. Die implementation in irgendeiner Sprache ist dann völlig irrelevant, dein post würde auch als pseudocode schaden, und nicht nur als voll-sinnlos-kommentierter-codeschnipsel.



  • otze schrieb:

    ...

    Ich bin derselben Meinung.
    Ich habe diese riesigen Beispielcodes immer gehasst. Ich habe einfach geschaut, was es am Schluss machen soll und dann selber angefangen, OHNE den Code anzuschauen. Wenn es dan gelaufen ist, habe ich ev. noch einen Blick auf den Code geworfen. Wenn ich wirklichen Code haben will, dann schaue ich mir Implementationen an, die wirklich auch was taugen, um die Kniffe daraus zu lesen.

    Vor allem ein Student sollte sich die Zeit nehmen und über das Problem Nachdenken. Er hat ja nichteinmal ein wenig Code vorgeschoben, um zu zeigen, dass er wirklich was probiert hat und lernwillig ist.



  • drakon schrieb:

    Implementationen

    Implementierungen


Anmelden zum Antworten