Linguaggi e Traduttori

Prof. Marco Gavanelli

16 giugno 2016

Esercizio 1 (punti 16)

Nelle elezioni con metodo proporzionale, i seggi dovrebbero essere ripartiti in proporzione ai voti ricevuti da ogni partito. In pratica, però, non è possibile seguire esattamente la proporzione, perché il numero di seggi assegnati deve sempre essere un numero intero. Per questo motivo, si utilizza un algoritmo di ripartizione dei seggi; uno dei più usati (usato anche in Italia) è il metodo d'Hondt.

Dopo che i voti sono stati contati, vengono calcolati dei quozienti successivi per ciascun partito. Il totale dei voti per ogni partito è diviso prima per 1, poi per 2, poi per 3, ecc. Si crea quindi una tabella con ha una riga per ogni partito ed un numero potenzialmente infinito di colonne; la casella (i,j) rappresenta il numero di voti del i-esimo partito diviso per j.

Se ci sono S seggi da assegnare, essi vengono assegnati ai partiti in base agli S numeri più alti nell'intera tabella.

Ad esempio, supponiamo che 8 seggi debbano essere suddivisi fra 4 partiti, chiamati A, B, C e D. I partiti hanno ricevuto i seguenti voti:

• partito A: 100000
• partito B: 80000
• partito C: 30000
• partito D: 20000

La tabella risulta:

Gli 8 numeri più alti nell'intera tabella sono indicati in grassetto; i seggi assegnati sono quindi:

• partito A: 4
• partito B: 3
• partito C: 1
• partito D: 0

Si scriva un programma Haskell per calcolare l'allocazione dei seggi secondo il metodo d'Hondt. Si scriva in particolare una funzione

che, dati un numero di seggi s e una lista di voti vs fornisce una lista con il numero di seggi assegnato a ciascun partito. Si può ipotizzare che la lista vs sia ordinata in ordine decrescente.

Non è necessario che la lista di uscita contenga i valori a zero; nell'esempio precedente

*Main> seggi 8 [100000,80000,30000,20000]
[4,3,1]

Esercizio 2 (Punti 2)

Si scriva un programma Lex che all'interno di ogni parentesi aggiunge il numero di parentesi aperte. Ad esempio, dato il testo

abc(asc(ddd)(dqw)((()))

produce

abc(1asc(2ddd2)(2dqw2)(2(3(44)3)2)

Soluzione Esercizio 1

seggi s vs = countSeats (dHondt s vs)

countSeats :: (Eq p, Num c) => [(p,c)] -> [Int]
countSeats [] = []
countSeats xs = let partito=(fst.head) xs
    in (length (filter ((==partito).fst) xs)): countSeats (filter ((/=partito).fst) xs)

dHondt seats votes = take seats (multiMerge (zipWith (\x ys -> zip (repeat x) ys) [1..] (map f votes)))

f x = (map (x/) [1..])

multiMerge xs = foldr merge [] xs

merge [] ys = ys
merge xs [] = xs
merge ((xParty,xVotes):xs) ((yParty,yVotes):ys)
   | xVotes >= yVotes  = (xParty,xVotes):merge xs ((yParty,yVotes):ys)
   | otherwise         = (yParty,yVotes):merge ((xParty,xVotes):xs) ys

Soluzione esercizio 2

%{
int cont=0;
%}
%%

"("		{cont++; printf("(%d",cont);}
")"		{printf("%d)",cont); cont--;}