3. Randomize()

Randomize()

  • ?

    Die Programmlogik habe ich mir jetzt nicht weiter angeschaut. Aber du greifst über die Grenzen deines Arrays zu.

    int array[48]; //48 elemente. von 0 bis 47

for(int a=0; a<48;a++)
oder
for(int a=0; a!=48;a++)
oder
for(int a=0; a<=47;a++)

    bei <= 48 greifst du auf element 48 zu, das es aber garnicht gibt

    0
  • ?

    jooo, das war ein dummer fehler... Danke.

    Jedoch bin ich noch immer so weit wie vorher 😞

    0
  • V

    Falls das Programm 49 unterschiedliche Zahlen würfeln soll, muß man noch an zwei oder drei Ecken schrauben.

    #include <iostream>
#include <ctime>
#include <cstdlib>

void randomize()
{
    srand(time(0));
}

bool checkme(int carray[],int anzahl)
{
    for(int a=0; a<anzahl;a++)
    {
        for(int i=0;i<anzahl;i++)
        {
            if(i!=a && carray[i]==carray[a])
            {
//                std::cout << carray[i] << std::endl;
                return false;
            }
        }
    }
    return true;
}

int main()
{
    srand((time(0)));
    int x[49];
    for(int i=0;i<=48;i++)
    {
        do{
            x[i] = rand()%255;
//            std::cout << x[i] << std::endl;
						for(int j=0;j<=i;j++)
						{
								std::cout << x[j] << ' ';
						}
						std::cout << '\n';
        }while(checkme(x,i+1)==false);
    }
}
    0
  • ?
     

    |
          ||
          ||
      --\ \||
       --\ \||
        --\ \||
         --\ \|
          --\ \
             \ \
              \ \
               \ \
              MMMMMMMMM                         MMMMMMMMM
          MMMMMMMMMMMMMMMMMM               MMMMMMMMMMMMMMMMMM
       MMMMMMMXXXXXXXXXXMMMMMMM         MMMMMMMXXXXXXXXXXMMMMMMM
    MMMMMMXXXXXXXXXXXXXXXXXMMMMMM     MMMMMMXXXXXX:::::XXXXXXMMMMMM
   MMMMMXXXXXXXX::::::::XXXXXXMMMM   MMMMXXXXXX:::::::::::XXXXXMMMMM
  MMMMXXXXXXX:::::::::::::::XXXXMMM MMMXXXX::::::::::::::::::XXXXMMMM
 MMMMXXXXXX::::::::::::::::::::XXXMMMXXX:::::::::::.....:::::::XXXMMMM
 MMMXXXXX::::::::::::::::::::::::XXXXX:::::::::...........::::::XXXMMM
MMMXXXXX:::::::::::.......:::::::::X::::::::......    ......::::XXXXMMM
MMMXXXX:::::::::..............:::::::::::.......         ....::::XXXMMM
MMMXXXX::::::::..................:::::.......             ...::::XXXMMM
MMMXXXX:::::::.....................:............         ....::::XXXMMM
MMMXXXX:::::::....................................       ....::::XXXMMM
MMMXXXX:::::::......................................    .....::::XXXMMM
MMMXXXXX::::::....................................... ......::::XXXXMMM
MMMMXXXX:::::::.............................................::::XXXMMMM
 MMMXXXX::::::::............................................::::XXXMMM
 MMMMXXXX::::::::..........................................::::XXXMMMM
  MMMXXXX::::::::::.......................................:::::XXXMMM
  MMMMXXXX:::::::::::...................................::::::XXXMMMM
   MMMXXXXX::::::::::::..............................::::::::XXXXMMM
   MMMMXXXXX:::::::::::::.........................::::::::::XXXXMMMM
    MMMMXXXXX:::::::::::::::...................::::::::::::XXXXMMMM
     MMMMXXXXX:::::::::::::::::.............::::::::::::::XXXXMMMM
      MMMMXXXXXX::::::::::::::::::.......::::::::::::::XXXXXXMMMM
       MMMMXXXXXXXX::::::::::::::::...::::::::::::::XXXXXXXXMMMM
         MMMMXXXXXXXXX::::::::::::::::::::::\::::XXXXXXXXXMMMM
           MMMMMXXXXXXXXXX:::::::::::::::::\ \XXXXXXXXXMMMMM
              MMMMMMXXXXXXXXXXX:::::::::XXXX\ \XXXXMMMMMM
                  MMMMMMXXXXXXXXXXX:XXXXXXXXX\ \MMMMM
                      MMMMMMXXXXXXXXXXXXXXXMMM\ \
                          MMMMMMXXXXXXXMMMMMM  \ \
                              MMMMMXMMMMM       \ \
                                 MMMMM           \ \   \
                                  MMM          \  \ \ \\
                                   M            \\\\\\\\
                                                  \\\\\\
                                                    \\\\
                                                      \\

    Danke

    0
  • V

    leicht verbesserte version.

    #include <iostream>
#include <ctime>
#include <cstdlib>

bool checkme(int carray[],int anzahl)
{
    for(int a=0; a<anzahl;a++)
    {
        for(int i=0;i<a;i++)
        {
            if(carray[i]==carray[a])
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    srand((time(0)));
    int x[49];
    for(int i=0;i<49;i++)
    {
        do{
            x[i] = rand()%256;
        }while(checkme(x,i+1)==false);
    }

    for(int i=0;i<49;i++)
    {
        std::cout << x[i] << ' ';
    }
    std::cout << '\n';
}
    0
  • ?

    Ach volkard, die Version ist mir lieber 🙂 Danke dir!

    ____               ____
	             /,,,,\_____________/,,,,\
	            |,(  )/,,,,,,,,,,,,,\(  ),|
	             \__,,,,___,,,,,___,,,,__/
	               /,,,/(')\,,,/(')\,,,\
	              |,,,,___ _____ ___,,,,|
	              |,,,/   \\o_o//   \,,,|
	              |,,|       |       |,,|
	              |,,|   \__/|\__/   |,,|
	               \,,\     \_/     /,,/
	                \__\___________/__/
	  ________________/,,,,,,,,,,,,,\________________
	 / \,,,,,,,,,,,,,,,,___________,,,,,,,,,,,,,,,,/ \
	(   ),,,,,,,,,,,,,,/           \,,,,,,,,,,,,,,(   )
	 \_/____________,,/             \,,____________\_/
	               /,/               \,\
	              |,| *H   U   G   S* |,|
	              |,|                 |,|
	              |,|                 |,|
	              |,|                 |,|
	               \,\       O       /,/
	               /,,\_____________/,,\
	              /,,,,,,,,,,,,,,,,,,,,,\
	             /,,,,,,,,_______,,,,,,,,\
	            /,,,,,,,,/       \,,,,,,,,\
	           /,,,,,,, /         \,,,,,,,,\
	          /_____,,,/           \,,,_____\
	         //     \,/             \,/     \\
	         \\_____//               \\_____//
    0
  • D

    Lässt sich optimieren, auf reduzierte Komplexität von O(n²) zu O(n).

    Alter Code:

    for(int a=0; a<anzahl;a++)
    {
        for(int i=0;i<a;i++)
        {
            if(carray[i]==carray[a])
            {
                return false;
            }
        }
    }

    Neuer Code:

    #include <iostream>
#include <ctime>
#include <cstdlib> // rand, srand

void randomize()
{
    srand(time(0));
}

/** vergleiche die zahlen deiner liste nur bis zur neuen zahl    **/
/** ein doppelter vergleich mit den alten zahlen ist nicht nötig **/
/** es ist bekannt das diese einmalig sind!                      **/  

bool checkme(int carray[], int checkpos)
{
    for(int a=0; a < checkpos; a++)
    {
        if(carray[checkpos] == carray[a])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int x[49];
    randomize();

    for(int i=0;i<=48;i++)
    {
        do
        {
            x[i] = rand()%255;
        }
        while(checkme(x, i)==false);
    }

    for(int i=0;i<=48;i++)
      std::cout << x[i] << std::endl;
}

    Ich hoffe das sehe ich richtig.

    0
  • C
    Mod

    Wir können auch gleich O(1) daraus machen

    #include <iostream>
#include <ctime>
#include <cstdlib> // rand, srand

void randomize()
{
    srand(time(0));
}

int main()
{
    int x[49];
    bool check[255]={};
    randomize();

    for(int i=0;i<=48;i++)
    {
        do
        {
            x[i] = rand()%255;
        }
        while(check[x[i]]);
        check[x[i]]=true;
    }

    for(int i=0;i<=48;i++)
      std::cout << x[i] << std::endl;
}
    0
  • N

    Falls es mit der STL gelöst werden soll:

    #include <iostream>
#include <vector>
#include <algorithm>

int main() 
{ 
    srand(static_cast<unsigned int>(time(0))); 
	const size_t max_size = 256;
	const size_t size = 49;

	std::vector<int> numbers(max_size);
	for (int i = 0; i < max_size; ++i)
		numbers[i] = i;

	std::random_shuffle(numbers.begin(), numbers.end()); 

	for (int i = 0; i < size; ++i)
		std::cout << numbers[i] << std::endl;
}
    0
  • D

    camper schrieb:

    Wir können auch gleich O(1) daraus machen

    Nein können wir nicht!

    for(int i=0;i<=48;i++)
    {
        do
        {
            x[i] = rand()%255;
        }
        while(check[x[i]]);
        check[x[i]]=true;
    }

    das hineinziehen des Funktionsaufrufs ändert die Komplexität nicht, wenn du darüber nachdenkst kommst du vielleicht von selber darauf.

    Eine Auswahl und Vergleich von Zufallsbestimmen Zahlen kann niemals O(1) sein, w.z.B konstante Aufrufe von 102, oder 100, 48 Schleifen. Es ist nicht bekannt wie viele Aufrufe stattfinden, der Aufruf ist zwar linear aber das n in O(n) müsste für diese n-Funktion erst noch ermittelt werden. Das n in O(n) hätte also einen min-Wert mittel-Wert und einen max-Wert und kann damit nicht const sein, was die Voraussetzung für O(1) ist.

    Bem: for() ist Konstant O(1), while() O(n) --> O(n+1) = O(n)

    0
  • C
    Mod

    Ich bezog mich nur auf die Komplexität des Vergleichs. Schließlich terminiert ein solcher Algorithmus im schlimmsten Fall gar nicht.

    0
  • D

    Doch tut er, weil die Funktion rand() garantiert das ALLE zahlen gleichverteilt vorkommen und folglich der max-Wert der Funktion dem O(lim n->∞ - const) entspricht, wobei gilt n != ∞ und const fest.

    0
  • V

    Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).
    Interesaant ist die Komplexität des ursprünglichen Algos, wenn man damit n zufällige Zahlen von 1 bis n finden will. Für n=10000 waren es glaub ich 20 Minuten und n=100000 hab ich mich nicht getraut. Ich glaube auch nicht, daß es O(n^3) ist, sondern was viel Schrecklicheres.

    0
  • D

    vokhard schrieb:

    Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).

    Also ich weiß ja nicht wo du Informatik/Mathematik studiert hast aber es ist wirklich nicht O(1), mein letzter Kommentar dazu.

    In diesem Sinne
    Gruß Deep Copy

    0
  • L

    Doch es der Vergleich ist bei camper O(1).

    @volkard: Dann probier doch mal Nexus Algorithmus aus. Der hat ja O(n) für die Gesamtlaufzeit ;).
    Für den ursprünglichen Algorithmus müsste man die erwartete Laufzeit ausrechnen... Würd man spontan auf O(n^3 log(n)) tippen..

    0
  • V

    DeepCopy schrieb:

    vokhard schrieb:

    Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).

    Also ich weiß ja nicht wo du Informatik/Mathematik studiert hast aber es ist wirklich nicht O(1), mein letzter Kommentar dazu.

    In diesem Sinne
    Gruß Deep Copy

    Der VERGLEICH, Du Nase! Du Weihnachtsmann!
    Der Aufruf von checkme(i) war vorher quadratisch und jetzt ist er ersetzt durch das konstante check[x[i]].
    Der Vergleich steckt noch in einer äußeren Schleife, weswegen der gesamte Algo O(viel) hat und nicht O(1), das ist klar.

    0
  • D

    volkhard schrieb:

    Der VERGLEICH, Du Nase! Du Weihnachtsmann!

    Ich kann mir ein Grinsen nicht verkneifen, ich ein Weihnachtsmann 👍

    Nicht böse sein, aber woher sollte ich wissen das du mit VERGLEICH eine Stelle im Code und nicht den ganzen Algo meinst.

    0
  • C
    Mod

    DeepCopy schrieb:

    ... woher sollte ich wissen das du mit VERGLEICH eine Stelle im Code und nicht den ganzen Algo meinst.

    Weil du damit angefangen hast, dich auf den Code, der den Vergleich durchführt, zu beschränken.

    DeepCopy schrieb:

    Lässt sich optimieren, auf reduzierte Komplexität von O(n²) zu O(n).

    Alter Code:

    ...
    0
Anmelden zum Antworten