losowe wypełnianie tablicy

Witajcie!
Potrzebuję się dzisiaj uporać z problemem...a już mi się pomysły skończyły...może ktoś coś poradzi.
Fragment gierki saper: funkcja, która ma wypełnić tablicę losowo minami (ozn 9) - użytkownik podaje ich ilość w procentach. Problem jest w funkcji losowej przy większych wartościach procentów (np 100%) - pętla się nie kończy, albo wykonuje się strasznie długo... Losowane liczby się powtarzają nie wypełniając całej tabeli.

void bomby (int **plansza) {
int x, proc;
cout<<"Ile ma byc bomb na planszy (procentowo)?"<<endl;
cin>>proc;

//oblicznie ilości bomb
x=static_cast<int>((proc*width*height)/100);
srand ((int) time(NULL));
for (int i=0;i<x;i++){
	int losX=rand()%(width);
	int losY=rand()%(height);
	if (plansza[losY][losX]!=9) {
		plansza[losY][losX]=9;
	} else { i--; }
}

Jeśli widzi ktoś tu błąd albo ma pomysł na rozwiązanie problemu to proszę o pomoc.

} else { i--; } a to w jakim celu ?

Żeby - jeśli pole jest już zajęte przez bombę - wykonało się dodatkowe losowanie. Bez tego jeśli dwa razy wylosuje te same współrzędne to nadpisuje bombę na już istniejącą i w rezultacie na planszy jest ich mniej niż powinno być.

dyju napisał(a)

Problem jest w funkcji losowej przy większych wartościach procentów (np 100%) - pętla się nie kończy, albo wykonuje się strasznie długo...

Tutaj nic nie jest źle, po prostu twój algorytm tak działa...
dla wartości >100 pętla nie ma prawa się zakończyć nigdy, bo jeśli się skończy, to znaczy że twój algorytm źle działa...

hmm... czy ty w ogóle rozumiesz co napisałeś? jeśli podasz wartość >100 to ilość bomb będzie większa niż ilość twoich pól, w takim wypadku nie da się rozstawić ich wszystkich, więc algorytm będzie w nieskończoność próbował wstawić bomby...

natomiast jeśli wartości będzie bliska 100, ale mniejsza, czy po prostu wysoka, prawie wszystkie pola będą musiały zostać wypełnione, a zanim wszystkie będą mogły być wylosowana maskarycznie wiele losowań zostanie wykonanych, na pole już wcześniej wylosowane, rozumiesz o co się rozchodzi?

twój algorytm będzie miał złożoność wykładniczą zależną od: proporcji ilości bomb do dostępnych pól, w skrajnym wypadku dla ilości bomb większej niż ilość pól będzie nieskończony :>

jedyna opcja to zmieć algorytm na taki w którym nie będzie możliwości wylosowania ponownie tego samego pola...

void bomby (int **plansza) {
int x, proc;
cout<<"Ile ma byc bomb na planszy (procentowo)?"<<endl;
cin>>proc;

//oblicznie ilości bomb
x=static_cast<int>((proc*width*height)/100);
srand ((int) time(NULL));
std::vector<unsigned long> pools(width*height); //pojemnik na pola
for(int x = 0; x < width; x++)
  for(int y = 0; y < height; y++)
    pools[y*width + x] = (y<<16) | (unsigned short)x; //wypełnienie pól planszy (bitowo, żeby już ci klas czy struktur nie wprowadzać :>)

for(int i = 0; i < x && pools.size(); i++) //wstawianie bomb
{
  int los = rand() % pools.size();
  std::vector<unsigned long>::iterator it = pools.begin();
  it += los;
  plansza[(*it) >> 16][(*it) & 0xffff] = 9;
  pools.erase(it);
}

/*
//algorytm naiwny:
for (int i=0;i<x;i++){
        int losX=rand()%(width);
        int losY=rand()%(height);
        if (plansza[losY][losX]!=9) {
                plansza[losY][losX]=9;
        } else { i--; }*/
}

nie sprawdzałem, mogą być błędy, ale coś w ten deseń...
działa to mniej więcej jak losowanie lotto, masz pojemnik ze współrzędnymi planszy i je losuje i usuwa z pojemnika, na pewno można wymyślić coś lepszego, ale na pewno też lepszy niż ten naiwny :>

^^unknown^^ napisał(a)

dla wartości >100 pętla nie ma prawa się zakończyć nigdy, bo jeśli się skończy, to znaczy że twój algorytm źle działa...

Jasne - chodziło mi o wartości duże ale zawsze <100 .
Ten algorytm rzeczywiście działa dobrze. Błąd udało mi się zlokalizować - tyle, że wpływały na niego miało działanie wcześniejszych funkcji. Z różnych przyczyn musiałem powiększyć tablicę do rozmiarów (width+1)x(height+1) czego nie uwzględniłem w tej funkcji... [glowa]
W wyniku tego nie było szans wylosowania 100% współrzędnych bo zakres losowania był za mały. Po zmianie na

	int losX=rand()%(width+1);
	int losY=rand()%(height+1);

wszystko hula jak należy :)
Sorry za ten głupi błąd [wstyd] i dzięki za zainteresowanie !!
</quote>

Dzięki za przykład! Jak uda mi się go rozkminić to pozwolę sobie zaczerpnąć z niego inspiracji :);)