Avatar billede everclear Praktikant
20. august 2010 - 22:13 Der er 5 kommentarer og
1 løsning

Rekursiv metode til fortløbende tal

Det kan være det er fordi jeg har kigget på det for længe eller fordi det er fredag aften; men jeg kan ikke vikle min hjerne omkring denne her lige nu :)

Jeg skal bruge en metode, der kan tage imod en række tal (i en liste eller array) samt et enkelt tal, der indikerer det antal fortløbende tal, der skal tjekkes for i listen - og den skal desuden returnere de tal, der matcher forespørgslen.

Altså - hvis jeg giver metoden følgende data:

List<int> tal = new List<int>() {1, 2, 6, 7, 8, 10};
int antalFort = 2;

Så vil jeg gerne tjekke "tal" for de sammensætninger, der har 2 (antalFort) fortløbende tal og så returnere den komplette liste:

1 -> 2 er fortløbende - tilføj 1 til listen
2 -> 6 er ikke fortløbende - ignorer
6 -> 7 er fortløbende - tilføj 6 til listen
7 -> 8 er fortløbende - tilføj 7 til listen
8 -> 10 er ikke fortløbende - ignorer

Dette skal give mig en liste (eller array) tilbage med (1, 6, 7).

Ændres værdierne til f.eks.:

List<int> tal = new List<int>() {4, 5, 6, 7, 8, 10, 11, 12, 19, 20};
int antalFort = 3;

så skal følgende ske:

4 -> 5 -> 6 er fortløbende - tilføj 4 til listen
5 -> 6 -> 7 er fortløbende - tilføj 5 til listen
6 -> 7 -> 8 er fortløbende - tilføj 6 til listen
7 -> 8 -> 10 er ikke fortløbende - ignorer
8 -> 10 -> 11 er ikke fortløbende - ignorer
10 -> 11 -> 12 er fortløbende - tilføj 10 til listen
11 -> 12 -> 19 er ikke fortløbende - ignorer
12 -> 19 -> 20 er ikke fortløbende - ignorer
19 -> 20 kan ikke danne 3 fortløbende tal - ignorer
20 kan ikke danne 3 fortløbende tal - ignorer

Med disse værdier skulle jeg gerne ende ud med en liste med (4, 5, 6, 10).

Logisk set burde en rekursiv metode til dette være relativt simpel, men min hjerne vil slet ikke vikle sig omkring den lige nu - er der nogen, der kan hjælpe? :)
Avatar billede Syska Mester
20. august 2010 - 22:40 #1
Kønt er det ikke ... men det virker da :-)

Måske arne_v kommer på banen med en super elegant løsning :-)

mvh

private static List<string> GetFort(List<int> list, int antalFort)
{
    List<string> containsList = new List<string>();
    foreach (int i in list)
    {
        var conList = new List<int>()
                            {
                                i
                            };

        bool contains = true;
        for (int x = 1; x < antalFort; x++)
        {
            int item = i + x;
            contains = list.Contains(item);
            if (!contains)
                break;
            conList.Add(item);
        }


        if(contains)
        {
            containsList.Add(string.Join(",", conList.ToArray()));
        }
    }

    return containsList;
}
Avatar billede arne_v Ekspert
20. august 2010 - 22:47 #2
En ikke-rekursiv loesning med samme ide men dog et lidt andet twist:

        public static List<int> Find1(List<int> lst, int nmatch)
        {
            List<int> res = new List<int>();
            for(int i = 0; i < lst.Count - nmatch + 1; i++)
            {
                bool good = true;
                for(int j = 1; j < nmatch; j++)
                {
                    if(lst[i+j] != lst[i+j-1] + 1)
                    {
                        good = false;
                    }
                }
                if(good)
                {
                    res.Add(lst[i]);
                }
            }
            return res;
        }
Avatar billede arne_v Ekspert
20. august 2010 - 22:53 #3
Jeg synes ikke at det er nemt at lave en rekursiv loesning, men her er et bud:

        private static bool Good(List<int> lst, int ix, int nmatch)
        {
            if(nmatch <= 1)
            {
                return true;
            }
            else
            {
                return (lst[ix]+1 == lst[ix+1]) && Good(lst, ix+1, nmatch-1);
            }
        }
        public static List<int> Find2(List<int> lst, int nmatch)
        {
            List<int> res = new List<int>();
            for(int i = 0; i < lst.Count - nmatch + 1; i++)
            {
                if(Good(lst, i, nmatch))
                {
                    res.Add(lst[i]);
                }
            }
            return res;
        }
Avatar billede everclear Praktikant
20. august 2010 - 23:02 #4
I er nogle fantastiske mennesker begge to - I har lige redet min aften! :)

Min egen løsning var ret tæt på faktisk - havde vist bare kigget på det for længe :)

Jeg er dog endt ud med at bruge Arnes første løsning, da den er dejlig elegant og noget pænere end min egen - men tusinde tak for dit indspark Buzzzz.

Smider du et svar Arne?
Avatar billede Syska Mester
20. august 2010 - 23:08 #5
Jeg var ikke sikker på at dine tal kom i rækker følge, men man kunne selvf bare have lavet en OrderBy først ... :-) så var jeg nok også mer eller mindre kommet frem til arne's forslag.

mvh
Avatar billede arne_v Ekspert
20. august 2010 - 23:20 #6
svar

man kan jo ogsaa dele
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