admin « Programmare con Pascal

Author Archives: admin

Temporaneo

Posted on 02/07/2015 by admin

Comments off

Il Pascal è utilizzato ancora…

è linguaggio ufficiale, insieme con C e C++, delle Olimpiadi di Informatica
Delphi è molto utilizzato in ambito gestionale
Free Pascal è utilizzato in ambito open source.

	Sintassi	Applicazioni
I TIPI DI DATO E LE ESPRESSIONI	Lessico Identificatori Numeri interi Numeri reali Logici Caratteri Stringhe Riepilogo tipi di dato e operatori Operatori e ordine di valutazione	Prova gli interi – 1 Prova gli interi – 2 Prova gli interi – 3 Prova gli interi – 4 Prova i reali Prova i logici Prova i caratteri
IL CONTROLLO DELL’ESECUZIONE	Sequenza Selezione singola Selezione doppia Selezione multipla Selezione multipla – 2 Selezioni annidate Alternativa ciondolante Selezioni Selezioni multiple Ripetizione con controllo in coda Ripetizione con controllo in testa Ripetizioni	Scambiare due variabili Funzioni mancanti Problemi di geometria Sei pari o dispari? Minimo Classificazione dei triangoli – 1 Equazione di 1° grado Sistema lineare Equazione di 2° grado Menu di scelta 1 Classificazione dei triangoli – 2 Prova i logici 2 Problemino di Gauss Congettura di Collatz Numeri perfetti
I SOTTOPROGRAMMI	Sottoprogrammi Funzioni Visibilità delle risorse Procedure Pascal Funzioni Pascal Riepilogo sottoprogrammi	Menu di scelta – 2 Procedure senza parametri Procedure con parametri per valore Procedure con parametri per variabile Procedure con parametri misti Esempi di funzioni Aritmetica: somma Aritmetica: prodotto Aritmetica: potenza Fattoriale Algoritmo di Euclide Numeri di Fibonacci La torre di Hanoi
LE STRUTTURE DATI	Array Matrici Stringhe Set Record	Problemi con array Contare i caratteri Lanciare un dado Lanciare due dadi Problemino di Carla Ricerca sequenziale Ricerca con sentinella Ricerca binaria Fusione di sequenze Ordinare due dati Bubble sort Shaker sort Insertion sort Selection sort Merge sort Quick sort Fare 4 note
I FILE	File ad accesso sequenziale File ad accesso casuale File di testo File binari	Prova i file Prova i file di testo File di temperature Confronta i formati file per i tipi elementari Operazioni sui file di testo Conteggio di parole/frasi Calcolo paghe Archivio di libri
Le strutture informative dinamiche	Memoria dinamica	Lista semplice Lista con testa e coda Lista circolare Lista bidirezionale Lista multipla Alberi: visite / Alberi binari / Alberi binari di ricerca
La programmazione modulare	Unit System Crt Dos Graph Printer	Matrici sparse / Logici / Stringhe Stack / Coda Tabella semplice / Tabella ordinata Date / Ore Insiemi / Polinomi / Matrici Numeri razionali / Numeri complessi

Ancora

Quesiti della fase scolastica/territoriale/nazionale delle Olimpiadi di Informatica
Matematica Senza Frontiere: Al biliardo – Decrescita programmata

Decrescita programmata

Posted on 12/02/2015 by admin

Comments off

Matematica Senza Frontiere – 10/2/2015 n. 2

Annamaria si diverte con le successioni numeriche.
Sceglie un numero intero naturale come primo numero della successione; calcola il successivo moltiplicando tra loro le cifre del numero.
Procede analogamente con il numero ottenuto finché non ottiene un numero con una sola cifra.

Ad esempio, iniziando da 68, ottiene la successione di quattro numeri 68, 48, 32, 6.

Quale numero intero naturale inferiore a 100 comporta, seguendo il procedimento descritto, la successione più lunga?

Vedi la discussione.

Il programma produce tutte le serie per i numeri da 1 a 99

Uses Crt;

Var i: Integer;

Procedure NUMERO(num: Integer);

Var

dd, uu: Byte;

Begin

Write(num, ': ');

While(num >= 10) Do

Begin

dd :=num Div 10;

uu :=num Mod 10;

num:=dd*uu;

Write(num, ' ');

End;

Begin

For i:=1 To 50 Do

Begin

GotoXY(1,i);

NUMERO(i)

End;

For i:=51 To 99 Do

Begin

GotoXY(15,i-50);

NUMERO(i)

End;

GotoXY(1,52);

Readln;

End.

msf_2015_02_p

Aritmetica: potenza

Posted on 01/01/2015 by admin

Comments off

Iterativa

M^N = Pot(M, N) = M*M*...*M (N fattori)

Function PotIter(M, N: Integer): LongInt;

Var

I, Risp: LongInt;

Begin

Risp:=1;

For I:=1 to N Do

Risp:=Risp*M;

PotIter:=Risp;

End;

Ricorsiva

M⁰ = 1, per N = 0
M^N = M*M^N-1, altrimenti

oppure

Pot(M, N) = 1, per N = 0
Pot(M, N) = M*Pot(M, N-1), altrimenti

Function PotRic(M, N: Integer): LongInt;

Begin

If(N = 0) Then

PotRic:=1

Else

PotRic:=M*PotRic(M, N-1);

End;

Aritmetica: prodotto

Posted on 01/01/2015 by admin

Comments off

Iterativo

M*N = 0, per N = 0
M*N = M+M+...+M (N addendi), altrimenti

Function ProdIter(M, N: Integer): LongInt;

Var

I : Integer;

Risp: LongInt;

Begin

Risp:=0;

For I:=1 To N Do

Risp:=Risp+M;

ProdIter:=Risp;

End;

Oppure

M*N = 0, per N = 0
M*N = INCREMENTA^N(0, m), altrimenti

Function ProdIter(M, N: Integer): LongInt;

Var

I : Integer;

Risp: LongInt;

Begin

Risp:=0;

For I:=1 To N Do

Inc(Risp, M);

ProdIter:=Risp;

End;

Oppure

Prod(M, N) = 0, per N = 0
Prod(M, N) = Prod(M, N-1)+M, altrimenti

Esempio

M=5, N=3

Prod(5, 3) = Prod(5, 3-1)+5 = Prod(5, 2)+5 = 10+5 = 15
Prod(5, 2) = Prod(5, 2-1)+5 = Prod(5, 1)+5 = 5+5 = 10
Prod(5, 1) = Prod(5, 1-1)+5 = Prod(5, 0)+5 = 0+5 = 5
Prod(5, 0) = 0

Function ProdRic(M, N: Integer): LongInt;

Begin

If(N = 0) Then

ProdRic:=0

Else

ProdRic:=ProdRic(M, N-1)+M;

End;

Aritmetica: somma

Posted on 01/01/2015 by admin

Comments off

Iterativa

Osserva le diverse versioni

M+N = M+1 ... +1 (N volte)
M+N = ((...((M+1)+1)...)+1)
Somma(M, N) = Successivo(Successivo(...Successivo(M)...))
Somma(M, N) = Successivo^N(M)

Function SomIter(M, N: LongInt): LongInt;

Var

I: LongInt;

Begin

For I:=1 To N Do

Inc(M); { M:=M+1; } { M:=Succ(M); }

SomIter:=M;

End;

apri M dita della mano destra
apri N dita della mano sinistra
mentre la mano sinistra non è chiusa esegui
inizio
apri un dito a destra
chiudi un dito a sinistra
fine
la risposta è nella mano destra

Function SomIter(M, N: LongInt): LongInt;

Begin

While(N > 0) Do

Begin

Inc(M);

Dec(N);

End;

SomIter:=M

End;

Function SomIter(M, N: LongInt): LongInt;

Var

I: LongInt;

Begin

For I:=N DownTo 1 Do

Inc(M);

SomIter:=M;

End;

Ricorsiva

Somma(M, N) = M, per N = 0
Somma(M, N) = 1+Somma(M, N-1), altrimenti

Esempio

M=5, N=3

Somma(5, 3) = 1+Somma(5, 2) = 1+7 = 8
Somma(5, 2) = 1+Somma(5, 1) = 1+6 = 7
Somma(5, 1) = 1+Somma(5, 0) = 1+5 = 6
Somma(5, 0) = 5

Function SomRic(M, N: LongInt): LongInt;

Begin

If(N = 0) Then

SomRic:=M

Else

SomRic:=SomRic(M, N-1)+1;

End;

Ricorsiva

Somma(M, N) = M, per N = 0
Somma(M, N) = Successivo(Somma(M, Precedente(N))), altrimenti

Esempio

M=5, N=3

Somma(5, 3) = Successivo(Somma(5, Precedente(3)) = Successivo(Somma(5, 2)) = Successivo(7) = 8
Somma(5, 2) = Successivo(Somma(5, Precedente(2)) = Successivo(Somma(5, 1)) = Successivo(6) = 7
Somma(5, 1) = Successivo(Somma(5, Precedente(1)) = Successivo(Somma(5, 0)) = Successivo(5) = 6
Somma(5, 0) = 5

Function SomRic(M, N: LongInt): LongInt;

Begin

If(N = 0) Then

SomRic:=M

Else

SomRic:=SomRic(M, N-1)+1;

End;

Function SomRic(M, N: LongInt): LongInt;

Begin

If(N = 0) Then

SomRic:=M

Else

SomRic:=Succ(SomRic(M, Pred(N)));

End;

Oppure

Somma(M, N) = M, per N = 0
Somma(M, N) = Somma(M+1, N-1), altrimenti

Function SomRic(M, N: LongInt): LongInt;

Begin

If(N = 0) Then

SomRic:=M

Else

SomRic:=SomRic(M+1, N-1);

End;

Oppure

Somma(M, N) = M, per N = 0
Somma(M, N) = Somma(Successivo(M), Precedente(N)), altrimenti

Esempio

M=5, N=3

Somma(5, 3) = Somma(Successivo(5), Precedente(3)) = Somma(6, 2) = 8
Somma(6, 2) = Somma(Successivo(6), Precedente(2)) = Somma(7, 1) = 8
Somma(7, 1) = Somma(Successivo(7), Precedente(1)) = Somma(8, 0) = 8
Somma(8, 0) = 8

Function SomRic(M, N: LongInt): LongInt;

Begin

If(N = 0) Then

SomRic:=M

Else

SomRic:=SomRic(Succ(M), Pred(N));

End;

Algoritmo di Euclide

Posted on 01/01/2015 by admin

Comments off

L’algoritmo di Euclide permette di calcolare il massimo comun divisore, MCD, tra due numeri interi. Vedi Wikipedia: Algoritmo di Euclide.

Algoritmo

Dati due numeri naturali a e b

se b è zero allora la risposta è a
altrimenti si divide a per b e si assegna ad r il resto della divisione
- se r=0 allora la risposta è b
- altrimenti a ⇐ b e b ⇐ r e si ripete nuovamente la divisione.

Esempi

Con a=70, b=15

a	b	r
70	15	70=4*15 + 10
15	10	15=1*10 + 5
10	5	10=25 + 0, STOP*

MCD(70, 15)=5.

Con a=15, b=70

a	b	r
15	70	15=0*70 + 15
70	15	…

MCD(15, 70)=5.

Con a=71, b=15

a	b	r
71	15	71=4*15 + 11
15	11	15=1*11 + 4
11	4	11=2*4 + 3
4	3	4=1*3 + 1
3	1	3=31 + 0, STOP*

MCD(71, 15)=1.

euclide_1 L’algoritmo precedente può essere trasformato in un programma di alto livello soltanto utilizzando l’istruzione GOTO.

Con qualche modifica (le due assegnazioni vengono eseguite comunque) può essere adattato alla esigenze della programmazione strutturata.

Function euclide(a, b: Integer): Integer;

Var

r: Integer;

Begin

If(b = 0) Then

euclide:=a

Else

Begin

Repeat

r:=a Mod b;

a:=b;

b:=r;

Until(r = 0);

euclide:=a;

End;

euclide Con qualche altra modifica si semplifica ulteriormente il codice necessario

Dati due numeri naturali a e b

se b è diverso da 0

r ⇐ resto della divisione intera tra a e b
a ⇐ b
b ⇐ r
ripeti l’operazione

altrimenti

la risposta è a

Esempio

Con a=70, b=15

a	b	r
70	15	70=4*15 + 10
15	10	15=1*10 + 5
10	5	10=2*5 + 0
5	0	STOP

MCD(70, 15)=5.

Function euclide(a, b: Integer): Integer;

Var

r: Integer;

Begin

While(b <> 0) Then

Begin

r:=a Mod b;

a:=b;

b:=r;

End;

euclide:=a;

End;

Versione ricorsiva

Con a=70, b=15

MCD(70, 15) = MCD(15, 70 Mod 15)
= MCD(15, 10) = MCD(10, 15 Mod 10)
= MCD(10, 5) = MCD(5, 10 Mod 5)
= MCD(5, 0) = 5

Function euclide(a, b: Integer): Integer;

Begin

If(b <> 0) Then

euclide:=euclide(b, a Mod b)

Else

euclide:=a;

End;

oppure…

Function euclide(a, b: Integer): Integer;

Begin

If(b = 0) Then

euclide:=a

Else

euclide:=euclide(b, a Mod b);

End;

La torre di Hanoi

Posted on 01/01/2015 by admin

Comments off

Il problema

Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.
Sul primo di tali perni sono infilati 64 dischi d’oro, di dimensioni decrescenti, che formano una torre.
Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore.
Per risolvere la questione si può utilizzare il secondo perno come perno di servizio.

Quando i monaci termineranno l’opera il mondo sarà finito!

Analisi

Siano D₁, D₂, …, D_n le etichette dei dischi di una torre di Hanoi con n dischi.

Il problema con un solo disco è banale

il disco è sinistra
sposta il disco D₁ dalla 1° alla 3° torre

Se i dischi sono 2 le mosse sono 3

i dischi sono a sinistra
sposta il disco D₁ dalla 1° alla 2° torre
sposta il disco D₂ dalla 1° alla 3° torre
sposta il disco D₁ dalla 2° alla 3° torre

Se i dischi sono 3 le mosse sono 7

i dischi sono a sinistra
sposta il disco D₁ dalla 1° alla 3° torre
sposta il disco D₂ dalla 1° alla 2° torre
sposta il disco D₁ dalla 3° alla 2° torre
sposta il disco D₃ dalla 1° alla 3° torre
sposta il disco D₁ dalla 2° alla 1° torre
sposta il disco D₂ dalla 2° alla 3° torre
sposta il disco D₁ dalla 1° alla 3° torre

…

Se i dischi sono 4, 5, … si può riconoscere lo schema risolutivo

i dischi sono a sinistra
sposta i dischi D₁…D_n-1 dalla 1° alla 2° torre (usando la 3° come appoggio) in modo da liberare D_n
sposta il disco D_n dalla 1° alla 3° torre
sposta i dischi D₁…D_n-1 dalla 2° alla 3° torre (usando la 1° come appoggio) sopra D_n

Algoritmo

Ad ogni passo è sufficiente specificare

il numero di dischi coinvolti, perché si parla sempre dei dischi in cima a una torre
il nome della torre di origine
il nome della torre di appoggio
il nome della torre di destinazione

allora l’algoritmo risolutivo per il problema

Hanoi(n, origine, appoggio, destinazione)

diventa

Hanoi(n-1, origine , arrivo , appoggio )
Hanoi( 1, origine , appoggio, destinazione)
Hanoi(n-1, appoggio, origine , destinazione)

con l’accortezza che nel caso di torre con un solo disco è sufficiente comunicare di spostare il disco dalla torre origine alla torre destinazione.

Procedure Hanoi(n, origine, appoggio, destinazione: Byte);

Begin

If(n = 1) Then

WriteLn(origine, ' - ', destinazione)

Else

Begin

Hanoi(n-1, origine , destinazione, appoggio );

Hanoi( 1, origine , appoggio , destinazione);

Hanoi(n-1, appoggio, origine , destinazione);

End;

Var num: Byte:

Begin

Write('Numero dischi? ');

Readln(num);

Hanoi(num, 1, 2, 3);

Readln;

End.

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti di dischi

T(1) = 1 T(2) = T(1)+T(1)+T(1) = 1+1+1 = 3 T(3) = T(2)+T(1)+T(2) = 3+1+3 = 7 T(4) = T(3)+T(1)+T(3) = 7+1+7 = 15 ... T(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1

…

Numericamente si tratta della successione

1, 3, 7, 15, 31, 63, 127, ...

cioè

2¹-1, 2²-1, 2³-1, 2⁴-1, 2⁵-1, 2⁶-1, 2⁷-1, ...

quindi

T(n) = 2ⁿ-1

I tempi necessari per risolvere il problema sono

n	T(n) = 2ⁿ-1	1 Hz (uomo)	1 GHz (PC)
1	2¹-1 = 1	un secondo	10^-9 s
2	2²-1 = 3	3 secondi	3*10^-9 s
10	2¹⁰-1 = 1023	~17 minuti	~10^-6 s
20	2²⁰-1 = 1.048.575	~12 giorni	~10^-3 s
30	2³⁰-1 = 1.073.741.823	~34 anni	~1 s
64	2⁶⁴-1 = 18.446.744.073.709.551.615	~5*10¹¹ anni	~500 anni

Conclusioni

L’algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2ⁿ)
Non può esistere un algoritmo con complessità minore
Il problema della torre di Hanoi è un problema intrinsecamente esponenziale
Il problema della torre di Hanoi è un problema intrattabile!

Problemi con caratteri

Posted on 01/01/2015 by admin

Comments off

Un carattere

Restituire il maiuscolo (minuscolo) corrispondente
È maiuscolo (minuscolo, cifra)?

Due caratteri

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

Sequenze di caratteri

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

Parole

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

Frasi

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

Contare i caratteri

Posted on 01/01/2015 by admin

Comments off

I problemi con i testi (parole, frasi) sono diversi da quelli con i numeri…

Quanti caratteri in un testo?
Quante vocali, consonanti?
Quante maiuscole, minuscole?
Quante A, B, C, …, Z?

Per contare quante volte compare ciascun lettera puoi cominciare così…

Var

CONTATORI: Array['A'..'Z'] of Word; (* fino a ~65000*)

frase : String;

Procedure Inizializza;

Var i: Char;

Begin

For i:='A' To 'Z' Do

CONTATORI[i]:=0;

End;

Procedure Visualizza;

Var i: Char;

Begin

For i:='A' To 'Z' Do

Writeln(i, ' ', CONTATORI[i]);

End;

Procedure Conta;

Var i: Byte;

C: Char;

Begin

For i:=1 To Length(frase) Do

Begin

C:=frase[i];

Inc(CONTATORI[C]);

End;

Begin

Writeln('Inserisci una frase a piacere');

Readln(frase);

Inizializza;

Conta;

Visualizza;

Readln;

End.

Note

Il codice precedente conta le lettere maiuscole
Se la frase in input contiene caratteri diversi ci sarà un errore in esecuzione
Si potrebbero convertire le lettere minuscole in lettere maiuscole, con Upcase(), e poi conteggiarle.

1

C:=UpCase(frase[i]);
Si potrebbero contare tutti i caratteri della tabella ASCII dal codice #0 al codice #255

1

Type CONTATORI: Array[#0..#255] of Word;

Problemi con numeri casuali

Posted on 01/01/2015 by admin

Comments off

Genera numeri casuali

Testa o croce?
Una cifra
Nell’intervallo [0, A[
Nell’intervallo [A, B[
Nell’intervallo [-A, A[

Lanciare i dadi

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

Lettere casuali

Maiuscola
Minuscola
Maiuscola o minuscola
Vocale

Giocare con il computer

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

Utilizzando un array di appoggio

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%
Generare tanti numeri casuali nell’intervallo [1, 100] e conteggiare le uscite (le frequenze assolute/relative…)
Generare le uscite della Tombola
Generare un Mazzo di carte
1. napoletane, 40 carte (bastoni, coppe, ori, spade)
2. francesi, 52 carte (cuori, quadri, fiori, picche)

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