Monthly Archives: dicembre 2014

Problemi con numeri

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.

Quick sort

Un algoritmo di ordinamento

  • molto complicato: ricorsivo e difficile da ricordare
  • ma ottimo: è quasi sempre molto veloce…

Merge Sort

Algoritmo intuitivo e ottimo.
Utilizza l’algoritmo di fusione di sottosequenze ordinate.

La chiamata chiede di ordinare l’array dal primo, 1, all’ultimo, N, elemento.
A ogni chiamata, dopo aver calcolato Medio, si effettuano due chiamate ricorsive, da Inf a Medio e da Medio+1 a Sup.

In pratica le chiamate ricorsive scendono fino al livello di array con un solo elemento.
Al ritorno di ogni coppia di chiamate si effettua la fusione, merge, delle due parti ordinate (l’array con un solo elemento è già ordinato…).

ms1Esempio 1

Sia v={1, 3, 7, 4, 15, 0, 9, 10}

Le chiamate ricorsive sugli indici da 1 a 8 e con i valori medi successivi

  • (1+8)/2 = 4
  • (1+4)/2 = 2
  • (5+8)/2 = 6
  • (1+2)/2 = 1
  • (3+4)/2 = 3
  • (5+6)/2 = 5
  • (7+8)/2 = 7

hanno l’effetto di raggiungere i singoli elementi.

Con i valori effettivi, l’array dopo le chiamate ricorsive diventa una sequenza di 8 array con un elemento

ms11

Al ritorno di ogni due chiamate ricorsive avviene la fusione di due array ordinati…

ms12

ms2Esempio 2

Sia v={1, 3, 7, 4, 15, 0, 9, 10, 8, 2}

Le chiamate ricorsive sugli indici da 1 a 10 raggiungono i singoli elementi con 2 passaggi in più…

  • (1+10)/2 = 5
  • (1+5)/2 = 3
  • (6+10)/2 = 8
  • (1+3)/2 = 2
  • (4+5)/2 = 4
  • (6+8)/2 = 7
  • (9+10)/2 = 9
  • (1+2)/2 = 1
  • (6+7)/2 = 6.
Considerando i valori effettivi dell’array e l’esecuzione di tutti i passi…
ms22

Selection Sort

Algoritmo intuitivo e più veloce del bubble sort.

Si può individuare il valore minimo in un array V e scambiarlo con il valore alla prima posizione.

In questo modo l’elemento alla posizione 1 occupa definitivamente il posto che gli spetta…

Ripetendo la stessa operazione con i sottovettori

da 2 a N-1
da 3 a N-1

da N-1 a N

andranno al loro posto gli elementi alla posizione 2, 3, …, N-1.
L’elemento alla posizione N occuperà l’unico posto rimasto libero per l’elemento più grande…

Osserva

ss1

Miglioramento

Con un If(...) Then... aggiuntivo si può evitare di eseguire inutilmente la SCAMBIA() quando un elemento occupa già il posto giusto

Liste

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

Lista con testa e coda

Puntatore di testa e puntatore di coda

listabi

Lista circolare

L’ultimo nodo punta alla testa

listaci

Il nodo iniziale è meglio che sia l’ultimo…

listaci2

Lista bidirezionale

A doppi puntatori: nei nodi puntatori nelle due direzioni

listabi

Lista multipla

listam1Una 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

Problemi con ADT

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

ADT

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.

Funzioni

Notazioni

Prefissa -x
Infissa x+y
Postfissa x!
xy+
Funzionale Succ(x)
Altre… x2
xy
logab

Notazione funzionale

Un’espressione come la seguente

Z <-- (a+b)*(c-d)

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

Z:=(a+b)*(c-d);

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

Z <-- (a UNO b) TRE (c DUE d)

possiamo utilizzare le procedure per ottenere

UNO(a, b, X);
DUE(c, d, Y);
TRE(X, Y, Z);

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

Se fosse almeno possibile utilizzare la notazione funzionale della matematica

Z:=TRE(UNO(a, b), SUB(c, d));

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()

Unità Insiemi

Analisi

Unità

oppure, senza incapsulare …

Unità Complessi

Analisi

Unità

Test