Algorytm na nie dublowanie się liczb losowanych

0

Mam taki kodzik:

#include <iostream>
#include <windows.h>

using namespace std;

int main ()
{
	int gotowa=0;
  srand (GetTickCount());
  int test[6];
  for (int i=0;i<6;i++)
  {
	gotowa=rand()%49+1;
	test[i]=gotowa;
  }
  int tmp;
  for (int i=0;i<=4; i++)
	for (int j=0;j<=4; j++)
	if (test[j]>test[j+1])
	{
	tmp = test[j];
	test[j] = test[j+1];
	test[j+1] = tmp;
	}

  for (int i=0;i<=5;i++)
  {
	  printf("%d",test[i]);
	  if (i!=5)
	  {
		  printf(",");
	  }
	  if (i==5)
		  printf(".");
  }
  printf("\n");
  getchar();
  return 0;
}

I mam takie pytanie:

Jak powinien wyglądać kod, żeby liczby się nie powtarzały w losowaniu?

0

Musisz zapamiętywać, które liczby były losowane i powtarzać losowanie jeżeli trafisz na "zużytą" liczbę.

0
Wibowit napisał(a)

Musisz zapamiętywać, które liczby były losowane i powtarzać losowanie jeżeli trafisz na "zużytą" liczbę.

W teorii to wiem, że powinienem wylosować liczbę, przypisać ją do zmiennej tymczasowej, następnie przelecieć całą tablicę i jeśli liczba ta już wystąpiła to jeszcze raz losować liczbę, a gdy liczba ta już się nie powtórzyła to mogę ją wpisać w i-ty element tablicy. Tylko właśnie dostałem zaćmienia, bo nie wiem jak to najlepiej ująć (pętla warunkowa) i warunek.

Jedyne na co wpadłem, to jest to:

#include <iostream>
#include <windows.h>
 
using namespace std;
 
int main ()
{
	int gotowa=0;
	srand (GetTickCount());
	int test[6];
	for (int i=0;i<6;i++)
	{
		test[i]=rand()%49+1;
		for (int k=0;k<6;k++)
		{
			if (test[i]==test[k])
			{
				test[k]=rand()%49+1;
			}
		}
	}
	int tmp;
	for (int i=0;i<=4; i++)
		for (int j=0;j<=4; j++)
			if (test[j]>test[j+1])
			{
				tmp = test[j];
				test[j] = test[j+1];
				test[j+1] = tmp;
			}
	for (int i=0;i<=5;i++)
	{
		printf("%d",test[i]);
		if (i!=5)
			printf(",");
		if (i==5)
			printf(".");
	}
	printf("\n");
	getchar();
	return 0;
}

Ale to nie chroni przed powtarzaniem się liczb w całej tablicy i tu właśnie mam z tym problem, a właściwie to brak pomysłu, jakieś sugestie?

0

tworzysz tablice i zapisujesz do niej wylosowane liczby, a w pętli porównujesz aktualnie wylosowaną liczbę z liczbami w tablicy. Jeśli ta aktualnie wylosowana liczba nie jest w tablicy to zapisujesz ją jako kolejny element tej tablicy i robisz kolejne losowanie, a jeśli jest w tablicy to losujesz od nowa i od nowa powtarzasz.

0
    int tab[] = {0, 1, 2, 3, 4};
    for(int i = 5; i > 0; --i)
    {
        int res = rand() % i;
        swap(tab[res], tab[i-1]);
        cout << tab[i-1];
    }

proszę. Metoda z porównywaniem jest o wiele mniej efektywna zwłaszcza, że na samym końcu będziesz musiał tak długo czekać aż padnie ci ta ostatnia liczba.

0

A nie możesz uzyć jakiegos kontenera? Np. vector ma metodę contains (czy coś podobnego), która sprawdza, czy taki element jest już w wektorze.

0

To mi przypomina algorytm symulujący działanie totolotka, który pisałem jeszcze w szkole średniej. Krokowo wygląda to tak:

  • Generujesz tablicę n elementów zapełnioną liczbami od 0 do n-1;
  • Losujesz liczbę x z przedziału od 0 do n-1;
  • Do tablicy wylosowanych liczb dodajesz liczbę z tablicy wygenerowanej w punkcie pierwszym znajdującej się pod indeksem x;
  • Zamieniasz elementy tablicy z punktu pierwszego o indeksach n i x miejscami;
  • Jeśli posiadasz już wystarczającą ilość liczb, to kończysz działanie pętli, w przeciwnym warunku zmniejszasz n o 1 i wracasz do punktu 2.
0

Odwołuję mój poprzedni komentarz, czy to będzie tablica, czy std::set, czy cokolwiek - rozwiązanie z losowaniem i sprawdzaniem czy dana liczba była już wybrana będzie nieprzyzwoicie powolne już dla losowania 29999 liczb z zakresu 1..30000. Nie mówiąc już o tym, że na standardowej (i dalekiej od ideału, jak wiadomo) funkcji rand() nie wylosujemy liczby większej niż RAND_MAX (przynajmniej 32767) bez kombinowania. ;)

Alternatywa:

#include <cstdlib>
#include <ctime>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
//#include <iterator> // ostream_iterator
#include <exception>

namespace my {

    class Maszyna_Losujaca {
        unsigned najmniejsza_wartosc;
        std::vector<unsigned> pula;
    public:
        Maszyna_Losujaca(unsigned najmniejsza_wartosc, unsigned rozmiar, unsigned krok = 1)
            : najmniejsza_wartosc(najmniejsza_wartosc), pula(rozmiar) {
            if (rozmiar == 0) { throw "Kup sobie kredki na baterie..."; }
            for (unsigned i = 0, j = najmniejsza_wartosc; i < pula.size(); ++i, j += krok) {
                pula[i] = j;
            }
        }

        std::vector<unsigned> losuj_bez_powtorzen(unsigned ile) throw (const char*) {
            if (ile == 0) { throw "Kup sobie kredki na baterie..."; }
            if (ile > pula.size()) { throw "Chcesz wylosowac wiecej niz mozesz, pora na niebieskie tabletki..."; }
            std::random_shuffle(pula.begin(), pula.end());
            return std::vector<unsigned>(pula.begin(), pula.begin() + ile);
        }
    };

    template<typename T>
    void print(const T& v) {
        std::cout << v << " ";
    }
    
}


int main() {
    using namespace std;
    srand(time(0));
    
    try {
        my::Maszyna_Losujaca lotto(1, 49000);
        vector<unsigned> wylosowane = lotto.losuj_bez_powtorzen(5);
        cout << "Wylosowano: ";
        //C++0x
        for (unsigned i : wylosowane) { cout << i << " "; }
        // lub
        //for_each(wylosowane.begin(), wylosowane.end(), [](unsigned n){ cout << n << " "; });
        // etc
        
        //C++03 np:
        //copy(wylosowane.begin(), wylosowane.end(), ostream_iterator<unsigned>(cout, " "));
        // lub:
        //for_each(wylosowane.begin(), wylosowane.end(), my::print<unsigned>);
        // zwykły for po indeksach, iteratorach, etc
        cout << '\n';
    } catch (const char* msg) {
        cerr << "PEBKAC: " << msg;
    } catch (const exception& msg) {
        cerr << "Exception: " << msg.what();
    }
    
    return 0;
}

Wada? Około sizeof(unsigned) * rozmiar_puli wymaganej pamięci, w kontrze do sizeof(unsigned) * ilosc_losowanych podczas losowania - ale czasowo wyrabia się zdecydowanie lepiej niż "losowanie, sprawdzanie, powtórz", im większa pula - tym większa różnica na korzyść kodu powyżej. ;)

1

Ogólnie używając rand() można sensownie wygenerować takie ciągi tylko dla niewielkiej ilości elementów (dla zwykłego przypadku - 12). Jest to spowodowane tym, że różnych permutacji n elementów jest n!, a 13!>2^32. Dla większej ilości liczb należy zastosować lepsze generatory (z większym stanem). Ze względu na konstrukcje standardu POSIX nie można zrobić lepszej funkcji generującej liczby losowe w systemach z nim zgodnych. O generowaniu liczb bez powtórzeń prawdopodobnie można przeczytać w nowym TAOCP (tylko czekam jak sprowadzą ją do biblioteki).
//edit W tym wypadku jednak chyba możesz sobie pozwolić na użycie rand(), w tym wypadku masz tylko ok. 14 mln możliwości (brałem wcześniej pod uwagę kolejność), co jest pewnie mniejsze niż RAND_MAX.

1 użytkowników online, w tym zalogowanych: 0, gości: 1