Programmare con Pascal

Un carattere

1. Restituire il maiuscolo (minuscolo) corrispondente
2. È maiuscolo (minuscolo, cifra)?

Due caratteri

1. Sono la stessa lettera?
   • a=A / a=a / A=a, A=A
2. Quanto vale la somma dei codici tra i due caratteri?
3. Determinare i due caratteri che si trovano a una certa distanza, prima e dopo, di un certo carattere

Sequenze di caratteri

1. Concatenare una stringa N volte
   • s1=”abc”, N=3 -> s2=”abcabcabc”
2. Quante volte compare un certo carattere?
3. Eliminare la prima occorrenza di un certo carattere
4. … ultima …
5. … tutte …
6. Contare il numero di lettere maiuscole contenute
7. … minuscole …
8. … maiuscole e minuscole …
9. Calcolare la somma dei codici dei caratteri contenuti
10. Una stringa è una sottostringa dell’altra?

Parole

1. Quante volte compare una certa parola?
2. Quante sono le parole in un testo?
3. Quante sono le parole di lunghezza 1, 2, 3, …?
4. Quante volte compare ogni singola parola?

Frasi

1. Quante sono le frasi in un testo?
2. Quante sono le frasi con 1, 2, 3, … caratteri?
3. Quante sono le frasi con 1, 2, 3, … parole?

Genera numeri casuali

1. Testa o croce?
2. Una cifra
3. Nell’intervallo [0, A[
4. Nell’intervallo [A, B[
5. Nell’intervallo [-A, A[

Lanciare i dadi

1. Un dado
2. Lancia continuamente un dado e si ferma con l’estrazione del 3
3. 2 dadi
4. n dadi

Lettere casuali

1. Maiuscola
2. Minuscola
3. Maiuscola o minuscola
4. Vocale

Giocare con il computer

1. Indovino io – Il computer prova a indovinare un numero che l’utente ha pensato…
2. Indovina tu – Il computer pensa un numero e invita l’utente a indovinarlo…
   Alla fine sarà visualizzato il numero di tentativi.
3. Dadi – Stabilisci prima le regole…
4. Roulette – …

Utilizzando un array di appoggio

1. Lanciare un dado (due dadi) più volte e conteggiare le uscite (le frequenze assolute/relative…)
   lanci=10

   1	2	3	4	5	6
   1	0	3	2	3	1
   10%	0%	30%	20%	30%	10%

2. Generare tanti numeri casuali nell’intervallo [1, 100] e conteggiare le uscite (le frequenze assolute/relative…)
3. Generare le uscite della Tombola
4. Generare un Mazzo di carte
   1. napoletane, 40 carte (bastoni, coppe, ori, spade)
   2. francesi, 52 carte (cuori, quadri, fiori, picche)

Problemi di base

1. Dati 2 (3/4) numeri reali calcolare
   1. la somma
   2. il prodotto
   3. la media
   4. il valore minimo
   5. il valore massimo
2. Dato un numero intero < 1000
   1. visualizzare le sue cifre separatamente
      128: 1 2 8
   2. calcolare la somma delle sue cifre
      128: 1+2+8=11
   3. calcolare la somma dei quadrati delle sue cifre
      128: 1+4+64=69
3. Verificare se una variabile reale x appartiene all’intervallo [-A, A[
4. Dato un certo mese (da 1 a 12)
   1. Come si chiama?
      2: febbraio
   2. Quanti giorni ha?
      2: 28

Sia N un numero intero positivo

1. Calcolare la somma degli interi da 1 a N
   1+2+...+N
2. Calcolare la somma degli interi da -N a N
   -N+...+N
3. Quanti numeri interi X consecutivi bisogna sommare per raggiungerlo (o superarlo) ?
   1+2+...+X >= N
4. Calcolare la somma dei quadrati dei primi N numeri naturali
   1+4+9+...+N*N
5. Calcolare la somma dei numeri dispari da 1 a N
   1+3+5+...
6. Calcolare la somma dei primi N numeri dispari
   1+3+5+...
7. Quanti sono i suoi divisori?
   10: 1, 2, 5, 10 -> 4
8. Quanti sono i suoi divisori propri (escluso N) ?
   10: 1, 2, 5 -> 3
9. Quanti sono i suoi divisori pari?
10. Calcolare la somma dei suoi divisori propri
    10: 1, 2, 5 -> 8
11. È perfetto?
    Se il numero è uguale alla somma dei suoi divisori propri…
12. È primo?
    Se non ha divisori (escluso 1 e N)…
13. Quanti numeri primi ci sono da 2 a N?
    10: 2, 3, 5, 7 -> 4
14. Calcolare la somma dei numeri primi da 2 a N
    10: 2+3+5+7=17
15. Calcolare la somma dei primi N numeri primi
    10: 2+3+5+7+11+13+17+19+23+29=129

Siano N e M due numeri interi

1. Realizzare un messaggio che illustri la relazione esistente
   • … è maggiore di …
   • … è uguale a …
   • … è minore di …
2. Calcola il m.c.m. (minimo comune multiplo)
3. Calcola il M.C.D. (massimo comun divisore)
4. Calcolare la somma dei quadrati degli interi compresi tra N e M
5. Calcolare il prodotto tra N e M, immaginando di possedere solamente le operazioni di addizione e sottrazione
6. Calcolare il quoziente (intero) della divisione tra N e M utilizzando il metodo delle sottrazioni successive
7. Calcolare il quoziente e il resto.

Sequenza

1. L’utente inserisce una certa sequenza di numeri che termina con 0
   1. calcolare i valori massimo e minimo
   2. calcolare il totale
   3. calcolare la media
   4. quante volte compare un certo valore X
2. L’utente inserisce da tastiera una sequenza di coppie di numeri (codice classe, numero studenti)
   1. calcolare il numero medio di studenti per classe
   2. decidere qual è il codice della classe più numerosa
   3. decidere quali sono i codici della classe più numerosa e della classe meno numerosa.

Liste a puntatori: semplice, circolare, con testa e coda, bidirezionale, multipla.

Lista semplice

Puntatore di testa e tre nodi con informazioni A-B-C

Lista con testa e coda

Puntatore di testa e puntatore di coda

Lista circolare

L’ultimo nodo punta alla testa

Il nodo iniziale è meglio che sia l’ultimo…

Lista bidirezionale

A doppi puntatori: nei nodi puntatori nelle due direzioni

Lista multipla

Una possibile combinazione è la seguente

• lista primaria con puntatore di testa e puntatore di coda, bidirezionale e con puntatori alle liste secondarie: A-B-C
• liste secondarie semplici: p, q-r-s

Operazioni

Le operazioni più comuni per qualsiasi tipo di lista

Aggiungere un nodo

• In testa / in coda / in ordine
• Prima di un certo nodo / dopo un certo nodo

Visitare la lista per

• Visualizzare il contenuto
• Calcolare minimo / massimo / totale / media …
• Contare quante volte compare una certa informazione
• Trovare la posizione di una certa informazione
• È ordinata?

Eliminare un nodo

• In testa / in coda
• Con un certo valore / con un certo puntatore
• Prima di un certo nodo / dopo un certo nodo
• Eliminare tutti i nodi

Date due liste

• Hanno la stessa lunghezza? / Hanno lo stesso contenuto?
• Appendere alla fine della prima una copia della seconda
• Concatenare l’inizio della seconda alla fine della prima

Ordinamento

• Ordinare due nodi rispetto al contenuto
• Ordinare la lista
• Date due liste ordinate fonderle in una terza ordinata

Tipi di dato

1. logico
2. intero molto lungo
3. reale con precisione fissata
4. stringa con lunghezza fissa

Matematica

1. Enti geometrici piani: quadrato, cerchio, …
   • enti geometrici solidi: cubo, sfera, …
2. Equazione di I grado
   • equazione di II grado
3. Sistema di equazioni di I grado
   • sistema di equazioni di II grado
4. Numeri razionali
   • numeri complessi
   • vettori 2d / 3d
5. Matrice 2×2
   • matrice 3×3
   • matrice NxN
   • matrice NxM
   • matrice di numeri razionali
   • matrice di numeri complessi
6. Insieme di numeri
   • insieme di caratteri, stringhe
7. Polinomio
   • polinomio di numeri razionali
   • polinomio di numeri complessi

Tempo

1. Ora
   • data
   • data e ora
2. Calendario
   • agenda

Tabelle

1. Classe di studenti
2. Scaffale di libri
3. Collezione di figurine
4. Rilevazione di dati meteorologici

Definizione

Un tipo di dati

• del quale conosciamo l’interfaccia ma non l’implementazione
• non presente nel linguaggio di programmazione.

Progettazione – Analisi e progetto

Elenco analitico delle proprietà

1. la tipologia degli elementi componenti il nuovo dato;
2. la struttura relazionale che esiste tra le componenti, ovvero il legame che caratterizza la struttura;
3. il dominio dei valori possibili che il dato può assumere;
4. l’insieme delle operazioni ammesse sul dato.

In particolare, il documento di specifica conterrà per ogni operazione

1. Interfaccia: prototipo della procedura/funzione
2. Effetti: risultato dell’operazione eseguita
3. Prerequisiti: le precauzioni da prendere sui parametri
4. Esempi d’uso: forma sintattica che assume la chiamata di procedura/funzione.

Progettazione – Implementazione

Dalle specifiche al codice

1. Scelta del linguaggio di programmazione
2. Scelta della rappresentazione fisica dei dati
3. Codifica della libreria

Test e uso

Dimenticando completamente il codice di implementazione si possono scrivere programmi che usano l’adt con la sola disponibilità delle specifiche.

Notazioni

Notazione funzionale

Un’espressione come la seguente

utilizzando le espressioni con gli operatori propri del linguaggio (+, -, * …) diventa in modo quasi automatico

Se le operazioni da svolgere non sono previste dal linguaggio (UNO, DUE, TRE...)

possiamo utilizzare le procedure per ottenere

dove X e Y sono delle variabili di appoggio per i risultati intermedi.

Se fosse almeno possibile utilizzare la notazione funzionale della matematica

ci sarebbe un notevole miglioramento...

Funzioni

Dovendo svolgere delle azioni e dare infine una risposta si usa una notazione simile a quella delle procedure

nella quale compare il TIPO della risposta che la funzione restituisce nel punto dove è stata chiamata.

Per realizzare questo, è obbligatoria almeno un’istruzione del tipo

nel blocco delle istruzioni della funzione stessa.

Gli operatori binari infissi non sono definibili da programma per realizzare i nostri algoritmi (invece con l’overloading del C++...) e quindi dobbiamo accontentarci della notazione funzionale.

Esercizi

Funzioni con e senza parametri da realizzare, anche imitando le versioni originali.

• Funzioni SENZA parametri: RandRIGA, RandCOL, RandCIFRA, RandALFA
• Funzioni CON parametri: Media(X, Y), Minimo(X, Y), Massimo(X, Y), ByteAlto(), ByteBasso(), BytesSwap(), Tangente(x), Potenza(X, Y), Log10(), Pari(), MediaGeometrica(X, Y), InteroSuperiore(), Maiuscolo(), Minuscolo()

Scrivi l’espressione logica che corrisponde a ognuna delle domande seguenti sulla variabile x

1. x è positiva?
2. x è positiva o nulla?
3. x non è positiva?
4. x è pari?
5. x appartiene all’intervallo [2, 5] ?
6. x è pari e positiva?
7. x appartiene all’intervallo ]2, 5[ ?
8. x è diversa da zero?
9. x appartiene all’intervallo [2, 5] oppure è negativa?
10. x non appartiene all’intervallo [2, 5] ?
11. x appartiene all’insieme [2, 5] U ]10, 12[ ?
12. …

Scrivi l’espressione logica che corrisponde a ognuna delle domande seguenti per un triangolo di lati A, B e C

1. è equilatero?
2. è isoscele, con lati obliqui A e B?
3. è isoscele, con lati obliqui A e C?
4. è isoscele, con lati obliqui B e C?
5. è isoscele?
6. è scaleno?
7. è rettangolo, con cateti A e B?
8. è rettangolo, con cateti A e C?
9. è rettangolo, con cateti B e C?
10. è rettangolo?
11. NON è un vero triangolo, A è troppo grande
12. NON è un vero triangolo, B è troppo grande
13. NON è un vero triangolo, C è troppo grande
14. NON è un vero triangolo.

Le risorse (costanti, variabili, sottoprogrammi, …) che un programma utilizza diventano presto centinaia e difficili da gestire.

Risorse globali   Sequenzialità	Il sottoprogramma P1 ha accesso alle risorse globali a e b. Il blocco principale ha accesso alle risorse locali a, b e P1.
	Il sottoprogramma P1 ha accesso alle risorse globali a e b. Il sottoprogramma P2 ha accesso alle risorse globali a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2. Il sottoprogramma P1 non ha accesso alla risorsa P2.
Risorse locali   Regola gerarchica	Il sottoprogramma P1 ha accesso alle risorse locale: X globali: a e b. Il sottoprogramma P2 ha accesso alle risorse locale: Y globali: a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2. Il sottoprogramma P2 non ha accesso alla risorsa locale X in P1. Il blocco principale non ha accesso alle risorse locali X in P1 e Y in P2.
Omonimie	Il sottoprogramma P1 ha accesso alle risorse locale: X globali: a e b. Il sottoprogramma P2 ha accesso alle risorse locale: X globali: a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2. La X di P1 e la X di P2 sono due risorse diverse.
	Il sottoprogramma P1 ha accesso alle risorse locale: a globale: b. Il sottoprogramma P2 ha accesso alle risorse globali: a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2. La risorse locale a in P1 nasconde la risorsa globale a con lo stesso nome che diventa irraggiungibile.
Passaggio dei parametri	Il sottoprogramma P1 ha accesso alle risorse locale: p e X globali: a e b. Il sottoprogramma P2 ha accesso alle risorse locale: Y globali: a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2. La risorsa p in P1 è un parametro formale che assume il valore del parametro attuale all’atto della chiamata.
	Il sottoprogramma P1 ha accesso alle risorse riferimento: p locale: X globali: a e b. Il sottoprogramma P2 ha accesso alle risorse locali: q e Y globali: a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2. La risorsa p in P1 è un parametro formale che fa riferimento alla variabile associata all’atto della chiamata (il parametro attuale). La risorsa q in P2 è un parametro formale che assume il valore del parametro attuale all’atto della chiamata.
Ricorsione	Il sottoprogramma P1 ha accesso alle risorse locale: P1 globali: a e b Il sottoprogramma P2 ha accesso alle risorse locale: P2 globali: a, b e P1. Il blocco principale ha accesso alle risorse locali a, b, P1 e P2.

Un programma può diventare molto lungo…

• ricorrere a delle linee vuote o di commento
• dare dei nomi a a parti di codice riconoscibili
• separare questi blocchi dal flusso principale
• scrivere una sola volta parti di codice che si ripetono
• …

Se a questi blocchi di codice si da un nome e si separano dal programma principale, scrivendoli prima, diventano dei sottoprogrammi

Per passare il controllo al sottoprogramma è necessario chiamarlo.

Il controllo ritorna al chiamante quando si giunge all’etichetta di fine del sottoprogramma End.

Il blocco principale non ha l’esclusiva di fare le chiamate, anzi ogni sottoprogramma può chiamare tutti gli altri sottoprogrammi.

Parametri per valore

All’atto della chiamata di un sottoprogramma è possibile specificare dei parametri

Prima dell’esecuzione del codice del sottoprogramma P1 avviene un passaggio, assegnazione, del valore di a in x e del valore di b in y.

Il sottoprogramma P1 svolgerà l’operazione per la quale è stato progettato in modo parametrico, cioè in funzione dei valori assunti dai parametri formali (x, y, …) specificati dal chiamante tramite i parametri attuali (a, b, …)

Note

1. l’elenco dei parametri attuali deve corrispondere in numero e tipo all’elenco dei parametri formali
2. ogni parametro formale viene dichiarato e si comporta come una variabile locale inizializzata al valore specificato con il parametro attuale all’atto della chiamata
3. i parametri attuali devono essere valori, quindi possono essere costanti (-1, +5.0), variabili (a, b), espressioni (-a, b+5.0), …
4. al termine dell’esecuzione del sottoprogramma le eventuali modifiche dei valori dei parametri formali scompariranno per sempre…

Parametri per variabile

Piuttosto che passare dei valori si può scegliere di passare delle variabili (indirizzi, reference, …).

Si dice che x e y sono solo reference, riferimenti, per a e b

Note

1. gli effetti dell’esecuzione del sottoprogramma P2 si manifestano nei valori contenuti nelle variabili utilizzate come parametri attuali all’atto della chiamata
2. i parametri attuali devono essere variabili

Parametri misti

Le due modalità di passaggio dei parametri (per valore, per riferimento) possono essere utilizzate contemporaneamente

Alla fine dell’esecuzione del sottoprogramma P3 il valore di a, nel chiamante dipenderà dalle operazioni che sono state eseguite su x in P3.

Funzioni

Quando il sottoprogramma F termina restituisce un risultato che occuperà logicamente lo spazio di codice della chiamata

Il chiamante riceverà da F (la funzione) un dato, risultato dell’elaborazione, e potrà utilizzarlo come argomento di altre elaborazioni

• visualizzazione
• assegnazione a una variabile
• elaborazione all’interno di un’espressione
• come parametro all’interno di un’altra chiamata
• …

Note

1. Si assegna letteralmente il risultato alla funzione.
2. L’assegnazione potrebbe avvenire più volte, quindi l’ultima assegnazione determinerà il risultato effettivo.

Ricorsione

Se il linguaggio di programmazione prevede la ricorsione… un sottoprogramma PR può chiamare il sottoprogramma PR, se stesso, per svolgere lo stesso compito ma con un’stanza diversa

Il sottoprogramma PR chiama il sottoprogramma PR … finché non succede qualcosa (l’istanza diventa un caso particolare che non necessita di un’ulteriore chiamata ricorsiva) e si ritorna all’indietro fino alla prima chiamata…

Può essere una funzione FR …

La ricorsione può essere anche indiretta: il sottoprogramma PR1 chiama il sottoprogramma PR2 che a sua volta … che a sua volta chiama PR1.

Conclusioni

Si può immaginare un sottoprogramma come uno strumento del quale non si conosce l’implementazione (scatola nera) ma si conoscono

• il nome
• la funzionalità che offre
• l’elenco dei parametri formali (con la loro modalità di passaggio e il loro ruolo)
• l’eventuale tipo del valore di ritorno