Avatar billede odsgaard Praktikant
22. november 2009 - 12:15 Der er 14 kommentarer og
2 løsninger

Formattere en seedningsrækkefølge

Hej

Jeg er igang med et program, der bl.a. skal håndtere seedning af spillere i en turnering.

Jeg har brug for lidt hjælp til at lave en metode, der kan sortere en liste af spillere efter deres seedning.(antallet af spillere = n^2 = {2, 4, 8, 16 ... } - test ikke nødvendig)

Et eksempel er:

ved 2 spillere er rækkefølgen {1,2}
Ved 4 spillere er rækkefølgen {1,4,2,3}
Ved 8 spillere er rækkefølgen {1,8,4,5,2,7,3,6}

Parvis er summen = antal spillere + 1

Metoden skal tage en liste af spillere som parameter og skal returnere en sorteret list

public List<Spiller> seedning (List<Spiller> liste)
{
List<Spiller> sorteret = new List<Spiller>();

// Den spændende kode ... :)

return sorteret;
}

På forhånd tak
Brian
Avatar billede tjacob Juniormester
22. november 2009 - 14:01 #1
Jeg kan ikke give dig koden, da jeg ikke er så stiv i C# syntaks, men metoden er rimelig simpel:

De første 4 er givet (med 0 som start index):
0 = 1
1 = antal spillere
-hvis antal spillere > 2:
2 = antal spillere/2
3 = (antal spillere/2) + 1
-hvis antal spillere > 4:
kan du loope opad:
hvis index mod 2 = 0 (4, 6, 8 osv): værdi = index/2
hvis index mod 2 = 1 (5, 7, 9 osv): værdi = antal spillere + 1 - (forrige index/2)
Avatar billede tjacob Juniormester
22. november 2009 - 14:04 #2
nederste linie er så:
hvis index mod 2 = 1 (5, 7, 9 osv): værdi = antal spillere + 1 - (index - 1/2)
Avatar billede tjacob Juniormester
22. november 2009 - 14:05 #3
Argh. Jeg ryster lidt på hånden i dag:
hvis index mod 2 = 1 (5, 7, 9 osv): værdi = antal spillere + 1 - ((index - 1) / 2)
Avatar billede arne_v Ekspert
22. november 2009 - 15:42 #4
Til inspiration:

using System;

namespace E
{
    public class Program
    {
        public static void Pair(string[] names)
        {
            for(int i = 0; i < names.Length/2; i++)
            {
                Console.WriteLine(names[i] + " - " + names[names.Length - i - 1]);
            }
        }
        public static void Main(string[] args)
        {
            string[] a = { "a", "b", "c", "d", "e", "f", "g", "h" };
            Pair(a);
            Console.ReadKey();
        }
    }
}
Avatar billede odsgaard Praktikant
22. november 2009 - 20:33 #5
Tak for dit forslag tjakob.

Det virker fint ved 8 spillere, men hvis jeg øger det til 16 spillere, så virker det ikke efter hensigten.

Her er min kode:
String s = "";
s += "[" + 1 + "]";
s += "[" + antal + "]";
s += "[" + (antal / 2) + "]";
s += "[" + ((antal / 2) + 1) + "]";
for (int i = 4; i < antal; i++)
{
if (i % 2 == 0) { s += "[" + (i / 2) + "]"; }
else { s += "[" + (antal + 1 - ((i - 1) / 2)) + "]"; }
}

ved 16 spillere får jeg følgende resultat:
1 16 8 9 2 15 3 14 4 13 5 12 6 11 7 10
Det rigtige resultat er skal være:
1 16 8 9 4 13 5 12 2 15 7 10 3 14 6 11

Tallene bliver parvis sat rigtig sammen (summen giver antal + 1), men rækkefølgen er ikke rigtig.
1 - 2 skal mødes i finale
1 - 4 & 2 - 3 i semifinale
1 - 8 & 4 - 5 & 2 - 7 & 3 - 6 i kvartfinale
etc ...
Avatar billede sirius Nybegynder
23. november 2009 - 08:13 #6
du kan gøre det på følgende måde:
public static List<Spiller> seedning(List<Spiller> liste)
{
    List<Spiller> sorteret = new List<Spiller>();
    int start = 0, end = liste.Count - 1;
    while (start < end)
    {
        sorteret.Add(liste[start]);
        sorteret.Add(liste[end]);
        start++;
        end--;
    }
    return sorteret;
}

kræver dog at din liste er sorteret i forvejen og at der er et lige antal spillere
Avatar billede odsgaard Praktikant
23. november 2009 - 09:48 #7
Sirius:

Når jeg umiddelbart kigger på din kode, så virker den ved 4 spillere, men vil ekke give mig det ønskede resultat ved flere spillere.

Din liste vil ved 8 spillere returnere:
1 8 2 7 3 6 4 5
Det ønskede resultat er:
1 8 4 5 2 7 3 6

----------------
Jeg kan prøve at beskrive, hvordan man kan bygge rækkefølgen op, så kan det måske give ideer :)

start med første spiller
1

så fordobles antallet og der tilføjes en spiller tv for hver af de eksisterende, så summen er antal+1:
1 2 (sum = antal+1 = 3)

førnævnte gentages
1 4 2 3 (sum = antal+1 = 5)

og gentages
1 8 4 5 2 7 3 6 (sum = antal+1 = 9)

og gentages
1 16 8 9 4 13 5 12 2 15 7 10 3 14 6 11

etc ...
Avatar billede sirius Nybegynder
23. november 2009 - 11:28 #8
her kommer lige en revideret løsning, kræver at man kan aflæse Seedningsnummeret fra en spiller, derfor har jeg lavet en dum spiller klasse med et seedningsnummer, det kan du jo bare rette til så det passer til din løsning:

public class Spiller
{
    public int SeedNumber;
}

public static List<Spiller> seedning(List<Spiller> liste)
{
    List<Spiller> sorteret = new List<Spiller>();
    sorteret.Add(liste[0]);
    int antal = liste.Count;
    while (sorteret.Count < antal)
    {
        int sum = (sorteret.Count * 2) + 1;
        int listeCount = sorteret.Count;
        for (int i = 0; i < listeCount; i++)
        {
            int pos = sum - sorteret[i+i].SeedNumber - 1;
            sorteret.Insert((i+i), liste[pos]);
        }
    }
    sorteret.Reverse();
    return sorteret;
}
Avatar billede arne_v Ekspert
23. november 2009 - 22:38 #9
Det kan ogsaa goeres unden indsaet:

using System;

namespace E
{
    public class Program
    {
        public static int[] Pair(int n)
        {
            int[] ix = new int[n];
            ix[0] = 0;
            for(int i = 2; i <= ix.Length; i *= 2)
            {
                int d = ix.Length / i;
                for(int j = d; j < ix.Length; j += 2 * d)
                {
                    ix[j] = i - 1 - ix[j - d];
                }
            }
            return ix;
        }
        public static void Main(string[] args)
        {
            string[] a = { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16" };
            int[] ix = Pair(a.Length);
            for(int i = 0; i < ix.Length; i += 2)
            {
                Console.WriteLine(a[ix[i]] + " - " + a[ix[i+1]]);
            }
            Console.ReadKey();
        }
    }
}
Avatar billede janus_007 Nybegynder
24. november 2009 - 19:18 #10
Hvad katten er forskellen uden indsæt? Ifht. metoden seedning?

jojo...

Jeg kan skam skrive hele metoden i main, men hvor fedt er det?
Avatar billede arne_v Ekspert
24. november 2009 - 19:37 #11
Forskellen betyde naeppe noget ved det antal spillere det drejer sig om.

Men principielt er indsaet metoden en O(n^2) algoritme mens den viste beregning er en O(n) algoritme.

Og jeg er ikke helt klar over hvor Main metoden kommer ind i billedet.
Avatar billede janus_007 Nybegynder
24. november 2009 - 21:23 #12
Big O på de funktioner er vidst lige avanceret nok :)

Men jeg vil nu mene at begge er O(n^2), pga. din Pair
Avatar billede arne_v Ekspert
24. november 2009 - 21:36 #13
Den er O(n). Hvert element bliver kun sat en gang. Den ville vaere O(n^2) hvis de 2 for loekker var i++ og j++, men der de ikke.
Avatar billede odsgaard Praktikant
25. november 2009 - 08:48 #14
Arne_v og sirius

Tak for jeres svar.

Jeg har prøvet at køre dem begge to og de giver mig det ønskede resultat.

Jeg syntes, at det har været rigtig svært (for mig) at gennenskue en algoritme der kunne løse problemet, så det er dejligt, at i har taget jer tid til det :)

Vil i deles om pointene, så må i begge smide et svar

Hilsen
Brian
Avatar billede sirius Nybegynder
25. november 2009 - 08:54 #15
Vi deler :-)
Avatar billede arne_v Ekspert
25. november 2009 - 15:10 #16
svar
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
IT-kurser om Microsoft 365, sikkerhed, personlig vækst, udvikling, digital markedsføring, grafisk design, SAP og forretningsanalyse.

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester