Appunti di programmazione

GENERAZIONE DI NUMERI CASUALI

srand(<seed>);

definita in stdlib.h

seed = seme di inizializzazione sulla quale si baserà la rand, dovrà essere un numero il più casuale possibile (ricavato in genere da elementi hardware del computer);

es.

time(NULL) = restituisce i secondi passati dal 1 gennaio del 1970 (= unix time)

time è definita in time.h

infine utilizzo

rand();

per generare i numeri “casuali”

QUALCHE ALGORITMO...

ALGORITMO DI EUCLIDE PER IL CALCOLO DELL’MCD TRA DUE NUMERI

L’idea si basa sulla seguente osservazione:

per qualunque coppia di valori interi positivi x e y tali che x > y, l’insieme dei divisori di x e y coincide con l’insieme dei divisori di x - y e y

quindi:

• se m=n allora il MCD(m,n) è m (o n)

• se m?n allora

  • se m>n allora MCD(m,n)=MCD(m-n,n)

  • se m<n allora MCD(m,n)=MCD(m,n-m)

Ripetendo questo procedimento, prima o poi si ottengono due numeri uguali che sono quindi il MCD(m,n) cercato

#include <stdio.h>

int MCD(int x, int y) {

while (x!=y)

if (x>y) x = x - y;

else y = y - x;

return x;

}

Invariante del ciclo:

Siano m e n i parametri attuali, quindi l’invariante è:

{ x > 0, y > 0, Div(x,y) = Div(m,n) }

Terminazione: la funzione d(x,y) = x + y per valori x > 0 e y > 0 decresce ad ogni iterazione del ciclo

ALGORITMI DI ORDINAMENTO

ORDINAMENTO PER INSERZIONE

ORDINAMENTO PER SELEZIONE

1. si esamina dell’intero array alla ricerca della stringa più piccola, quella cioè che precede alfabeticamente tutte le altre. Questa stringa viene scambiata con la prima stringa dell’array: dunque la stringa più piccola diventa la prima dell’array.

2. si passa a considerare le restanti n-1 stringhe alla ricerca della più piccola, che sarà scambiata con la seconda stringa dell’array

3. si passa alle restanti n-2 stringhe, in cerca della più piccola, che viene scambiata con la terza stringa dell’array, e così via finché l’array non sarà ordinato

Per trovare la stringa più piccola, ad ogni passaggio, si confronta ciascuna delle stringhe non ancora ordinate con la prima stringa: se si trova una stringa più piccola della prima le due stringhe vengono scambiate

ORDINAMENTO BUBBLE-SORT

supponiamo di voler ordinare i numeri 5, 92, -543, 0, -1

facciamo una serie di confronti tra due numeri vicini ed eventualmente li scambiamo se il numero di destra è minore di quello di sinistra

1. Confrontiamo il 5 con il 92 e vediamo che sono in posizione corretta (5<92)

2. Confrontiamo il 92 con il -543 e vediamo che sono da scambiare e quindi lo facciamo
   Otteniamo così la seguente situazione: 5, -543, 92, 0, 1

3. Confrontiamo il 92 con lo 0 e vediamo che anche questi sono da scambiare
   Otteniamo così la seguente situazione: 5, -543, 0, 92, 1 

4. Confrontiamo il 92 con l' 1 e vediamo che anche questi sono da scambiare
   Otteniamo così la seguente situazione: 5, -543, 0, 1, 92 

Abbiamo finito la prima passata facendo n-1 confronti (dove n è il numero di numeri da ordinare)
il numero più grande si trova ora a destra

Si prosegue con il controllo partendo nuovamente dall'inizio ma non effettuando l'ultimo controllo in quanto sappiamo già che il 92 è il numero più grande

Quindi :

1. Confrontiamo il 5 con il -543 e vediamo che sono da scambiare e quindi lo facciamo
   Otteniamo così la seguente situazione: -543, 5, 0, 1, 92

2. Confrontiamo il 5 con lo 0 e vediamo che  sono da scambiare
   Otteniamo così la seguente situazione: -543, 0, 5, 1, 92

3. Confrontiamo il 5 con l' 1 e vediamo che anche questi sono da scambiare

Otteniamo così la seguente situazione: -543, 0, 1, 5, 92

Come accennato prima non facciamo l'ultimo controllo perché sappiamo già che il maggiore si trova in fondo quindi passiamo alla serie seguente di confronti con un'altra modifica, non confronteremo non solo l'ultimo elemento ma ora anche il penultimo (per lo stesso motivo). Quindi:

1. Confrontiamo il -543 con lo 0 e vediamo che sono in posizione corretta (-543 < 92)

2. Confrontiamo lo 0 con l' 1 e vediamo che sono in posizione corretta (0 < 1)

Con questo metodo, al massimo si devono fare n-1 cicli (dove n è il numero di elementi da confrontare) ognuno dei quali sarà composto da n-m confronti (dove n è sempre il numero di elementi da confrontare e m è il numero della ciclo di controlli che si sta effettuando).

es. 5 elementi: nel caso peggiore ci sarebbero da fare:

5 -1 = 4 cicli

con al loro interno:

5 -1=4 confronti per il primo ciclo

5-2=3 confronti per il secondo ciclo

5-3=2  per il terzo ciclo

5-4=1 per il quarto ciclo
In totale 4+3+2+1=10 confronti