Jak skrócić sprawdzanie warunków w du?żym lotku?

Napisałem program losujący dużego lotka:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

void duzylotek()
{                                                  
 FILE *plik;                                      
 int l[6], x=0, i;
 printf("\nOto wylosowane liczby: ");
 x=random(36)+1; l[0]=x;
 do{x=random(36)+1; l[1]=x;}while(l[1]==l[0]);
 do{x=random(36)+1; l[2]=x;}while((l[2]==l[0])||(l[2]==l[1]));
 do{x=random(36)+1; l[3]=x;}while((l[3]==l[0])||(l[3]==l[1])||(l[3]==l[2]));
 do{x=random(36)+1; l[4]=x;}while((l[4]==l[0])||(l[4]==l[1])||(l[4]==l[2])||(l[4]==l[3]));
 do{x=random(36)+1; l[5]=x;}while((l[5]==l[0])||(l[5]==l[1])||(l[5]==l[2])||(l[5]==l[3])||(l[5]==l[4]));
 for(i=0;i<=5;i++)
 {
  printf("%d,",l[i]);
  }
 getch();
 }

int main()
{
 duzylotek();
 return 0;
 }

Moje pytanie dotyczy warunków w while. Czy można skrócić jakoś ich pisanie. Zastanawia mnie to, gdyż, np. Przy pisaniu multilotka trzeba się z warunkami już nieźle namęczyć.</cpp>

Oto moja propozycja:

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

const unsigned ZAKRES=46,ILE=6;

bool szukaj(unsigned *tab,unsigned jaka,unsigned ile)
{
for(unsigned i=0;i<ile;++i)
{
if(tab[i]==jaka) return true;
}
return false;
}

void duzy_lotek()
{
unsigned liczby[ILE],x;
srand(static_cast<unsigned>(time(NULL)));
for(unsigned i=0;i<ILE;)
{
if(!szukaj(liczby,x=rand()%ZAKRES+1,i))
{
liczby[i++]=x;
}

}
cout<<"Oto wylosowane liczby:"<<endl;
for(i=0;i<ILE;++i)
{
	cout<<liczby[i]<<"  ";
}

}

int main()
{
duzy_lotek();
return 0;
}

Oto moja propozycja dla dowolnej ilości szukanych liczb w Multi Lotku:

do{
x=0;
for(i=0;i<ile;i++) // ile - oznacza ile liczb ma być losowanych
wylosowane[i]=random(80)+1;
do
{
y=0;
for(i=0;i<ile-1;i++)
{
if(wylosowane[i]>wylosowane[i+1]) tutaj dane są sortowane
{
y=1;
pomoc=wylosowane[i+1];
wylosowane[i+1]=wylosowane[i];
wylosowane[i]=pomoc;
}
if(wylosowane[i]==wylosowane[i+1])
x=1;
}
}while(y!=0);
}while(x!=0);
// wyświetlanie dopisz już sam :)

Chyba krócej się nie da, zwłaszcza że jest tu jeszcze sortowanie ale może ktoś ma lepszy pomysł :)

O rany, ale koszmarki (bez urazy). Krocej sie nie da?

map<int, int> wylosowane;
while (wylosowane.size() < ILE_LICZB)
    wylosowane[rand() % 80 + 1] = 1;
for (map<int, int>::iterator i = wylosowane.begin(); i != wylosowane.end(); i++)
    printf("%d\n", i->first);

Krotsze, zgrabniejsze, szybsze i jeszcze na dodatek sortuje. Uczcie sie STLa, dzieci :)

hmm Krolik wez mi powiedz czemu w twoim algorytmie liczby sie nie potworza...

k moja propozycja

#define ILOSC_LICZB 49
#define WYLOSOWAC 6

int cmp( const void *a, const void *b ) { return (*(int*)a) - (*(int*)b); }

...

int tab[ILOSC_LICZB], i, j, k;
for( i = 0; i < ILOSC_LICZB; i++ ) tab[i] = i + 1;
for( i = 0; i < WYLOSOWAC; i++ )
{
  j = i + rand( ) % ILOSC_LICZB;
  k = tab[ j ]; tab[ j ] = tab[ i ]; tab[ i ] = k;
}  
qsort( tab, WYLOSOWAC, sizeof(int), cmp );
for( i = 0; i < WYLOSOWAC; i++ ) printf( "%i ", tab[ i ] );
putchar( '\n' );

hmm Krolik wez mi powiedz czemu w twoim algorytmie liczby sie nie potworza...

Musisz mi uwierzyc na slowo :)
A tak serio, to nie powtorza sie, bo map<> to jest slownik a nie wieloslownik. Wlasciwie mozna bylo uzyc tez set<>, ale juz sie przyzwyczailem do uzywania map<> i tak mi bylo wygodniej.

Ponowne wstawienie tej samej liczby nie zmienia zwartosci slownika, nie zmienia wiec tez liczby elementow w slowniku. Petla moze obrocic sie wiecej razy niz ILE_LICZB. Poza tym wykorzystanie slownika, ktory jest zrealizowany na drzewie binarnym, pozwala uzyskac calkowita zlozonosc algorytmu O(n*log n), duza lepsza w porownaniu ze wszystkimi zaprezentowanymi tu rozwiazaniam (razem z Twoim): O(n^2). A liczby sa posortowane, bo tak dziala slownik. Wystarczy wziac np. Maly Slownik Jezyka Polskiego, zeby sie przekonac. :-D

ok o to mi chodzilo jesli chodzi o map ;> thx

Poza tym wykorzystanie slownika, ktory jest zrealizowany na drzewie binarnym, pozwala uzyskac calkowita zlozonosc algorytmu O(n*log n), duza lepsza w porownaniu ze wszystkimi zaprezentowanymi tu rozwiazaniam (razem z Twoim): O(n^2). A liczby sa posortowane, bo tak dziala slownik. Wystarczy wziac np. Maly Slownik Jezyka Polskiego, zeby sie przekonac. :-D

natomiast co do zlozonosci
moj algorytm natomiast ma zlozonosc O(n + nlog n), czyli O(nlog n).. zauwaz ze samo wybieranie jest liniowe, bo nie mam (ty akurat to masz) sprawdzania czy liczba sie powtarza, bo uzyty algorytm (podobny do sortowania przez przestawianie) zapewnia nie powtarzanie sie liczb.. zwalnia mnie tylko algorytm sortowania, czyli qsort, ktory ma zlozonosc O(n*log n), i jest teoretycznie najlepszym algorytmem tego typu, tak ze oboje mamy zlozonosc O( n * log n ), mimo ze praktycznie twoj algorytm z uwagi na wykorzystanie drzewa jest szybszy (o pol grosza ;>)

moj algorytm natomiast ma zlozonosc O(n + nlog n), czyli O(nlog n)..

Twoj alg. ma srednia zlozonosc faktycznie O(n * log n), ale pesymistyczna zlozonosc ma O(n^2). Qsort ma taka wade, niestety. Operacje slownikowe maja zas pesymistyczna zlozonosc O(n * log n). Poza tym Twoj algorytm musi najpierw wypelnic tablice 80 elementow. W tym czasie moj juz zdazy podac wyniki, bo ma do wstawienia jedynie 6 elementow. Zreszta nie klocmy sie o szczegoly - tu szybkosc i tak sie nie liczy, a Twoj pomysl mi sie najbardziej podoba z tu przedstawionych. Byc moze w innym zastosowaniu okaze swoja przewage nad map<>.

A.. fakt ;p jeszcze musze tablice wypelnic ;>>> w sumie zlozonosc sie nie zmieni ale szybkosc bedzie faktycznie mniejsza ;> Co do qsort masz ofc racje ;> jesli tablica byla by posortowana to mam zlozonosc niefajna ;> wada qsorta ;>
K EOT z mojej strony ;>

#include <stdio.h>

#define MAXN 49
#define LOSUJ 6

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int liczby[MAXN];
    int sorted[MAXN];
    int i,k;


    srand(time(NULL));

    for (i=0; i<MAXN; i++) {
        liczby[i] = i+1;
        sorted[i] = 0;
    }

    /* permutacja 1..MAXN */
    for (i=MAXN-1; i>1; i--) {
        k = rand() % i ;
        swap(&amp;liczby[k],&amp;liczby[i]);
    }

    for (i=0; i<LOSUJ; i++)
        sorted[ liczby[i] ] = liczby[i];

    for (i=0; i<MAXN; i++)
        if (sorted[i]) printf("%d ",sorted[i]);

    printf("\\n");

    return 0;
}

Złożoność O(n) kosztem pamięci O(n) ;P Koncepcyjnie tak jak jedno z powyższych rozwiązań, tzn. generujemy losową permutację liczb a później sortujemy przez zliczanie.

pzdr,

y.

hehehe ;> typowy przyklad programu ktory mimo mniejszej zlozonosci jest wolniejszy ;>
dla <font color="green">MAXN == 10000000</span> i <font color="green">6</span> liczb do wylosowania obawiam sie ze nawet z <font color="green">O(n)</span> twoj prog jest na szarym koncu jesli chodzi o szybkosc, jako ze twoje <font color="green">n</span> jest zalezne od <font color="green">MAXN</span> (w 2/3 petli), a nie od ilosci liczb do wylosowania (moje jest w 1/3 od tego zalezne), czy tez Krolika, ktorego <font color="green">n</span> jest w ogóle zalezne tylko i wylacznie od ilosci liczb do wylosowania ;>

Owszem, czasem stała potrafi zabić lepszą złożoność. Co do algorytmu to dla dużego MAXN i LOSUJ=MAXN-1 (perfidne warunki :P) sytuacja powinna się zmienić i to dość drastycznie :P Co jeśli ktoś podmienił generator liczb losowych (a to cham :P) i otrzymujemy 1,1,1,1,2,2,2,2,3,3,3,3,... (pseudolosowe o dość krótkim
okresie, bardzo krótkim :P) ? W każdym razie warto też zwrócić uwagę na problem
generatora liczb pseudolosowych, ciekawe czy w totku rozkład losowanych liczb
jest jednostajny ;P (teoretycznie tak, ale w praktyce widać chyba różnice mimo
niewielkiej ilości próbek) Wracając do szybkości to jak powiedział Lis do Małego Księcia: "Nie ma rzeczy doskonałych" ;)

pzdr,

y.

Jeszcze prościej ? :

#include <stdio.h>

#define MAXN 49
#define LOSUJ 6

int main() {
  int liczby[MAXN]; // char... cokolwiek co ma min 2 stany
  int i=0,k;

  srand(time(NULL));
  memset(liczby,0,sizeof(liczby));
  while(i<LOSUJ){
    k=rand()%MAXN;
    i+=(!liczby[k]);
    /*if(!liczby[k])*/liczby[k]=1;
  }
  i=0;
  while(i<MAXN)if(liczby[i++])printf("%d ",i); // albo {if(liczby[i])printf("%d ",i+1);i++;}
  printf("\\n");
  return 0;
}

Mam gdzies złożoność ;] Bo mam najmniej kodu i danych ;p

// do posto puniżej... static powoduje bezczelna stałą alokację pamieci ;] więc jesli funkcja nie jest wywoływana z dosc duża czestotliwoscia, to mija się z celem... i jeden jeszcze błąd fakt 0 sie nie losuje ;] poprawione (bylo if(liczby[i])printf("%d ",i);)

ahahaha flabra gosu rozwiazanie ;>>> podoba mi sie ;>
z tym ze twoj algorytm nie jest odporny na bledny generator numerow losowych (o ktorym mowil y. ) ;> poza tym wywal memset i wrzuc static przed deklaracje tablicy ;> jednej petli mniej ;>
y. rand() zly akurat mojego algorytmu nie zaboli ;> co za pewne widziales, czego nie mozna powiedziec o LOSUJ = MAXN - 1 ;ppp tyo by bylo nie fajne dla mojego algorytmu, chociaz taka wielka roznica by nie byla, wkoncu n*log n nie jest taki straszny ;> nyo...
swoja droga autor ma algorytmow do wyboru calkiem niezla ilosc ;>
hehe jak y. zacytowal, nie ma rzeczy doskonalych, ale imho wszystkie te sa fajne ;>

ciekawe czy w totku rozkład losowanych liczb
jest jednostajny ;P (teoretycznie tak, ale w praktyce widać chyba różnice mimo
niewielkiej ilości próbek)

W ciągach losowych zawsze zobaczysz tylko róznice.
teoretycznie rzucając monetą 10 razyprawdopodobieństwo wylosowania ciągów
oooooooooo
rrrrrrrrrr
ororororor
oorrorrror
jest identyczne
ale przy trzech pierwszych większość ludzi powie, że coś jest nie tak, tylko ten ostatni będzie skłonna zaakceptować jako losowy.

Tak samo w totku

Wasze algorytmy są błędne, dlatego, że w każdym z 6-ciu losowań prawdopodobieństwo wylosowania każdej liczby jest jednakowe. A niepowinno być.

ciekawe czy w totku rozkład losowanych liczb
jest jednostajny

Rozkład nie jest jednostajny bo nie może być. To jest zmienna losowa o rozkładnie dyskretnym.

// Powtórz sobie statystykę, ale tym razem zacznij od podstaw, czyli od logiki [mf]

swiety: nasze algorytmy sa odpowiedzia na pytanie zadane w topicu, i jako odpowiedz sa 100% poprawne... ich celem nie jest dokladna symulacja zachowan maszyny losujacej uzywanej w grach typy duzy lotek, a przyspieszenie algorytmu wybierania ciagu niepowtarzajacych sie liczb ;>

Wasze algorytmy są błędne, dlatego, że w każdym z 6-ciu losowań prawdopodobieństwo wylosowania każdej liczby jest jednakowe. A niepowinno być.

ciekawe czy w totku rozkład losowanych liczb
jest jednostajny

Rozkład nie jest jednostajny bo nie może być. To jest zmienna losowa o rozkładnie dyskretnym.

Jak dla mnie rozkład jednostajny może być zadany na zbiorze dyskretnym ;) Wtedy gęstość g(x)=L(A)^-1 * I_A(x), gdzie L(A) = ilość elementów A (możliwe, że przecięta z {1,2,...49}, zależy co się chce mieć) czyli taka namiastka miary Lebesgu'ea, a I_A(x) to funkcja chrakterystyczna zbioru A. Ale to tylko taka dygresja matematyczna, nie mająca wiele wspólnego z samym algorytmem. Jeśli chodzi o poprawność algorytmów to są jak najbardziej poprawne, a losowość można różnie modelować. Nikt nie broni podłączyć własnego
rand'a dającego pierwszą liczbę z pr. 1/49, drugą 1/48 itd. Jak ktoś jest zainteresowany generowaniem liczb z różnych rozkładów i lubi gotowe, sprawdzone biblioteki to polecam http://www.gnu.org/software/gsl/

pzdr,

y.</url>

Flabra napisał:

Powtórz sobie statystykę, ale tym razem zacznij od podstaw, czyli od logiki

Jeśli już to rachunek, bo statystyka nie ma nic z tym wspólnego, a tak w ogóle to czego nie rozumiesz, wyjaśnie.

// Nic nie tlumacz... Przekuj piekną teorię na brudna praktyke i napisz po prostu algorytm ktory zgodnie z tematem wylosuje n liczb bez powtarzania. [mf]

Flabra: nie masz najmniej kodu i danych, bo moj kod byl chyba troche
krotszy i duzo czytelniejszy (zmiennych tez mniej - policz, jak nie wierzysz).
Mial 5 prostych i dosyc standardowych linijek. Wiec co najwyzej pod wzgledem
prostoty rozwiazania jestes na razie drugi.

Ale spoko, bez urazy. Generalnie wszystkie rozwiazania sa fajne. Flabry jest najbardziej
"niskopoziomowe", moje najbardziej "wysokopoziomowe", inne gdzies posrodku. Autor posta ma wiec w czym
wybierac. :)

Pomysl z O(n) jest fajny, ale niestety jest on w wiekszosci przypadkow wolniejszy
niz ten z drzewem slownikowym. Jesli jednak ktos chce miec w moim programie zlozonosc
O(n) to wystarczy zmienic map<> na hash_map<> i na poczatku ustawic odpowiednio
rozmiar hash_mapa na liczbe wieksza niz zakres losowanych liczb. Stopien skomplikowania
algorytmu i jego zapis pozostaje dokladnie ten sam:

hash_map<int, int> wylosowane(80);
// dalej tak samo

Wasze algorytmy są błędne, dlatego, że w każdym z 6-ciu losowań prawdopodobieństwo wylosowania każdej liczby jest jednakowe. A niepowinno być.

Nie są błędne (czyt. nie są MATEMATYCZNIE błędne). Prawdopodobieństwo wylosowania w każdym z 6-ciu losowań danej liczby nie jest takie samo i jest całkowicie zgodne z rozkładem dyskretnym, który jest w totku w rzeczywistości, o ile tylko dysponujemy dobrym generatorem liczb pseudolosowych. Popatrz dokladniej na algorytmy. Prawd. wylosowania liczby 1 w pierwszym losowaniu wynosi 1/49, w drugim 1/48, w trzecim 1/47 itd. Wszystko jest ok.

Muszę przyznać, że te wasze algorytmy są ekstra. W pełni zgadzam się z krolikiem, że prawdopodobieństwo losowań jest zgodne z rozkładem dyskretnym. Sprawdzałem wasze algorytmy i są naprawdę świetne!!

Prawd. wylosowania liczby 1 w pierwszym losowaniu wynosi 1/49, w drugim 1/48, w trzecim 1/47 itd. Wszystko jest ok.

Nieprawda. Wy za każdym razem losujecie z tego samego zbioru liczb i sprawdzacie warunek, czy czasem wylosowana liczba już nie padła. przecieŻ to się nijak ma do tego co napisałeś.

nie są MATEMATYCZNIE błędne

jeżeli wylosowałeś ciąg oooor to według ciebie prawd. wylosowania reszki wynosi 1/2.

jeżeli wylosowałeś ciąg oooor to według ciebie prawd. wylosowania reszki wynosi 1/2.

Tak, bo to jest prawda.
Nawet jesli wylosowalem oooooooooooooooooooooooooooooor to nadal prawdopodobienstwo wylosowania reszki w kolejnym rzucie wynosi 1/2. Prawdopodobienstwo wylosowania reszki jest ZAWSZE 1/2 niezaleznie od tego co bylo wylosowane wczesniej. To sie nazywa, ze zmienna losowa nie ma pamieci. Dlatego losowanie i powtarzanie losowania, jesli liczba jest taka sama daje ten sam rozklad, co losowanie bez powtorzen.
Radze Ci powtorzyc (sic!) sobie rachunek prawdopodobienstwa ze szkoly sredniej.

Prawd. wylosowania liczby 1 w pierwszym losowaniu wynosi 1/49, w drugim 1/48, w trzecim 1/47 itd. Wszystko jest ok.

Nieprawda. Wy za każdym razem losujecie z tego samego zbioru liczb i sprawdzacie warunek, czy czasem wylosowana liczba już nie padła. przecieŻ to się nijak ma do tego co napisałeś.

Nie wszystkie... pare algorytmow (np moj) ma prawdopodobienstwo dobre

Nieprawda. Wy za każdym razem losujecie z tego samego zbioru liczb i sprawdzacie warunek, czy czasem wylosowana liczba już nie padła. przecieŻ to się nijak ma do tego co napisałeś

Przecież jeśli sprawdzamy warunek, żeby się dana liczba nie powtarzała, to tak jakby była wykluczona z kolejnych losowań. Nawet jeśli zostanie wylosowana, to i tak losowanie będzie powtarzane do momentu, aż wylosowana zostanie liczba inna od wylosowanych wcześniej. Czyli co z tego, że losujemy cały czas ze zbioru 49 liczb, skoro w drugim losowaniu można wylosować tylko 1 z 48, bo warunek wyklucza wylosowanie tej 49.</quote>

Do ort!: zgadza się, w kolejnym rzucie jest równe 1/2, ale nie w całym procesie losowania. Jak masz w urnie 5-b i 3-c to jak masz ciąg bbbc to P(c)<>3/8.

Do szeli: Patrz wyżej. A jak dla Ciebie losowanie kuli ze zwracaniem i bez to to samo to o czym my tu mówimy.

Do krulika: zgadza się, w kolejnym rzucie jest równe 1/2, ale nie w całym procesie losowania. Jak masz w urnie 5-b i 3-c to jak masz ciąg bbbc to P(c)<>3/8.

Tak, nie zaprzeczam. Przeciez wlasnie we wszystkich podanych tu algorytmach tak wlasnie jest. Jesli wylosujesz najpierw powiedzmy 1, to w drugim losowaniu mozesz wylosowac liczbe z zakresu [2; 49]. Czyli: P(1) = 0, P(2) = 1/48, P(3) = 1/48, ...., P(49) = 1/48. Jesli pozniej wylosujesz powiedzmy 3, to masz: P(1) = 0, P(2) = 1/47, P(3) = 0, P(4) = 1/47, P(49) = 1/47. Tak jest w naszych programach i tak jest w rzeczywistosci. Nie ma zadnego bledu.

Do szeli: Patrz wyżej. A jak dla Ciebie losowanie kuli ze zwracaniem i bez to to samo to o czym my tu mówimy.

Szela nic takiego nie napisal, ze dla niego to to samo. Nasze alg. realizuja losowanie kuli BEZ ZWRACANIA. Losowanie z szerszego zakresu i odrzucanie liczby, jesli sie powtorzyla, jest czysto technicznym zabiegiem i NIE MA ZADNEGO ZNACZENIA dla rozkladu prawdopodobienstwa wynikow.

Jesli twierdzisz, ze rozklad generowany przez nasze alg. jest inny, to podaj (i uzasadnij), ktore kombinacje sa wg Ciebie bardziej prawdopodobne (w rzeczywistosci rozklad jest jednostajny, wiec twierdzisz, ze w naszych alg. taki nie jest).

Szeli dostał odpowiedzi i ma z czego wybierać a wątek odbiegł od tematu i polazł hen na manowce. Potwornie nie lubie czczych i jałowych dyskusji oraz dzielenia włosa na czworo. Nie ważne jak sie losuje, ważne, żeby wylosować i nie potrzeba do tego głębokich teorii.

Wszystkie losowania powyższe to losowania ze zwracaniem, ale gdy zostanie wylosowana powtornie ta sama kula (wartość) to wynik losowania zostaje odrzucony bądź zignorowany, bądz w ogole nie wpływa na wynik koncowy.... Co daje efekt taki sam jak losowanie bez zwracania. Zresztą nigdzie nie jest napisane, że musze losować tylko 6 razy ! Mogę losowac i tysiąckrotnie, byleby wylosować 6 niepowtarzalnych cyfr.

Cytat dla świętego:

'Nie mnóż bytów ponad potrzebę' Ockham

// niniejszym temat uważam za wyczerpany. Swięty następnym razem wrzuc algorytm, albo zmien forum.