Problem z algorytmem na losowanie liczb bez powtórzeń, proszę o pomoc w poprawce

0

Napisałem już tyle:

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

using namespace std;

int const wylosuj_liczb=10;
int const zakres_liczb=10;

int main ()
{
	srand (GetTickCount());

	int wylosowana_liczba=0;
	int test[wylosuj_liczb];

	// losowanie liczb (bez powtórzeń)
	for (int i=0;i<wylosuj_liczb;i++)
	{
		wylosowana_liczba=rand()%zakres_liczb+1;
	}
	// sprawdzanie czy liczba się nie powtórzyła
	for (int i=0;i<wylosuj_liczb;i++)
	{
		wylosowana_liczba=rand()%zakres_liczb+1;
		for (int j=0;j<wylosuj_liczb;j++)
		{
			if (test[j]==wylosowana_liczba)
				wylosowana_liczba=0;
			if (wylosowana_liczba>0)
				test[i]=wylosowana_liczba;
			else
				i--;
		}
	}
	// sortowanie bąbelkowe
	int tmp;
	for (int i=0;i<(wylosuj_liczb-1); i++)
		for (int j=0;j<(wylosuj_liczb-1); j++)
			if (test[j]>test[j+1])
			{
				tmp = test[j];
				test[j] = test[j+1];
				test[j+1] = tmp;
			}
	// wyświetlanie
	for (int i=0;i<wylosuj_liczb;i++)
	{
		printf("%d",test[i]);
		if (i!=(wylosuj_liczb-1))
			printf(",");
		if (i==(wylosuj_liczb-1))
			printf(".");
	}
	printf("\n");
	getchar();
	return 0;
}

Problem jest taki, że ten mój algorytm nie działa poprawnie, liczby się powtarzają a teraz to już w ogóle program zaczął mi się sypać, czy ktoś mógłby rzucić wprawionym okiem i podsunąć poprawkę?

0
for (int i=0;i<wylosuj_liczb;i++)
        {
                wylosowana_liczba=rand()%zakres_liczb+1; //tutaj losujesz liczby których potem nie wykorzystujesz
        }
        // sprawdzanie czy liczba się nie powtórzyła
        for (int i=0;i<wylosuj_liczb;i++)
        {
                wylosowana_liczba=rand()%zakres_liczb+1; // ponieważ tutaj losujesz je ponownie
                for (int j=0;j<wylosuj_liczb;j++)
0
        for(int i=0,j=0;i<wylosuj_liczb;j=0)
          {
           wylosowana_liczba=rand()%zakres_liczb+1
           while((j<i)&&(test[j]!=wylosowana_liczba)) ++j;  // masz tylko do i wylosowanych
           if(j>=i) test[i++]=wylosowana_liczba;
         }
0

@autor przelatywanie całej tablicy i porównywanie za każdym razem czy dana liczba została już wylosowana nie jest najlepszym pomysłem
Algorytm na nie dublowanie się liczb losowanych sprawdź w tym temacie ostatnie odpowiedzi. Są tam ciekawsze pomysły.

0

Ja bym wykonał to rekurencyjnie.
losuj(pocz, koniec)
I że wzoru rand() % koniec + pocz;

0

wydaje mi się, że ten algorytm działa poprawnie, ale siedzę na wykładzie i nie jestem w stanie sprawdzić. Bardzo bym sobie chwalił gdyby osoby dłużej siedzące w programowaniu pomogły mi w ulepszeniu algorytmu. Przyda się on na pewno w dziale Newbie

#include <iostream>
#include <ctime>
using namespace std;

const int p = 1;
const int k = 10;

void losuj(const int, const int, int*);

int main()
{
	srand(static_cast<int>(time(0)));
	
	int rozmiar = k - p + 1;
	int *tab = new int[rozmiar];
	
	losuj(p, k, tab);

	for(int i = 0; i < rozmiar; i++)
		cout << "tab[" << i << "] = " << tab[i] << endl;

	getchar();
	return 0;
}
 
void losuj(const int pocz, const int koniec, int *tab)
{
    static int licznik;
    if(pocz > koniec)
        return;
    int w = rand() % (koniec - pocz + 1) + pocz;
 
    if(pocz == koniec)
    {
        tab[licznik++] = pocz;
        return;
    }
 
    if(pocz == koniec - 1)
    {
        if(w == pocz)
        {
            tab[licznik++] = koniec;
            tab[licznik++] = w;
        }
        else
        {
            tab[licznik++] = pocz;
            tab[licznik++] = w;
        }
        return;
    }

	losuj(pocz, w - 1, tab);
	losuj(w + 1, koniec, tab);
	
	tab[licznik++] = w;
}
0

Program zamieszczony przez autora nie pasuje do tematu wątku. Temat wątku dotyczy (a), zamieszczony program (b).
Są dwa bardzo różne zagadnienia:
(a) spośród liczb 1,...,n wylosować k różnych liczb,
(b) liczby 1,...,n ustawić w losowej kolejności.
Wydajne rozwiązanie (b) jest takie: wpisujemy liczby 1,...,n do tablicy "jak leci", potem wielokrotnie losujemy dwa indeksy i przestawiamy liczby z wylosowanych pozycji.
Jeśli chodzi o (a), to trzeba wpierw porównać liczby k i n. Jeśli k jest duże, to należy losować liczby, które należy pominąć.
Proponuję zastanowić się nad losowaniem 999999 różnych liczb spośród miliona dostępnych.

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