Övning6

Hemuppgifter

1. Som statistiskt mått på en mängd tal används ibland typvärdet, d.v.s. det värde som är mest frekvent (oftast förekommande). Skriv en procedur som beräknar typvärdet för data i en array med heltal. Om flera värden är lika vanliga skall proceduren ge det minsta av dem.
   
   
2. Skriv en metod för att en lista med positiva och negativa tal ordnas så att de negativa talen kommer först och sedan de positiva. Negativa respektive positiva tal behöver inte vara sorterade, du behöver endast samla alla negativa tal för sig. Använd inte en extra array, problemet kan lösas ändå. Indata ska vara en array med tal (exempelvis heltal men det spelar ingen roll). Din metod ska göra så att de negativa talen kommer före de positiva. Metoden ska gå i linjär tid, det är alltså inte meningen att arrayen ska sorteras!
   
   
3. Olle sitter och rättar ett tentatal. Tentatalet går ut på att man ska skriva en grammatik för meddelande av följande typ:
   Båt 42, båt 73, båt 4711 och båt 17 ska in!
   Båt 1 och båt 2 ska in!
   Båt 13 ska in!
   
   Vilken eller vilka av följande alternativ kan producera dessa meddelanden? Motivera varför de övriga inte kan producera dem (ange exempel på meddelanden som inte kan produceras).
   En del av alternativen kan producera oönskade meningar, man vill t.ex. inte ha
   Båt 1 och båt 2, båt 3 och båt 4 ska in!
   Vilken eller vilka av alternativen kan producera oönskade meningar? Ge exempel.
   
   <meddelande> ::= Båt <tal><svans> | <meddelande> båt <tal><svans>

   <svans> ::= och | ska in! | , 
   <tal> ::= 1 | 2 | 3 | ... 
   
   <meddelande> ::= Båt <tal> ska in! | Båt <tal> <svans> 
   <svans> ::= och båt <tal> ska in! | , båt <tal> <svans> 
   <tal> ::= 1 | 2 | 3 |... 
   
   <meddelande> ::= Båt <tal><svans> 
   <svans> ::= ska in! | , båt <tal> | och båt <tal> 
   <tal> ::= <svans> | 1 | 2 | 3 |... 
   
   <meddelande> ::= Båt <tal><svans> | båt<tal><svans> 
   <svans> ::= ska in! | , | och 
   <tal> ::= 1 | 2 | 3 | ...

    

Uppgift på övningen

sortering