[C++] Losowanie liczb bez powtórzeń - mój kod

pytanie zadane 12 sierpnia 2015 w C i C++ przez sngl00 Obywatel (1,110 p.)
edycja 15 września 2016 przez sngl00

Napisałam ostatnio program na losowanie liczb bez powtórzeń. Program działa jak należy, ale w sumie jestem jeszcze początkująca, dlatego chciałabym się spytać czy program ma jakieś wady, w porównaniu do np. http://miroslawzelent.pl/informatyka/losowanie-bez-powtorzen-php-c++-gra-milionerzy/ czy http://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Losowanie-bez-powtorzen/293 albo czy istnieją szybsze lub bardziej optymalne sposoby?

Tutaj mój kod:

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

using namespace std;

int main()
{
    srand(time(NULL));

    cout << "Losowanie 5 cyfr z zakresu 1-n bez powtorzen" << endl;
    int n;

    do
    {
        cout << "Podaj n: ";
        cin >> n;
    }
    while(n<5);

    cout << endl;

    int cyfra;
    int tab[5] = {};
    int licznik = 0;

    while(!tab[4])
    {
        cyfra = (rand()%n)+1;

        for (int j=0; j<=4; j++)
        {
            if (cyfra == tab[j])
                break;
            else
            {
                if (j==4)
                {
                    tab[licznik] = cyfra;
                    cout << tab[licznik] << "\t";
                    licznik++;
                }
            }
        }
    }

    fflush(stdin);
    getchar();

    return 0;
}

4 odpowiedzi

odpowiedź 13 sierpnia 2015 przez nowyfolder Mądrala (7,250 p.)
wybrane 13 sierpnia 2015 przez sngl00

Najlepsza

Generalnie jak na kogoś kto jest totalnie początkujący to kod bardzo dobry, żadnych typowych błędów.
Mój pomysł:
Przetrzymywanie danych w std::set, czyli zbiorze. Ma on jedną przydatną właściwość - nie przechowuje duplikatów. Więc możesz swobodnie dodawać elementy w pętli, dopóki zbiór nie będzie mieć rozmiaru 5. Wstawianie do zbioru za pomocą metody insert ma złożoność logn, więc cały algorytm z O(n*n) awansuje na O(nlogn)

Twoja pętla(i jej okolice) by wyglądała tak:

//to na samej górze ;d
#include <set>
// ...
int cyfra;
set<int> zbior;
 
while(zbior.size() < 5)
{
    cyfra = (rand()%n)+1;
    zbior.insert(cyfra);
}
 
//tzw petla for each, aby wypisac wylosowane liczby, nie przejmuj sie nia zbytnio :P
for(int var : zbior){
    cout<<var<<' ';
}

Och, zapomniałem, standardowo, tu masz dokumentację :P
http://www.cplusplus.com/reference/set/set/

komentarz 13 sierpnia 2015 przez sngl00 Obywatel (1,110 p.)

O, warto wiedzieć , będę musiała o tym poczytać :)

komentarz 13 sierpnia 2015 przez nowyfolder Mądrala (7,250 p.)

Liczę na okejkę

komentarz 13 sierpnia 2015 przez krecik1334 Maniak (58,390 p.)

Nie wpadłbym na to żeby to zakodzić na secie, aczkolwiek fajna sprawa. Coś pomiędzy tablicą booli a brutem :) Dla pewnych danych optymalne. Daję okejkę.

komentarz 13 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Ciekawy i przede wszystkim krótki sposób:D

odpowiedź 14 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Jeszcze coś takiego :)

int a,b,c,d,*los,k,n,licznik;
	bool powtorzenie;
	do
	{
		cout << "Losowanie liczb bez powtorzen." << endl;
		cout << "Wprowadz ilosc liczb do wylosowania: ";
		cin >> c;
		los = new int[c];
		cout << "Wprowadz zakres liczbowy losowanych liczb:" << endl;
		cout << "Podaj mniejsza liczbe: ";
		cin >> a;
		cout << "Podaj wieksza liczbe: ";
		cin >> b;
		d = b - a;
	} while (d < c);
	
	n = 0;
	while (n<c)
	{
		powtorzenie = false;
		k = rand() % (d) + 1+a;
		for (int i = 0; i < n; i++)
		{
			if (los[i] == k)
				powtorzenie = true;
		}

		if (!powtorzenie)
		{
			los[n] = k;
			n++;
		}

		
	}

komentarz 14 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Dowolna ilość liczb w dowolnym zakresie liczbowym( bez powtórzeń)

komentarz 14 sierpnia 2015 przez sngl00 Obywatel (1,110 p.)

Dzięki za ten sposób ;) tylko, że ja jeszcze nie umiem wskaźników i operatora new, więc wrócę do tego kodu za jakiś czas żeby lepiej go zrozumieć.

komentarz 14 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Jasne, póki co skup się na pozostałej częsci :)

odpowiedź 12 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Coż mogę powiedzieć :P Skoro jesteś początkujący, to najważniejsze, że działa, ciekawie to rozwiązałeś :)
Opierałeś się na info z tych stron czy może, sam to zrobiłeś od dechy do dechy ?

komentarz 12 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

jedyne co, to nieciekawie wygląda ta pętla while a w nim for, nie lepiej byłoby to zrobić w ten sposób, że losujesz liczbę ,a nasępnie sprawdzasz, czy taka jest w tablicy, jeżeli tak to losujesz ponownie ?

komentarz 12 sierpnia 2015 przez Patrycjerz Mędrzec (192,320 p.)
edycja 12 sierpnia 2015 przez Patrycjerz

Drugi raz w tym dniu upominam kogoś, że osoba pytająca to dziewczyna

komentarz 12 sierpnia 2015 przez sngl00 Obywatel (1,110 p.)

Sama napisałam w całości bo chciałam sprawdzić czy mi się uda.

komentarz 12 sierpnia 2015 przez Krawiec91 Pasjonat (19,600 p.)

Straszni szowiniści na tym forum.

komentarz 12 sierpnia 2015 przez sngl00 Obywatel (1,110 p.)

Ja już się chyba do tego przyzwyczaiłam :p bo u mnie w szkole 90% uczniów to chłopacy i nauczyciele często się zwracają do nas "panowie" albo coś w tym stylu.

komentarz 13 sierpnia 2015 przez Patrycjerz Mędrzec (192,320 p.)

To jeszcze nic w porównaniu z moim nauczycielem od informatyki, który jawnie mówi od uczennic "chłopie"

komentarz 13 sierpnia 2015 przez sngl00 Obywatel (1,110 p.)

haha no nieźle :p ale cóż nauczyciele to specyficzni ludzie

komentarz 13 sierpnia 2015 przez Krawiec91 Pasjonat (19,600 p.)

Hahahaha. No nieźle. Akurat takich sytuacji w szkole średniej to nie miałem - 100% samców w klasie.

komentarz 13 sierpnia 2015 przez Dragonet.17 Pasjonat (19,630 p.)

Ojej, bardzo przepraszam, bardzo się cieszę, że mamy koleżankę w naszych szeregach :)
Nawet " Początkujący", nie pomaga :D
Sorki za niedopatrzenie z mojej strony :)

odpowiedź 12 sierpnia 2015 przez krecik1334 Maniak (58,390 p.)

Polecam zakodzić to w taki sposób:

Globalna tablica booli o rozmiarze np. 10000000 lub max do 10^8 i gdy wylosujesz liczbę sprawdzasz czy tablica[liczba] == 0, jeśli tak to oznaczasz jako 1 czy może już jest 1 bo już taka została wylosowana wtedy wracasz do punktu wyjścia. Twoje rozwiązanie ma złożoność O(n*n) i dla dużych danych będzie wolne.

komentarz 12 sierpnia 2015 przez sngl00 Obywatel (1,110 p.)

Dzięki za sugestię, jutro jeszcze coś pokombinuję z tym

komentarz 12 sierpnia 2015 przez nowyfolder Mądrala (7,250 p.)

Lepiej zrobić GLOBALNĄ tablicę zżerającą 10000000bajtów?

komentarz 12 sierpnia 2015 przez krecik1334 Maniak (58,390 p.)

Oczywiście, przecież to zajmuje malutko czasu. To zależy od tego ile liczb masz do wylosowania, jeśli mało (tak do 1000 - 5000) to złożoność kwadratowa przeboleje, ale jak masz do wylosowania np. 100000liczb z zakresu 0 - 10^8 bez powtórzeń to tylko za pomocą tablicy booli.

komentarz 13 sierpnia 2015 przez Rogargol Pasjonat (16,610 p.)

Najlpeiej byloby to zrobic na liscie. Po wylosowaniu sprawdzaloby sie czy jest juz w liscie taka wartosc i tyle. Do tego malo miejsca i stosunkowo szybko przeszukiwane, bo od razu moznaby segregowac dane.

komentarz 13 sierpnia 2015 przez nowyfolder Mądrala (7,250 p.)
edycja 13 sierpnia 2015 przez nowyfolder

Zakładając że n jest dodatnie to i tak 10-100M bajtów to wartość z... wiaodmo skąd. Program musiałby mieć tablicę INT_MAX bajtów, żeby działał dla każdej liczby, czyli nawet dla n == INT_MAX. A to jest już ponad giga ramu, no thx.

komentarz 13 sierpnia 2015 przez Rogargol Pasjonat (16,610 p.)

Jedyna opcja jest zapamietywanie wynikow w pliku jesli nie chcemy angazowac pamieci.

Moje rozwiazanie byloby znacznie lepsze jesli losowaloby sie nie wszystkie liczby tylko ich czesc. Przy wszystkich, to tak czy inaczej pamiec musi byc zjedzona, albo operacyjna, albo ta na dysku.

komentarz 13 sierpnia 2015 przez nowyfolder Mądrala (7,250 p.)

Nie trzeba tyle pamięci angażować, wystarczy to zapisać w kontenerze, który pozwala łatwo znależć element, zerknij na moją odpowiedź.

komentarz 13 sierpnia 2015 przez Rogargol Pasjonat (16,610 p.)

Pisalem juz o liscie, ale w momencie jesli mamy duzy zakres w ktorym losujemy, to bedzie zajete docelowo odpowiednio duzo pamieci. To ze np lista czy tez zbior bylyby bardziej "eleganckie" to fakt, ale pamiec docelowo i tak bedzie zajeta. Co innego gdybysmy losowali np 100 liczb sposrod 1000000 i nie chcieli zeby sie powtarzaly, wtedy przewaga odpowiedniego konteneru nad tablica boolów jest zdecydowana.