Dicembre « 2014 « Programmare con Pascal

Monthly Archives: Dicembre 2014

Problemi con numeri

Posted on 31/12/2014 by admin

Comments off

Problemi di base

Dati 2 (3/4) numeri reali calcolare
1. la somma
2. il prodotto
3. la media
4. il valore minimo
5. il valore massimo
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
Verificare se una variabile reale x appartiene all’intervallo [-A, A[
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

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

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

Sequenza

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

Posted on 31/12/2014 by admin

Comments off

Un algoritmo di ordinamento

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

Procedure QUICKSORT(var V: Vettore; Inf, Sup: Integer);

Var

i, j: Integer;

Perno: Elemento;

Begin1

If(Inf < Sup) Then

Begin

i:=Inf;

j:=Sup;

Perno:=V[(Inf+Sup) DIV 2];

Repeat

While(V[i] < Perno) Do

Inc(i);

While(Perno < V[j]) Do

Dec(j);

If(i <= j) then

Begin

SCAMBIA(V[i], V[j]);

Inc(i);

Dec(j);

End;

Until(I > J);

QUICKSORT(V, Inf, j);

QUICKSORT(V, i, Sup);

End;

Merge Sort

Posted on 31/12/2014 by admin

Comments off

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

Procedure MERGESORT(Var V: Vettore; Inf, Sup: Integer);

Var

Medio: Integer;

Begin

If(Inf < Sup) Then

Begin

Medio:=(Inf+Sup) Div 2;

MERGESORT(V, Inf , Medio);

MERGESORT(V, Medio+1, Sup );

Merge(V, Inf, Medio, Sup);

End;

...

MERGESORT(V, 1, N);

...

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…).

Esempio 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

Esempio 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…

Selection Sort

Posted on 31/12/2014 by admin

Comments off

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.

PosMin:=1;

For j:=2 To N

If(V[j] < V[posMin]) Then

PosMin=j;

SCAMBIA(V, 1, PosMin)

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…

Procedure SELESORT(Var V: Vettore; N: Integer);

Var

PosMin, i, j: Integer;

Begin

For i:=1 To N-1 Do

Begin

PosMin:=i;

For j:=i+1 To N Do

If(V[j] < V[PosMin]) Then

PosMin:=j;

SCAMBIA(V[i], V[PosMin]);

End;

Osserva

ss1

Miglioramento

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

Procedure SELESORT(var V: Vettore; N: Integer);

Var

PosMin, i, j: Integer;

Begin

For i:=1 To N-1 Do

Begin

PosMin:=i;

For j:=i+1 To N Do

If(V[j] < V[PosMin]) Then

PosMin:=j;

If(PosMin <> i) Then

SCAMBIA(V[i], V[PosMin]);

End;

Liste

Posted on 31/12/2014 by admin

Comments off

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

listam1 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

Problemi con ADT

Posted on 31/12/2014 by admin

Comments off

Tipi di dato

logico
intero molto lungo
reale con precisione fissata
stringa con lunghezza fissa

Matematica

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

Tempo

Ora
- data
- data e ora
Calendario
- agenda

Tabelle

Classe di studenti
Scaffale di libri
Collezione di figurine
Rilevazione di dati meteorologici

ADT

Posted on 31/12/2014 by admin

Comments off

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à

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

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

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

Progettazione – Implementazione

Dalle specifiche al codice

Scelta del linguaggio di programmazione
Scelta della rappresentazione fisica dei dati
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

Posted on 31/12/2014 by admin

Comments off

Notazioni

Prefissa	`-x`
Infissa	`x+y`
Postfissa	`x! xy+`
Funzionale	`Succ(x)`
Altre…	`x²` `x^y` `log_ab`

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

1	Function NOME(lista argomenti...): TIPO;

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

1	NOME:="Espressione";

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

Posted on 31/12/2014 by admin

Comments off

Analisi

…

Unità

100

{************************************************************************}

Unit Insiemi;

{************************************************************************}

INTERFACE

{************************************************************************}

Const MaxIns = 20;

Type Elemento = 1..MaxIns;

Insieme = Array[Elemento] Of Boolean;

Procedure AggiungiE (Var I: Insieme; e: Elemento );

Procedure TogliE (Var I: Insieme; e: Elemento );

Function AppartieneE ( I: Insieme; e: Elemento ): Boolean;

Procedure VuoToI (Var I: Insieme );

Procedure ComplemenToI (Var I: Insieme );

Procedure UnioneI (i1, i2: Insieme; Var i3: Insieme);

Procedure IntersezioneI(i1, i2: Insieme; Var i3: Insieme);

Procedure DifferenzaI (i1, i2: Insieme; Var i3: Insieme);

{

sono ancora da fare le operazioni:

Function InclusoUgI (i1, i2: Insieme): Boolean;

Function IncludeUgI (i1, i2: Insieme): Boolean;

Function UgualiI (i1, i2: Insieme): Boolean;

Function DiversiI (i1, i2: Insieme): Boolean;

}

{************************************************************************}

IMPLEMENTATION

{************************************************************************}

{********************* incapsulamenTo dei dati ... **********************}

Procedure AggiungiE(Var I: Insieme; e: Elemento);

Begin

I[e]:=True;

End;

Procedure TogliE(Var I: Insieme; e: Elemento);

Begin

I[e]:=False;

End;

Function AppartieneE(I: Insieme; e: Elemento): Boolean;

Begin

AppartieneE:=(I[e]);

End;

{************************************************************************}

Procedure VuoToI(Var I: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

TogliE(I, e);

End;

Procedure ComplemenToI(Var I: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

if(AppartieneE(I, e)) Then

TogliE(I, e)

else

AggiungiE(I, e);

End;

Procedure UnioneI(i1, i2: Insieme; Var i3: Insieme);

Var

e: Elemento;

Begin

VuoToI(i3);

For e:=1 To maxIns Do

if(AppartieneE(i1, e) Or AppartieneE(i2, e)) Then

AggiungiE(i3, e);

End;

Procedure IntersezioneI(i1, i2: Insieme; Var i3: Insieme);

Var

e: Elemento;

Begin

VuoToI(i3);

For e:=1 To maxIns Do

if(AppartieneE(i1, e) And AppartieneE(i2, e)) Then

AggiungiE(i3, e);

End;

Procedure DifferenzaI(i1, i2: Insieme; Var i3: Insieme);

Var

e: Elemento;

Begin

VuoToI(i3);

For e:=1 To maxIns Do

if(AppartieneE(i1, e) And Not AppartieneE(i2, e)) Then

AggiungiE(i3, e);

End;

{************************************************************************}

Begin

writeln('Unit Insiemi 20/11/2000...');

readln;

End.

{************************************************************************}

oppure, senza incapsulare …

Procedure VuoToI(Var I: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

I[e]:=False;

End;

Procedure ComplemenToI(Var I: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

I[e]:=(Not I[e]);

End;

Procedure UnioneI(i1, i2: Insieme; Var i3: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

i3[e]:=(i1[e] Or i2[e]);

End;

Procedure IntersezioneI(i1, i2: Insieme; Var i3: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

i3[e]:=(i1[e] And i2[e]);

End;

Procedure DifferenzaI(i1, i2: Insieme; Var i3: Insieme);

Var

e: Elemento;

Begin

For e:=1 To maxIns Do

i3[e]:=(i1[e] And Not i2[e]); {!!!}

End;

Unità Complessi

Posted on 31/12/2014 by admin

Comments off

Analisi

…

Unità

Unit Complex;

{----------------------------------------------------------------}

Interface

{----------------------------------------------------------------}

Type Comp = Record

reale,

immag: Real;

End;

Procedure InitC (Var r: Comp; reale, immag: Real);

Function RealeC (Var r: Comp): Real;

Function ImmagC (Var r: Comp): Real;

Procedure RecC (Var r: Comp);

Procedure OppC (Var r: Comp);

Function ModC ( r: Comp): Real;

Procedure AddC ( r, s: Comp; Var t: Comp);

Procedure SubC ( r, s: Comp; Var t: Comp);

Procedure MulC ( r, s: Comp; Var t: Comp);

Procedure DivC ( r, s: Comp; Var t: Comp);

Function UgualiC( r, s: Comp): Boolean;

{----------------------------------------------------------------}

Implementation

{----------------------------------------------------------------}

Procedure InitC(Var r: Comp; reale, immag: Real);

Begin

r.reale:=reale;

r.immag:=immag;

End;

Function RealeC(Var r: Comp):Real;

Begin

RealeC:=r.reale;

End;

Function ImmagC(Var r: Comp):Real;

Begin

ImmagC:=r.immag;

End;

Procedure OppC(Var r: Comp);

Begin

InitC(r, -RealeC(r), -ImmagC(r));

End;

Function ModC(r: Comp): Real;

Begin

ModC:=Sqrt(Sqr(RealeC(r))+Sqr(ImmagC(r)));

End;

Procedure RecC(Var r: Comp);

Var M: Real;

Begin

M:=ModC(r);

If(M = 0) Then Halt(1);

M:=Sqr(M);

InitC(r, RealeC(r)/M, -ImmagC(r)/M);

End;

Procedure AddC(r, s: Comp; Var t: Comp);

Begin

InitC(t, RealeC(r)+RealeC(s), ImmagC(r)+ImmagC(s));

End;

Procedure SubC(r, s: Comp; Var t: Comp);

Begin

OppC(s);

AddC(r, s, t);

End;

Procedure MulC(r, s: Comp; Var t: Comp);

Begin

InitC(t, RealeC(r)*RealeC(s)-ImmagC(r)*ImmagC(s), RealeC(r)*ImmagC(s)+RealeC(s)*ImmagC(r));

End;

Procedure DivC(r, s: Comp; Var t: Comp);

Begin

RecC(s);

MulC(r, s, t);

End;

Function UgualiC(r, s: Comp): Boolean;

Begin

UgualiC:=(RealeC(r) = RealeC(s)) And (ImmagC(r) = ImmagC(s));

End;

{----------------------------------------------------------------}

Begin

Writeln(‘Unit Complex, ver. 1.0 ...’);

End.

Test

…