Lotto C++:lla
Pertti.O.Jauhiainen
Elikkä pitäis saada tulostettua 7 sattumanvaraista numeroa jotka ovat
pienempiä
kuin 30 mutta suurempia kuin nolla. Kokeilin tehä sitä for silmukalla ja
random funktiolla mutta sain aina samat numerot.
Kiitos! Kaikille vastaajille.
Juhana "The Voice" Jauhiainen
Paavo Sinisalo
Pertti.O.Jauhiainen kirjoitti viestissä <7stj2h$e4c$1...@tron.sci.fi>...
mutta turbo pascalissa pitää ainakin käytää randomize komentoa
randomin lisäksi, jotta kone arpoo joka kerta eri numerot.
Että löytyisikö c++:stä jokin randomize komennon tyylinen komento ?
(mutua, anteeksi!) ;)
t:paavo sinisalo
Antti-Juhani Kaijanaho
> Kokeilin tehä sitä for silmukalla ja random funktiolla mutta sain
> aina samat numerot.
Auttaisiko ryhmän FAQ:n lukeminen? (Osoite sigussa.)
--
%%% Antti-Juhani Kaijanaho % ga...@iki.fi % http://www.iki.fi/gaia/ %%%
FAQ on ystäväsi.
<URL: http://www.iki.fi/gaia/faq/saoa-faq.html >
Jori M{ntysalo
> Mitenkähän tekisin Lotto ohjelman C++:lla. [...] random funktiolla
> mutta sain aina samat numerot.
Satunnaislukugeneraattori pitää alustaa. Se tapahtuu C:ssä ja C++:ssa
funktiolla srand. Alustamiseen pitäisi keksiä jostain "aito"
satunnaisluku. Paremman puutteessa voit käyttää kellonaikaa.
Tässä esimerkki melkein suoraan Borland C++ Builderin ohjeista
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main()
{
int i;
time_t t;
srand((unsigned) time(&t));
printf("Ten random numbers from 0 to 99\n\n");
for(i=0; i<10; i++)
printf("%d\n", rand() % 100);
}
Tuo antaa sitten aina samat luvut, jos se käynnistetään samaan
kellonaikaan. Riittää lottorivin generointiin, mutta ei riitä
esimerkiksi salausavaimen generointiin tms.
Vastaus löytyy myös ryhmän FAQ:sta, osoite
http://www.iki.fi/gaia/faq/saoa-faq.html
kohta 4.1. Satunnaisuus on kuitenkin niin monimutkainen asia,
että tuon luettuaan ei pidä luulla tietävänsä aiheesta kaikkea.
--
= = = = Jori Mäntysalo - jm5...@uta.fi = = = =
"Ja äijä kirjoittaa ...matematiikkaryhmään. Hitto mikä nörtti!" -JP
Juho Cederstrom
Pertti.O.Jauhiainen <per...@dlc.fi> wrote:
> Mitenkähän tekisin Lotto ohjelman C++:lla. Kääntäjä on Borland Turbo C++.
(En vastaa kysymykseen, vaan esitän itse lisäkysymyksen)
Olen aina ihmetellyt, että kuinka tuossa lottoarvonnassa pidetään huoli,
ettei sama numero tule kahdesti. Onko se vain tehtävä niin, että jos tulee
numero, joka on jo arvottu, arvotaan uudestaan?
Tehdäänkö dynaaminen taulukko (siis sellainen, jonka kokoa saa muutettua),
ja lisätään siihen kaikki mahdolliset numerot. Sitten, kun ollaan arvottu
sieltä yksi numero, poistetaan se taulukosta ja niin edelleen?
--
#!/usr/bin/perl -wT -- Please take a look at my mail address when replying
$_ = "-~--~-~- -~~~-~-~ -~~~--~~ -~~~-~-- --~----- -~-----~ ";
$_ .= "-~~-~~~- -~~-~~~~ -~~~-~-- -~~-~--- -~~--~-~ -~~~--~- ";
$_ .= "--~----- -~-~---- -~~--~-~ -~~~--~- -~~-~~-- --~----- ";
$_ .= "-~--~--- -~~----~ -~~---~~ -~~-~-~~ -~~--~-~ -~~~--~- ";
tr/~-/10/;my$a;foreach(split/\s/){print(pack"B8",$_)}print"\n";
Kimmo K. I. Surakka
> Olen aina ihmetellyt, että kuinka tuossa lottoarvonnassa pidetään huoli,
> ettei sama numero tule kahdesti. Onko se vain tehtävä niin, että jos tulee
> numero, joka on jo arvottu, arvotaan uudestaan?
Voi tuotakin koittaa, mutta siinä on se vaara, että voidaan
jäädä ikisilmukkaan.
> Tehdäänkö dynaaminen taulukko (siis sellainen, jonka kokoa saa muutettua),
> ja lisätään siihen kaikki mahdolliset numerot. Sitten, kun ollaan arvottu
> sieltä yksi numero, poistetaan se taulukosta ja niin edelleen?
Vaikkapa. Tai näin:
int koko=39;
int taulukko[koko]
for (int i=0; i< koko; i++)
taulukko[i] = i+1;
/* Nyt taulukossa on kaikki sallitut luvut */
for (int n=0; n< 7; n++) {
/* Arvotaan 7 lukua */
int idx = rand() % koko;
printf("Arvottin numero %d.\n", taulukko[idx]);
/* Poistetaan valittu numero taulukosta: */
taulukko[idx]=taulukko[koko];
koko--;
}
Taulukon itse ei siis tarvitse olla dynaaminen, pitää vain
pitää kirjaa siitä, kuinka isoa osaa siitä käytetään.
Kusti
--
Kimmo K. I. Surakka : puh: (0400) 546 024
Insinöörinkatu 60 B 80 : e-mail: ku...@cs.tut.fi
33720 TAMPERE, FINLAND : http://www.cs.tut.fi/~kusti/
Mika Viskari
> Olen aina ihmetellyt, että kuinka tuossa lottoarvonnassa pidetään huoli,
> ettei sama numero tule kahdesti. Onko se vain tehtävä niin, että jos tulee
> numero, joka on jo arvottu, arvotaan uudestaan?
Vaikka näin (koodi Pascalia/pseudoa, random palauttaa luvun nollan ja
ykkösen väliltä: 0 <= X < 1):
var
i: integer;
TarvittaviaNumeroita: integer;
begin
TarvittaviaNumeroita := 7;
for i := 1 to 39 do begin
if random < (TarvittaviaNumeroita / (40 - i)) then begin
Print 'Valittu numero: ' + i;
TarvittaviaNumeroita := TarvittaviaNumeroita - 1;
end;
end;
end;
Ideana on että kun ollaan tutkimassa ykköstä, niin sen valituksi
tulemisen todennäköisyys on 7/39. Jos ykköstä ei valita, kakkosen
todennäköisyys on 7/38, jos taas ykkönen valittiin, kakkosen
todennäköisyys on 6/38. Seitsemän numeroa tulee varmasti valituksi,
koska viimeistään sitten kun käsiteltävä numero on 33 ja oletetaan että
yhtään numeroa ei ole vielä valittu), (TarvittaviaNumeroita / (40 - i))
= (7 / 7) = 1 ja 33 valitaan varmasti, kuten kaikki loputkin numerot,
eli 7 kappaletta.
Mika Viskari
Marko Poutiainen
: Olen aina ihmetellyt, että kuinka tuossa lottoarvonnassa pidetään huoli,
: ettei sama numero tule kahdesti. Onko se vain tehtävä niin, että jos tulee
: numero, joka on jo arvottu, arvotaan uudestaan?
Itse olen tuota käyttänyt useasti, hyvin on toiminut.
: Tehdäänkö dynaaminen taulukko (siis sellainen, jonka kokoa saa muutettua),
: ja lisätään siihen kaikki mahdolliset numerot. Sitten, kun ollaan arvottu
: sieltä yksi numero, poistetaan se taulukosta ja niin edelleen?
Voin sen tietysti noinkin tehdä, mutta voit tehdä sen myös niin, että teet
oikean kokoisen taulukon tyyppiä Boolean (int, whatever) ja merkkaat jo
arvotun numeron trueksi. Tai läimit vain johonkin taulukkoon ne jo arvotut
arvot. Tai...
Ratkaisu riippuu tietysti siitä, miten isosta numeroavaruudesta on kyse ja
kuinka monta lukua siitä arvotaan.
--
Marko Poutiainen | These are my principles.
m...@paju.oulu.fi | If you don't like them, I have others.
http://www.toffeeweb.org | -Groucho Marx
Marko Poutiainen
: ceder...@kolumbus.REMOVE_THIS.fi (Juho Cederstrom) writes:
: > Olen aina ihmetellyt, että kuinka tuossa lottoarvonnassa pidetään huoli,
: > ettei sama numero tule kahdesti. Onko se vain tehtävä niin, että jos tulee
: > numero, joka on jo arvottu, arvotaan uudestaan?
: Voi tuotakin koittaa, mutta siinä on se vaara, että voidaan
: jäädä ikisilmukkaan.
Jos jäädään tilanteessa, jossa arvottavien lukujen määrä on pienempi kuin
joukko, josta ne arvotaan, jossakin on vikaa. Idea on siis seuraavanlainen:
dim arvotut[1..39] as boolean
dim found as boolean
dim i as integer
dim val as integer
randomize
found = false
for i = 1 to 7
do while found = false
val = int((39*rnd)+1)
if arvotut[val] = false then
arvotut[val] = true
found = true
end if
loop
found = false
next
VB:nä, jotta ei-C-miehetkin tajuavat. Enkä mene bugittomuudesta takuuseen.
Luvut voi sitten kivasti tulostaa vaikka tuosta taulukosta
(For..Next-loopilla).
Jos tuo jää ikiluuppiin, niin satunnaislukugeneraattori on rikki.
ja...@my-deja.com
>On 30 Sep 1999 11:50:59 +0300, ku...@cs.tut.fi (Kimmo K. I. Surakka)
>IMO tuo on turhaa.
Ideanahan oli estää jumiin jääminen arvottaessa toistamiseen samaa
numeroa. Erittäin epätodennäköistä että noin käy, mutta jos käy
kerrankin niin se on liikaa.
Jukka Suomela
> In sfnet.atk.ohjelmointi.alkeet Kimmo K. I. Surakka <ku...@cs.tut.fi> wrote:
> : ceder...@kolumbus.REMOVE_THIS.fi (Juho Cederstrom) writes:
> : > Olen aina ihmetellyt, että kuinka tuossa lottoarvonnassa pidetään huoli,
> : > ettei sama numero tule kahdesti. Onko se vain tehtävä niin, että jos tulee
> : > numero, joka on jo arvottu, arvotaan uudestaan?
> : Voi tuotakin koittaa, mutta siinä on se vaara, että voidaan
> : jäädä ikisilmukkaan.
IMO olennaista tässä on se, että tuo hylkäämismenetelmä on tehoton.
Erityisesti tämä tulee esiin, jos arvottavien numeroiden lukumäärä on
lähellä kaikkien numeroiden lukumäärää.
Hylkäämismenetelmässä on ongelmana se, että ohjelman suoritusaika on
ennalta-arvaamaton. Käytännössä tietokoneiden
satunnaislukugeneraattoreita käytettäessä voidaan aina sanoa jokin raja
sille, kuinka monta arvontaa kaikkiaan voidaan joutua tekemään, mutta
tuo raja voi olla tilanteesta riippuen hyvinkin suuri. Ja täydellisten
satunnaislukugeneraattorien kohdalla tuollaista rajaa ei voida edes
antaa - on olemassa positiivinen todennäköisyys sille, että n arvontaa
ei riitä, oli tuo n sitten mikä tahansa kokonaisluku.
Tämän vuoksi on luonnollisesti fiksua pyrkiä välttämään algoritmeja,
jotka perustuvat joidenkin satunnaislukujen hylkäämiseen.
_Joissain_ tilanteissa voi olla vaikea löytää menetelmää, jossa ei
jouduttaisi koskaan hylkäämään arvottua lukua. Esimerkiksi haluttaessa
arpoa satunnaisesti jokin piste mutkikkaan, moniulotteisen kappaleen
sisältä, voi olla kaikkein yksinkertaisinta ja kohtalaisen tehokastakin
arpoa jokin piste kappaletta ympäröivän särmiön sisältä ja hylätä
pisteet, jotka osuvat kappaleen ulkopuolelle.
Sen sijaan _tässä_ lottoarvontaongelmassa hyvin yksinkertaisella
algoritmilla voidaan välttää tuo arvottujen lukujen hylkääminen
kokonaan. Näin arvonnan suoritusaika saadaan ennalta-arvattavaksi.
--
Jukka Suomela - http://narnia.tky.hut.fi
Servin-Maijan tie 10 F 83, 02150 ESPOO, FINLAND
Marko Poutiainen
: IMO olennaista tässä on se, että tuo hylkäämismenetelmä on tehoton.
: Erityisesti tämä tulee esiin, jos arvottavien numeroiden lukumäärä on
: lähellä kaikkien numeroiden lukumäärää.
Juu, tottakai, mutta threadin otsikko "Lotto C++:lla". Ymmärsin niin, että
kyseessä olisi ohjelma, joka arpoo muutamia lottorivejä.
: Sen sijaan _tässä_ lottoarvontaongelmassa hyvin yksinkertaisella
: algoritmilla voidaan välttää tuo arvottujen lukujen hylkääminen
: kokonaan. Näin arvonnan suoritusaika saadaan ennalta-arvattavaksi.
Juu, tottakai (kaikuuko täällä), jos tehdään sovellusta, jossa nuo ovat
olennaisia. Pitää kuitenkin muistaa se KISS-sääntö. Turha tehdä ongelmasta
tarpeettoman monimutkaista. Todennäköisyys, että esittämäni algoritmin
suorittaminen kestäisi merkittävän ajan, on tähtitieteellisen pieni.
Kimmo K. I. Surakka
> Juu, tottakai (kaikuuko täällä), jos tehdään sovellusta, jossa nuo ovat
> olennaisia. Pitää kuitenkin muistaa se KISS-sääntö. Turha tehdä ongelmasta
> tarpeettoman monimutkaista. Todennäköisyys, että esittämäni algoritmin
> suorittaminen kestäisi merkittävän ajan, on tähtitieteellisen pieni.
Totta, mutta algoritmisi ei ole niin paljon yksinkertaisempi
kuin jo arvottujen poisto, että olisi perusteltua käyttää sitä
tässä. Kuitenkin joku haluaa soveltaa sitä myös
ylävoltalaiseen lottoarvontaan, jossa valitaankin 20 numeroa
25:stä, tai johonkin muuhun etäisesti alkuperäistä ongelmaa
muistuttavaan tilanteeseen. Kannattaa pyrkiä tekemään
sellaista koodia, joka taipuu helposti uusiin tilanteisiin,
niin saadaan jonkinlaista uudelleenkäytettävyyttäkin.
Juho Cederstrom
Toni Parviainen <toni.pa...@sci.fi> wrote:
> while(taulukko[luku]=1) do /* 1 = numero on jo arvottu */
> luku = arvo_luku();
Tässähän oli juuri se häviävän pieni mahdollisuus, että ohjelma jää
ikisilmukkaan.
--
#!/usr/bin/perl -wT -- Please take a look at my mail address when replying
$_= "Perl is just another great programming language!" ;my@a=split
/\s/;my$b=ucfirst$a[2].' '.ucfirst$a[3].' '.$a[0];$b.=" Hacker\n";print $b;
Valmari Antti
Tämä keskustelu toistuu näköjään määräajoin ...
Kimmo Surakka:
! int koko=39;
! int taulukko[koko]
! for (int i=0; i< koko; i++)
! taulukko[i] = i+1;
! /* Nyt taulukossa on kaikki sallitut luvut */
! for (int n=0; n< 7; n++) {
! /* Arvotaan 7 lukua */
! int idx = rand() % koko;
! printf("Arvottin numero %d.\n", taulukko[idx]);
! /* Poistetaan valittu numero taulukosta: */
! taulukko[idx]=taulukko[koko];
! koko--;
! }
Olen nähnyt aika monta tarjokasta tähän tehtävään, ja tämä on
niistä kirkkaasti paras: helppo toteuttaa, luotettava ja
tehokas (ja löytyy oppikirjoista).
Ainoa pikkupurnaukseni liittyy riviin "int idx = rand() % koko;".
Tavoitteena on muodostaa tasan jakautunut (vale)satunnainen
kokonaisluku väliltä 0, ..., koko-1. Ikävä kyllä "rand() % koko"
ei tuota tasajakaumaa, vaan hieman suosii pieniä numeroita. Jos
rand tuottaa 32-bittisen valesatunnaisluvun ja koska koko <= 39
on vinoutuma kyllä aika pieni. Vähän isompi ongelma on, että rand()
itsessään on usein sangen huono, esim. tuottaa joka toisella
kerralla parillisen ja muilla kerroilla parittoman luvun.
Generaattori, jossa nämä molemmat puutteet on korjattu löytyy esim.
http://www.cs.tut.fi/~ava/81120extra/random.cc
Mika Viskari:
% Vaikka näin (koodi Pascalia/pseudoa, random palauttaa luvun nollan ja
% ykkösen väliltä: 0 <= X < 1):
%
% var
% i: integer;
% TarvittaviaNumeroita: integer;
% begin
% TarvittaviaNumeroita := 7;
%
% for i := 1 to 39 do begin
% if random < (TarvittaviaNumeroita / (40 - i)) then begin
% Print 'Valittu numero: ' + i;
% TarvittaviaNumeroita := TarvittaviaNumeroita - 1;
% end;
% end;
% end;
Tätä en ole ennen nähnytkään! Tämä tuottaa kyllä oikean jakauman,
mutta en silti suosittele kahdesta syystä. Ensinnäkin, tämä on
edellistä hitaampi, koska kutsuu valesatunnaislukugeneraattoria
39 kertaa 7:n sijasta, ja hyvä valesatunnaislukugeneraattori voi
olla kohtalaisen hidas. Hitautta aiheuttaa myös liukulukulaskennan
käyttö. Lottokoneessa tällä nopeuserolla tuskin on merkitystä,
mutta jossain muussa sovelluksessa ero voi olla olennainen.
Toinen vika on, että liukulukulaskenta on periaatteessa aina
epätarkkaa. On pieni periaatteellinen mahdollisuus, että tuo
tuottaa pyöristysvirheiden takia liikaa tai liian vähän lukuja.
Mahdollisuus on kyllä äärimmäisen pieni, koska pyöristysvirheen
tulisi tapahtua testissä random < 0/x tai random < x/x, mutta
takaako mikään, että mahdollisuus on nolla?
Tässäkin muuten on jakaumassa pieni vinoutuma, mutta nyt on vaikea
nähdä, mitä lukuja se suosii.
Toni Parviainen:
> IMO [Surakan ratkaisu] on turhaa. Jos kerran käyttää 39 alkioista taulukkoa niin
> siinähän ne numerot ovat jo. Toki voi tehdä samantien 40 alkiota jos
> se selkiyttää (ei tarvitse käyttää ekaa alkiota). Sitten arpoo
> numeroita ja jos numeroa ei ole vielä arvottu heittää kyseiseen
> alkioon esim. 1, eli kai jotenkin näin:
>
> int luku;
>
> for(i=0; i<7; i++)
> {
> luku = arvo_luku(); /* arvo_luku() palauttaa satunnaisluvun */
> while(taulukko[luku]=1) do /* 1 = numero on jo arvottu */
> luku = arvo_luku();
> taulukko[luku] = 1;
> }
Tämän ratkaisun näkee aika ajoin. Näin ei pidä missään nimessä
tehdä! Lottokoneena tämä vielä toimii, mutta esimerkiksi korttipakan
sekoitukseen tämä periaate on onnettoman hidas, kun taas Surakan
ratkaisu on aina nopea.
Marko Poutiainen puolusti olennaisesti samaa ratkaisua ja totesi:
# Jos tuo jää ikiluuppiin, niin satunnaislukugeneraattori on rikki.
Kuinka niin? Pikemminkin päinvastoin. Aidolla satunnaislukugeneraattorilla
tuo voi jäädä ikuiseen silmukkaan (tosin vain todennäköisyydellä 0).
Kaikki valesatunnaislukugeneraattorit ovat sen verran epätäydellisiä,
että niillä tuo ei voi jäädä ikuiseen silmukkaan. Mutta kuten sanoin,
lottokoneelle tuo toimii, mutta korttipakan sekoittajana ei kunnolla.
Jukka Suomela näköjään analysoi tätä hyvin. Siihen lisään:
valitettavasti valesatunnaisluvun skaalaus annetulle alueelle on
yleensä mahdotonta ilman, että välillä hylätään lukuja. Kuten sanoin,
rand() % koko; ja int((39*rnd)+1) suosivat hieman pieniä lukuja.
Koska valesatunnaislukugeneraattorin alueen koko on yleensä kahden
potenssi ja kahden potenssit eivät jakaannu tasan 39:llä, käy niin,
että kaikkia mahdollisia lopputuloksia ei voi jakaa tasan 39 lokeroon
vaikka miten yrittäisi ilman, että jotain hylätään. Mutta kun
hylkääminen tehdään oikein ovat haitat pienet. Toisaalta, niin pieni
epätasaisuus kuin tässä syntyy on omassa lottokoneessa varmasti
hyväksyttävissä. Viranomaisten lottokoneesta en ole aivan varma.
# Juu, tottakai, mutta threadin otsikko "Lotto C++:lla". Ymmärsin niin, että
# kyseessä olisi ohjelma, joka arpoo muutamia lottorivejä.
Tässä tilanteessa on olemassa ratkaisu, joka on yksinkertainen ja aina
nopea ja luotettava. En tiedä yhtään ainutta tilannetta, jossa se olisi
huonompi kuin Poutiaisen kannattama. Kenenkään ei kannata opetella
huonompaa ratkaisua kun yksiselitteisesti parempikin on olemassa.
KISS-sääntö ei päde tällä kertaa, sillä Surakan ratkaisu ei ole yhtään
monimutkainen. Tai oikeastaan KISS-sääntö sanoo, että kannattaa muistaa
vain Surakan ratkaisu ja unohtaa muut, sillä on yksinkertaisempaa muistaa
yksi yleiskäyttöinen ratkaisu, kuin monta ratkaisua tai yksi rajoitettu
ratkaisu rajoineen.
Ei ole mitään pahaa siinä, että itse kukin ehdottaa omia ratkaisuja, jotka
toimivat vain kyseisessä tilanteessa. Kyllä omia ratkaisuja saa
ehdottaa! Se ei ole typerää.
Jos sitten kuitenkin joku perustellusti huomauttaa, että tuo ei toimi
aina ja tässä on toinen ratkaisu joka on muissa suhteissa ainakin yhtä
hyvä ja lisäksi toimii aina, niin silloin olisi typerää ummistaa korvansa
ja linnoittautua puolustamaan omaa ratkaisua. Yksi uutisryhmien hienoja
puolia on, että kanssakirjoittaja saattaa olla aivan aloittelija tai
kymmenien vuosien kokemuksen omaava asiantuntija, jolla on hyllyssään
alan kirjallisuus ja tieto. Aina kun ehdottaa jotain ratkaisua, on
olemassa vaara, että asiantuntijat tyrmäävät sen. Se kuuluu uutisryhmien
luonteeseen. Jos näin käy, niin viisas ihminen toteaa että noinhan se
onkin, olen oppinut jotakin, keskustelusta oli hyötyä.
Sen jälkeen kun on tullut tietoiseksi paremmasta ratkaisusta ja huomannut,
että se todella on parempi, ei huonompaa ratkaisua pidä enää mainostaa.
--- Antti Valmari ---
Mika Viskari
>
> Kimmo Surakka:
> ! int koko=39;
> ! int taulukko[koko]
> ! for (int i=0; i< koko; i++)
> ! taulukko[i] = i+1;
> ! /* Nyt taulukossa on kaikki sallitut luvut */
> ! for (int n=0; n< 7; n++) {
> ! /* Arvotaan 7 lukua */
> ! int idx = rand() % koko;
> ! printf("Arvottin numero %d.\n", taulukko[idx]);
> ! /* Poistetaan valittu numero taulukosta: */
> ! taulukko[idx]=taulukko[koko];
> ! koko--;
> ! }
Kun tämä nyt kerran todettiin parhaaksi ratkaisuksi (ja oma hävisi),
niin kai jotain huomautettavaa on pakko löytää ;)
Eikös noiden viimeisten rivien järjestystä pitäisi muuttaa, muuten
taulukosta osoitetaan yli.
koko--;
taulukko[idx]=taulukko[koko];
> Mika Viskari:
> (todennäköisyyttä käyttävä ratkaisu)
> Tätä en ole ennen nähnytkään!
Lukaisepa kirja nimeltä Programming Pearls... sieltä muistui tällainen
mieleen.
Hidashan tämä on mutta eipä kuluta muistia.
> On pieni periaatteellinen mahdollisuus, että tuo
> tuottaa pyöristysvirheiden takia liikaa tai liian vähän lukuja.
> Mahdollisuus on kyllä äärimmäisen pieni, koska pyöristysvirheen
> tulisi tapahtua testissä random < 0/x tai random < x/x, mutta
> takaako mikään, että mahdollisuus on nolla?
Tekemällä algoritmiin hieman lisää tilanteen tarkkailua, voidaan nuo
kaksi kohtaa käsitellä erikseen, jolloin pyöristysvirheistä päästään.
> Sen jälkeen kun on tullut tietoiseksi paremmasta ratkaisusta ja huomannut,
> että se todella on parempi, ei huonompaa ratkaisua pidä enää mainostaa.
Auts, tulikohan tässä vielä mainostettua omaa Vähän Muistia Kuluttavaa
Arpomisalgoritmia (tm)...
Mika Viskari
Valmari Antti
Valmari Antti wrote:
>
> Kimmo Surakka:
> ! int koko=39;
> ! int taulukko[koko]
> ! for (int i=0; i< koko; i++)
> ! taulukko[i] = i+1;
> ! /* Nyt taulukossa on kaikki sallitut luvut */
> ! for (int n=0; n< 7; n++) {
> ! /* Arvotaan 7 lukua */
> ! int idx = rand() % koko;
> ! printf("Arvottin numero %d.\n", taulukko[idx]);
> ! /* Poistetaan valittu numero taulukosta: */
> ! taulukko[idx]=taulukko[koko];
> ! koko--;
> ! }
Mika Viskari:
> Kun tämä nyt kerran todettiin parhaaksi ratkaisuksi (ja oma hävisi),
> niin kai jotain huomautettavaa on pakko löytää ;)
> Eikös noiden viimeisten rivien järjestystä pitäisi muuttaa, muuten
> taulukosta osoitetaan yli.
Kyllä pitäisi.
(Mahdollisia irvileukoja varten täsmennän, että Viskari tarkoitti
tietysti rivejä "taulukko[idx]=taulukko[koko];" ja "koko--;".)
Sanoisin, että Viskarin ratkaisu hävisi vain rinnan mitalla,
kun taas "hylkää jos tuli jo arvottu luku" häviää reilusti.
Viskari on oikeassa siinäkin, että hänen ehdottamansa ratkaisu
säästää muistia --- olettaen, että liukulukujen käyttöönotto
ei vastaavasti lisää muistin tarvetta ohjelmakoodissa, mikä
riippuu monista asioista, kuten että käytettäisiinkö liukulukja
muutenkin, ja missä määrin laitteisto tukee niitä.
--- Antti Valmari ---