Gestire i tempi di una gara di slalom.

Realizzare un tipo grandeint per interi che superano la capacità del tipo integer.

realizzare il tipo razionale

Ricercare una sottostringa r in una stringa s.

Determinare tutti i numeri primi minori di n.

Dato un numero intero n dire se è primo.

Torre di Hanoi

Problema 1: scrivere un programma per gestire i tempi di una gara di slalom.

OBIETTIVO: in genere con il termine "gestire" si intende offrire la possibilità di inserire, visualizzare, modificare e ricercare dati di un determinato tipo. Nel nostro caso i tempi degli atleti di una gara di slalom. La visualizzazione sarà la stampa della classifica con tempo e atleta, che dovrà avvenire dopo ogni discesa. Poichè inoltre le gare di slalom si svolgono in due manche, durante la seconda discesa sarà necessario visualizzare anche la classifica finale. Ovviamente il programma dovrà permettere di inserire, dopo ogni discesa, il tempo dell'atleta. Ogni atleta sarà individuato dal numero di pettorale.

RISULTATI: la classifica dopo ogni concorrente, la classifica della prima manche, la classifica finale.

DATI: il numero di pettorale e il tempo di ciascun concorrente nella prima e nella seconda manche. Supponiamo che il tempo sia misurato in centesimi di secondo e che in caso di prova nulla sia assegnato il tempo massimo di 32000. La variabile che dovrà contenere il tempo sarà di tipo integer.

STRUTTURA DATI: per quanto riguarda la struttura dati sono necessarie alcune osservazioni. Noi dobbiamo conoscere il pettorale ( un integer ) con un tempo corrispondente ( un integer ). I pettorali sono tutti diversi e, a priori si conosce quanti atleti partecipano alla gara. Inoltre la stampa delle classifiche avverrà sempre per ordine crescente di tempi. I dati saranno inseriti uno alla volta rispettando l'ordinamento. Si possono utilizzare, per ogni classifica, due vettori uno per i tempi e uno per i pettorali. Alla posizione i del vettore dei tempi ci sarà il tempo del concorrente classificato all'i-esimo posto. Il numero di pettorale che individua l'atleta sarà alla stessa posizione del vettore dei pettorali. La struttura dati sarà:

CONST

TYPE

VAR

manche1, manche2, finale,

petto1, petto2, pettof :vettore

ALGORITMO:

END.

• leggi: non presenta particolari difficoltà.

PROCEDURE leggi( VAR t, p:INTEGER );

BEGIN

END;

• inizializza:

PROCEDURE inizializza;

BEGIN

END;

- fine: utilizziamo una funzione che richiede conferma per giudicare terminata una gara.

FUNCTION fine:BOOLEAN;

VAR

BEGIN

END;

- inserimento: avverrà rispettando l'ordinamento crescente del vettore dei tempi.

PROCEDURE inserisci( t, p:INTEGER; VAR cl, pp:vettore );

VAR

{ l'inserimento avviene ordinato per tempi crescenti }

FUNCTION posizione( v:vettore; x:INTEGER ):INTEGER;

{ ricerca la posizione dove inserire il nuovo tempo }

VAR

BEGIN

END; { posizione }

PROCEDURE buco( VAR v:vettore; p:INTEGER );

{ sposta tutti gli elementi del vettore per inserire il nuovo dato }

VAR

BEGIN

END; { buco }

BEGIN { inserisci }

END;

- aggiornamento della classifica finale: è necessario svolgere una ricerca per ottenere il tempo di ogni atleta nella prima manche. Se realizziamo una function che, avuto in input un numero di pettorale e la classifica, ci restituisce il tempo che ha ottenuto ecco che il problema è risolto.

FUNCTION tmp( tempi, petto:vettore; p:INTEGER ):INTEGER;

VAR

BEGIN

END;

Osserviamo che se uno sciatore gareggia nella seconda manche sicuramente sarà disceso anche nella prima.

Aggiorna finale e pettof diventerà:

PROCEDURE aggiorna( tempo, pettorale:INTEGER );

BEGIN

END;

- stampa: utilizziamo una procedura che avuto in ingresso un vettore di tempi e il corrispondente vettore dei pettorali li stampa.

PROCEDURE stampa( t, p:vettore );

VAR

BEGIN

ELSE

END;

Problema 2: realizzare un tipo grandeint per interi che superano la capacità del tipo integer.

Le funzioni che si devono realizzare per gestire il tipo grandeint sono le stesse che il Pascal mette a disposizione per il tipo integer. Per quanto riguarda la struttura dati possiamo "copiare" quella utilizzata per il tipo integer e cioè utilizzare una rappresentazione binaria del numero con l'accorgimento di utilizzare molti più bit. Ad esempio potremo rappresentare il tipo grandint così:

CONST

TYPE

N.B la posizione 0 del vettore serve solo a semplificare la scrittura delle procedure: i bit significativi sono 1..64.

Alla costante FALSE assoceremo 0, alla costante TRUE assoceremo 1.

La posizione 1 avrà il peso maggiore. Se il numero è rappresentato in complememto a due il bit del segno sarà il bit 1. Il bit 0 è stato inserito per semplificare la scrittura di alcune funzioni.

Vediamo alcune funzioni.

1- la procedura ZERO pone il numero a zero: cioè pone tutti gli elementi del vettore di BOOLEAN a FALSE.

PROCEDURE zero (VAR v:grandint);

VAR

BEGIN

END;

2- la procedura SUCCESSIVO incrementa di uno il valore del numero: partendo dal bit meno significativo si cambiano i bit da 1 a 0 fermandosi quando si incontra un bit a 0 che viene posto a 1.

Esempio: 10110111 + 1 = 010111000

11111111 + 1 = 000000000

PROCEDURE successivo (VAR v:grandint);

VAR

BEGIN

END;

La procedura SUCESSIVO sfrutta la presenza della posizione 0 del vettore.

3- la procedura COMPLEMENTO calcola il complemento a 2 di un numero: calcola il complemento a 1 e somma 1.

PROCEDURE complemento (VAR v:grandint);

VAR

BEGIN

END;

4- la procedura SOMMA somma due numeri: partendo dal bit meno significativo si può notare che i casi possibili si riducono a due:

1- i bit da sommare sono uguali:

rip = 1 rip = 0 rip = 1 rip = 1

a[i]= 0 a[i]= 0 a[i]= 1 a[i]= 0

b[i]= 0 b[i]= 0 b[i]= 1 b[i]= 0

portano sempre a:

c[i]:=rip e rip:=a[i]

2- i bit da sommare sono diversi:

rip = 1 rip = 0 rip = 1 rip = 0

a[i]= 1 a[i]= 1 a[i]= 0 a[i]= 0

b[i]= 0 b[i]= 0 b[i]= 1 b[i]= 1

portano sempre a:

se rip=1 allora c[i]:=0 altrimenti c[i]:=1

rip rimane invariato

PROCEDURE somma (a,b:grandint; VAR c:grandint);

VAR

BEGIN

END;

5- la procedura SOTTRAI calcola c= a - b : il calcolo viene eseguito sommando ad a il complemento a 2 di b.

PROCEDURE sottrai (a,b:grandint; VAR c:grandint);

BEGIN

END;

6- la funzione IS_ZERO rstituisce TRUE se un numero è uguale a 0: controlla che tutti gli elementi del vettore siano FALSE.

FUNCTION is_zero (v:grandint):BOOLEAN;

VAR

BEGIN

END;

7- la procedura PRODOTTO calcola il prodotto di due numeri: viene implementata tramite moltiplicazioni per due e somme successive.

PROCEDURE prodotto (a,b:grandint; VAR c:grandint);

VAR

PROCEDURE perdue (VAR a:grandint);

VAR

BEGIN

END;

BEGIN

END;

8- la procedura STAMPA visualizza il numero in binario.

PROCEDURE stampa (v:grandint);

VAR

BEGIN

END;

Come applicazione delle funzioni precedenti calcoliamo il fattoriale.

PROCEDURE fatt(v:grandint; VAR c:grandint);

VAR

BEGIN

END;

Esercizio. Implementare le seguenti funzioni e PROCEDURE definite sul tipo grandint.

1. FUNCTION minore(a:grandint; b:grandint):BOOLEAN;

2. FUNCTION maggiore(a:grandint; b:grandint):BOOLEAN;

3. FUNCTION uguale(a:grandint; b:grandint):BOOLEAN;

4. FUNCTION positivo(a:grandint):BOOLEAN;

5. FUNCTION negativo(a:grandint):BOOLEAN;

6. PROCEDURE assegna(a:grandint; VAR b:grandint);

7. PROCEDURE eleva (a:grandint; b:grandint; VAR c:grandint);

8. PROCEDURE divisodue (a:grandint; VAR b:grandint);

9. PROCEDURE dividi (a:grandint; b:grandint; VAR c:grandint);

10. Sviluppare una funzione di lettura che permetta di ricevere dall'esterno un numero grande e restituisca un grandint.

Problema 3: realizzare il tipo razionale.

Dalla matematica sappiamo che ogni numero razionale può essere rappresentato come rapporto tra due numeri interi primi tra loro.

Allora per la rappresentazione dei razionali abbiamo bisogno di un vettore con due elementi, il numeratore e il denominatore.

STRUTTURA DATI:

TYPE

Per utilizzare i razionali abbiamo bisogno di un costruttore, cioe di una procedura che, avuto in input due numeri interi restituisce un razionale, cioè un vettore contenente un numeratore e un denominatore primi tra loro, e di due selettori, uno che restituisce il numeratore e l'altro il denominatore. Utilizzando poi queste funzioni elementari si possono costruire tutte le operazioni con i razionali.

Il costruttore dei razionali sarà:

PROCEDURE crea_raz (x:INTEGER ; y:INTEGER ; VAR r:RAZIONALE);

VAR

FUNCTION mcd (x: INTEGER; y: INTEGER): INTEGER;

VAR

BEGIN

END;

BEGIN { crea_raz }

END;

Il selettore num, sarà una funzione che, avuto in ingresso un razionale restituisce il numeratore.

FUNCTION num (r:RAZIONALE): INTEGER;

BEGIN

END;

Il selettore den, sarà una funzione che, avuto in ingresso un razionale restituisce il denominatore.

FUNCTION den (r:RAZIONALE): INTEGER;

BEGIN

END;

Con queste tre funzioni si possono realizzare tutte le operazioni con i razionali. Ad esempio:

PROCEDURE add_raz ( x:RAZIONALE; y:RAZIONALE; VAR z:RAZIONALE );

BEGIN

END;

PROCEDURE sub_raz ( x:RAZIONALE; y:RAZIONALE; VAR z:RAZIONALE );

BEGIN

END;

PROCEDURE molt_raz ( x:RAZIONALE; y:RAZIONALE; VAR z:RAZIONALE );

BEGIN

END;

PROCEDURE div_raz ( x:RAZIONALE; y:RAZIONALE; VAR z:RAZIONALE );

BEGIN

END;

PROCEDURE print_raz( x:RAZIONALE );

BEGIN

END;

FUNCTION ug_raz( x:RAZIONALE; y:RAZIONALE ):BOOLEAN;

BEGIN

END;

Esercizio 1. Definire il tipo complesso e realizzare le seguenti primitive:

1. PROCEDURE crea_complesso (a,b:REAL; VAR c:complesso);

2. FUNCTION parte_reale (a:complesso):REAL;

3. FUNCTION parte_imm (a:complesso):REAL;

4. PROCEDURE add (a,b:complesso; VAR c:complesso)

5. PROCEDURE molt (a,b:complesso; VAR c:complesso)

6. PROCEDURE sub (a,b:complesso; VAR c:complesso)

7. PROCEDURE div (a,b:complesso; VAR c:complesso

8. PROCEDURE print (a:complesso);

9. FUNCTION eguali (a,b:complesso):BOOLEAN;

10. FUNCTION is_zero (a:complesso):BOOLEAN;

Esercizio 2. Definire il tipo data e realizzare le seguenti primitive:

1. PROCEDURE crea_data(a,b,c:INTEGER; VAR d:data);

2. FUNCTION giorno(d:data):INTEGER;

3. FUNCTION mese(d:data):INTEGER;

4. FUNCTION anno(d:data):INTEGER;

5. PROCEDURE successivo(VAR d:data);

6. FUNCTION giorni_tra_due_date(a,b:data):INTEGER;

Problema 4: ricercare una sottostringa r in una stringa s.

RISULTATI: la posizione della prima occorrenza di r in s, 0 se non esiste.

DATI: la striga r e la stringa s STRUTTURE DATI:

CONST

dim=600;

TYPE

VAR

s:stringa;

r:stringa;

supponiamo che le stringhe s ed r siano terminate dal carattere CHR(0).

ALGORITMO: si deve realizzare una funzione che, avuto in input le due stringhe, restituisca 0 se non trovato, l'indice della prima occorrenza, se trovato.

Soluzione 1.

WHILE NOT TROVATO DO BEGIN

FUNCTION ricerca( VAR s,r:stringa ):INTEGER;

VAR

FUNCTION confronta( p:INTEGER ):BOOLEAN;

{ confronta tutti i caratteri di r con quelli di s a partire dalla posizione p }

VAR

BEGIN

END;

BEGIN { ricerca }

END;

Soluzione 2.

Nell'algoritmo presentato in precedenza l'indice i viene sempre incrementato di 1. Ma nel 1976 due ricercatori dell'università di Austin, nel Texas hanno trovato un metodo che consente incrementi maggiori di i.

Sia

s: l'uomo vive ogni cosa subito per la prima volta, senza preparazione.

r: cosa

Supponiamo di avere a disposizione una tabella contenente per ogni lettera la distanza dall'ultimo carattere della parola da ricercare: per i caratteri non presenti in r e per l'ultimo di r ci sarà la lunghezza della parola:

a ---- 4

b ---- 4

c ---- 3

d ---- 4

........

........

o ---- 2

........

s ---- 1

Il confronto avviene così:

L'uomo vive ogni cosa subito per la prima volta, senza preparazione.

cosa

Si confronta a partire dall'ultimo carattere di r. Se il corrispondente è diverso si sposta r del valore indicato nella tabella in corrispondenza del carattere di s. Nell'esempio si cerca la lettera o.

L'uomo vive ogni cosa subito per la prima volta, senza preparazione.

cosa

cosa

cosa

cosa

cosa

cosa

cosa

Nel caso in cui le lettere sono uguali si passa ad esaminare la penultima lettera, ripetendo il ragionamento descritto in precedenza.

L'algoritmo completo sarà:

FUNCTION len( VAR x:stringa ):INTEGER;

{ calcola la lunghezza di una stringa }

VAR

BEGIN

END;

FUNCTION ricerca( VAR s, r:stringa ):INTEGER;

TYPE

VAR

BEGIN

END;

Problema 5: determinare tutti i numeri primi minori di n.

DATI: n

RISULTATO: vettore di numeri primi compresi tra 1 e n

ALGORITMO:

Un numero T è primo se non ammette divisori tra i numeri primi compresi fra 2 e la parte intera della radice quadrata di T.

L'algoritmo diventa:

PROGRAM num_primi (INPUT,OUTPUT);

CONST

dim=100;

TYPE

VAR

PROCEDURE calc_primi (VAR v:vet;max,dimens:INTEGER;VAR num_valori:INTEGER);

VAR

BEGIN

END;

BEGIN

END.

Problema 6: dato un numero intero n dire se è primo.

DATI: n

RISULTATI: "primo", "non primo"

ALGORITMO

Vogliamo quì presentare un algoritmo probabilistico per determinare se un numero è primo. Il punto di partenza è il teorema di Fermat:

se N è primo e A è un naturale < N allora

A^N mod N = A

Quindi:

se A^N mod N <> A allora N non è primo

se A^N mod N = A , con A scelto a caso ,allora ci sono " buone probabilità" che N sia primo; tali probabilità aumentano se ciò si verifica per più valori casuali di A.

L'algoritmo consiste quindi nel ripetere un certo numero di volte il test di Fermat: la funzione fast_prime svolge questo compito.

La funzione fermat_test genera semplcemente un numero casuale e verifica la condizione di uguaglianza imposta dal test.

A questo punto abbiamo il problema di calcolare A^N mod N. Se procediamo con il calcolo di A^N dovremo affrontare problemi notevoli: ad esempio supponiamo di voler sapere se 1000 è un numero primo: se il valore casuale generato è 100 dovremmo calcolare 100^1000. Il risultato non è rappresentabile con il tipo integer. Ci viene in aiuto una semplice proprietà aritmetica:

(x * y) mod n = ((x mod n) * (y mod n)) mod n

Infatti siano

r1= x mod n r2= y mod n

allora

x = q1 * n + r1 y = q2 * n + r2

x * y = (q1*n+r1)*(q2*n+r2) = (q1*q2*n + q1*r2 + q2*r1) * n + r1*r2

(x * y) mod n = (r1*r2) mod n

E` evidente quindi anche

x^2 mod n = (x mod n)^2 mod n

Ricordando che:

b^e = 1 se e = 0

(b^e/2)^2 se e è pari

(b * b^(e-1) se e è dispari

ricaviamo:

(b^e)mod n = 1 se e = 0

(b^e/2 mod n)^2 mod n se e è pari

((b mod n) * (b^(e-1) mod n)) mod n se e è dispari

Si noti che:

1- Nel notro caso b mod n = b poichè si sceglie b < n;

2- Il numero maggiore che compare è minore di n^2;

PROGRAM fermat(INPUT,OUTPUT);

VAR

FUNCTION expmod(b,e,m:INTEGER):INTEGER;

BEGIN

END;

FUNCTION fermat_test (n:INTEGER):BOOLEAN;

VAR

BEGIN

END;

FUNCTION fast_prime(n,volte:INTEGER):BOOLEAN;

BEGIN

END;

BEGIN

END.

Quando questo algoritmo dice che il numero non è primo il risultato è valido, ma quando dice che è primo lo afferma associando ad esso una probabilità.

Si tenga presente inoltre che esistono particolari numeri che eludono il test di Fermat per quante volte esso venga ripetuto: ci sono dei numeri N non primi tali che

a^n mod n = a per tutti gli a < n

Esempi di questi numeri (non primi) sono:

561, 1105, 1729, 2465, 2821

La probabilità di errore è minore di 1/2^m dove m è il numero di volte che viene eseguito il test di Fermat.

Questo algoritmo è molto efficiente e molto usato: si tenga però presente che in Pascal, il fatto che gli INTEGER siano definiti a 16 o 32 bit lo rende così come esposto praticamente inutile.

Questo algoritmo ha dimostrato, ad esempio, che 2^400 - 593 è (probabilmente) primo: tale numero non è rappresentabile in Pascal col tipo INTEGER.

Problema 7: siano dati tre pioli e N dischi. I dischi possono essere impilati sui pioli in modo da formare delle torri. Sia N il numero dei dischi inizialmente posti sul piolo A, in ordine di dimensione decrescente. Il problema consiste nello spostare N dischi dal piolo A al piolo C in modo che siano disposti secondo l'ordine originale. Vengono posti i seguenti vincoli:

1- ad ogni passo si sposta un solo disco

2- un disco non può essere messo sopra un disco più piccolo

3- può essere usato solo un terzo piolo come deposito ausiliario

(Il problema è noto come il problema della " torre di Hanoi " )

Algoritmo per spostare una torre di altezza N da A a C servendosi di B

se N=1 allora spostare l'unico disco da A a C

altrimenti

1- spostare una torre di N-1 dischi da A a B servendosi di C

2- portare il disco da A a C

3- spostare una torre di N-1 dischi da B a C servendosi di A

PROCEDURE Hanoi(n:INTEGER;sorg,dest,interm:CHAR);

BEGIN

END;