20 svar
154 visningar

Linjärsökning med rekursion, men kan inte gå över 996

Hej, jag har svårt att tolka uppgiftinstruktionerna

Visa spoiler

Får jag använda den vanliga "in"? Jag tror inte det för då skulle de bli alldeles för enkelt. Därför har jag skrivit en klumpig letare:

Visa spoiler

Men ordlistan är 2500 ord lång

Laguna 11626
Postad: 29 okt 2020

Du får nog använda "in". Det står "... eller endast en tillämpning av en inbyggd operator".

Det här är inte ett bra tillfälle att använda rekursion. Gör en loop i stället. Man ska inte räkna med att kunna göra rekursion mer än kanske hundra steg.

Eventuellt optimeras svansrekursion: prova att ta bort "else:" och flytta anropet till linsok åt vänster. Jag vet inte om det fungerar, men tekniskt skulle det kunna göra det - en del språk har sådan optimering.

Jaha... Nu ska jag bara ctrl+Z några hundra gånger, det var det jag gjorde från början. Det står att "linsok" kan vara "väldigt kort", men jag trodde inte kort.

Tex såhär?

for i in range(len(lista)): osv... 

Qetsiyah 4726 – Volontär digitala räknestugor
Postad: 29 okt 2020 Redigerad: 29 okt 2020

Hej igen, vidare ska vi skriva ett program som söker efter "kuperade ord", dvs ordet delas i mitten och de två bitarna byter plats, tex "ängel"-"länge", "pinal"-"alpin", där kuperingen har skett vid sista respektive tredje bokstaven. Ordlistan innehåller bara ord med fem bokstäver.

Som hjälp har vi fått en binärsökare (istället för att använda "in"), men jag förstår inte den:

på rad 33 och 36 så finns olikheter mellan en sträng och ett tal?? Jag förstår att "ord" ska vara "ord"s index i listan, men det får vi väl inte genom att bara skriva "ord"?

Laguna 11626
Postad: 29 okt 2020

Jag tror de jämför strängar. 

Jag googlade snabbt, < kan jämföra index på strängar, det visste jag inte.

Qetsiyah skrev:

Jaha... Nu ska jag bara ctrl+Z några hundra gånger, det var det jag gjorde från början. Det står att "linsok" kan vara "väldigt kort", men jag trodde inte kort.

Tex såhär?

for i in range(len(lista)): osv... 

Eller såhär?

def linsok(lista, elem): return elem in lista

Laguna 11626
Postad: 30 okt 2020
Qetsiyah skrev:

Jag googlade snabbt, < kan jämföra index på strängar, det visste jag inte.

Vad menar du med index? Strängarna själva jämförs, inte deras eventuella index i en lista.

Qetsiyah 4726 – Volontär digitala räknestugor
Postad: 30 okt 2020 Redigerad: 30 okt 2020

lindehaven: åh, kompakt! Det tänkte jag itne på'

Laguna: men... men hur går det att säga att en sträng är större/mindre än en annan sträng? Vad jämför den?

Alfabetisk ordning. Det gör att åäö hamnar fel eftersom de "sitter fel" i ASCII-tabellen jämfört med vårt alfabet. Stor eller liten bokstav spelar också roll, normalt sett.

Laguna 11626
Postad: 30 okt 2020

Jag skulle inte våga lita på att sorteringen blir rätt med svenska bokstäver utan vidare, men den kanske blir det ändå, om man använder datorns så kallade "locale", som säger hur tecken ska sorteras. När jag testade kom i alla fall å, ä och ö i inbördes rätt ordning.

I ASCII ingår svenska bokstäver strängt taget inte alls. Numera kan man oftast räkna med att alla strängar använder Unicode, där icke-ASCII-tecken använder en byte om det går och annars två, tre eller fyra bytes.

Jaha bokstavsorning... oj vad jag är dum.

Okej laguna, vi får se. Jag gör såndana synder hela tiden, tex ha svenska bokstäver i funktionsnamn och variabelnamn och .py filnamn (och dessutom mellanslag). 

Prova att använda slicing för kuperingen. Ungefär så här (har inte provat koden så det troligen något eller några off-by-one-error):

for i in range(len(ord) - 1):

    if ord[i:] + ord[:i] in lista:

        return True

return False

Laguna 11626
Postad: 30 okt 2020
Qetsiyah skrev:

Jaha bokstavsorning... oj vad jag är dum.

Okej laguna, vi får se. Jag gör såndana synder hela tiden, tex ha svenska bokstäver i funktionsnamn och variabelnamn och .py filnamn (och dessutom mellanslag). 

Apropos det så råkar ditt variabelnamn 'ord' vara en inbyggd funktion, som du härmed har tagit bort (det är helt ok att göra så, men om man också tänkte använda den inbyggda funktionen så kan man bli förvånad). Intressant nog så är den relaterad till det här med teckenkoder: den returnerar koden för ett tecken.

>>> ord('ä')
228
>>> ord('å')
229
>>> ord('ö')
246
>>> 'ä' < 'å'
True

Tydligen är det den koden som används vid jämförelse, så jag tar tillbaka det där med att det kanske fungerar. Det fungerar inte att sortera ord med åäö i rätt ordning med <.

Jaha! Men vad kan "ord" betyda på engelska?

Jag har svårt att förstå det du säger. Vad är då koden för ett ord? Summan av bokstävernas koder? Så vad är det som jämförs i koden ovan när det bara står "ord"?

Funktionen ord() ger unicode-värdet för tecknet.

Laguna 11626
Postad: 30 okt 2020

"Ord" är en förkortning av ordet "ordinal" som betyder ordningsnummer. Du har ordinaltal i matte.

När man jämför strängar jämför man först första tecknen. Om de är lika jämför man nästa tecken osv. tills nånting är olika eller det tar slut.

Vad ord('långtord') blir vet jag inte. Prova. 

TypeError: ord() expected a character, but string of length 8 found

Funktionen tar ett tecken och returnerar dess unicode-värde. 

Lindehaven skrev:

Prova att använda slicing för kuperingen. Ungefär så här (har inte provat koden så det troligen något eller några off-by-one-error):

for i in range(len(ord) - 1):

    if ord[i:] + ord[:i] in lista:

        return True

return False

Har provat nu och det finns ett off-by-one-error i min kod. Lätt att hitta så jag säger inte var det finns :-)

Qetsiyah 4726 – Volontär digitala räknestugor
Postad: 2 nov 2020 Redigerad: 2 nov 2020

Ursäkta att jag inte svarat, jag har redan löst uppgiften. 

Den är lite mer avancerad än nödvändigt, den sorterar i fyra listor. Det som är fel med din är väl att i börjar på noll? Om ett ord är kuperat vid noll är den bara sig själv!

(jag har inte sagt det men alla ord i listan är 5 bokstäver)

Ja, det som är fel i min kod är att den inte kuperar vid rätt kuperingsställe. Koden kan dock hantera godtycklig längd på orden att kupera och orden i listan. 

Svara Avbryt
Close