Capitoli

Il corso in breve

L'avvertenza che conta

Il corso insegna due cose distinte, che avanzano in parallelo ma restano indipendenti:

1. Analizzare i problemi e inventare algoritmi che li risolvano → attività creativa;
2. Codificare quegli algoritmi in programmi scritti in C89 → attività di codifica, con un certo grado di creatività.

Questi appunti tengono separate le due cose: i capitoli 1–2 sono sul ragionamento (pseudocodice e diagrammi di flusso), i capitoli 3–5 sulla codifica.

Stato degli appunti

Coperto finora, dal materiale disponibile al 21 settembre 2026:

Che cos'è l'informatica

L'oggetto dell'informatica è l'informazione: come ricavare ciò che non si sa (e che interessa) a partire da ciò che si sa.

Due definizioni equivalenti, entrambe usate a lezione:

• scienza dell'elaborazione dell'informazione (e della sua rappresentazione);
• scienza degli algoritmi.

Il corso è progettuale, come tutta l'ingegneria: si impara a ragionare per ideare algoritmi e scrivere programmi che risolvano un problema assegnato. Servono pochissime conoscenze disciplinari: è ragionamento puro.

La nozione di algoritmo ne richiede altre due, che vanno definite prima: problema ed esecutore.

Il problema: la terna (I, O, R)

L'esecutore

Un esecutore tipico per i nostri esempi sa fare solo questo:

• acquisizione dei dati (lettura);
• produzione dei risultati (scrittura);
• addizione di due numeri;
• sottrazione fra due numeri;
• confronto fra due numeri (calcolo dell'esito vero / falso);
• memorizzazione di un valore in un contenitore (vedi più avanti).

L'algoritmo

Esempio: l'opposto di un numero intero

1. Acquisisci un numero intero
2. Sottrai dal valore 0 il valore del numero acquisito
3. Produci in uscita il risultato della sottrazione
4. TERMINA

Qui i passi sono eseguiti uno dopo l'altro: è una pura sequenza.

Esempio: il massimo fra due numeri naturali

1. Acquisisci due numeri naturali in ingresso
2. Confronta il valore dei due numeri
3. Se il primo numero è maggiore del secondo
3.1    produci il primo numero come risultato in uscita
   Altrimenti
3.2    produci il secondo numero come risultato in uscita
4. TERMINA

Qui compare una selezione: i passi 3.1 e 3.2 sono alternativi, non verranno mai eseguiti entrambi.

Le proprietà che rendono un algoritmo tale

La memorizzazione: i contenitori

La notazione usata a lezione è la freccia:

A ← B - C
A ← B - 3

Sono due passi in uno:

1. si calcola la sottrazione fra due valori (ciascuno può essere contenuto in un contenitore, come B e C, oppure un valore non memorizzato, come 3);
2. si memorizza il risultato nel contenitore A. Da quel momento il valore resta lì, inalterato, fino a un eventuale futuro A ← … che lo sovrascrive: del vecchio valore si perde ogni memoria.

Un algoritmo minimo che lo usa: lo scambio

Le tre strutture di controllo

I «modi» per combinare i passi elementari si chiamano strutture di controllo. Sono tre, e bastano tutte e sole queste per esprimere qualunque algoritmo:

1 · Sequenza

Un passo dopo l'altro, nell'ordine scritto. L'algoritmo dell'opposto è tutto qui.

2 · Selezione

Durante l'esecuzione viene esaminata una condizione. Se risulta vera si esegue una certa sequenza di passi, se risulta falsa se ne esegue una diversa. Le due sequenze sono alternative: non verranno mai eseguite entrambe. Il ramo «altrimenti» può anche essere vuoto (non fare nulla).

3 · Iterazione (ciclo)

Un ciclo è caratterizzato da una condizione e da una sequenza di passi. Quando la computazione raggiunge la condizione la valuta:

• se risulta falsa, il corpo non viene eseguito e si passa oltre;
• se risulta vera, esegue i passi del ciclo e poi torna a valutare la condizione.

Diagrammi di flusso

Il diagramma di flusso rende visibile il percorso della computazione. Stessa cosa del pseudocodice, vista da un'altra angolazione: utile quando devi convincerti che tutti i cammini finiscono davvero in «Fine».

La versione eseguibile passo passo di questo algoritmo è nel capitolo 2.

Il livello di dettaglio è una scelta

Lo stesso algoritmo si può disegnare a granularità diverse, a seconda di che cosa l'esecutore sa fare. Se l'esecutore non ha il confronto diretto ma solo la sottrazione, il blocco X > Y ? si espande in due passi:

D ← X - Y
D > 0 ?

È la stessa idea del passaggio dal problema al programma: si decompone un passo complesso in sottopassi semplici finché ogni pezzo è eseguibile.

Il metodo di lavoro

1 · Divisione intera per sottrazioni ripetute

Esecutore: lettura, scrittura, addizione, sottrazione, confronto fra naturali, memorizzazione. Non possiede la divisione: è proprio quello che dobbiamo costruire.

2 · Logaritmo intero in base B

Esecutore: come sopra, ma con la divisione intera fra i passi elementari.

3 · Massimo di una sequenza

Leggi in sequenza valori interi positivi, in quantità non specificata, fino al primo valore negativo (che segnala la fine della lettura), e stampa il massimo fra i valori positivi letti. Se non viene letto alcun valore positivo, stampa 0.

4 · Massimo comun divisore (Euclide)

5 · Ricerca sequenziale

La ricerca «dello schedario»: esamina la prima scheda; se autore e titolo coincidono la ricerca è conclusa con successo, altrimenti passa alla scheda successiva; ripeti fino a conclusione o fino a raggiungere l'ultima scheda.

6 · Ricerca dicotomica in una sequenza ordinata

Esecutore (descrizione specifica): accedere all'elemento in una determinata posizione, memorizzare, addizione/sottrazione/divisione intera, confronto.

Prima di arrivarci: due versioni che NON funzionano

Vale la pena vedere gli errori, perché sono gli stessi che farai tu la prima volta.

Errore 1 — le due metà coprono tutta la porzione

Se la «prima metà» comprende l'elemento centrale (Fine ← Media) invece di escluderlo, la porzione può smettere di rimpicciolirsi. Prova a cercare 3 nella sequenza 2 5:

Errore 2 — non si gestisce la porzione vuota

Escludendo il centro si può benissimo arrivare a una porzione vuota: è il caso in cui l'elemento è assente. Bisogna accorgersene e terminare esplicitamente con insuccesso, altrimenti non si sa nemmeno quale sia «l'elemento centrale» di una porzione di zero elementi.

La versione corretta

0. Acquisisci la sequenza ordinata e il numero da cercare
1. Inizio ← posizione del primo elemento
2. Fine   ← posizione dell'ultimo elemento
3. mentre (Inizio <= Fine) esegui          /* porzione attuale non vuota */
3.1    Media ← (Inizio + Fine) / 2          /* divisione intera */
3.2    se (A[Media] == cercato)
3.2.1      produci Media e STOP
       altrimenti
3.2.2      se (cercato < A[Media])
3.2.2.1        Fine ← Media - 1             /* prima metà, centro escluso */
           altrimenti
3.2.2.2        Inizio ← Media + 1           /* seconda metà, centro escluso */
4. produci -1                               /* numero non presente */
5. STOP

Quanto conviene davvero

Ogni confronto dimezza la porzione: il numero di confronti è circa il logaritmo in base 2 di N — lo stesso algoritmo del §2 di questa pagina, con B = 2.

Riepilogo

Componenti della macchina C

Le idealizzazioni: perché «astratta»

La macchina C che studiamo è una semplificazione di quella reale:

• non c'è nessun limite al numero delle celle (memoria infinita);
• non c'è nessun limite al valore numerico contenuto;
• i contenitori si raggiungono tramite un nome, non tramite un indirizzo numerico;
• un contenitore può occupare una o più celle, a seconda del tipo di dato, senza che ce ne occupiamo.

Su che cosa si può operare

• sui valori contenuti nelle variabili;
• su valori direttamente riconoscibili dal C, cioè scritti nel testo del programma:
  • numeri interi relativi: 23, -64
  • numeri reali: 5.0, 2.34, -43.56
  • caratteri: 'h', '8', ' ' (spazio), '.'
  • stringhe: "carta", "MNZLSS34L03F205T" — sequenze di caratteri in celle adiacenti (cap. 5)

E come non si perdono i risultati delle operazioni? Memorizzandoli, anche solo temporaneamente, in contenitori.

Identificatori e parole chiave

• Le maiuscole sono distinte dalle minuscole: Var1, var1 e VAR1 sono tre identificatori diversi.
• Per evitare ambiguità non si può usare lo stesso identificatore per elementi diversi, né identificatori diversi per lo stesso elemento.

Struttura di un programma C

direttive per il compilatore        /* es. #include <stdio.h> */
definizioni di tipo                 /* … vedremo in seguito … */

int main()                          /* intestazione del programma principale */
{
    dichiarazioni                   /* quali contenitori userò e di che tipo */
    istruzioni                      /* i passi da eseguire */
    return(0);                      /* finale convenzionale */
}

altri sottoprogrammi                /* … vedremo in seguito … */

Contenitori: perché servono le dichiarazioni

Un contenitore, visto da vicino, è:

In linguaggio macchina si identifica un contenitore con l'indirizzo (come «via Metastasio 76»); in C con un nome, l'identificatore (come «Palazzo Madama»).

I tipi di dato

char  carA;   /* conterrà valori di tipo char: un carattere */
int   n;      /* conterrà valori di tipo int: un intero relativo */
float x;      /* reale in virgola mobile, singola precisione */
double y;     /* reale in virgola mobile, doppia precisione */

Costanti

Un contenitore può essere dichiarato costante: riceve un valore che il programma non potrà modificare.

const float Pi = 3.1415;   /* il valore non sarà modificabile dal programma */

Esiste anche la direttiva #define, che non crea un contenitore ma dice al compilatore di sostituire testualmente un nome con un testo, prima di compilare:

#define MAX 100      /* ovunque compaia MAX, il compilatore scrive 100 */
#define base 2

Espressioni

La definizione è ricorsiva: un'espressione è

<espressione> :=  <valore riconoscibile dal C>              oppure
                  <nome di una variabile>                    oppure
                  <nome di una costante>                     oppure
                  <espressione> <operatore aritmetico> <espressione>

<operatore aritmetico> :=  +   -   *   /   %

Esempi:

La complessità è in teoria illimitata; per le parentesi valgono le stesse regole della matematica.

Dove si trovano le espressioni

1. Nelle istruzioni di assegnamento: n = (m+3)*(n - 23*m);
2. Nelle istruzioni di uscita: printf("meta' di n: %d", n/2);
3. Nelle condizioni (qui sotto).

Condizioni

<valore logico> := false, true

<operatore di confronto> :=  <   <=   >   >=   ==   !=

<operatore logico> :=  &&   ||   !

<condizione elementare> :=  <valore logico>   oppure
                            <espressione> <operatore di confronto> <espressione>

<condizione> :=  <condizione elementare>   oppure
                 <condizione> <operatore logico> <condizione>

Operatori logici e tabelle di verità

• ! negazione (non): data una condizione C, !C ha valore di verità opposto;
• && congiunzione (e): C1&&C2 è vera solo quando entrambe sono vere;
• || disgiunzione (o): C1||C2 è falsa solo quando entrambe sono false.

Esempi di lettura:

• !(x==4) → x NON è uguale a 4
• (x<10)&&(y>=100) → x minore di 10 e y maggiore o uguale a 100
• (y==1)||(z!=2) → y è uguale a 1 oppure z è diverso da 2
• (n <= -7) || (n >= 7) → il valore assoluto di n è almeno 7

Precedenze… e come non pensarci

La regola del risparmio (valutazione in corto circuito)

Non è una curiosità: è ciò che rende corretto (e non solo veloce) uno schema che userai continuamente:

while (i < MAX && Sequenza[i] != cercato)
    i = i + 1;
/* se i < MAX è falsa, Sequenza[i] NON viene valutato:
   non si accede a un elemento fuori dall'array */

Invertire le due clausole romperebbe il programma. L'ordine delle clausole, qui, è parte del ragionamento.

Tipi, espressioni e conversioni

Regola 1 — nelle espressioni: vince il tipo più ricco

Se in un'espressione compare un'operazione fra dati di tipo diverso, il C usa come operandi valori del tipo più ricco.

int   n = 4;
float x = 2.13;
int   y;
y = n * x;

Nell'espressione n * x si usa, invece dell'intero 4, il float 4.0 (stesso valore matematico): l'operazione diventa 4.0 * 2.13 e il risultato è il float 8.52.

Regola 2 — nell'assegnamento: vince il tipo del contenitore

Se il tipo della variabile e il tipo del risultato dell'espressione sono diversi, il C assegna un valore dello stesso tipo della variabile. Tale valore può:

1. avere lo stesso valore matematico del risultato — es. x = n; assegna 4.0 a un float;
2. essere un arrotondamento (troncamento) — es. y = n * x; con y intero assegna (int)8.52, cioè 8.

Casting esplicito

Quando la conversione automatica non scatta ma ci serve, la si chiede esplicitamente con (tipo)espressione. Caso tipico: la media di due interi.

int somma = 7, cont = 2;
float media;
media = somma / cont;                     /* 3.0  — divisione INTERA: 7/2 = 3, poi convertito */
media = (float)somma / (float)cont;       /* 3.5  — divisione reale: CORRETTO */

Provalo

char e int

• Gli operatori aritmetici possono essere applicati a valori char, trattandoli come interi (si usa il loro codice ASCII).
• Si possono eseguire operazioni fra int e char, ma spesso non hanno alcun significato e derivano da errori.
• Eccezione utile: la differenza fra la versione maiuscola e minuscola della stessa lettera (es. 'R' e 'r') è la stessa per tutte le lettere alfabetiche, e si può usare per convertire fra minuscolo e maiuscolo.

Assegnamento

<nome di variabile> = <espressione>;

n = 18;
A = (A * 15.3) - B / (f + 32.1);
cont++;            /* equivale a cont = cont + 1; */

È la traduzione in C del passo A ← … del capitolo 1: prima si valuta tutta l'espressione a destra, poi si scrive il risultato nel contenitore a sinistra.

Ingresso e uscita

scanf — lettura

scanf("%d", &n);   /* legge da tastiera un valore e lo memorizza come intero in n */

printf — scrittura

printf(" n vale %d e \n la parola ha \n %d caratteri", n, n + 3);

Gli argomenti dopo la stringa di formato sono espressioni: possono essere calcolate sul posto, come n + 3 o n/2.

Provalo: formati e argomenti

Istruzione condizionale (selezione)

if ( <condizione> ) {
    <istruzioni da eseguire se la condizione è vera>
}
else {
    <istruzioni da eseguire se la condizione è falsa>
}

Il ramo else è facoltativo.

Esempio: valore assoluto di un numero reale

#include <stdio.h>
int main(){
    float x;
    scanf("%f", &x);
    if (x < 0.0)
        x = -x;
    printf("\n valore assoluto: %f", x);
    return 0;
}

Qui il ramo «altrimenti» è vuoto: se il numero è già positivo non c'è niente da fare.

Esempio: massimo e minimo di due numeri

#include <stdio.h>
int main(){
    int m, n;
    int max, min;
    scanf("%d", &m);
    printf("\n");
    scanf("%d", &n);
    if (m > n) {
        max = m;
        min = n;
    }
    else {
        max = n;
        min = m;
    }
    printf("\n massimo: %d, minimo: %d", max, min);
    return 0;
}

Iterazione: while

while ( <condizione> ) {
    <istruzioni>
}

La condizione è valutata prima di ogni esecuzione del corpo: il corpo può essere eseguito zero volte.

Esempio: calcolo di potenze intere

#include <stdio.h>
int main(){
    int base;
    int esponente;
    int potenza;
    int contatore;
    scanf("%d", &base);
    scanf("%d", &esponente);
    potenza = 1;
    contatore = 0;
    while (contatore < esponente) {
        potenza = potenza * base;
        contatore = contatore + 1;
    }
    printf("\n %d alla %d: %d", base, esponente, potenza);
    return 0;
}

Modifica: la massima potenza che non supera una soglia

Calcolare la massima potenza di una base che non superi una data soglia. Se la base è 10 e la soglia 93017, la risposta è 10000.

#include <stdio.h>
int main(){
    int base;
    int soglia;
    int potenza;
    scanf("%d", &base);
    scanf("%d", &soglia);
    potenza = 1;
    while (potenza*base <= soglia)
        potenza = potenza * base;
    printf("\n massima potenza di %d <= %d: %d", base, soglia, potenza);
    return 0;
}

Esempio: logaritmo intero

Per quante volte posso dividere un numero per un valore senza che il risultato scenda sotto 1? (È l'algoritmo del cap. 2 §2.)

#include <stdio.h>
int main(){
    int base;
    int numero, numcorrente;
    int logaritmo;
    printf("\n digita una base intera > 1 \n");
    scanf("%d", &base);
    printf("\n digita il numero positivo di cui calcolare il logaritmo \n");
    scanf("%d", &numero);
    numcorrente = numero;
    logaritmo = 0;
    while (numcorrente >= base) {
        numcorrente = numcorrente / base;
        logaritmo = logaritmo + 1;
    }
    printf("\n log di %d in base %d: %d", numero, base, logaritmo);
    return 0;
}

Iterazione: do-while

do {
    <istruzioni>
}
while ( <condizione> );

Qui la condizione è valutata dopo il corpo: il corpo viene eseguito almeno una volta.

Esempio: lettura di un dato con criterio di validità

Continua a chiedere il dato finché la condizione di validità non è soddisfatta.

#include <stdio.h>
int main(){
    int dato;
    do {
        printf("\n digita un intero positivo < 10");
        scanf("%d", &dato);
    }
    while (dato < 0 || dato >= 10);
    /* qui dato è sicuramente valido */
    return 0;
}

Iterazione: for

for ( istruzione1 ; condizione ; istruzione2 ) {
    <istruzioni>
}

• istruzione1: eseguita una sola volta, prima di iniziare il ciclo;
• condizione: se vera si reitera, se falsa si esce;
• istruzione2: eseguita al termine di ciascuna iterazione, subito prima di rivalutare la condizione.

for (cont = 0; cont < esponente; cont++)
    potenza = potenza * base;

equivale esattamente a

cont = 0;
while (cont < esponente) {
    potenza = potenza * base;
    cont++;
}

Programmi completi

Sommatoria di interi letti (termina al primo negativo)

#include <stdio.h>
int main(){
    int nletto;
    int somma = 0;                  /* assegnamento in fase di dichiarazione */
    scanf("%d", &nletto);           /* prima lettura, fuori dal ciclo */
    while (nletto >= 0) {
        somma = somma + nletto;     /* accumulatore */
        scanf("%d", &nletto);       /* lettura in coda al corpo */
    }
    printf("Sommatoria = %d", somma);
    return(0);
}

Stesso schema «leggi–elabora–rileggi» del massimo di una sequenza: cambia solo che cosa si fa con il valore letto.

Media di interi letti — con casting esplicito

#include <stdio.h>
int main(){
    float media;
    int nletto;
    int somma, cont;
    somma = 0;
    cont = 0;
    scanf("%d", &nletto);
    while (nletto >= 0) {
        somma = somma + nletto;
        cont++;                      /* equivale a cont = cont + 1; */
        scanf("%d", &nletto);
    }
    media = (float)somma / (float)cont;
    printf("\n Media = %f", media);
    return(0);
}

MCD, algoritmo di Euclide

#include <stdio.h>
int main(){
    int m, n;
    int resto;
    int temp;
    scanf("%d%d", &m, &n);
    if (n > m) {              /* scambio: metto il maggiore in m */
        temp = m;
        m = n;
        n = temp;
    }
    while (m % n != 0) {
        resto = m % n;
        m = n;
        n = resto;
    }
    printf("Massimo comune divisore = %d", n);
    return(0);
}

Lo scambio iniziale è, riga per riga, l'algoritmo del cap. 1. La simulazione passo passo è nel cap. 2 §4.

Cifre binarie di un numero frazionario — casting automatico

Stampare le prime 8 cifre in base 2 di un numero frazionario x, con 0 < x < 1.

#include <stdio.h>
#define base 2
#define Max 8
int main(){
    float x;
    int cifra;
    int cont;
    printf("\n digita un valore reale tra 0 e 1 \n");   /* segnala all'utente l'attesa */
    scanf("%f", &x);
    cont = 0;
    while (x > 0 && cont < Max) {
        cifra = x * base;      /* l'espressione vale x*2.0: il valore viene
                                  troncato all'intero e assegnato a cifra */
        printf("%d", cifra);
        x = x * base - cifra;  /* qui il risultato resta float: nessun troncamento */
        cont++;
    }
    return(0);
}

Conversione in maiuscolo — codici ASCII

Leggi caratteri alfabetici fino a un terminatore (un carattere non alfabetico) e converti ciascun carattere minuscolo in maiuscolo, lasciando inalterati i maiuscoli.

#include <stdio.h>
int main(){
    char cletto;
    char convertito;
    scanf("%c%*c", &cletto);
    while ((cletto >= 'a' && cletto <= 'z') ||
           (cletto >= 'A' && cletto <= 'Z')) {
        if (cletto >= 'a' && cletto <= 'z')
            convertito = cletto + 'A' - 'a';
        else
            convertito = cletto;
        printf("%c", convertito);
        scanf("%c%*c", &cletto);
    }
    return(0);
}

Linee guida di stile

Che cos'è un array

float SequenzaFloat[11];   /* ha undici (11) elementi */
char  parola[30];          /* ha trenta (30) elementi */
int   elenco[100];         /* ha cento (100) elementi */

I singoli elementi sono contenitori a tutti gli effetti:

parola[0]            /* il PRIMO carattere nell'array parola */
SequenzaFloat[6]     /* il SETTIMO float nell'array SequenzaFloat */
elenco[99]           /* l'ULTIMO intero in elenco */

Assegnare un valore a un elemento

La forma generale dell'assegnamento si estende così:

<nome di variabile>        = <espressione>;
<indicazione di contenitore> = <espressione>;

parola[0] = 'd';
SequenzaFloat[6] = 3.14 * 2.0;
SequenzaFloat[8] = SequenzaFloat[6] * 4.0;

Inizializzazione contestuale alla dichiarazione

int A[10] = {10, 7, 5, 5, 1, 7, 7, 8, 6, 9};
int trovato = 0;

int A[10];
int B[10];
A = B;      /* NON SI PUO' FARE !!! */

for (i = 0; i < 10; i++)   /* occorre copiare elemento per elemento */
    A[i] = B[i];

#define MAX 100
int main(){
    int A[50];
    int B[MAX/2 + 1];    /* ok: il compilatore sa calcolarlo */
    /* int C[n];            NO: n è una variabile */
}

Per dimensioni davvero variabili servono altre strutture (liste dinamiche, array dinamici): le vedremo più avanti nel corso.

Scorrere un array

#include <stdio.h>
#define MAX 10                    /* direttiva: sostituisce MAX con 10 */
int main(){
    int Sequenza[MAX];
    int i;
    for (i = 0; i < MAX; i++)          /* lettura: dall'inizio alla fine */
        scanf("%d", &Sequenza[i]);
    for (i = MAX-1; i >= 0; i--)       /* stampa: dalla fine all'inizio */
        printf(" %d ", Sequenza[i]);
    return 0;
}

La stampa in ordine inverso si può ottenere anche scorrendo in avanti e «riflettendo» l'indice:

for (i = 0; i < MAX; i++)
    printf(" %d ", Sequenza[MAX-1-i]);

Quando i vale 0 si legge l'ultimo elemento, quando vale MAX−1 si legge il primo: stesso risultato, schema di conteggio diverso. Verifica sempre i due estremi quando scrivi un'espressione di indice.

Ricerca in un array

Elenco non ordinato — con variabile sentinella

#include <stdio.h>
#define MAX 100
int main(){
    int i;
    int trovato = 0;          /* sentinella: "l'ho già trovato?" */
    float Sequenza[MAX];
    float cercato;
    /* … qui il popolamento dell'array … */
    scanf("%f", &cercato);
    i = 0;
    while (i < MAX && trovato == 0) {
        if (Sequenza[i] == cercato)
            trovato = 1;
        else
            i = i + 1;        /* avanzo solo se NON ho trovato */
    }
    if (trovato == 1)
        printf("numero %f trovato in posizione %d", cercato, i);
    else
        printf("numero %f non presente", cercato);
    return 0;
}

Versione alternativa — senza sentinella

#include <stdio.h>
#define MAX 10
int main(){
    int i;
    float Sequenza[MAX] = {12, 5, 6, 1, 7, 9, 3, 11, 14, 8};
    float cercato;
    scanf("%f", &cercato);
    i = 0;
    while (i < MAX && Sequenza[i] != cercato)
        i = i + 1;
    if (i < MAX)
        printf("numero %f trovato in posizione %d", cercato, i);
    else
        printf("numero %f non presente", cercato);
    return 0;
}

Elenco ordinato — ricerca dicotomica

#include <stdio.h>
#define MAX 100
int main(){
    int min, max, med;
    int trovato = 0;
    float Sequenza[MAX];
    float cercato;
    /* … qui il popolamento dell'array … */
    min = 0;
    max = MAX - 1;
    scanf("%f", &cercato);
    while (min <= max && trovato == 0) {
        med = (min + max)/2;
        if (Sequenza[med] == cercato)      trovato = 1;
        else if (cercato < Sequenza[med])  max = med - 1;
             else                          min = med + 1;
    }
    if (trovato == 1)
        printf("numero %f trovato in posizione %d", cercato, med);
    else
        printf("numero %f non presente", cercato);
    return(0);
}

È la codifica dell'algoritmo del cap. 2 §6; qui l'uscita dal ciclo è resa esplicita dalla variabile sentinella trovato, invece che da uno STOP in mezzo al ciclo. Ripasso interattivo:

Rappresentazione di un numero in una base

Rappresentare un numero naturale in base B usando un array di cifre.

#include <stdio.h>
#define base 2
#define MAX 32
int main(){
    int n, i;
    int SequenzaCifre[MAX];          /* array di MAX cifre */
    scanf("%d", &n);
    if (n == 0) printf("%d", 0);
    else {
        i = MAX - 1;                 /* ultima posizione */
        while (n > 0 && i >= 0) {
            SequenzaCifre[i] = n % base;
            n = n / base;
            i = i - 1;               /* retrocedo di una posizione */
        }
        if (n > 0) printf("valore eccede i limiti");
        else {
            i = i + 1;
            while (i < MAX) {
                printf("%d", SequenzaCifre[i]);
                i = i + 1;           /* avanzo di una posizione */
            }
        }
    }
    return(0);
}

Massimi locali: quando modificare i dati rovina il confronto

Azzerare gli elementi di un array che non sono massimi locali (un elemento è massimo locale se è strettamente maggiore dei suoi vicini immediati).

#define N 10
int main(){
    int A[N] = {10,7,5,5,1,7,7,8,6,9};
    int prec, i;
    /* primo elemento: unico vicino è A[1] */
    prec = A[0];
    if (A[0] <= A[1]) A[0] = 0;
    /* elementi intermedi */
    for (i = 1; i < N-1; i++)
        if (A[i] <= prec || A[i] <= A[i+1]) {
            prec = A[i];       /* salvo PRIMA di azzerare */
            A[i] = 0;
        }
        else prec = A[i];
    /* ultimo elemento: unico vicino è prec */
    if (A[N-1] <= prec) A[N-1] = 0;
    for (i = 0; i < N; i++)
        printf("\n A[%d] = %d", i, A[i]);
    return 0;
}

Stringhe

Spesso ci sono elementi dell'array non utilizzati. Per un cognome di 7 caratteri, «Zanardi», in un array Arr di 20 elementi:

Inversione di una stringa

#include <stdio.h>
#define MAX 30
int main(){
    int i;
    char Parola[MAX];
    scanf("%s", Parola);
    i = 0;
    while (i < MAX-1 && Parola[i] != '\0')   /* cerco il terminatore */
        i = i + 1;
    if (Parola[i] == '\0')
        i = i - 1;                            /* ultimo carattere utile */
    while (i >= 0) {
        printf("%c", Parola[i]);
        i = i - 1;
    }
    return(0);
}

Le due fasi sono nettamente distinte: prima si trova dove finisce la stringa, poi si scorre all'indietro. Esercizio suggerito a lezione: seguire l'evoluzione della memoria durante l'esecuzione.

Stringhe palindrome

int main(){
    char Str[30];
    int i, j;
    scanf("%s", Str);
    j = 0;
    while (j < 30 && Str[j] != '\0') j++;   /* cerco il terminatore */
    j--;                                     /* ultimo carattere utile */
    i = 0;
    while (i < j && Str[i] == Str[j]) {
        j--;
        i++;
    }
    if (i >= j) printf("palindroma");
    else        printf("non palindroma");
    return 0;
}

Prossimi argomenti

Dal programma del corso, non ancora coperti da questi appunti: la codifica binaria dell'informazione, i sottoprogrammi, la memorizzazione persistente mediante file, l'allocazione dinamica della memoria e la ricorsione come tecnica di risoluzione dei problemi. Man mano che le lezioni procedono, si aggiungono qui.