Welche Datenstruktur ist geeignet?



  • Es werden 0-8 Werte in zufälliger Reinfolge in a(n) eingefügt. a(n) wird nun mit a(n-1) verglichen, von Interesse sind hier die Werte die in a(n) und nicht in a(n-1) sind und die werte die in a(n-1) und nicht in a(n) sind. a(n-1) wird danach nicht mehr gebraucht.



  • Gruum schrieb:

    Es werden 0-8 Werte in zufälliger Reinfolge in a(n) eingefügt. a(n) wird nun mit a(n-1) verglichen, von Interesse sind hier die Werte die in a(n) und nicht in a(n-1) sind und die werte die in a(n-1) und nicht in a(n) sind. a(n-1) wird danach nicht mehr gebraucht.

    Konkretes Beispiel vormachen bitte. Und warum überhaupt die Überlegung bei nur 9 Werten?



  • Vermutlich zwei sortierte Arrays der festen Größe 9 nebst passendem Füllstandsanzeiger. Eingefügt wird wie bei insertion sort.
    Geprüft wird dirch paralleles Ablaufen wie dem mergen in mergesort.



  • a_n als vektor (a^{n}_0 ... a^{n}_8) betrachten, wobei a^{n}_i = true gdw. i \in a_n

    vektor delta_1 = (d_0 ... d_8) = a_n - a_{n-1} betrachten. dann gilt d_i = true gdw. i \in a_n und i \notin a_{n-1}

    vektor delta_2 = (d_0 ... d_8) = a_{n-1} - a_n betrachten. dann gilt d_i = true gdw. i \notin a_n und i \in a_{n-1}

    mit bitsets implementieren



  • mist. falsch gelesen. 0-8 werte und nicht werte 0-8.



  • std::vector
    std::sort
    std::set_symmetric_difference


Log in to reply