- Bliver fyldt
- Læses
- Svar
Længste voksende delfølge (LIS)
Hvor mange tal kan du vælge fra en liste, så de beholder deres rækkefølge, og hvert tal er større end det forrige? Den længste voksende delfølge giver svaret. Skriv en liste, og se dynamisk programmering regne ud, for hver position, hvilken kæde der er den længste, der slutter dér. Tryk på Afspil for at se tabellen blive fyldt ud, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Skriv en liste af tal. For hver position indeholder tabellen længden af den længste voksende kæde af værdier, der slutter dér, og den tidligere position, som kæden fortsætter. Sæt flueben ved Tillad ens værdier for kæder, der aldrig går ned. Til sidst læses kæden baglæns fra dens sidste værdi. Nyt eksempel laver en anden liste. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Skriv en liste af tal, adskilt af kommaer eller mellemrum. Sæt flueben ved Tillad ens værdier for kæder, der aldrig går ned.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
- Se hver position blive sammenlignet med alle tidligere, og se derefter den længste kæde læst baglæns i orange.
Sådan virker tabellen
Tabellen har tre rækker: værdierne, længden af den længste voksende delfølge, der slutter ved hver position, og den position, den fortsætter. En værdi alene er en kæde af længde 1. Derefter tjekkes hver tidligere position: hvis dens værdi er mindre, kan kæden, der slutter dér, forlænges med denne værdi, så længden bliver én større. Den længste forlængelse vinder, og dens position kommer i tredje række.
Læs kæden baglæns
Den længste voksende delfølge slutter ved positionen med den største længde. Derfra fortæller tredje række, hvilken position der kommer før, og tredje række for den position fortæller, hvilken der kommer før den, indtil en position uden forgænger. Læst i rækkefølge er disse værdier svaret. Med flueben ved Tillad ens værdier må en værdi også komme efter en lige så stor værdi, og så får man den længste kæde, der aldrig går ned.
Ofte stillede spørgsmål
Hvad er forskellen på en delfølge og et delarray?
Et delarray er en blok af naboværdier. En delfølge beholder rækkefølgen, men må springe værdier over, så i 3, 10, 2, 1, 20 danner værdierne 3, 10 og 20 en voksende delfølge, selv om 2 og 1 står imellem dem.
Hvor hurtig er LIS-algoritmen?
Tabelmetoden sammenligner hvert par af positioner: n·(n − 1)/2 sammenligninger for n værdier. Kabalesortering klarer det i O(n log n): den husker for hver længde den mindste værdi, der afslutter en kæde af den længde, og placerer hver ny værdi med binær søgning.
Er den længste voksende delfølge entydig?
Ikke altid. I 1, 3, 2, 4 har både 1, 3, 4 og 1, 2, 4 længde 3. Tabellen giver længden, og den baglæns læsning finder en af dem.
Hvor bruges den længste voksende delfølge?
Ved sammenligning af filer og genomer, hvor nogle metoder først finder linjer, der passer sammen, og derefter tager en voksende delfølge af deres positioner; i planlægning og i gåder om at stable kasser; og i matematikken, hvor længden af LIS for en tilfældig blanding er et berømt studieobjekt.
Bliver noget sendt nogen steder hen?
Nej. Alt regnes ud i din browser, og dine seneste indstillinger bliver i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor