3. n-viele Integer Zahlen deklarieren?

n-viele Integer Zahlen deklarieren?

  • Mod

    Das hier immer wieder so Algorithmen mit derart schlechter Zeitkomplexität vorgeschlagen werden. 🙄

    @Maxi und Jochen S.: Testet Eure Vorschläge mal mit 10.000 oder 100.000 Zahlen und staunt wie lange selbst ein heutiger Rechner dafür braucht.

    0
  • B

    Hmm ich werde mal das von Jochen S. testen. Der Rest ist für mich als Anfänger leider etwas zu kompliziert, bzw reichen meine ohnehin eher dürftigen Kenntnisse nicht soweit.

    Vielleicht kann mir jemand noch zum Schluss diese Frage beantworten.

    rand()%m; // ERZEUGT Zahlen zwischen 0 und m

    oder

    rand()%m; // ERZEUGT Zahlen zwischen 0 und m-1

    ps. laut Aufgabenstellung soll das Feld beliebig groß sein (jedoch nicht zu groß -.-) Denke so eine Begrenzung durch das Konsolenfenster ist legitim.

    0
  • J

    rand()%m erzeugt Zufallszahlen zwischen 0 und m-1.
    Wenn du Zufallszahlen zwischen 1 und m haben willst, musst du noch 1 hinzuaddieren.

    Kleine Optimierung meiner Funktion Random:

    int Random(int m)
{
    static std::vector<int> A(m);
    static NumValues = 0;

    bool RunLoop = true;
    int x = rand()%m+1;
    int var = 0;

    while(RunLoop)
    {
        for(int i=0;i<NumValues;i++)
            if(A[i]==x){RunLoop = false;x=var++;}
        RunLoop = !RunLoop;
    }

    if(++NumValues>=m)NumValues=0;
    return x;
}

    Dürfte schneller sein. Ist aber nicht mehr ganz so zufällig 😉

    MfG, Jochen

    0
  • Mod

    Das sind Zahlen zwischen 0 und m-1, jeweils einschließlich. Das Prozentzeichen ist der modulo-Operator, das heißt der Rest einer Division durch m. Und der kann logischerweise nur zwischen 0 und m-1 liegen.

    0
  • M

    @SeppJ: Mir ist klar, dass der Algo nicht grad der schnellste ist. Dafür ist er leicht zu verstehen :).

    0

  • Da hab ich doch letzten auch was gepostet... passt gut hierher:

    RNG ohne Duplikate.
    Laufzeitverhalten ist linear beim Erzeugen, konstant beim Ziehen. Speicherverbrauch wächst leider auch linear 😃

    Edit:
    2. Posting auf der Seite

    0
  • U

    SeppJ schrieb:

    BAHA schrieb:

    Vector ist mir bekannt. Das Problem ist halt das ich n paarweise verschiedene Zahlen erzeugen will. 🙂

    Wenn ich dich recht verstehe: Schreib doch erstmal die Zahlen der Reihenfolge nach in den vector und dann mach ein random_shuffle.

    einfacher gehts gar nicht mehr - schneller auch nicht.

    #include <algorithm> //random_shuffle
#include <iostream> //ein + ausgabe
#include <vector> //unser container für die zahlen
#include <cstdlib> //unsere zufallszahlen-funktion

int main()
{
  using namespace std;

  srand(time(0)); //zufallszahlen generator initialisieren
  rand(); //die erste zufallszahl ist nicht gut genug für uns
    //dieser zufallszahlengenerator wird intern (so lang nicht anders angegeben) von random_shuffle verwendet

  int max;
  cin >> max;
  vector<int> numbers(max);
  for(int i(0); i != max; ++i)
    numbers[i] = i;
/*numbers sieht jz (bei max==5) so aus: {0; 1; 2; 3; 4}*/

  int count;
  cin >> count;
  if(count > max)
    return EXIT_FAILURE;
  random_shuffle(numbers.begin(), numbers.end()); //mischen
/*numbers sieht jz z.Bsp. so aus: {3; 2; 4; 0; 1}*/
  numbers.resize(count);
/*numbers sieht (bei count==3) so aus: {3; 2; 4}*/

//die ausgabe, damit du auch siehst, dass es funktioniert:
  for(vector<int>::const_iterator i(numbers.begin()), e(numbers.end()); i != e; ++i)
    cout << *i << endl;

  char dont_close;
  cin >> dont_close;
}

    random_shuffle(numbers.begin(), numbers.end()); //mischen
    die Zeile ist vermutlich die einzige, die du nicht verstehst.
    Sollte aber eigtl ganz intuitiv zu verstehen sein.
    Dokumentation dazu:
    http://www.cplusplus.com/reference/algorithm/random_shuffle/

    bb

    PS: Gabs bei std::vector nicht auch irgendwo im Standard nen Satz zum CTor(die iteratoren-Überladung) von wegen: Wenn der iterator zu nem size_t gecastet werden kann, dann werden Zahlen eingefügt? Habs gerad nicht auf die Schnelle finden können, war mir aber eigtl relativ sicehr... -.-

    0
  • ?

    unskilled schrieb:

    PS: Gabs bei std::vector nicht auch irgendwo im Standard nen Satz zum CTor(die iteratoren-Überladung) von wegen: Wenn der iterator zu nem size_t gecastet werden kann, dann werden Zahlen eingefügt? Habs gerad nicht auf die Schnelle finden können, war mir aber eigtl relativ sicehr... -.-

    was meinen? es gibt einen konstruktor, der X-mal den Wert Y einfügt, das hat aber nichts mit einem cast zu tun.

    0
  • U

    kunststudent schrieb:

    unskilled schrieb:

    PS: Gabs bei std::vector nicht auch irgendwo im Standard nen Satz zum CTor(die iteratoren-Überladung) von wegen: Wenn der iterator zu nem size_t gecastet werden kann, dann werden Zahlen eingefügt? Habs gerad nicht auf die Schnelle finden können, war mir aber eigtl relativ sicehr... -.-

    was meinen? es gibt einen konstruktor, der X-mal den Wert Y einfügt, das hat aber nichts mit einem cast zu tun.

    Ne, den meinte ich nicht.
    Mir war so, als ob es irgendwo nen (sequentiellen) COntainer gab, bei dem bei der Iterator-Überladung des inserts und/oder des CTors so etwas stand, wie:
    if 'Iterator' could be cast to an size_t ...

    habs aber nicht gefunden - hab 3 Standards(bzw Drafts: '95,'03,'05) durchsucht aber nichts gefunden - wer weiß, wo ich das wieder gelesen hatte... : D

    bb

    0
  • ?

    schau dir mal die allgemeine einleitung zu containern an, da steht afair irgendetwas zu dem thema, bezieht sich aber, glaube ich, generell darauf, dass es compilerspezifisch ist, zu bestimmen, ob der iterator ein inputiterator ist oder nicht und falls er das nicht ist, eine andere version der funktion/des konstruktors aufgerufen werden soll.

    eine zeit noch etwas vor concepts und type_traits (zumindest erlaubt es das verwenden von type traits).

    0
  • U

    da hatte ich eigtl auch nachgeguckt - hab jz auch keinen nerv mehr, so gehts ja auch:

    #include <iostream>
#include <iterator>

template<typename T>
struct counter
{
	typedef std::bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	typedef std::ptrdiff_t difference_type;
	typedef difference_type distance_type;
	typedef value_type* pointer;
	typedef value_type& reference;
	typedef const value_type& const_reference;

	reference operator++()
	{
		return ++me;
	}
	reference operator--()
	{
		return --me;
	}

	reference operator*()
	{
		return me;
	}
	const_reference operator*() const
	{
		return me;
	}

	counter(T me = T())
	:	me(me)
	{}

private:
	T me;
};

template<typename T>
bool operator== (counter<T> lhs, counter<T> rhs)
{
	return *lhs == *rhs;
}

template<typename T>
bool operator!= (counter<T> lhs, counter<T> rhs)
{
	return !(lhs == rhs);
}

namespace std
{
	template<typename T>
	typename counter<T>::difference_type distance(counter<T> lhs, counter<T> rhs)
	{
		return static_cast<typename counter<T>::difference_type>( *rhs - *lhs );
	}

	template<typename T, typename diff_t>
	void advance(counter<T>& these, diff_t diff)
	{
		*these += diff;
	}
}

#include <vector>

int main()
{
	std::vector<int> container(counter<int>(3), counter<int>(8));

	std::copy(container.begin(), container.end(), std::ostream_iterator<int>(std::cout, "\r\n"));

	system("PAUSE");
}

    ist zwar nicht ganz standard-konform, im namespace std funktionen zu überladen, aber das ist ja auch bei swap gängige praxis, da weder der msvc noch der gcc immer adl nutzen.

    im standard steht aber mal wieder nicht, dass distance benutzt werden soll, um die größe herauszubekommen -> zumindest der msvc nutzt es nicht, weder die 9 noch die 10 - stinkt -.-'
    oder hab ich da irgendwo nen denkfehler gemacht, bei der distance-überladung?
    das random_access_tag wollt ich nicht nutzen, weil ich dann angst habe, dass intern iwo pointer-artithmetik genutzt wird und komische fehler auftreten^^

    bb

    0
  • K

    Jochen S. schrieb:

    int Random(int m)
{
    static std::vector<int> A(m);
    static NumValues = 0;
   
    bool RunLoop = true;
    int x = rand()%m+1;
    int var = 0;

    while(RunLoop)
    {
        for(int i=0;i<NumValues;i++)
            if(A[i]==x){RunLoop = false;x=var++;}
        RunLoop = !RunLoop;
    }

    if(++NumValues>=m)NumValues=0;
    return x;
}

    Dürfte schneller sein. Ist aber nicht mehr ganz so zufällig 😉

    😮 👎

    Pfui: Wenn Du 'ne Funktion "mit Zustand" willst, schreib 'nen "Funktor" (Klasse) und benutze keine static Variablen!

    Fehler: NumValues ohne Typ deklariert.

    Fehler: A wird nie mit Werten x gefüllt.

    Doof: RunLoop. Wenn man den Test hinter einem Funktionsaufruf verstecken kann, lässt sich dieser in der Schleifenbedingung verwenden, so dass Du kein RunLoop brauchst. Damit wird die Schleife auch leichter verständlich. Eine Endlosschleife a la while(true) oder for(;; ) mit break in der Mitte wäre auch denkbar, um RunLoop loszuwerden.

    Doof: Keine Gleichverteilung für die übrig gebliebenen Zahlen.

    Doof: Schlechte Laufzeitklasse: O(n2) für n Ziehungen mit n<=m. Das geht besser.

    Da es um das Setzen von Mienen auf Feldern geht und sowieso Speicher für alle Felder reserviert wird, wobei nur maximal eine Miene auf ein Feld kommen soll, kann man den Test, ob das Feld schon besetzt ist, viel eleganter durch eine einzige if-Abfrage regeln. Man wählt so lange eine neue zufällige Position aus, bis man ein freies Feld gefunden hat. Die Zahl der zu setzenden Mienen ist ja typischerweise auch nur ein kleiner Bruchteil der Anzahl der Felder, so dass im Schnitt weniger als zwei "Versuche" pro Miene benötigt werden. Damit es keine Endlosschleife gibt, sollte man die Zahl der Mienen nach oben hin durch Feldanzahl/3 (oder so) begrenzen.

    kk

    0
Anmelden zum Antworten