Dupla elemek kiszűrése a tömbből

C/C++

Üdv mindenki!

Egy C házimban kérném segítségetek. A feladat egy igen egyszerűnek induló lottó program volt, amivel 5-ös illetve 6-os lottó játszható. Tömböket ugyan még nem vettünk, de korábbi programozás ismereteim alapján úgy gondoltam, hogy jobban járok, ha ezt a struktúrát választom a számok eltárolására. Azonban belefutottam abba a hibába, hogy dupla random elemeket is generál a C a tömbömbe, amiket lottó esetében ugye muszáj lenne kiszűrni első lépésben, hogy be tudjam fejezni a programot. Viszont akárhogy próbálkoztam ennek megvalósításra, sehogy se sikerült. Valakinek lenne rá ötlete esetleg?

A kód a következő: http://pastebin.com/sVbbmkvB

( gthomas | 2010. 10. 11., h – 09:52 )

Halmaz (set)?

[szerk]
Bocs, azt hittem C++.

Minden beillesztésnél meg kell keresned, szerepel-e már a listában ez az elem. Az exponenciális futási időt úgy lehet elkerülni, hogy az elemeket rendezve tárolod, így rendezve gyorsan tudsz keresni.

A tároló sokminden lehet, de a legegyszerűbb valami fa.

nah ez egy tipikus hiba, amikor a programozo megismer fejlettebb algoritmusokat es adatszerkezeteket es egybol mindenre azokat akarja hasznalni. mi lesz ennek a vege?
sok-sok sornyi kod es kidobott ido egy egyszeru feladat vegrehajtasara es valoszinuleg meg lassu is lesz. lotto program, hatos lottonal max 5 elemet kell atnezni, erre egy tomb teljesen megfelel, semmi rendezesre nincs szukseg

--
NetBSD - Simplicity is prerequisite for reliability

( phaul | 2010. 10. 11., h – 09:49 )

Off : az a default : break; a switch tetejen nem biztos hogy az amit szeretnel
==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

( szemet | 2010. 10. 11., h – 09:53 )

for(i=0;i<90;++i)tomb[i]=i+1;
for(i=0;i<5;++i){
int tmp1,tmp2;
// veletlen index
tmp2=rand()%(90-i)+i;
//swap a veletlen indexu elemre
tmp1=tomb[i];tomb[i]=tomb[tmp2];tomb[tmp2]=tmp1;
}
// tomb[0..4] az ot külonbozo random szam

Még egy fontos (bár evidens) hatékonysági megjegyzés: a tömböt elég csak egyszer feltölteni a program legelején, nem kell minden sorsolásnál újrainicializálni...

Így hosszútávon átlagban egy egyszerű ötös ciklus elegendő a számok kiválasztására: ez hatékonyabb mint az ismétléseket figyelgetni...

Dehogynem, az i=4 esetben ha rand()%86==0 önmagára cserélődik a tomb[4].

Persze a ciklus korábbi részeiben is előfordulhat, hogy tomb[4] választódik ki a cserére.

Összességében minden szám ugyanakkora eséllyel kerül be a tömb első 5 elemébe, de hát ez a cél! A véletlen permutációk generálásában persze könnyen lehet hibázni, szóval jó, hogy alaposan végig gondolod. ;) Emlékezetes eset volt ugye:
http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html

szerk: Maga az algoritmus egyébként tökéletesen modellezi a lottóhúzást: 1/90 eséllyel húz egyet, majd a maradék 89 számból - ami 1..89 indexen van a csere után - 1/89 eséllyel egy következőt, majd a maradék 88 számból - ami 2..89 indexen van stb...

( Hevi v | 2010. 10. 11., h – 09:56 )

Ha jól értem, a húzott lottószámok duplikálódnak. Én valószínüleg generálnék egy számot, végigfutnék a tömbön, hogy van-e ilyen, ha nincs, akkor jó, ha van, akkor generálok újat.

En nem igy csinalnam. Talan meg 90/5 eseten jo ez a fajta ujrahuzas.
En feltoltenek egy 90 elemu tombot: 1-90
sorsolnek egy szamot 1-90.
Utana feltoltenek egy 89 elemu tombot az elozoleg kihuzott szam kivetelevel.
sorsolnek ujra: 1-89, es a tomb erteke lenne a megfelelo szam.
...es igy tovabb (1-88...)

Nyilvan jo a vissza ellenorzos megoldas, de ha mas esetben 90/85ot kellene huzni, a vegen mar sok lenne az ujrahuzas.

A

http://hup.hu/node/93935#comment-1135132

megoldas pontosan ezt csinalja, azzal a kulonbseggel, hogy az iteracion belul a feltoltest egy swap valtja ki (gyorsabb es jobb).

Pl. kihuzod az 59-es szamot, ezzel az ervenytelenne valt. Ekkor ha a 90-es elemet berakod az 59-es helyere, es a kovetkezo korben csak a 89 elemu tombre boksz egyet veletlenszeruen, akkor ugyanott vagy.
(A kivalasztas szempontjabol erdektelen, hogy a 90-es szam a tomb[89] vagy tomb[58]-on van, ugyanakkora az eselye (1:89) a kivalasztodasra.

( kikuchiyo | 2010. 10. 11., h – 11:08 )

Alternatív megoldás:

- deklarálok egy N elemű tömböt (ahol N jelen esetben 45 vagy 90), és feltöltöm nullákkal: a[N]
- a következőt addig ismétlem, amíg elegendő (5 vagy 6) számot nem sikerült húzni:
- generálok egy véletlen számot 0 és N-1 között (itt jegyzem meg, a rand() % N elég rossz minőségű véletlen számokat állít elő - egy ilyen példaprogramnál persze mindegy, de jobb már az elején figyelni az ilyenekre), legyen ez k
- ha a[k] nulla, akkor megnövelem eggyel, és k-t eltárolom, mint jó lottószámot, vagy kiíratom azonnal; ha a[k] 1 (ami azt jelenti, hogy már kihúztam egyszer), nem csinálok semmit.

A fenti, Fisher-Yates keverésen alapuló megoldás elvileg is jobb ennél.

Direkt nem írtam kódot, abból nem tanul a kolléga ha mások kódját másolgatja.

Ez sem rossz algoritmus, de overkill ehhez a feladathoz.

Amit itt leirtal, az inkabb akkor jo, ha egy adott n elemu tombbol elo kell allitani egy veletlenszeru m elemu tombot (m kisebb n*k) amely uj tombben minden egyes elembol maximim k db lehet.

Egy problemaja van ennek: minel kozelebb kerul az m hossza az n*k-hoz, annal lassabb lesz az uj elem generacioja, hiszen meg kell "talalnia" azt az elemet, amelyik meg nem fogyott ki. S ezzel vissza is vezettuk a problemat az elobbi swap-olos technikara:

letrehozunk egy n*k elemu tombot, ahol minden elem k-szor szerepel. Minden iteracional az utolso elemet swappoljuk a kiesett helyere es eggyel csokkentjuk a kivalasztas tombjenek meretet (utolso elemet kiejtjuk)

En azert tartom ezt a megoldast tutinak, mert tomb kornyezetben a legegyszerubb leprogramozni, egy for ciklus, egy eredmeny szamlalo meg egy tomb kell neki, slussz-passz. Szerintem egy, a programozassal most ismerkedo embernek ez eppen megfelelo megoldas, majd megtanulja a fakat meg a fuveket, meg az O(n) alaku akarmiket menet kozben.
-- 


Ki oda vagyik, hol szall a galamb, elszalasztja a kincset itt alant.

( mn3monic v | 2010. 10. 11., h – 11:48 )

Ide még tömb se kell :) 

int i, num = 0;
for (i=0;i<5;i++) {
    num = num + (random() % 18) + 1;
    printf("%d. %d\n", i+1, num);
}

Ez nem csak ezért rossz: az első szám ugyan egyenletes eloszlású véletlen szám, de az [1,18] tartományban ([1,90] helyett), a többi pedig nem is egyenletes eloszlású.

Meg lehet nézni pl. gnuplottal:
plot for [i=1:5] 'random.txt' u i:(1) sm freq tit ''.i

Az ötödik oszlop eloszlása egészen hasonlít a normálishoz.

( enpassant v | 2010. 10. 11., h – 12:38 )

Ha tömbbel akarod megoldani, akkor szemet megoldása jó.

Azon viszont a helyedben elgondolkodnék, hogy a tanárom nem-e arra kíváncsi, hogy a tanult eszközökkel hogyan tudom megoldani a feladatot.

( harlequin | 2010. 10. 11., h – 12:59 )

nagyon primitiv megoldas, tombok, meg mindenfele egyeb ekzotikus dolgok nelkul:

1: kidobni 6 veletlen szamot.

2: egy darab feltetelbe belenyomni, hogy megnezze, van-e ketto egyforma kozottuk
(valahogy igy: if ((a1==a2) or (a1==a3) or (a2==a3).... csak 15 feltetel 6 szamnal :) )

3: ha igen, goto 1

4: ha nem, kiirjuk oket.

nem optimalis meg nem is otletes (sot, inkabb elrettento peldanak jo), viszont nem kell felni, hogy olyan dolog van benne felhasznalva, amit meg nem tanultak :)

Ebben a megoldasban az a rossz, hogy eloallhat az a nem eletszeru eset, hogy a program vegtelen ciklusba lep, mert nem kepes sose 5 szamot ugy generalni, hogy ne legyen kozottuk egyezo.

Bar gyakorlatilag ez a program is mukodokepes, elmeletileg viszont nem jo a fentebbi okok miatt.

(Nem piszkalodasbol irtam ide, csak egy vizsga idejen ilyenre is gondolni kell)

A végtelen ciklus 0 valószínűségű esemény.(de nem lehetetlen esemény persze)

Nem számolok utána, de pár ezres ismétlés szám esetén már tuti kisebb az eredménytelenség vsz-e, minthogy becsapódik a Földbe egy meteorit és mind meghalunk az ominózus vizsgáig, ahol az ilyen nüansznyi dolgokat a szemünkre hánynák ;)

Hát igen, természetesen ki kéne számolni. Aztán az elfogadás mindig a követelmények kérdése.

Sok randomizált algoritmikus problémában a hibavalószínűség levihető nagyságrendekkel a tranzisztorhiba (memória, processzor hiba) valószínűsége alá, amikor emiatt elutasítod, ez nyilván olyan eleve elborult szcenáriókban jelenik meg, amikor eleve hibajavító/ellenőrző és rendundancia fokozó extrákkal agyonzsúfolt extrém módon komplikált architektúrán dolgozol...

Nincs ezen mit kiszámolni. Ha a futásnak van olyan kimenetele (=végtelen ciklus), mely a programozó által kezelhető, de nem kezelt, akkor az hiba, kivéve, ha ez a nem kezelés szándékolt.
A végtelen ciklus pedig ebben az esetben olyan lehetséges kimenetel, mely a programozó által kezelhető, de nem kezelt és ami ráadásul egyértelműen hibás algoritmus eredménye. És ezen nem változtat az sem, ha esetleg 100 billió milliárd esetből egyetlen egyszer fordul elő.

Ezzel a felfogással minden olyan kód hibás, ami az UUID-k egyediségét feltételezi, mert a legtöbb implementációban egy véletlenszám-generátor felel az egyediségért.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Úristen, na még egy. Hányan vagytok még?
Ahogy olvasom, az UUID esetében azzal küszöbölik ki az esetleges duplikációkat, hogy megpróbálják ennek az esélyét minimálisra csökkenteni. De ez egy lottó húzás, nem UUID! Nincs olyan eset, hogy nem ér véget. És nem csak borzasztóan alacsony a valószínűsége, hogy nem ér véget, hanem lehetetlen, hogy normál körülmények közt ne érjen véget. Van 90 számom, 6-ot kell kiválasztani, ismétlések nélkül. Nincs olyan, hogy nem tudok kiválasztani hatot. És ha a való életben nincs olyan, hogy nem tudok kiválasztani hatot, akkor normál körülmények közt algoritmikusan sincs. És nem elfogadható olyan megoldás, ami azt mondja, hogy algoritmikusan normál körülmények közt azért egy kicsi esély csak van. A harder hiba, a Nap, a meteor, a tök tudja mi, nem normál körülmény.
Mennyire nehéz a lottó húzásnál maradni és megállapítani, hogy nincs olyan, hogy végtelen ciklus? Már elmentünk autó/vonat, harder hiba, meteor, Nap, UUID, minden irányba, hogy ott bizony van, de atyaég, lottóról beszélünk és az arra adott algoritmusról.

> És ha a való életben nincs olyan, hogy nem tudok kiválasztani hatot, akkor normál körülmények közt algoritmikusan sincs.

Visszatevéses vs. visszatevés nélküli húzás. A való életben nem teszik vissza a kihúzott számot, a rand() viszont adhatja ugyanazt. És ez teljesen normál körülmény. Ezért képzelhető el a végtelen ciklus. És nekem se tetszik az olyan megoldás, amiről már a tervezés fázisában tudod, hogy van esély hibás működésre, de nem baj, mert csak kicsi.

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Na jó, ez már tényleg a kabaré rész. De még egyszer, közkívánatra.

A való életben nem teszik vissza a kihúzott számot, a rand() viszont adhatja ugyanazt
Remek, ezek szerint legalább az lottó húzás menetét nem kell elmesélni. A rand() adhatja ugyanazt, kivéve ha programozottan megakadályozod. Ahogy látható is volt egy olyan példa, hogy előbb az összes elemből randol egy indexet, majd az (összes elem-1)-ből, majd (összes elem-2)-ből és mindig kiveszi az elemek közül a kihúzott számot. Így még véletlenül sem lehet az az eset, hogy ugyanazt kétszer húzza vagy pedig soha ne fejeződjön be a húzási esemény.
Ha a való életben nem teszik vissza a számot és a való életben nincs olyan, hogy nem sikerül kihúzni ötöt, sőt olyan sincs, hogy elsőre nem sikerül kihúzni öt különböző számot, akkor algoritmikusan sem elfogadható olyan esemény, ahol 0-nál akár csak egy kicsit is nagyobb a valószínűsége annak, hogy nem sikerül kihúzni ötöt vagy duplikátumot tartalmaz.

És ez nem tetszik/nem tetszik kérdése. Elfogadhatatlan, hogy egy véges és jól definiált problémára olyan algoritmus szülessen, aminél akár csak a lehető leghalványabb esély is felmerüljön, hogy esetleg nem ér véget. A való világ modellezése a cél, nem pedig a való világé plusz még egy kicsi.

Van még olyan ember, aki úgy gondolja, hogy algoritmikusan elfogadható lottó húzásnál a végtelen ciklus kialakulásának lehetősége, akármennyire is kicsiny legyen ez az esély? Ha a válasz az, hogy igen, akkor az ég szerelmére, válassz másik szakmát kérlek, annyi szép szakma van még a világon.

Azért vicces vagy. Tehát egy egyszerű, jól definiált problémára, amire 1 perc alatt ír az ember MAJDNEM BIZTOSAN véges időn belül lefutó algoritmust, nem szabad ezt alkalmazni, hanem bonyolítani kell. Szerintem az váltson szakmát, aki nem tudja a mértékeket. Amíg az egyetemen vagy, addig amit mondasz az szép. Aztán ha elkezdenek mérnöknek hívni és nem a NASA-nak dolgozol, akkor bejön a költség paraméter. Megéri 1 percnél több időt szánni erre? Egyértelmű a nemleges válasz. Fel tudnak idegesíteni az akadémikusok, mármint amikor belepofáznak az ilyen praktikus dolgokba... az ész sosem az egyetemről ment az iparba, hanem fordítva, az ipari dolgokat formalizálták az egyetemen.
----
Hülye pelikán

Egyrészt a szóban forgó algoritmus egy adott problémára íródott, másrészt kicsit sok lenne a telitalálatos, csak idióták csinálnának ilyen lottót, harmadrészt az adott problémára nyílván más algoritmus születne (mondjuk EGYET randomizálna, és azt venné ki, mindenféle ellenőrzés nélkül), negyedrészt, és ez a legjobb, nem csak elgondolkodtam de ki is próbáltam (mondjuk a "szóban forgó algoritmust" nem találtam, de újraírtam set-tel), és kb 20 futás után mondom, hogy 300-550 randomizáció után megvan a 89 szám, és villámgyorsan.
El kéne tényleg gondolkodni, hogy mennyit ér a programozó ideje...
----
Hülye pelikán

Összefoglalva: tehát nem csak nem oldja meg a feladatot, de még csak nem is optimális azoknál az eseteknél sem, ahol valamit csinál.
Azt nem tudom, mit rugózol a programozó idejével. Nyilván, ha egy olyan programom van, ahol könnyen átírhatom a bemenő paramétereket 90/5-ről 10000000000000/10000000000000-1-re, az adott esetben sokkal több időmegtakarítás, mint összedobni egy rossz programot, amit aztán át kell írni később. (És igen, tudom, hogy ez nem életszerű, meg nem futna le ekkora számokra, meg stb.,de azért remélem, érthető, mire akarok kilyukadni.)

KisKresz

Ez egy szép gondolat, csak sajnos egyik itt leírt algoritmus sem olyan, hogy szabadon változtathatnám a paramétereket.
A tömbös megoldás pl elég szarul teljesít, ha sok szám közül kell keveset kiválasztani. A tömb nélküli (fix futásidejű) rosszul teljesít, ha sok számot kell kihúzni. A nem fix futásidejűek pedig ha az alaphalmaz és a húzandók száma közel van egymáshoz.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Látom nem láttad még az én megoldásomat :-)
Minden pontnak megfelel, főleg, ha a tömböt lecserélnénk láncolt listára.
Ez egy jó általános megoldás, ahol szabadon változtathatóak a paraméterek.
Ha viszont arra gondolsz, hogy úgy szabadon változtatni a paramétereket, hogy minden esetben ne legyen nála jobb algoritmus, akkor persze igazad van. Viszont olyan algoritmus nem csak erre a problémára, hanem tetszőleges problémára nem létezik.

De láttam. Miben is különbözik az enyémtől?
Már azon kívül, hogy van benne egy brake és emiatt kicsit elegánsabb a rendezés?
Ugyanaz az ötlet, ugyanúgy O(M^2). (Szemben a tömbös O(N+M)-jével.)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Igazad van, majdnem ugyanaz a kettő, én nem láttam a tiédet.
Az enyém kicsit gyorsabb ;-), legjobb esetben O(M) alatt fut le, legrosszabban O(M^2). Általában a kettő között félúton.

Akkor most már ide vehetjük a Te megoldásodat is. Szerintem az is egy jó általános megoldás, ahol a paraméterek átírhatók. Általában talán lassabb, mint a tömbös, de sokkal kisebb a memória szükséglete.

Nem érdemes legjobb meg legrosszabb esetet nézni. Ez egy O(M^2)-es algoritmus. Ebből következik, hogy akkor jó, ha M<<N.

N=90 és M=5 esetén a tömbös valószínűleg gyorsabb.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

"N=90 és M=5 esetén a tömbös valószínűleg gyorsabb."
Arra könnyű kiszámolni! :-)

Tömbös:
5 véletlen szám generálás
105 értékadás

Enyém (legrosszabb esetben):
5 véletlen szám generálás
15 feltétel vizsgálat
20 érték adás

Tehát az enyém gyorsabb és még sorba is rendezte.

Szerk.: egyébként érdemes legjobb, legrosszabb és várható (átlagos) esetet is nézni.

Így darabra. De futásidőben?

Merthogy a 105-ös értékadás (ami egyébként több, de mindegy) nagy része a tömb értékadása, ami viszont irtó könnyen optimalizálható a fordító által, predikálható a CPU által, se cache miss, se semmi, brutál gyors.

Az intervallumos alg. viszont kevesebb műveletet végez ugyan, de ezekről ez nem mondható el.

Mond már el mi az a legjobb eset, amikor kijön az M-es futásidő...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

"Az intervallumos alg. viszont kevesebb műveletet végez ugyan, de ezekről ez nem mondható el."

Melyik utasítás sokkal lassabb szerinted? Ezekről van szó: 


if (lotto[j] <= idx)
idx++;
lotto[k] = lotto[k-1];
lotto[j] = idx;

Ha találsz olyat, akkor azt is írd le, hogy melyik processzoron! ;-)

A legjobb eset, amikor egyre kisebb számokat generál a véletlen szám generátor. Ilyenkor nem kell végig menni a korábban generáltak listáján.
A legrosszabb, amikor egyre nagyobbakat generál, ilyenkor mindig végig kell menni az összes korábbin.

Ráadásul láncolt listával még ennyi utasítás sem kell, mivel beszúráskor nem kell a tömb elemeit odébb mozgatni.

Szerk.: Illetve tömb esetén a memcpy használatával további gyorsítás érhető el.

"Melyik utasítás sokkal lassabb szerinted?"
Egyik ciklus sem értelmesen unrolling-olható, az első meg kifejezetten rosszul predikálható.
De hajrá, hasonlítsd össze a kettőt, kíváncsi vagyok melyik lesz gyorsabb.

"A legjobb eset, amikor egyre kisebb számokat generál a véletlen szám generátor. Ilyenkor nem kell végig menni a korábban generáltak listáján."
Viszont a rendezés miatt az összes eddigi elemet arrébb kell rakni.

Azaz még a legjobb esetben is O(M^2)-es ez az algoritmus.

Listával persze nem. De azt tartom, hogy semmi értelme legjobb esetet nézni, ha az ilyen ritka, és az átlagos és a legrosszabb eset is O(M^2).

"Illetve tömb esetén a memcpy használatával további gyorsítás érhető el."
Szerintem nem kaphat a memcpy átfedő src és dst memóriaterületet, de FIXME.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Miről is beszélünk akkor? Az eredeti algoritmus gyakorlatilag ugyanazt csinálja, mintha tömbünk lenne, csak tömb nélkül. De ugyanakkora a helyfoglalása, mindene ugyanakkora. Tehát gyakorlatilag egyenértékű a halmazos-keresőfás megoldással, csak ez utóbbi gyorsabb, de ugyanannyi fals randomot ad. Tehát megoldja a feladatot, és kit érdekel, ha nem optimális ott, ahol nem számít, mert halál mindegy, hogy a lottószámokat 0.0001 vagy 0.001 másodperc alatt húzza ki? Programozó ideje: ha a programozó 2 perc alatt összedob egy halál primitív, tömbös megoldást, ami esetleg, 0 valószínűséggel végtelen ideig fut akkor az JÓ megoldás. Olcsó volt. Ha a programozó kicsit gondolkodik, 10 perc alatt összedob egy megoldást, ami biztosan nem fut végtelen ideig, az ugyan jó megoldás, de 5x annyiba került, mint az eredeti, nehezebben karbantartható, nehezebben olvasható.
Csak azt szeretném mondani, hogy sokkal fontosabb szempontok is vannak az életben, iparban mint az elméleti hibátlanság, főleg, ha a gyakorlati hibátlanság megvan. Mennyi a valószínűsége egy 0 valószínűségű eseménynek? Előbb fog felrobbanni a processzorod, minthogy egy ilyen algoritmus túl sokáig fusson.
----
Hülye pelikán

Nem tudom, nálatok mi a helyzet.
Jó pár olyan megoldást láttam, volt, hogy csináltam is, ami a "jaj, gyorsan üssünk össze egy dirty-hacket, jó lesz az, hamar, hamar!" kategóriába tartozott. Gondolkoznom kellene azon, volt-e köztük olyan, ami később nem ütött vissza...

KisKresz

Eltolod a dolgot. Itt nem arról van szó, hogy van egy probléma, van rá egy szép megoldás, de gyorsan összeütünk egy hekket. (pedig finom az a hekk) Arról van szó, hogy van egy probléma, amire adódik magától egy megoldás, ami naív abból a szemszögből, hogy lehetséges végtelen futása. Gyakorlatilag ilyen nem fordul elő, tehát a triviális megoldás egyben jó megoldás is, és az a hülye, aki ennél több időt szentel rá.
----
Hülye pelikán

90-ből 89-et húzni ekvivalens a 90-ből 1-et húzni problémával (azt sorsoljuk amit végül nem választunk.)

A legütközésveszélyesebb így valójában a 90-ből 45 húzás lesz.

Ez alapján: http://en.wikipedia.org/wiki/Coupon_collector's_problem

Csak 45 számra felírva:

E(T) = 90 * (harmonicnum(90) - harmonicnum(44)) = 63.88

Azaz várható értékben csak 64 számot kell kisorsolni ahhoz, hogy 45 különböző legyen közte.

A vita már rég nem arról szól, hogy az eredeti lottóhúzásos feladatnak mi a legszebb megoldása. A vita arról szól, hogy élből elvetsz egy megoldást, mert 0 valószínűséggel végtelen ideig futhat.

Mivel más is felvetette, hogy azért sem jó ez a megoldás, mert mi van, ha több mint 5-6 számot kell húzni, most én is csavarok egyet rajta:

Feladat:
Véletlenszerűen válasszunk két különböző számot a 0..2^32-1 intervallumból. (Minden számpár azonos valószínűségű kell legyen.)

Várom az egyszerű, minden esetben véges futásidejű megoldásokat.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

A vita mindig is arról az algoritmusról szólt (részemről legalábbis), amit fentebb írt valaki a lottó húzásra. Kár, hogy mindenki más elkezdett belemagyarázni mindenfélét. Egyébként meg miért is kellene kihúzni többet 5-6 számnál. A feladat világos. Pontosan 5 vagy pontosan 6 szám, lottó típustól függően, ismétlés nélkül. Erre a konkrét feladatra kell algoritmust adni, nem pedig mindenféle kreálmányokra, hogy mi történik, ha jön a meteor és mi van, ha hardver hiba lép fel vagy mi van ha a 0..2^32-1 intervallumból.

A végtelen ciklus esetleges lehetősége meg távol áll a szépségtől. Alapvetően hibás, ha engedi bekövetkezni egy olyan konkrét esetben, amikor abszolút nem lenne szabad bekövetkeznie. Úgyhogy ne csavargass, hanem az eredeti feladatra és az arra adott algoritmusra koncentrálj.

Óbakker, ne már. Akkor nézd végig, hogy az én hozzászólásom miből indult és az a hozzászólás miből indult és így tovább, míg oda nem jutsz az első hozzászóláshoz. Az hogy egyeseknek nehézkes kontextust értelmezni, az nem az én problémám. Nem önálló kijelentést tettem, hanem választ egy válaszra, ami meg más valaminek a válasza. Attól nem lesz külön szál, hogy én azt mondjuk a válasz válaszának válaszára tettem. Ha te ott meg elvágod, mert úgy érzed, hogy úgy a jó, akkor az megint nem az én problémám.

Vagy ezt "A végtelen ciklus 0 valószínűségű esemény" meg úgy értelmezed, hogy mindig 0? Mert akkor while(true) aztán kész is vagyunk az ellenpéldával.

hogy élből elvetsz egy megoldást, mert 0 valószínűséggel végtelen ideig futhat.
Nem. Élből elvetek egy olyan megoldást, aminél bizonyítottan létezik jobb algoritmus, ahol a végtelen ciklus algoritmusból bekövetkező lehetősége konkrétan kizárt.

Az inkább a sokkolóan megdöbbentő, hogy van aki nem így tesz. És továbbra is köti az ebet a karóhoz, hogy a másik is jó megoldás erre a konkrét esetre, bár ugyan lehet van egy kis hibája, de ha szemet húnyunk fölötte, akkor azért úgy már nem problémás.

Jelen pillanatban nem lehet mérlegelési kérdés, hogy egy ötös vagy hatos lottó esetén mennyire elfogadható egy esetleges végtelen ciklus kialakulásának lehetősége.
Van olyan helyzet, amikor esetleg mérlegelhető, de ez nagyon nem az.

Akkor ne tárold le a 90-es tömböt, teljes mértékben rajtad áll, hogy milyen algoritmust használsz. De azt nem tartom érvnek, hogy azért vetsz el egy megoldást, mert az tökéletesen modellezi a való világ eseményeit, még akkor is, ha letárol mondjuk 90 elemet hozzá.
Ha ugyanezt meg tudod tenni más algoritmussal is, akkor az szuper, végre valami, erről van szó, ezt már szeretjük, a kreativitás a lényeg. De az, hogy lemodellezed a való világot plusz még egy kicsit (=végtelen ciklus), az számomra nem elfogadható. Ha a való világban ennél az egyszerű problémának a megoldásánál nem fordul elő végtelen ciklus soha, akkor nehezen tudom bevenni, hogy az algoritmikusan nem modellezhető ugyanolyan jól. Nem közel jól, hanem pontosan ugyanolyan jól. Természetesen könnyen lehetnek olyan összetettebb problémák, amik nem modellezhetőek tökéletesen, akkor majd kötünk kompromisszumot, hogy esetlegesen más is történhet és az milyen gyakorisággal. De egy ötös vagy hatos lottó húzásban nincs helye kompromisszumnak.

nem kell tomb.

az elso szam: a1 =random (90)
a masodik szam: a2 = random (89), es ha a2>=a1 akkor a2++
a harmadik szam: a3 = random (88), -> itt mar bonyolodik:
a1-et es a2-t nagysag szerint rendezem:
ha (a3>=a1) es (a3
ha (a3>=a2-1) akkor a3=a3+2

a negyedik szam: a4 = random (87)... es meg jobban bonyolodik :)

viszont nincsenek tombben a szamok..., sot nem hasznalunk semmilyen bonyolult matematikai dolgot (talan a rendezes ilyen, de az is megoldhato maskeppen). Valamint veges is, es meteorbiztos.

amugy meg persze hogy nem elegans, viszont lehet irni egy programot ami kigeneral egy ilyen programot tetszoleges szamokra :)
Inkabb csak azon gondolkoztam el, hogy tenyleg hogy megoldhato minimalista hozzaallassal.

szerk: most latom hogy a lap vegen egy hasonlo algoritmus tunt fel, de foloslegesen van ciklusokkal bonyolitva
(amugy nem :) )

Ezt mondjuk nem érzem C kódnak de sebaj. :)

Pont erre az ötletre jutottam magam is, most próbálom kiterjeszteni lottóhúzásra, de valahogy kezdi elveszteni az eleganciáját. :)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Több számnál sorrendezett listába célszerű beilleszteni az új elemeket, amiket mindig egyel kisebb modulóval generálsz. Ez O(log) nagyságrend a keresésre, O(1) a beillesztésre számonként.
Majd a végén minden számhoz hozzáadni a listában elfoglalt pozíciójának indexét (0-tól kezdve)

Nyilván.

Én szerettem volna megúszni a rendezést, de úgy szörnyű lett.

Erre jutottam.

"Majd a végén minden számhoz hozzáadni a listában elfoglalt pozíciójának indexét (0-tól kezdve)"
Ez viszont jó ötlet... lenne, de azt hiszem nem helyes. Pl az első szám legyen a 90-es. Upsz.
(Nem a végén kell, hanem minden szám kihúzása után.)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Az első random szám a 90-es. Ha berakod egy rendezett listába, akkor mindig az utolsó marad. Ha tehát a végén adod hozzá a pozíciót, akkor 94 lesz belőle.

Minden szám kihúzása/generálása után csak az aktuális számhoz kell hozzáadni a pozícióját. Közben vigyázni kell, mert a növelés miatt hátrébb kerülhet a listában.
Félek a lista itt már bezavar.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Ha jól értem, az a lényeg, hogy ha kihúztál egy számot, akkor "kiveszed", és a tőle jobbra levőket eltolod eggyel balra, hogy megszűnjön a rés; ennek kompenzálására vezetsz be egy indexfüggvényt, hogy a további húzásoknál meg tudd állapítani, hogy melyik pozícióban melyik golyó van.

Hátránya, hogy az indexfüggvény minden húzásnál kicsit bonyolultabb lesz, mert minden húzás bevezet az indexfüggvénybe egy újabb intervallum-vizsgálatot. Ez viszont nem vészes, és a műveletigénye egyértelműen kiszámolható, véges érték, ami csak a húzások számától függ. Ráadásul könnyen megérthető, implementálható és tesztelhető.

Amit fentebb valaki nem vett figyelembe, az az volt, hogy minden lépésben eggyel csökkenő intervallumból kell a golyót húzni, pl. a 3. golyót az 1..88 intervallumból. Ha ezt elfelejted, akkor kaphatsz 92-t meg ilyesmit.

tfh. 64 bites (vagy több, a lényeg hogy a (2^32-1) maradék már kb. egyenletesnek számítson) változóink vannak:

i1 = rand64() % 2^32;
i2 = (i1 + (rand64() % (2^32-1)) + 1) % 2^32;

Átrendezéssel biztos le lehet írni egyszerűbben, a lényeg, hogy i1-hez max. (2^32-1) és min. 1-et hozzáadva (és ennek utolsó 32 bitjét véve, vagy ha i2 eleve 32 bites akkor automatikusan túlcsordul az igényeink szerint): i2 mindent felvehet egyenletesen kivéve i1-et

Nyertem? ;)

szerk: megelőztek :(

Remek, de rögtön azzal kezdődik az egész, hogy: "designed by", ami szerintem előre vetíti a szándékoltságot.
A fenti példa viszont, ha szándékoltan designed by, akkor rögtön hozzá kell tenni, hogy very poorly, ugyanis egy gyengesége (végtelen ciklus) biztos van és abszolút nem kívánatos hatás.

Való igaz, kiváló példa az UUID v4, rosszul fogalmaztam meg a mondanivalómat.

Helyesen így lett volna:
Nehezen tudnék elképzelni olyan esetet ebben az esetben, amikor valamilyen algoritmikus hiba elképesztően kicsiny bekövetkezésének valószínűsége elfogadhatóvá tenné magát az algoritmust.

Ez az összes többi esetben is előfordulhat. A fenti példánál viszont nem feltételezve ilyen hibás hardver működést, akkor is előállhat a végtelen ciklus. Tegyünk már különbséget a hardverben bekövetkezett hibás működés és a hibás algoritmus között.
Most komolyan, ennyire nehéz észrevenni, hogy a fent definiált algoritmus önmagában hordozza a végtelen ciklus kialakulásának lehetőségét mindenféle hardver hiba nélkül is?

És ez miért is jobb annál az algoritmusnál, amikor kizárható a végtelen ciklus? A fenti algoritmus csak abban az esetben lenne elfogadható, ha belátható, hogy nincs olyan másik megoldás, ami ugyanarra az eredményre vezet és nem hordoz önmagában nem kívánt kimenetelt.

az eddig felsorolt algoritmusoknal azert, mert nem hasznal olyan utasitasokat amelyeket a temanyito meg nem tanult az iskolaban (tombot vagy egyeb adatstrukturat pl.), konnyen atlathato es egyszeru.

annyiban meg rosszbb, hogy van ra vegtelenul kicsi (kozelit a nullahoz, gyakorlatilag elhanyagolhato) esely, hogy vegtelenul sokaig fog tartani.

persze van meg jobb algoritmus, amely:
- csak veletlenszam-generalast, osszehasonlitast, ertekadast es alap matematikai muveleteket hasznal
- ugyanakkor veges

csak eppen ha jol latom meg nem irta ide senki.

Az nem mentség, hogy valaki nem ismeri/nem tanulta. Ez így ebben a formában nem ad minden esetben véges megoldást egy deklaráltan véges kérdésre. Egy deklaráltan véges kérdésre pedig csak és kizárólag egy deklaráltan véges megoldással adható adekvát válasz. Aminél előfordulhat (és abszolúte lényegtelen, hogy mekkora valószínűséggel), hogy nem ad, az értelemszerűen nem tekinthető helyes megoldásnak.

Igen, most van nála jobb megoldás.

De egyébként simán beleférne ez a "lehetőség". Az, hogy 1000-nél többszöri próbálkozás kelljen annak vsz.-e pl. kisebb mint 1/10^950.

Ha a világ minden részecskéje külön-külön végig futtatna egy ilyen ciklust Planck-időnként egyszer, és tenné ezt mondjuk a világegyetem koránál 10^800-szor több ideig, akkor se látnál ilyet...

Mindentől függetlenül az összes lehetséges kimenetel közt van egy olyan, ami azt mondja, hogy ez bizony egy végtelen ciklus. Az meg, hogy melyik hat számot generálta véletlenszerűen, annak nincs hatása arra, hogy következőnek melyik hatot fogja, így akár az is előfordulhat, hogy mindig lesz azonos szám a generáltak közt.
És amíg található olyan algoritmus, ami kizárja a kimenetelek közt a végtelen ciklus lehetőségét, addig nem tudom elfogadni ezt a lehetőséget, mint opció.

Volt már olyan, hogy valahová autóval mentél ahová vonattal is lehetett volna?

Ha igen, akkor hogyan fogadtad el, hogy MÉRHETŐ különbség van a két UGYANOLYAN EREDMÉNYRE vezető eszköz baleseti kockázatában?

Ez esetben az életedről volt szó.
Annál elhanyagolsz ilyen 1/10^6 nagyságrendű valószínűségkülönbségeket?

Akkor lenne reális a példa, hogy ha azt mondanád, hogy ha vonattal mész, akkor soha nem halsz meg (=nincs végtelen ciklus), de ha autóval, akkor esetlegesen előfordulhat, hogy meghalsz (=végtelen ciklus). Ha a cél az, hogy semmiképp ne következhessen be halál, akkor a vonat az egyértelmű választás, akkor is ha kocsival elenyészően kevés a halálos kimenetel. Azért, mert a vonattal való halálozás pontosan 0-val tér el a 0-tól, míg a másik esetben akármilyen alacsony is ez az eltérés, 0-nál biztosan nagyobb. Tekintsünk el a "hardver" hibáktól, nem ez a tárgy, tehát a sín, az úttest, mind-mind ideális, a körülmények adottak, hogy A-ból B-be jussunk.

Nem pedig olyan módon értékeljük, hogy jaj, de hát úgysem halsz meg egyiknél se. Van egy esetünk, amikor ideális körülmények közt (nincs hardver hiba) nincs végtelen ciklus és van egy, ami hasonlóan ideális körülmények közt produkálhat végtelen ciklust. Ez van a mérleg két serpenyőjében. Természetesen visszarakhatnánk a mindkét serpenyőbe a hardver hibákat, de ha mindkettőben ugyanaz a hardver hiba van, akkor akár ki is hagyhatjuk, a mérést érdemben nem befolyásolja.

"Ha egy esemény nem lehetetlen, akkor azzal számolni illik és kell is."
Most akkor kell szamolni hardverhibaval, vagy nem? Ertem en, hogy mire gondolsz (lasd random sort worst-case futasideje), de ettol meg az algoritmus nem hibas, csak elfordulhat, hogy vegtelen ciklusba kerul. 0 valoszinuseggel. Ez az algoritmus nem hibas, csak van egy ismert gyenge pontja. A ket dolog nem ugyanaz. Ilyen erovel genetikus algoritmust, barmifele heurisztikat is tilos hasznalni a gondolkodasod szerint. Vagy barmilyen olyan eljarast, amelyrol nem tudhato biztosan, hogy vegeter-e. Vagy hash-fuggvenyeket se, hiszen elmeleti lehetoseg megvan a kulcsutkozesre, igy a modern hitelesitesi eljarasokat is dobjuk a francba. Szep dolog az elmelet, de csak akkor, ha gyakorlatban is alkalmazzak.

Egy minden esetben véget érő algoritmust hasonlítunk össze egy olyan algoritmussal, aminél van olyan eset, amikor nem ér véget. Mindkettő véletlenszerű számokon dolgozik és mindkettőnek az a feladata, hogy 6 különböző számot kiválasszon véletlenszerűen. Az egyik minden esetben terminál, a másik meg nem. Nekem úgy tűnik, hogy ez utóbbi hibás. Egy ilyen lottóhúzós eseménynél pedig alapvető feltétel a mindig terminálás. Ugyanis az, hogy adj 6 véletlenszerűen generált különböző számot, az magában foglalja, hogy szeretnék a végén 6 számot látni, ergo termináljon a program minden körülmények közt.

A feladat egy igen egyszerűnek induló lottó program volt, amivel 5-ös illetve 6-os lottó játszható.
A kiírásból kristály tisztán kiolvasható, hogy a végtelen ciklus nem fogja kielégíteni a lottó játszhatóságának fogalmát, így az hibásnak tekinthető a feladat megoldásának szempontjából.

"Egy minden esetben véget érő algoritmust hasonlítunk össze egy olyan algoritmussal, aminél van olyan eset, amikor nem ér véget."

De mit is jelent az, hogy ez az algoritmus vegtelen?
Minel tovabb fut, annal kisebb az esely arra, hogy ne alljon le.
Ahogy a futasi ido novekszik, az esely csokken.
Ha a futasi idot vegtelenre noveljuk (=veget nem ero algoritmus), az esely a hibara nullara csokken.

vagy nem? :)

Eredetileg nem akartam belefolyni a vitába, de kezdenek egyre hajmeresztőbb dolgok előkerülni. Az hogy pont neked írom, csak lustaságból teszem, mert nincs kedvem összevadászni egyesével, hogy ki mit írt. :)

Idézet: A végtelen ciklus 0 valószínűségű esemény.(de nem lehetetlen esemény persze)

Definíció szerint lehetetlen eseménynek nevezzük azon eseményeket, amelyek valószínűsége 0.

Azt hiszem abba keveredtetek bele, hogy két különböző dolog folyik össze ebben a témában. Az egyik, hogy az algoritmus véget ér-e, a másik pedig az, hogy mikor.

1. Ha a véletlenszám-generátor megfelelő tulajdonságú, akkor annak a valószínűsége, hogy nem tud 5 különböző lottószámot előállítani véges sok lépésben - azaz a ciklus végtelen ideig fut - pontosan 0, azaz lehetetlen esemény. Másképpen: 1 valószínűséggel befejeződik véges sok lépésben. Tehát nem kell aggódnunk a végtelen ciklus miatt. DE:

2. Tetszőleges n nemnegatív egészre P("nincs meg az 5 lottószám n lépésben") > 0, vagyis a lépésszámnak nincs felső korlátja. Más szóval, hiába tudjuk, hogy véges az algoritmus, akármilyen nagy lépésszám elképzelhető.

Alapvetően egyetlen generált szám sem befolyásolja a következő generált számot, sem a generált ötösöket, így az is előfordulhat, hogy mindig ugyanaz a szám jön ki, vagy pedig minden egyes ötösben lesz azonos szám, semmi nem zárja ki a létezését a fenti algoritmusban.

Ha 10x fejet dobtunk egymás után, akkor ugyanúgy semmi nem zárja ki, hogy a 11. ne fej legyen és azt se, hogy a 12. is és így tovább a végtelenségig. Akkor se, ha a gyakorlatban szinte lehetetlenség ilyet produkálni (mert a statisztika azt mutatja, hogy úgyis lesz írás egy véges idő után).

Nem kell aggódni, ehh. Mintha azt mondanád egy bankban, hogy a te algoritmusod elenyészően kevés esetben fogja csak másnak utalni a pénzt, mint kellene. De persze azt tudjuk, hogy algoritmikusan lehet olyan csillagzat, hogy mégis másnak megy a pénz. Még mindig nem beszélünk semmilyen hardver hibáról, csak és kizárólag magáról az algoritmusról. Szerinted mit szólnának hozzá? Sebaj, jó ez így?

Azt hiszem, hogy vagy nem olvastad a 2. pontot, vagy nem értetted az 1. pontban az iróniát. Arról szólt a dolog, hogy a valószínűségszámítás szerint az algoritmus befejeződik, viszont lehet, hogy futás közben a Nap elhasználja az üzemanyagát, vörös óriássá változik, és bekebelezi a Naprendszert, ami megnehezíti a témaindító srác számára a házi feladat bemutatását. Reméltem, kiderül, hogy mennyire rossznak találom az ilyen megoldásokat, különösen azért, mert nagyon sokszor tesztelve is produkálhat nagyon gyors eredményt, és csak hónapok / évek múlva szívja meg vele valaki.

A fej vagy írás témát én megkérdeztem annak idején a gyakorlatvezetőtől az egyetemen. Azt mondta, hogy matematikailag ez jön ki és kész, de úgysem lehet a gyakorlatban ellenőrizni, szóval kopjak le. :)

Ami zavaro ebben a kerdesben, az a vegtelen fogalma.
Kicsit olyan ez a vita, mint arrol vitatkozni hogy akkor most az (1/x) erteke a vegtelenben 0 vagy nem nulla - mikozben igazabol a kerdes ertelmetlen (nem hiaba talaltak ki a haterertek-szamitast, hogy legyen erre a problemara normalis matematikai apparatus), es valamilyen formaban ("a vegtelenben" definiciojatol fuggoen) mindket valasz igaz :)

nem értetted az 1. pontban az iróniát
Vagy nem tudod kifejezni az iróniát, de nyilvánvalóan ezt az opciót vessük is el rögtön, mert akkor nem mondhatnád, hogy én nem értettem. Sajnos az sem derült ki, hogy mennyire rossznak találod az ilyen megoldásokat. De ez is az én hibám, biztos megint nem úgy értettem, ahogy a fejedben hangzott, mielőtt leírtad.

Ok. Arra gondoltam, hogy nyilvánvaló, mennyire rossz az olyan algoritmus, ami ugyan 1 valószínűséggel befejeződik, de a felső korlát hiánya miatt akár évmilliárdokig is futhat, semmi nem zárja ki. Másodszor a Naprendszeres dologgal is a futásidőre céloztam, nem valamilyen katasztrófa bekövetkezésére. De mivel ezt a részt már törölted, gondolom közben rájöttél. :)

Azért legközelebb igyekszem pontosan fogalmazni, főleg mivel a fórumindító srác egy kezdő kérdést tett fel, ilyenkor meg inkább világos válaszok kellenek, nem utalások.

De mivel ezt a részt már törölted, gondolom közben rájöttél. :)
Nem, egyszerűen csak meguntam a hülyeséget. Meteor, Nap bekebelezi a Földet, hadverhiba és tök tudja még mi, el sem hiszem. Most komolyan, amikor valaki algoritmust ír, akkor épít arra, hogy meteor csapódik az arcába?

A lehetetlen eseményt meg szokás különböztetni a 0 valószínűségű eseménytől (ami nem feltétlenül lehetetlen).

A wikipedia http://en.wikipedia.org/wiki/Probability oldaláról:
"An impossible event has a probability of 0, and a certain event has a probability of 1. However, the converses are not always true: probability 0 events are not always impossible, nor probability 1 events certain. The rather subtle distinction between "certain" and "probability 1" is treated at greater length in the article on "almost surely"."

Például 0-1 között bármely konkrét valós szám kiválasztása egyenletes eloszlás esetén 0 valószínűségű, de nem lehetetlen. Bármely szám kiválasztása lehetséges...

Intervallumon kívüli számot választani, vagy egy kék golyókkal teli urnából piros golyót húzni viszont lehetetlen.

Ha tudtam volna, hogy ekkora althreadet inditok el :)

Az en eredeti problemam a "programozasi habit". Ha egy programozo megszokja, hogy nem kell vele foglalkozni, mert feltesszuk, hogy sose kovetkezik be, akkor elobb utobb elkezdenek szaporodni az ilyen funkciok es parameterek a programban. (Ezt a funkciot amugy sem hivjuk meg negativ ertekkel. Ebben az adatbazis mezoben ugysem szerepel 10-nel hosszabb keresztnev ... ugye ismeros? :) )

A problema alapvetoen az, hogy implicit tudasra tamaszkodik az algoritmus, ami a rendszer szempontjabol veszelyes lehet. Ha a program engedi a nem kezelt agakat, akkor elobb utobb eler az alkalmazas arra a pontra, hogy a fene tudja, hogy miert mukodik, ha mukodik.

Ami miatt en kikeltem a lottos program random 5 szam kapcsan az ugyanaz, amit az egyetemen tanitanak: sosem bizunk a bejovo/random adatokban.

fene tudja, hogy miert mukodik, ha mukodik.
Illetve a még veszélyesebb, hogy a fene tudja most éppen miért nem és nem is nagyon lehet reprodukálni.

A programozás meg egyelőre még nem feltételezéseken alapszik, szerintem.

Amúgy itt sem bízik a bejövő adatban (jelenleg véletlenszám generátor állítja elő az input adatokat), mert benne van az ellenőrzés, hogy hasonlítsa össze őket mielőtt bármit is tenne velük. Ha az ellenőrzés sikertelen, akkor újabb input adatot kér.

Nekem csak annyi a furcsa, hogy páran leseprik az asztalról a kérdést, hogy olyan eset úgysem lesz, így abszolút nincs is semmi probléma.

Tanárként ez az a megoldás, amire biztosan elégtelent adnék. Code-officerként kivenném a repoból a kódot, és kérném a készítőjét, hogy gondolja át újra.
--
"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live." John F. Woods

( naszta v | 2010. 10. 11., h – 15:41 )


#include <algorithm>

int main()
{
int tomb[N];
// ... feltöltöd
std::sort(tomb,tomb+N);
int * last = std::unique(tomb,tomb+N);
// itt a last pointer az utolsó utáni elemre fog mutatni
}

--
http://www.naszta.hu

( mxr576 | 2010. 10. 12., k – 09:49 )

a sok gyors választ! Volt köztük jó néhány, amire sose gondoltam volna megoldásként, mégis nagyon jók. Valahogy azonban a saját kódomba is sikerült egy olyan while ciklust beleírni, ami kiszűri a dupla elemeket (legalábbis teszteléskor jó párszor megtette). A futtatási időre nincs statisztikám, de mivel nem sok számról beszélünk, ezért nem lehet olyan végtelenül hosszú a legrosszabb esetben sem. Mégegyszer köszönöm a segítségeket.

http://pastebin.com/Pxt7sZfv

A futtatási időre nincs statisztikám, de mivel nem sok számról beszélünk, ezért nem lehet olyan végtelenül hosszú a legrosszabb esetben sem.
A két dolog (nem sok számról beszélünk vs. nem lehet olyan végtelenül hosszú legrosszabb esetben sem) nem áll összefüggésben egymással.

Ez érdemi működést nem befolyásol, de a generate-nek átadott lotto paramétert semmire nem használod. Helyette inkább többször meghívod a metóduson belül a lotterytype(input)-ot, miközben pont annak eredménye van a lotto-ban.

Hopsz, nem neked akartam, hanem egy szinttel feljebb. Bocs. :)

Hát tervezési szempontból sokat lehetne fejleszteni...

Én pl. biztosan egy általános kombinacio(n,k) függvénnyel kezdeném, ami 1-n-ig tartó számokból választ k-t véletlenszerűen, amit egy k hosszúságú tömbben ad vissza.

És erre alapozva kéne aztán az ötös, hatos lottót (vagy akár kenot ill. bármi mást) megvalósítani...

Én még szándékosan nem akartam tervezésről beszélni, valószínűleg meghaladja a tananyag kereteit az ilyen gondolkodásmód. Mondjuk azért remélem, hogy nem főiskolai/egyetemi feladatról van szó. :)

De az mindenképpen szembeötlő, hogy átad egy olyan paramétert, amit semmire nem használ, helyette inkább újra és újra meghívja azt a metódust, ami már egyszer megmondta, hogy mennyi az annyi és átadta az eredményét.

Javaslom egyébként, hogy az algoritmusodat "játszd végig" papíron. Természetesen a random szám generátort is játszd el és nézd meg, hogy mi történik, ha mondjuk mindig ugyanazt a számot generálod. Vagy mondjuk csak 2x egymás után. Vagy csak elsőnek és utolsónak.
Nem túl bonyolult feladat szerintem és talán te is látod majd, hogy miért nem jó az amit írtál és esetleg hogy lehetne javítani rajta. Ha megtörtént a javítás, akkor meg megint eljátszod papíron és nézed, hogy mi az eredmény.

Miért inicializálod -1-el az n-et? Tömböt nem szokás -1-el indexelni, kivéve ha arra vagy kíváncsi hogy a tömb mekkora valószínűséggel van a program memóriájának határán.
Miért van szükség a z bevezetésére?
Mi van ha egyezés van, újragenerálod a számot, és az új szám egy kisebb n indexűvel válik egyenlővé? Az új szám generálásakor az összes alatta lévővel is össze kell vetni.

Szerk: Ja bocs, kicsit elkéstem ezzel a hozzászólással.Benéztem.

( bambano | 2010. 10. 13., sze – 00:11 )

ha és amennyiben pontosan a lottóhúzást kell szimulálni, akkor csak nekem furcsa, hogy tömböt akartok használni?

fogalmazzuk át kicsit a feladatot:
van egy listánk, amely sorszámozva van 1..n-ig. Példa kedvéért adott helyen élők címlistája. Ki kell választani z darab embert, mondjuk esküdtnek. Ehhez a kimenetre írandó z darab különböző egész szám 1..n intervallumból emelkedő számsorrendben. Ez n=90-re és z=5-re lottó.

Ehhez néhány skalár és egy O(n)-es ciklus elég. Sem tömb, sem range, sem bitmap, sem semmi ilyen komoly adatszerkezet nem kell.

ha és amennyiben pontosan a lottóhúzást kell szimulálni
Erről lehet szó. Kivéve, ha elmagyarázták neki a való életben tapasztalhatótól eltérő lottó húzási szabályokat. De amíg ilyet nem közöl velünk, addig nincs semmi ok feltételezni, hogy nem azt kell szimulálni.

Amúgy teljesen lényegtelen, hogy tömb vagy más adatszerkezet, hiszen a hardver hiba, a meteor és a Nap összeomlása úgyis megakadályozza majd, hogy bármit is használj. :)

( falu v | 2010. 10. 13., sze – 01:00 )

Én mondjuk csak ugatom C-t, és nem is tudom, hogy C-ben vannak-e dinamikus tömbök, de ha vannak, akkor én úgy csinálnám, hogy csinálnék egy dinamikus tömböt és úgy adnék hozzá random számokat, hogy vizsgálnám, hogy benne van-e már az adott szám a tömbben.
Pascalban valahogy így nézne ki: http://pastebin.com/kxbxAwnt

--
Falu.me | Tárhely

Ez nem C vs Pascal (dinamikus tömb) probléma. Ez algoritmikus probléma.
Azon problémáznak a fentebbi threadekben, hogy a random() nem biztos hogy - a jelen igények szempontjából - "eléggé" véletlen, emiatt elvileg előfordulhat, hogy amíg a programod fut, csak ugyanazt az egy számot adja ki - > végtelen ciklus. Függetlenül attól, hogy pascal vagy c.
A fentiek enyhébb következménye: A te programod futásideje nem határozható meg. Az, amelyik feltölt egy 90-es tömböt, és a maradékból választ véletlenszerűen indexet, pedig fix iterációs számmal rendelkezik, függetlenül a véletlenszámságtól.
(Az mondjuk érdekes felvetés, hogy mi a jobb, akkor ha a lottósorsoláskor egy adott (hibás) futási környezetben mindig pl: 1, 2, 3, 4, 5-öt sorsol, vagy ha egyszer végtelen ciklusba kerül, és az első(?) futáskor kibukik, hogy állandóan ugyanazt a a számot adja (a hibás működés felderíthetőségének kérdése)...)

( tr3w v | 2010. 10. 13., sze – 12:57 )

Mivel egyeseknek szúrja a szemét a 0 valószínűséggel bekövetkező végtelen ciklus, engem viszont legalább ennyire zavar a 90-es tömb lefoglalása, gondoltam itt egy másik megoldás: 



  int nums[5];

  for (int i=0;i<5;++i)
  {
     nums[i]=rand()%(90-i)+1;

     for (int j=0;j<i;++j)
       if (nums[j]<=nums[i])
         ++nums[i];

     /* sort */
     for (int j=i-1;j>=0;--j)
       if (nums[j+1]<nums[j])
       {
         int t=nums[j];
         nums[j]=nums[j+1];
         nums[j+1]=t;
       }
  }

  for (int i=0;i<5;++i)
  printf("%d.: %d\n",i+1,nums[i]);

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Kivettem a rendezést és körétettem egy for (n=0;n<1e6;n++) ciklust, hogy meg tudjam nézni a húzott számok eloszlását. Úgy tűnik, hogy az utolsó húzásnál jelentősen kevesebbszer húzza ki a 90-est, mint kellene. Az átlagban is van eltérés a 45.5-től (az 1., 2. oszlopban több, a 3., 4., 5. oszlopban kevesebb) de azt hirtelen nem látom, hogy ez szignifikáns-e.

Nekem is pont ilyen dolog jött ki, de a rendezés nélkül. Ha jól látom, mindenképp összehasonlítod az új elemet az összes korábban kihúzottal a korrekcióhoz, így mindegy, hogy milyen sorrendben vannak. A TV-ben is csak kényelmi szempontok miatt rakják sorrendbe, nem része a feladatnak a "lefelé buborékoztatásos" rendezés.

Sajnos a rendezés kell, mert a szám amihez hasonlítod az előzőeket változhat.
Azaz amiatt, hogy 1-gyel megnöveled a számot, átkerülhet másik intervallumba. Hogy ez ne okozzon galibát, kell a rendezés.

(Pl első szám 5, második 2. Most sorsoltunk egy 4-est. Nézd meg a te kódod mit csinál.)

Először én is rendezés nélkül próbáltam. Nem állítom, hogy lehetetlen, de nekem nem jött ki szép eredmény.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Hát akkor ez bizony így nem lesz jó. A lottó húzásnál nem mondhatod azt, hogy a második húzásnál csak 1-89-ig választhatsz, mert én ott szeretném látni a 90-est is, ha az elsőnél esetleg még nem húzták ki. Az intervallum szűkítése nem elfogadható, mert az durva befolyásolás.
Ez még rosszabb megoldás így, mint a végtelen ciklusos.

Egyébként olyan meg nincs, hogy nem lehet húzni 86, 87, 88, 89 és 90-es számokat egymás után. Vagy a lottóban megoldható? Ha igen, akkor az algoritmusodnak is meg kell oldania.

Nem érted az algoritmust.
Azért történik még pár dolog a rand() hívás után. Okkal.

Az algoritmus kimenetként megengedi a 86,87,88,89,90-et.

(pl, ha a rand-os sor a 90,89,88,87,86 számokat adja vissza, ebben a sorrendben.
Vagy jó a 86,89,88,87,86 is. Ha ez utóbbit végigzongorázod, rájössz, hogyan működik.)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Ahogy a lottóban is lehetne, így itt is szeretnék mondjuk 90-est látni másodikra. Nem úgy, hogy te közben korrigálod a számokat valami módon. Ha a lottóban lehetséges, hogy minden egyes húzásnál az 1-90 intervallumból válasszon az ember, akkor baromira nem tetszik, hogy te ezt leszűkíted. Ez nem a valós világ modellezése. Ez a végeredmény modellezése. A valós világ szabályait tessék betartani. A lottó egyik szabálya, hogy minden körben 1-90 intervallumba eső számok közül húz az ember és a kihúzott golyót nem helyezik vissza. Nem pedig az, hogy a végén 1-től 90-ig számokat lássak. Ennek megfelelően én is 1-től 90-ig szeretnék minden körben húzogatni, nem pedig úgy, hogy a második körben csak 89-ből és majd valamit korrigálok, hogy 90-es szám is kijöjjön.

Na várjál, mert ez: "Az nem lehetséges, mert csak az első számot generálja az 1-90-ből a másodikat 1-89-ből és így tovább." alapján másodjára már nem húzhatom ki a 90-est, pedig mondjuk elsőre nem a 90-est húztam. Most akkor ki vesz ki mit és honnan, de legfőképp miért?

Jó az érzésed. A való életben is gyakran kell eldönteni, hogy memóriából vagy processzoridőből használunk-e többet.

Ha M számot kell húzni 1-N intervallumból, és N nagy és/vagy M<<N akkor akkor ez jobb, mint a tömbös megoldás.

Egészen pontosan az én verzióm futásideje O(M^2), a tömbösé O(N+M).

M=5 és N=90-re a tömbös valószínűleg gyorsabb.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

A kódot nézd.

Az első húzáskor ugyebár egyenletes eloszlású véletlen számot gyártunk 1 és 90 között.
Legyen ez mondjuk a 47.

A második húzáskor gyártunk egy véletlen számot 1 és 89 között - ezzel modellezzük, hogy már csak 89 golyó volt az urnában.
Ezután megnézzük, hogy a most húzott szám kisebb-e az elsőnél. Ha igen, nem bántjuk. Ha nem, akkor megnöveljük eggyel. Ez ekvivalens azzal, hogy a 0,90 intervallumból húztunk, amiből előzőleg kivettük az első számot.
Tfh másodjára a 89-et adta ki a véletlenszám-generátor. Nagyobb 47-nél? Igen. Megnöveljük eggyel: ott a 90, amit akartál.

Ugyanaz mint eddig, a maradék számok közül a 48. kell.
Az i. szám i, ha i<47
Az i. szám i+3, ha i>=47

Azaz a 48. szám az 51-es.

Ugyanez a a kódban:
Az eddigi számok tehát rendezve: 47, 48, 49

A középső ciklusban 47<=48, tehát a mostani számot növeljük eggyel: 49
Köv lépésben 48<=49 azaz megint növelünk: 50
Köv lépésben 49<=50 azaz megint növelünk: 51

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Ez eddig jó az ötlet, viszont nincs szükség szerintem a sorba rendezésre külön ciklusban. Az alábbi módon változtatnám meg a kódodat (rendezés rész ki, és helyben rendezés, mivel a j ciklus így is úgyis végig lépked 0-tól i-ig, és innét lehetne még tovább optimalizálni):

http://pastebin.com/WcrsETSr

(a "<" jelet idézőjelbe tettem az oldal miatt) 


int main(){

const int n = 90;
const int x = 5;

int nums[x];
int i, j, t, f;

  srand ( time(NULL) );

  for (i=0;i"<"x;++i)
  {
     nums[i]=rand()%(n-i)+1;

     f = 0;
     for (j=0;j"<"i;++j) {
       if (nums[j] "<"= nums[i]) {
         if (f == 0) ++nums[i];
       }
       else {
         f=1;
         t=nums[j];
         nums[j]=nums[i];
         nums[i]=t;
       }
     }

  }

  for (i=0;i"<"x;++i)
    printf("%d.: %d\n",i+1,nums[i]);

  return 0;
}

Na itt egy basic (nem hatékony) implementáció (a binomiálisokat azért memorizálja, szóval több húzás esetén csak egy várhatóan 5*45-ös ciklus lesz):

http://pastebin.com/ZdUKQ0bQ

De a matematikai szépsége a megoldásnak látszik:

csak egyszer kell random számot generálni

( Swifty v | 2010. 10. 13., sze – 16:31 )

Az én kódom:

int i;
int j;
int voltmar;
int tomb[5];
for(i=0;i<5;voltmar?i:i++){
voltmar=0;
tomb[i]=rand()%90+1;
for(j=0;j< i;j++)if(tomb[i]==tomb[j])voltmar++;
}

--
Debian Linux rulez... :D

Ezzel harlequin "megoldásához" hasonlóan egyeseknek az a gondjuk, hogy 0 valószínűséggel ugyan, de végtelen ideig futhat.

(Az, hogy várható értékben ez a leggyorsabb algoritmus az eddigiek közül őket nem hatja meg. :) )

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

A 0 valószínűség az biztos...
Gyakorlatilag nem mehet végtelen ciklusba... nem lehet, (hacsak nem sz*rik be a véletlen szám generátor...) hogy 90 szám közül ne lehessen 5 különbözőt találni...

Akkor menne végtelenbe, ha 90 közül 91 különbözőt szeretne a LUSER...
De ki is lehet próbálni... :D

--
Debian Linux rulez... :D

( taxy | 2010. 10. 13., sze – 16:59 )

Én egyszer így oldottam meg: 


for(i=0;i<90;i++)tomb[i]=i+1;
for(i=0;i<5;i++){
	int ri;

	ri=rand()%(90-i);
	eredmeny[i]=tomb[ri];

	for(j=ri; j<(90-i-1); j++)tomb[j]=tomb[j+1];
}

De a Fisher–Yates_shuffle tényleg gyorsabb.

Igaz, felesleges az összes elemet mozgatni: 


for(i=0;i<90;i++)tomb[i]=i+1;
for(i=0;i<5;i++){
	int ri;

	ri=rand()%(90-i);
	eredmeny[i]=tomb[ri];

	tomb[ri]=tomb[90-i-1];
}

:) Máris ott vagyok ahol a part szakad.
Szerk:
Ez akkor jó, az ismételgetős módszerrel szemben, ha az összes elemet véletlen sorrendebe rakjuk. Az ismételgetésnél mikor ki akarjuk venni az utolsó elemet akkor már csak 1/90 az esélyünk hogy beletalál a halmazba.

( enpassant v | 2010. 10. 13., sze – 18:13 )

Akkor álljon itt az én megoldásom is.
Húzás sorrendjében és emelkedő számsorrendben is kiírja: 


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

int main ()
{
	srand ( time(NULL) );
	int j, lotto[5];
	for (int i=0; i<5; ++i) {
		int idx = rand() % (90-i) + 1;
		for (j=0; j < i; ++j) {
			if (lotto[j] <= idx) idx++;
			else break;
		}
		for (int k=i; k>j; --k) {
			lotto[k] = lotto[k-1];
		}
		lotto[j] = idx;
		printf("%d ", idx);
	}
	printf("\n");
	for (int i=0; i<5; ++i) {
		printf("%d ", lotto[i]);
	}
}

( BaT | 2010. 10. 13., sze – 22:06 )

mondjuk még nincs manualja :) meg opciókezelése :) szégyellem... http://enyergija.hopto.org/hg/lotto/summary
a lényeg: ez pwgen jellegű tömeges lottószámgeneráláshoz van, hogy a rendszer entrópiatartalékait a lehető legjobban kihasználja
egy gyűrűben tárolja a lottószámokat, amit véletlen számmal "forgat" és ahol megáll azt egy rendezett listába rakja át a gyűrűből.
vissza rakja ezeket ha kész van
és lehet újra húzni
nem lehet 2x ugyanaz ebből kifolyólag.
sajna még nincs cli opciókezelés (ha kellett ikább újraforgattam más paraméterrekkel :) és manuál sem.
restellem
a kód licensze: ha nemm ttudsz magadtól ilyet, dögölj meg.
ha tudsz, akkor úgyis megírtad már magadnak ha kellett
public domain azoknak akiknek nincs szükségük rá. mindenki más előtt zárt
:D
tömbben van amúgy a gyűrű. hogy ha sok számra ki lenne terjesztve, malloc hegyek ne tördeljék a memóriám

( tomsolo | 2010. 10. 13., sze – 23:06 )

Le kell generálni egy tömbbe az összes lehetséges kombinációt majd megkérni a felhasználót gondoljon véletlenül egy számra 0 és 43 949 267 között. Természetesen ha kétszer ugyanarra a számra gondol akkor érte jön lány a kútból, és meglátogatja a tévéjén/monitorján keresztül :)

No rainbow, no sugar

( szemet | 2010. 10. 14., cs – 22:23 )

Összesítve, elérhető legjobb komplexitások n-ből m-húzva, Neumann architektúrán, talán nincs benne hiba:) :

1. tömbkeverés Fisher-Yates

O(n+min(m,n-m)) hosszútávon sok húzás O(min(m,n-m)) - hosszútávon kis n-re talán a legjobb

2. nem determinisztikus: ütközéskor új dobás. Várható értékben
hn - harmonic number function

O(n*(hn(n)-hn(n-min(m,n-m))) * log(min(m,n-m))) - dobások várható száma illetve azok beillesztése rendezett listába az ütközések detektálásához - legegyszerűbb naiv megoldás (főleg rendezett lista használata nélkül az), nagy n-re és kis m-re egészen versenyképes lehet

3. determinisztikus ütközésfeloldással

O(min(m,n-m)*log min(m,n-m)) - m v. n-m dobás illetve azok rendezett listába illesztése és közben ütközésfeloldás - ez talán a legjobb általános megoldás ami nagy n-re is működik

4. kombinatorikus számrendszer

O(n*min(m,n-m)) darab binomiális + O(n*log min(n,n-m)) sorsoláskor
az összeg második tagja érvényes hosszútávon (előre kiszámolt binomiálisok esetén) -
Nem szokványos, lassú és/vagy memóriaigényes de talán ez használja ki leg(jobban/takarékosabban) a rendelkezésre álló entrópiát.

5. legenerálni az összes kombinációt egy tömbbe, és választani egy véletlen elemet
O(binom(n,min(m,n-m))) + O(1)
O(1)-hez tart a hosszútávú költség
4-eshez hasonlóan takarékos az entrópiával, de rengeteg ramot igényel, a sebessége csak extrém sok sorsoláskor versenyképes

6. Ez még nem volt, de opció: minden számhoz generálunk egy véletlen kulcsot minél nagyobb intervallumból (pl. 64,128 bit), a legnagyobb kulcsokat kapott m számot választjuk ki
O(n*log(min(m,n-m))) - ha ütközés van a kulcsok között az pontatlanságot okoz, de kellően nagy kulcsok esetén ez elhanyagolható szintre csökkenthető, ez is egy permutáció generálós megoldás de itt nem kell mind az n számot tárolni csak mindig a legnagyobb m-et

Van még?

Az ötös ponthoz - ha így van le írva - nem kell igazából elkészíteni az összes kombinációt mert ha valamilyen - visszakövethető - lineáris generálási módot - vagy módokból !* - választunk akkor elég a kvázi indexekből választani egyet és csak azt egyet legenerálni. :)

* Pl. az összes kombináció elméleti permutációja alapján már elég sok generálási módot lehet készíteni hogyan legyen elméletben felépítve a tömb.

No rainbow, no sugar

Na még egy extrém megoldás, remélem tetszeni fog ;)

Ugye a legtöbb megoldás m-től függ, és ha m közel van n/2-höz akkor nem hatékony. De ekkor lehet (talán) gyorsítani:
- legyen r() n bites random számot generáló függvény
- legyen x az m/n törtszám bináris felírása
pl 0.011100...
a 0-ra "bináris és" az egyre "bináris vagy" műveletet végzünk a véletlen számokkal a következőképpen zárójelezve (a példaszámmal):
r()&( r()|( r()|( r()|( r()&( r()| ... r())))))...)

Ez olyan n bites véletlen bináris számhoz tart rohamosan, aminek minden bitje m/n vsz.-el egyes és 1-m/n vsz.-szel 0

Kapunk tehát várható értékben m darab egyest tartalmazó n hosszú számot. Persze ez általában nem pont m hanem néhánnyal több vagy kevesebb egyest jelent, de ekkor már csak a különbséget kell véletlenszerűen törölni vagy hozzáadni azaz a sorsolandó m számot (ami ugye n/2 közeli) hatékonyan lecsökkentettük, így az m-től függő algoritmusok felgyorsíthatók....

Persze csak elméletben, mert nem hiszem hogy létezhet hatékony gyakorlati megvalósítása, különösen gép szóhosszánál nagyobb n-re (extrém vektorművelet támogatás esetén max)... ;)

Hát gondoltam bináris kereséssel beszúrjuk az új számokat a rendezett régiek közé. (ez a log-os rész)
És az így nyert pozícióját adjuk hozzá a számhoz ütközésfeloldásként (ettől esetleg még 1-2-t előrébb lép a rendezett listán de ezt talán csak konstans faktor).
Ez így nem lehetséges?

Ha rendezett lista alatt egy lista adatszerkezetet értesz, abba tudtommal nem tudsz log idő alatt elemet szúrni. Ha viszont fára gondolsz, ott nem tudod, hogy hányadik helyre szúrod. De még ha tudnád is, a szám változtatása miatt lehet, hogy hátrébb kéne rakni a listába, amiatt pedig újra növelni kéne, ami miatt lehet, hogy megint hátrébb kerül, stb.

Szerintem ez a lépés nem nagyon megy log alatt...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Képzelj el egy bináris keresőfát aminél minden elágazásban számon tartjuk a bal és jobb részfa méretét is.

Új elem beillesztésekor, ahogy haladunk lefelé a fában, amerre megyünk annak a részfának az adott elágazásbeli számlálójához mindig 1-et hozzáadunk, így a számlálókat pontosan tarthatjuk.
Közben ettől függetlenül valahányszor jobbra megyünk (a nagyobb számok felé) a bal részfa számlálójának ismeretében frissíthetünk egy idx változót amiben számon tartjuk hány elem van a beillesztettől balra.

Szerintem így a log idejű beillesztéssel együtt az indexet is megkaphatjuk. Persze kell itt azért még trükközni mert az, hogy a beillesztett elemet megnöveljük az indexszel nehezíti majd az update-et, de a log-os nagyságrendből emiatt nem törünk ki szerintem. (kis backtracing a beillesztés végén...)

Trükkös, de szerintem a backtrace miatt legalább még egy log-os tag bejön, szóval akkor is log^2.

Azt azért vegyük észre, hogy ez így nem egy kész algoritmus, úgyhogy max sejtésünk lehet, hogy lehetséges O(min(m,n-m)^2)-nál gyorsabban...

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

( szemet | 2010. 10. 19., k – 00:06 )

Na még egy rövid, ami ráadásul rendezetten írja ki a megoldást. Ebben van egy kis valszám trükközés, de minden ötös azonos vsz-el kerül kiválasztásra, aki akarja számolja végig ;) :

int m,i;
for(m=5,i=90;i>0;--i)
if(rand()%i<m){
printf("%d\n",91-i); --m;
}

Az ilyen feladatoknál talán nem a diploma számít, nem is feltétlen az aktuális tudás, hanem hogy az ember belekényelmesedik-e az általa ismert megoldásokba, vagy nyitott és kitartóan keres jobbat.

Itt sokan voltak a második, kereső csoportban, te pedig az elsőben, pedig van jobb megoldás annál amit ismertél:
http://hup.hu/node/93935#comment-1141043

Szóval én a helyedben senkit sem zrikálnék a thread többi hozzászólója közül...

Ezek szerint én nem rendes egyetemre jártam.
Sőt itt szemeten kívül senki, mert ő volt az első aki leírta. Ez ilyen egyszemélyes egyetem lehet.

Egyébként szerintem sokkal több reményre ad okot, hogy többen elgondolkoztunk a feladaton, mint az adott volna, hogy valaki emlékezetből beböfögi a megoldást.
Persze a mi oktatási rendszerünk ez utóbbit honorálja, de pont ettől szar.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

A feladatmegfogalmazasod nem teljesen jo. Ugyanis kulonbozo, ES veletlenszeruen kivalasztott szamokat kell keresni. Mindig a veletlennel van a gond, hogy mennyire jo veletlen. Nem az n db szambol kivalasztott k db kulonbozo szammal, hanem a veletlennel. Milyen eloszlasu valoszinusegi valtozoval irhato le a kapott szamotos?

ha rand % i kisebb mint 5, akkor csökken csak m értéke, egyébként lépked tovább az i-vel a ciklus, és így a maximális lefutás a for cikluson belül 90, nem pedig 5. lehet 5 is, ha éppen úgy jön ki, hogy az első talált 5 véletlen szám kisebb vagy egyenlő mint 5, és ekkor _jack_ által adott break kilépne, mert hogy meg van az 5 számunk. egyéb esetben nem.

Ez igaz, de én "vizsgálat" alatt az m vizsgálatát értettem, mert arról volt szó. Amit erdohegr írt, az a for ciklus leállási feltételét bővíti, így minden lépésben ellenőrizné m-et, pedig legtöbbször fölösleges. Amit én javasoltam, az az m-et csak akkor vizsgálja, ha változik az értéke. Tehát pontosan 5-ször.

erdohegr kiegészítésével ez is megoldódik, úgy látom. A megoldás igazi matekos megoldás, nagyon gyönyörű, csak mint a matekos megoldások általában, nem törődik az ilyen elfutó végekkel, hiszen ha m == 0 akkor úgysem csinál semmit, hadd fusson :D

szerk: mégsem jó. Mivel elvileg a választás szétoszlik az intervallumon, így átlag 1/k futásidőt tudunk csak megspórolni azzal, ráadásul plusz feltételellenőrzés. Nem tudom, matekos megoldás, nem ideális hatékonyságú de gyönyörű :D
----
Hülye pelikán

Ez így van, de ezesetben hacsak nem trükközöl a RAND_MAX-szal (vagy fordítva?), akkor ez minden esetben benne van. Viszont ha kiszámolod, hogy n hányszor van meg a RAND_MAX-ban akkor megkapod, hogy mennyit jelent ez az eltolódás. Nem sok. Én gyönyörű egyenletes eloszlást kaptam amikor kétezerszer futtattam egy 1-20 intervallumra a rand()-t (ez akkor volt, amikor a 20 oldaló kockámmal dobtam 2000-szer, és össze akartam hasonlítani a valódi véletlent a pszeudóval, és hát :D). Tehát elhanyagolható ez az eltérés, de igazad van.
----
Hülye pelikán

Random fv.:

#define K_A 16807
#define K_M 2147483647 /* Mersenne prime 2^31 -1 */
#define K_Q 127773 /* K_M div K_A */
#define K_R 2836 /* K_M mod K_A */

int Seed = 5; // vagy time() vagy akármi

double Random()
{
long hi, lo;
// Based on code in "Random Number Generators: Good Ones are Hard to Find,"
// by Stephen K. Park and Keith W. Miller in Communications of the ACM,
// 31, 10 (Oct. 1988) pp. 1192-1201.
// Borrowed from: Fuat C. Baran, Columbia University, 1988.

hi = Seed / K_Q;
lo = Seed % K_Q;
if ((Seed = K_A * lo - K_R * hi) <= 0)
{
Seed += K_M;
}

return static_cast(Seed)/K_M;
}

--
http://www.naszta.hu

Tényleg, bár ezzel a megoldással visszatérünk a sokak szemében (az enyémben nem) szálka módszerre: a nem determinisztikus lépésszámban befejeződő randomizált algoritmusokhoz ;)

(megkímélni a többieket a googletől: http://download.oracle.com/javase/6/docs/api/java/util/Random.html#next… )

szerk: És szerintem szebben és hatékonyabban is kivitelezhető ez az ötlet mint a Javaban történt, ennyi csak az egész:
int random_0tol_n_minusz_egyig(int n){
int kuszob=RAND_MAX-(RAND_MAX % n);
while((x=rand()) > kuszob) ;
return x%n;
}

szerk: na jó hatékonynak talán mégsem nevezhető a moduló használata miatt, ráadásul csak RAND_MAX/2-ig működik... :( Na jó feladom, nem akarok jobb lenni a javanál... ;)

ha jól értem, akkor elbeszéltek egymás mellett :)

tomaza szerintem arra gondolt, hogy az eredeti szám generátor nem pontosan annyi szám közül generál, mint a nekünk szükséges maximum, ezért a modulust generálva némely számok nem azonos valószínűséggel jelennek meg. ez utóbbi algoritmusban meg megint csak modulus-t használsz a max értékhez.

@ tomaza:
viszont szerintem ez nem küszöbölhető ki, mivel a random generátor adott (más kérdés hogy a 65535 nem-e egy 65536 modulus eredménye). mint feljebb is írták, ha van elég random bit, akkor ezek a különbségek elenyészőek.

De kiküszöbölhető, ha a futásidő nem determinisztikus. Pont ezt csinálja a java metódus is. Egyszerűsítve, egy konkrét példa:

Pl képzeld el hogy 0-10-ig akarsz generálni 4 random bitből:

1. random generálás
2. ha kisebb mint 10 elfogadjuk eredményként
3. ha nem: újra 1.

Az eloszlás tökéletesen egyenletes lesz (ez nem közelítés!). Cserébe viszont visszakapjuk a mások által kifogásolt nem korlátos maximális futásidőt.

Ironikus, hogy úgy tűnik egyelőre enélkül nem elképzelhető matematikailag tökéletesen korrekt megoldás...

Igen sima modulonál nem, de ami az én kódomban vagy a java kódban van:
a véletlen számot csak akkor fogadjuk el ha kisebb mint a modulus egy előre kiválasztott egész számú többszöröse, egyébként meg újat dobunk, akkor egyforma valószínűség lesz, hiszen a kiegyensúlyozatlanságot okozó eredménynél inkább ismétlünk

"Ironikus, hogy úgy tűnik egyelőre enélkül nem elképzelhető matematikailag tökéletesen korrekt megoldás..."
Teljesen determinisztikus, de nagy állapotterű gépeken amúgy sem tudsz valódi véletlent generálni, csak pszeudovéletlent. Determinisztikus gépen matematikailag tökéletesen korrekt véletlenszámot soha nem fogsz kapni. Elméletileg lehetetlen.

nem a véletlenről van szó hanem az "egyenletes eloszlásról" (igen, idézőjelben)
te is olvasd el amit linkelt ;P
(főleg a "The hedge..." bekezdést)

ps : tehát a lényeg hogy tökmindegy mennyire pseudóvéletlen vagy tökéletes véletlen, ha ezt úgy *használjuk*fel* hogy a kockadombásszimulátor 10-ből pontosan 9x 6-t dob a pseudovéletlnben és 99%-ban a valódi véletlen esetben

Ezért nem lesz valódi véletlen, mert nem egyenletes az eloszlása. pedig azt várnánk, hiszen a diszkrét intervallumból való véletlen választás nevezetes kísérlet, ugyanúgy, mint a szabályos kockadobásé, és ezen kísérlet eredménye valódi véletlen esetén egyenletes eloszlású. Ha nem egyenletes eloszlású a val.változó, akkor lehet, hogy mondjuk binomiális eloszlású. Vagy Poisson vagy más. De az megint más nevezetes véletlen kísérlet kimenete, így mást modellez. A valódi lottóhúzásnak megfelelő véletlen kísérletet hirtelen nem tudok mondani. Valszámtudorok segíthetnek.

szerintem félreérted még mindig (vagy persze én téged:) )

most azon túl van a vita hogy mennyire jó a véletlengenerátorunk (olyan amilyen), de ne rontsuk tovább, tehát pénzfeldobásnak az abs(rand()%3-1) érezhetően nem jó, függetlenül attól hogy a rand()mennyire jó véletlen, míg (mivel a rand-ban használt változó kettő hatvány) a rand()%2 *tökéletes* (tehát nem a véletlengenerátor tökéletes, hanem annak használata)

ja igen, a java-s megoldás is valószínűségben tökéletes csak, de ott már nem az eredmény esz elhanyagolhatóan kicsi valószínűségben hibás, hanem csak a futási idő lesz elhanyagolhatóan kicsivel több (és még az is csak bizonyos esetekben lesz kiemekedő), de az eredmény jó lesz

- nem beszélünk el, érti hogy mi a gond(om)
- olvasd el amit linkelt, elég tisztán le van írva és az algoritmus sem olyan bonyolult (egy képernyőnyi az egész a "nextLong" címszóig)
- másoknak is az elenyészőségre:

egyrészt egy c-s első zh kérdés ahol még éppenhogy vették a tömböket, szóval alapvető _programozás_ és _c_nyelvtudás_ zh kérdés ... szóval primitív

ha már 300. hsz-nál járunk akkor gondolom *szép* megoldást akar valaki, az hogy rövid egy kód ez *nekem* nem szép, működjön hibamentesen

hibamentes? elenyésző? adott esetben persze hogy az, a zh-n átmegy vele :P de hogy ezt nevezné valaki igényesnek ... majd jön a kopopészt bajnok programozó aki ezt a megoldást választja de ott ahol nem 90-ig kell választani hanem *tényleg* előjön a hibája ennek az algoritmusnak

tehát mire jó ez a megoldás? zh-ra vagy lottótippelésre? mindkettőre
szép megoldásnak? *nekem* szubjektíve semmiképp :)

nem kell félreérteni, maga az ötlet szép, én nem gondoltam rá és tetszik is, csak mint kivitelezés kritizáltam (beleszámítva amit írtam hogy 200+ hsz szép megoldás keresése jelen témára! )

Szép, ha igaz. Én nem látom, hogy azonos vsz-üek lennének az ötösök, de a valszám sosem volt az erősségem.

Szerk:
Ahh "The Art of programming Vol 2. 3.4.2 Algorithm S"
Újrafeltaláltad vagy emlékeztél rá?

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Nem fedeztem fel, igazából csak egy erős intuícióm volt, hogy számok közötti távolság eloszlásának generálásával biztos lehet jobb megoldást találni az eddigieknél, innentől meg keresgélés:
amivel megtaláltam ezt, meg a talán még mindig state of the artnak minősülő Vitter cikket

Nyilván be kellett volna rendesen járni egyetemre, de ami elmúlt az elmúlt... ;)

( BaT | 2012. 01. 14., szo – 13:58 )

Tudom, hogy marha régi topic, de többször eszembe jutott azóta, mert nekem is volt egy ötletem, csak volt egy pont amivel nem tudtam mit kezdeni. Aztán most újra eszembe jutott (vizsgaidőszak van... :)), és nagyjából sikerült megoldani ezt a problémát.

Kód: http://pastebin.com/f5mnCF8A (PowerShell, nem volt kedvem C-ben is implementálni, bár nem lenne nehéz.)

Kis magyarázat: az eredeti ötletem az volt, hogy ciklikus csoportban keressünk egy generátort, így azt mindig sorban hozzáadva az előző számhoz M+1 lépésben jutunk el ahhoz, hogy ütközés lépjen fel. A probléma csak az, hogy ez a megoldás túlzottan determinisztikus, már az első két szám ismeretében meghatározható az összes többi. Ezt az algoritmust demonstrálja a FirstRandomSequence függvény.

Majd arra gondoltam, hogy ha nem mindig 1-szer (vagy konstansszor) adnánk hozzá az előző számhoz a generátort, azzal a determinisztikusság csökkenne. Csakhogy ehhez kell egy második algoritmus is, ami képes úgy véletlen számokat generálni, hogy nem lép fel ütközés. Erre gondoltam ki azt, hogy az intervallumot valamilyen módon felosztom, ebből kiválasztok egy véletlen számot, egyrészt ezt hozzáadva az előző véletlen számhoz megkapom az új véletlen számot, másrészt az intervallumból ezen véletlen számot kivonva (és a maradék intervallumot újra felosztva) garantáltan tudom generálni a következő számot. Nyilvánvaló, hogy ezen módszer hátránya, hogy a folyamatosan csökkenő intervallum miatt a számok eloszlása nem lesz egyenletes, de a számok közötti különbségek eloszlása sokkal inkább fog hasonlítani a teljesen véletlen algoritmus által generált számok különbségének eloszlására. Ezt a második algoritmust demonstrálja a SecondRandomSequence. A kódban több különböző felosztással próbálkoztam, amiket kikommentelve benne hagytam, végül a nem kikommentelt verzió bizonyult a legjobbnak.

Ha összerakom a kettőt, azaz a ciklikus csoportban mindig véletlenszerűen lépek, ügyelve arra, hogy legfeljebb összesen 90-szer lépjek, az egy viszonylag jó sorozatot fog adni minden esetben. Ez az algoritmus a MyRandomSequence.

Az összehasonlítás érdekében a UsualRandomSequence a tömb nélküli, de nem teljes és nem determinisztikus algoritmust implementálja.

Összehasonlítás: http://batsite.zxq.net/files/RandomSequence.xlsx (Ez azt hiszem magáért beszél, az egyezés oszlop azt mutatja meg, hogy volt-e olyan eredmény, amiben voltak egyező elemek. Azért fordulhat elő, hogy a 0 különbség nem 0, mert az első elemet a 0-val hasonlítom össze, és előfordul, hogy az első elem a 0.)

Az jól látszik, hogy a MyRandomSequence egyenletes eloszlású, és a különbségek eloszlása is hasonlít a UsualRandomSequence különbségeinek eloszlásához, bár picit azért "szőrösebb". Tehát nem tökéletes a megoldás, nem igazán tudom, hogyan lehetne tovább javítani rajta. Viszont cserébe az algoritmus nem tárolja el az összes lehetséges elemet tömbben, és a futása is determinisztikus és teljes. Az egyetlen pont, ami nem egészen tetszik rajta, az a generátor generálása, talán azon lehetne még javítani.

Igazából az a 30 000-szeres ismétlés csak tesztelés miatt kellett, véletlenül maradt benne. :D
Köszi egyébként, kezdőként jó látni a tapasztaltabbak kódjait, nem is értem, miért cserélgettem a 2 számot, mikor csak az utolsót kellett volna beírni a kihúzott helyére.

( GerzSonka | 2016. 10. 21., p – 21:52 )

Generálsz egy tömböt 1-90-ig növekvő sorrendben. Lefuttatsz egy ciklust, ami mondjuk 2000 iterációban mindig megcserél 2-2 elemet. Az iteráció után kiveszed az első 5, vagy 6 elemet.
--
"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live." John F. Woods

Nem jó több okból. Még nagyobb iterációs számnál is kisebb lesz a keveredése a számoknak. Illetve sok lépés kell hozzá.

A fentiekben van jó példa pár lépésre:

véletlen szám bekér 1 és 90 között, majd az n-1 pozícióval felcserélni a véletlen számot egy 1-90-ig értéket tartalmazó tömbben. Ezt 5-szőr csökkentve 1-gyel a végén cserélt pozíciót. Az 5. lépés után a felső 5 elem a véletlen érték. Max ezt még sorrendbe rakod.