Trädvy Permalänk
Medlem
Plats
vetlanda
Registrerad
Okt 2010

Problem med nästlad for-loop

Jag håller just nu på med ett skolarbete där jag ska göra ett "bingo" spel. I programmet har jag koden:
Tanken är att göra 7 unika slumpade tal mellan 1 och 25

for (int i = 0; i < vinnande_Tal.Length; i++) { // Ger 7 slumpmässiga tal mellan 1-25 vinnande_Tal[i] = rng.Next(1, 25); // Jämför talen i vinnande_Tal med varandra, om något tal är samma som det andra byts talet ut mot ett nytt slumptal for (int j = 7; j > 0; j--) { if (vinnande_Tal[i] == vinnande_Tal[j]) { vinnande_Tal[i] = rng.Next(1, 25); } //slut if } // Slut nästlad loop }// Slut loop

När jag kör programmet så får jag felmeddelandet : " Index was outside the bounds of the array"
Hur kommer det sig? borde inte både variablerna i / j gälla i hela loopen?

Trädvy Permalänk
Medlem
Plats
Mantorp
Registrerad
Okt 2011

@JmSargent94: Arrayer indexeras från 0. Så 7 (första steget i inre loper) är index nummer 8.

Du loopar även över icke-initierade delar av arrayen. I inre loopen är bara index 0..i initialiserade, men du kollar 8..1 istället. Vilket kanske kan ge en hint om hur man kan fixa den inre loopen.

En annan hint är att den inre loopen inte på något sätt garanterar att du inte får samma nummer flera gånger (faktiskt inte ens att inget nummer är samma som nummer[i]. ).

Du har också en rätt ineffektiv implementation, men för sju tal spelar det ingen som helst roll. (Det hela är O(n^2), men går att skriva som O(n) eller O(n log2 n) enkelt)

Bara för att:

int used = 0; for(int i=0; i<7; i++ ) { int tal; do tal = rng.Next(1,25); while(used|(1<<tal) != 0); used |= 1<<tal; vinnande_tal[i] = tal; }

Trädvy Permalänk
Medlem
Plats
vetlanda
Registrerad
Okt 2010

@cardeci:

Så igentligen kanske det blir smidigare om jag väljer att göra två separata loopar så att alla tal i vektorn redan är utsatta innan jag påbörjar den andra loopen?

Som svar på ditt andra påstående får jag väl skylla på att det bara är programmering 1 jag håller på med, men jag antar att det är en mer effektiv sökalgoritm du föreslår?=)

Trädvy Permalänk
Medlem
Plats
Mantorp
Registrerad
Okt 2011
Skrivet av JmSargent94:

@cardeci:

Så igentligen kanske det blir smidigare om jag väljer att göra två separata loopar så att alla tal i vektorn redan är utsatta innan jag påbörjar den andra loopen?

Mjo, men problemet är att även när du hittar dubletter så byter du ju bara ut dem mot ett nytt slumpmässigt tal, som kan i sig vara en dublett med vilket annat tal som helst, så du måste loopa över loopen som byter nummer så länge som du bytt ett nummer. Enklare är att bara hålla reda på vilka tal som redan är använda, och slumpa om tills du får ett som inte är använt.

I mitt förslag lagras "använt eller inte" som bittar.

Ett annat alternativ är att göra en array av de 25 talen, och sedan plocka slumpmässiga tal ur arrayen (sätt sedan de nuffrorna till 'used', t.ex. 0). Det här är rätt likt hur det fungerar i verkligheten, även om det är mer likt alternativ 3: Ordna arrayen med nufforna slumpmässigt, och plocka de åtta första (bevisligen samma effekt som att plocka 8 slumpmässiga bollar, men garanterat O(n), alternativ som sätter tal till 'used' på ett eller annat sätt har en teoretiskt worst-case O(infinity), om slumpgeneratorn producerar samma tal hela tiden)

Att ordna om en array slumpmässigt är dock i sig ett intressant problem.

Nå.

Citat:

Som svar på ditt andra påstående får jag väl skylla på att det bara är programmering 1 jag håller på med, men jag antar att det är en mer effektiv sökalgoritm du föreslår?=)

Tja, mer att lagra talen mer effektivt. För O(n) "normal" case så är metoden jag föreslår OK, även om den strikt talat inte är O(n), ju fler nummer (n) man väljer ut settet möjliga tal (1..25 i ditt fall) desto större är chansen att man får dubletter, så den inre do-while loopen får köra fler gånger.

T.ex, om n>25 kommer man hamna i en oändlig loop eftersom alla tal är använda.

O(whatver) innehär att algoritmen typiskt tar i genomsnitt "whatever" tid, normalt sätt uttryckt i 'n', där n är antalet element/punkter/prylar man opererar på.

https://en.wikipedia.org/wiki/Big_O_notation

Trädvy Permalänk
Medlem
Registrerad
Jul 2011

Om man får flika in lite här...
Ta en titt på din Random.Next() och fråga dig om den verkligen gör det du vill att den skall göra.

https://msdn.microsoft.com/en-us/library/2dx6wyd4(v=vs.110).aspx

Hint:

Citat:

maxValue
Type: System.Int32
The exclusive upper bound of the random number returned. maxValue must be greater than or equal to minValue.

Trädvy Permalänk
Medlem
Plats
Mantorp
Registrerad
Okt 2011
Skrivet av Mempatch:

Om man får flika in lite här...
Ta en titt på din Random.Next() och fråga dig om den verkligen gör det du vill att den skall göra.

En annan detalj, om vi nu låtsas att det är riktigt lotto, är att Random är en svag pseudo-random algorithm, och inte lämplig för det ändamålet.

Mempatch: Klar bonuspoäng om du orkar lista ut hur man kan använda System.Security.Cryptography.RNGCryptoServiceProvider.GetBytes för att leverera slumptal mellan 1 och 25 utan bias i distributionen.

Trädvy Permalänk
Medlem
Plats
vetlanda
Registrerad
Okt 2010
Skrivet av cardeci:

Mjo, men problemet är att även när du hittar dubletter så byter du ju bara ut dem mot ett nytt slumpmässigt tal, som kan i sig vara en dublett med vilket annat tal som helst, så du måste loopa över loopen som byter nummer så länge som du bytt ett nummer. Enklare är att bara hålla reda på vilka tal som redan är använda, och slumpa om tills du får ett som inte är använt.

I mitt förslag lagras "använt eller inte" som bittar.

Ett annat alternativ är att göra en array av de 25 talen, och sedan plocka slumpmässiga tal ur arrayen (sätt sedan de nuffrorna till 'used', t.ex. 0). Det här är rätt likt hur det fungerar i verkligheten, även om det är mer likt alternativ 3: Ordna arrayen med nufforna slumpmässigt, och plocka de åtta första (bevisligen samma effekt som att plocka 8 slumpmässiga bollar, men garanterat O(n), alternativ som sätter tal till 'used' på ett eller annat sätt har en teoretiskt worst-case O(infinity), om slumpgeneratorn producerar samma tal hela tiden)

Att ordna om en array slumpmässigt är dock i sig ett intressant problem.

Nå.

Tja, mer att lagra talen mer effektivt. För O(n) "normal" case så är metoden jag föreslår OK, även om den strikt talat inte är O(n), ju fler nummer (n) man väljer ut settet möjliga tal (1..25 i ditt fall) desto större är chansen att man får dubletter, så den inre do-while loopen får köra fler gånger.

T.ex, om n>25 kommer man hamna i en oändlig loop eftersom alla tal är använda.

O(whatver) innehär att algoritmen typiskt tar i genomsnitt "whatever" tid, normalt sätt uttryckt i 'n', där n är antalet element/punkter/prylar man opererar på.

https://en.wikipedia.org/wiki/Big_O_notation

Skrivet av Mempatch:

Om man får flika in lite här...
Ta en titt på din Random.Next() och fråga dig om den verkligen gör det du vill att den skall göra.

https://msdn.microsoft.com/en-us/library/2dx6wyd4(v=vs.110).aspx

Hint:

cardeci:
ah jag ser din poäng, tack för tipset!

Mempatch:
All hjälp upskattas, tackar:)
Next(1,26)

Trädvy Permalänk
Medlem
Registrerad
Okt 2014
Skrivet av JmSargent94:

Jag håller just nu på med ett skolarbete där jag ska göra ett "bingo" spel. I programmet har jag koden:
Tanken är att göra 7 unika slumpade tal mellan 1 och 25

for (int i = 0; i < vinnande_Tal.Length; i++)

När jag kör programmet så får jag felmeddelandet : " Index was outside the bounds of the array"

vinnande_Tal.Length - 1 så hade det inte varit utanför. Length är alltid en större än själva arrayn.

Själv skulle jag lösa bingo nummer med en lista.

static int[] BingoNummer() { Random r = new Random(); List<int> vinnar_lista = new List<int>(); int nytt_bingo_tal = 0; do { nytt_bingo_tal = r.Next(1, 26); if (!vinnar_lista.Contains(nytt_bingo_tal)) { vinnar_lista.Add(nytt_bingo_tal); } } while (vinnar_lista.Count <= 6); return vinnar_lista.ToArray(); }

Dold text

Dator: Ett metall chassi med varierande komponenter på insidan.

Trädvy Permalänk
Medlem
Plats
vetlanda
Registrerad
Okt 2010
Skrivet av Creatooz:

vinnande_Tal.Length - 1 så hade det inte varit utanför. Length är alltid en större än själva arrayn.

Själv skulle jag lösa bingo nummer med en lista.

static int[] BingoNummer() { Random r = new Random(); List<int> vinnar_lista = new List<int>(); int nytt_bingo_tal = 0; do { nytt_bingo_tal = r.Next(1, 26); if (!vinnar_lista.Contains(nytt_bingo_tal)) { vinnar_lista.Add(nytt_bingo_tal); } } while (vinnar_lista.Count <= 6); return vinnar_lista.ToArray(); }

Dold text

tjena, tack för tipsen!
anledningen till att jag valde array är mer att jag känner mig säkrare på det än listor än så länge så det blev lite goto valet. Det där va ju en väldigt mycket smidigare lösning än det jag var inne på!:)

Trädvy Permalänk
Medlem
Plats
Mantorp
Registrerad
Okt 2011
Skrivet av JmSargent94:

tjena, tack för tipsen!
anledningen till att jag valde array är mer att jag känner mig säkrare på det än listor än så länge så det blev lite goto valet. Det där va ju en väldigt mycket smidigare lösning än det jag var inne på!:)

List är en Array, men med dynamisk storlek (klassisk exponentiell resize)

Se upp med tidskomplexiteten på den där lösningen, dock, den skulle få undertjänt(tm) i verkligheten(tm) om n > 7. list.contains är O(n), så det hela blir O(n^2) totalt, helt i onödan (igen. )

List använder ju också oftast avsevärt mer minne, men återigen, det spelar inte roll för n=7 direkt.

Fast det är såna saker som gör att modern mjukvara använder så mycket mer RAM och CPU än "gammalmodig" mjukvara.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013

Vet inte om du löste denna, men som ett spår kan ju vara detta.

var numbers = Enumerable.Range(1, 25).OrderBy(g => Guid.NewGuid()).Take(7).ToArray();

Lite lat, men det gör saker rätt och lite kod.
Förklaring, Skapar en array med alla tal mellan 1 och 25, sorterar dem efter en unik GUID och plockar ur de 7 första. Kanske inte det mest resurseffektiva dock kan inte samma nummer förekomma flera gånger än en gång som do while loopar kan resultera i eftersom Random inte är helt fool proof.

INTEL CORE I7 5960X 3 GHZ 20MB S-2011-3 @ 4.5G, ASUS RAMPAGE V EXTREME, CORSAIR 16GB DDR4 DOMINATOR 3000MHZ, CORSAIR 850W, Asus GTX980ti OC, FRACTAL DESIGN R4 | Astro gaming A50

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Mar 2011

Här får du en mer läsbar implementering (utan LINQ) i C#, hade tråkigt på jobbet

OBS: Fett långsam kod, ville mest bara visa hur man kan tänka

En benchmark mellan min kod och den ovan med linq visar att min tar i snitt 100ms, den med LINQ 0...

void Main() { var test = GetRandomNumbers(); } private static List<int> GetRandomNumbers() { var numbers = new List<int>(); for (var i = 0; i < 7; i++) { var randomNumber = GetRandomNumber(); while(numbers.Contains(randomNumber)) { randomNumber = GetRandomNumber(); } numbers.Add(randomNumber); } return numbers; } private static int GetRandomNumber() { var random = new Random(); var randomNumber = random.Next(1, 26); return randomNumber; }

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013

Sorry för lite muppig LINQ, är en sucker för one-liner.

INTEL CORE I7 5960X 3 GHZ 20MB S-2011-3 @ 4.5G, ASUS RAMPAGE V EXTREME, CORSAIR 16GB DDR4 DOMINATOR 3000MHZ, CORSAIR 850W, Asus GTX980ti OC, FRACTAL DESIGN R4 | Astro gaming A50

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Mar 2011

@ash9: JAG tycker inte den är muppig, jag tycker den är perfekt

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Nov 2013
Skrivet av joss:

@ash9: JAG tycker inte den är muppig, jag tycker den är perfekt

Haha! Bra det, inte helt fel då.

INTEL CORE I7 5960X 3 GHZ 20MB S-2011-3 @ 4.5G, ASUS RAMPAGE V EXTREME, CORSAIR 16GB DDR4 DOMINATOR 3000MHZ, CORSAIR 850W, Asus GTX980ti OC, FRACTAL DESIGN R4 | Astro gaming A50