JussiR kirjoitti:
Tässä koko ohjelman koodi
Jos kerran tuossa on koko ohjelman koodi, niin eihän tuo voi toimia, kun ei ole edes main-funktiota.
JussiR kirjoitti:
"`rand' undeclared (first use this function)"
Et ole ilmeisesti sisällyttänyt tarvittavaa otsikkotiedostoa (cstdlib), josta rand() löytyy.
Tuosta taulukoinnistahan ei ole mitään hyötyä jos vain tulostat arvotut luvut.
#include <iostream>
#include <cstdlib>
#include <ctime>
const int MAXI = 39;
const int NUMEROITA = 7;
int main()
{
std::srand(std::time(NULL));
for (int i = 0; i < NUMEROITA - 1; i++) {
std::cout << (std::rand() % MAXI) + 1 << " ";
}
std::cout << (std::rand() % MAXI) + 1 << std::endl;
return 0;
}EDIT: Jaaha, JussiR näköjään hölmöilee...
Joo sori :D poistin vahingos.
Kiitos korjauksesta mutta mitenkähän tekisin vielä tarkistuksen ettei tule kahta samaa numeroa..
Mahdoitko ajatella ollenkaan itse? Tietenkin laittamalla luvut taulukkoon ja tarkistamalla silmukassa, ettei arvottua lukua ole vielä.
Tehtävä ei ole ylivoimainen aloittelijallekaan vaan pyrkii nimenomaan kehittämään sitä ohjelmoinnissa tarvittavaa itsenäistä ajattelua.
Taikka sotketaan numerot taulukkoon ja otetaan tarvittava määrä:
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
int const palloja = 39;
int const valittavia = 7;
class numeroija
{
int n;
public:
explicit numeroija(int i = 1) : n(i) {}
int operator()() { return n++; }
};
class stdrand
{
int init() { std::srand(std::time(0)); return 0; }
public:
stdrand() { static int i = init(); }
int operator()() { return std::rand(); }
int operator()(int m)
{ return (int)(m*(std::rand()/(RAND_MAX+1.0))); }
};
int main()
{
int pallot[palloja];
std::generate(pallot, pallot+palloja, numeroija());
stdrand urd;
std::random_shuffle(pallot, pallot+palloja, urd);
std::copy(pallot, pallot+valittavia,
std::ostream_iterator<int>(std::cout, "\n"));
}PS. Saatiinko me hyvä arvosana?
Vielä yksi ratkaisu mahtuu mukaan:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define SUURIN 39
#define MAARA 7
int luvut[SUURIN];
int main(void) {
int i, n;
srand(time(0));
for (i = 0; i < SUURIN; i++) {
luvut[i] = i + 1;
}
for (i = 0; i < MAARA; i++) {
n = rand() % (SUURIN - i);
printf("%i ", luvut[n]);
luvut[n] = luvut[SUURIN - i - 1];
}
return 0;
}Tässä käytetään taulukkoa, johon tallennetaan aluksi kaikki luvut järjestyksessä. Aluksi arpomisalue on koko taulukko, mutta alueen oikeaa reunaa siirretään yhden luvun verran vasemmalle joka arpomisen jälkeen. Lisäksi arvotun luvun tilalle siirretään arpomisalueen oikealla reunalla oleva luku.
Jos lukuja on 9 ja niistä arvotaan 5, ohjelma toimii näin:
<----------arpomisalue---------->
i 0 1 2 3 4 5 6 7 8
luvut[i] 1 2 3 4 5 6 7 8 9
Arvotaan (väliltä 0...8) i = 3, jolloin valikoituu luku 4
<--------arpomisalue-------->
i 0 1 2 3 4 5 6 7 8
luvut[i] 1 2 3 9 5 6 7 8 9
Arvotaan (väliltä 0...7) i = 5, jolloin valikoituu luku 6
<------arpomisalue------>
i 0 1 2 3 4 5 6 7 8
luvut[i] 1 2 3 9 5 8 7 8 9
Arvotaan (väliltä 0...6) i = 3, jolloin valikoituu luku 9
<----arpomisalue---->
i 0 1 2 3 4 5 6 7 8
luvut[i] 1 2 3 7 5 8 7 8 9
Arvotaan (väliltä 0...5) i = 2, jolloin valikoituu luku 3
<--arpomisalue-->
i 0 1 2 3 4 5 6 7 8
luvut[i] 1 2 8 7 5 8 7 8 9
Arvotaan (väliltä 0...4) i = 2, jolloin valikoituu luku 8Nuo ehdotetut ratkaisut ovat kyllä tehokkaita, kun arpomisalue on pieni, mutta entäpä, jos arvotaankin miljardista luvusta sata? Silloin ei ole mielekästä tai edes mahdollista koota taulukkoa kaikista luvuista.
Yksinkertaisella idealla päästään O(n2)-aikaiseen ja O(n)-kokoiseen ratkaisuun, missä n on arvottavien lukujen määrä. Mikään ei siis riipu enää arvoalueesta, vain arvontojen määrä vaikuttaa. Antin ratkaisun mukaisesti voidaan pienentää arvonta-aluetta joka kierroksella, mutta koska lukuja ei ole tallennettu minnekään, täytyy selata jo saatua tulosta, jotta voidaan hypätä jo arvottujen lukujen yli. Arvottuun lukuun pitää siis lisätä aiemmin arvottujen sitä pienempien lukujen lukumäärä. Esimerkiksi kun 1 ja 3 on jo arvottu, 3. vapaa luku on 5.
#include <list>
#include <iostream>
#include <cstdlib>
#include <ctime>
int arvo(int min, int max)
{
return std::rand() % (max - min + 1) + min;
}
std::list<int> arvo_luvut(int min, int max, int n)
{
if (n > max - min + 1) throw "Liian pieni alue!";
if (n < 0) throw "Negatiivinen lukumäärä!";
if (n == 0) return std::list<int>();
std::list<int> alkuperainen, jarjestetty;
std::list<int>::iterator i;
int j;
j = arvo(min, max--);
alkuperainen.push_back(j);
jarjestetty.push_back(j);
while (--n) {
j = arvo(min, max--);
for (i = jarjestetty.begin(); i != jarjestetty.end(); ++i) {
if (*i > j) {
break;
} else {
++j;
}
}
jarjestetty.insert(i, j);
alkuperainen.push_back(j);
}
return alkuperainen;
}
int main()
{
const int min = 1, max = 39, lkm = 7;
std::list<int> l;
std::list<int>::iterator i;
std::srand(std::time(0));
std::cout << "Arvotaan " << lkm << " lukua väliltä " << min << " - " << max << "." << std::endl;
try {
l = arvo_luvut(min, max, lkm);
} catch (const char *s) {
std::cout << "Virhe arvonnassa: " << s << std::endl;
return 1;
}
i = l.begin();
std::cout << "Arvonnan tulos: " << *i;
for (++i; i != l.end(); ++i) {
std::cout << ", " << *i;
}
std::cout << std::endl;
return 0;
}Tämä ratkaisu on tietenkin lottonumerotapauksessa työläs ja hidas, mutta yleisessä tapauksessa aiemmin esitetyillä menetelmillä ei päästä kovinkaan pitkälle.
Jos lukualue on laaja mutta vain pieni osa luvuista tulee valituksi, voi myös käyttää sitä menetelmää, jossa arvonnassa voi tulla mikä tahansa luku, mutta luku hyväksytään vain, jos sitä ei ole valittu aiemmin. Hajautustaulun avulla voi tarkistaa vakioajassa, onko lukua vielä arvottu, jolloin koko arvonnan aikavaativuus on O(n) ja tilavaativuus on O(n), kun n on arvottavien lukujen määrä.
Aikavaativuus O(n) on varsin kohtuullinen, kun lukuja kuitenkin arvotaan n kappaletta. Mutta keksiikö joku, voiko tilavaativuutta vielä parantaa, jos ohjelman ei tarvitse tallentaa lukuja taulukkoon, vaan niiden tulostus riittää?
Antti Laaksonen kirjoitti:
Mutta keksiikö joku, voiko tilavaativuutta vielä parantaa, jos ohjelman ei tarvitse tallentaa lukuja taulukkoon, vaan niiden tulostus riittää?
Tarvitaan algoritmi lottorivien indeksointiin. Sitten vaan arvotaan indeksi, otetaan siitä luvut yksi kerrallaan ja tulostetaan ne.
Täällä on yksi algoritmi, mutta siinä käytetään lukualueen kokoista taulukkoa, jossa on esim. nollia ja ykkösiä. Jos sitä soveltaisi tähän, aikatehokkuus olisi siis suhteessa lukualueen kokoon. Onko jollain parempaa algoritmiä?
Antti Laaksonen kirjoitti:
Hajautustaulun avulla voi tarkistaa vakioajassa, onko lukua vielä arvottu, jolloin koko arvonnan aikavaativuus on O(n) ja tilavaativuus on O(n), kun n on arvottavien lukujen määrä.
Aikavaatimuksessakin on mukana satunnaistermi. Jos käytössä olisi oikea satunnaislukugeneraattori, pahimmassa tapauksessa aikaa kuluisi äärettömästi, ja esimerkiksi arvottaessa kaksi lukua sadasta arvontoja tarvitaan keskimäärin 2 + 1/99. Ero ei ole suurensuuri, mutta tarkoitus oli näyttää, että jo kahden luvun tapauksessa aikavaatimus ylittyy. Erilaisilla lukumäärillä, huonolla onnella tai kehnolla satunnaislukugeneraattorilla aikaa voi kulua huimasti enemmänkin.
Saivarteluksihan tämä kieltämättä menee, mutta sehän onkin yksi elämän suurista iloista.
funktio kirjoitti:
Tarvitaan algoritmi kombinaatioiden indeksointiin. Sitten vaan arvotaan indeksi, otetaan siitä luvut yksi kerrallaan ja tulostetaan ne.
Mutta miten kombinaation indeksi voidaan tallentaa alle O(n)-tilaan?
Metabolix kirjoitti:
Aikavaatimuksessakin on mukana satunnaistermi.
Niin on, ja vieläpä kaksi sellaista. Nimittäin hajautustaulun vakioaikaisuus perustuu myös siihen oletukseen, että luvut sijoittuvat mukavasti eri puolille taulua.
Jos arvottavia lukuja on vähän, voidaan olettaa, että niitä on alle puolet kaikista mahdollisista luvuista. Tällöin joka arvonnassa ainakin puolet luvuista kelpaa, jolloin keskimäärin kaksi arvontaa riittää. Toisin sanoen yhden luvun arvontakertojen lukumäärän odotusarvo on aina korkeintaan kaksi.
Metabolix kirjoitti:
Ero ei ole suurensuuri, mutta tarkoitus oli näyttää, että jo kahden luvun tapauksessa aikavaatimus ylittyy.
Ei se sentään tuossa ylity, koska voihan O(n) tarkoittaa sitäkin, että n luvun arvonnassa tehdään 2n arvontayritystä. Mutta olet oikeassa siinä, että satunnaisuus aiheuttaa (ainakin teoriassa) ongelmia, joten parempia aidosti O(n)-aikaisia algoritmeja saa ehdottaa.
Antti Laaksonen kirjoitti:
funktio kirjoitti:
Tarvitaan algoritmi kombinaatioiden indeksointiin. Sitten vaan arvotaan indeksi, otetaan siitä luvut yksi kerrallaan ja tulostetaan ne.
Mutta miten kombinaation indeksi voidaan tallentaa alle O(n)-tilaan?
Se on kokonaisluku.
Edit (en viitsi taas uutta viestiä tehdä): No joo, huono idea. En tajunnut, miten nopeasti eri vaihtoehtojen (ja indeksin vaatiman tilan) määrä kasvaa.
Mutta tuohan on vähän huijausta, kun samalla tekniikalla kokonaislukuun voi tallentaa vaikka kokonaisen kirjan. (Vaikkapa niin, että lukujoukon tilalla on miljardi kertaa suomen kielen aakkoset, ja ilmoitetaan siitä haluttu kombinaatio.)
J-kielessä onnistuu arvonta helposti. /:~>:x?y
Tässä /:~ järjestää vektorin, >: kasvattaa jokaista alkiota yhdellä vektorissa ja x?y luo vektorin, jossa on satunnaisesti valittu x alkiota väliltä 0..y-1 ilman takaisinpanoa. Ylläolevan malliset lottorivit syntyvät siis, kun x = 7 ja y = 39.
Esim:
/:~>:7?39 5 18 21 27 28 29 32
Virallisina valvojina toimivat Ken Iverson ja Roger Hui, joiden tapa tehdä ohjelmointikieliä on kyllä minulle lähes käsittämätön :-)
Kopeekka kirjoitti:
J-kielessä onnistuu arvonta helposti.
/:~>:x?y
Vaikuttaa opettelun arvoiselta ohjelmointikieleltä. C-kieli tuntuu nyt perin kömpelöltä.
Äh, jos asia voidaan kirjoittaa ihmiselle mielekkäämpään muotoon ohjelmallisen tehokkuuden siitä kärsimättä, kannattaa se tehdä.
Metabolix kirjoitti:
mutta entäpä, jos arvotaankin miljardista luvusta sata?
Yleensä ei ole edes järkevää käyttää samaa ratkaisumallia asioihin, joiden välillä on monen suuruusluokan ero.
Jos miljardista luvusta arvotaan sata, ihan käypä ratkaisu on arpoa numeroita ja tallettaa arvotut luvut taulukkoon. Jos saatu luku on jo tulostaulukossa, jatketaan arpomista, kunnes saadaan uusi. Kyllä, tämä malli toimii myös, kun arvotaan 39 luvusta 7, seiska kun on melko samalla hehtaarilla kuin sata.
Aiempi ratkaisuesitykseni on ihan kelvollinen, kun liikutaan korttipakkakokoluokassa. Lisäksi se hehkuttaa C++-kirjaston ja komponenttirakenteen käyttöä. Miljardikerhossa se ei oikein toimi, mutta vika ei ole varsinaisesti algoritmissa.
Jos nyt kuitenkin miljardiluokkaan siirryttäisiin, niin ensimmäinen asia, joka menee joka tapauksessa vaihtoon, on C-standardikirjaston satunnaislukufunktio. Sen ominaisuuksien riittävyydestä ei ole takeita oikein mihinkään oikeaan mallinnukseen tai simulointiin. Voi olla, ettei generaattori pysty tuottamaan kuin muutaman kymmenen tuhatta erilaista lukua (RAND_MAX).
Aihe on jo aika vanha, joten et voi enää vastata siihen.