Corso di Fondamenti di Informatica A

Scrivere un programma C che legga un intero positivo e visualizzi un messaggio per indicare se il numero è primo.
Il programma deve contenere due funzioni:

• la funzione pari() che ha come parametro di ingresso un intero e restituisce 1 se il numero è pari, 0 altrimenti.
• la funzione primo() che ha come parametro di ingresso un intero e restituisce 1 se il numero è primo, 0 altrimenti.

Funzione pari()

Specifica: se N è divisibile per 2 restuisci 1, altrimenti restituisci 0.

Codifica:
int pari(int n)
{
 if (n%2 == 0) return 1; /* se il resto della divisione e' 0 ... */
 else return 0;
}

Ma il C permette anche di utilizzare una scrittura sintetica (e poco leggibile!):

int pari(int n){return !(n%2);}
 
 

Funzione primo()

Specifica di I livello: occorre provare a dividere N per tutti i numeri K <= [sqrt(N)]: se nessuno risulta essere un divisore, allora N è primo (con [.] si è indicata la parte intera).

Specifica di II livello:

• Se N è 1, 2 o 3, allora è primo senz’altro.
• Altrimenti, se è un numero pari, certamente non è primo.
• Se così non è (quindi N è dispari e >3), occorre tentare tutti i possibili divisori da 3 in avanti, fino a sqrt(N).

int primo(int n) {
    int max,i;
    if (n>=1 && n<=3) return 1;  /* 1,2,3 ? ok */
    if (pari(n)) return 0;  /* no numeri pari */
    max = sqrt(n);
    for(i=3; i<=max; i+=2)
        if (n%i==0) return 0;
    return 1;
}
 

Ed infine il main:

main()
{
 int n,i;
 printf("n = ");
 scanf("%d",&n);
 if (primo(n)) printf("Il numero %d e' primo\n",n);
 else printf("Il numero %d non e' primo\n",n);
}

Ricordarsi di inserire le due direttive #include <stdio.h> e #include <math.h>

Esercizio: Calcolo della somma dei primi N numeri interi

• Scrivere un programma C che, dato un numero N, calcola la somma dei primi N numeri interi in maniera ricorsiva.
• Visualizzare passo passo l'esecuzione del programma osservando come variano i valori delle variabili ed lo stack di chiamate a funzione (in Rhide, menu Debug -> Call Stack).
• Progettare e codificare la versione tail-ricorsiva della funzione.

Soluzione (versione tail-ricorsiva)

Si utilizza una funzione di interfaccia int sumtail(int) che provvede a chiamare la funzione tail-ricorsiva inizializzando correttamente i parametri.

int sumtail2(int n, int v, int k)
{
 if (k<=n)
 {
  v = v + k;
  k++;
  sumtail2(n,v,k);
 }
 else return v;
}

int sumtail(int n){return sumtail2(n,0,1);}

Esercizio: Prodotto di due numeri

Soluzione: funzione ricorsiva

Caso generale: x * y = (x - 1) * y + y
Caso base: 0*y = 0

Codifica:
int prod(int x, int y)
{
 if (x>0) return y+prod(x-1,y);
 else return 0;
}
 

Soluzione: funzione tail-ricorsiva

Anche in questo caso si utilizza una funzione di interfaccia.

int prod_tail2(int x,int y,int v,int k)
{
 if (k<=x)
 {
  v = v + y;
  k++;
  return prod_tail2(x,y,v,k);
 }
 return v;
}

int prod_tail(int x,int y){ return prod_tail2(x,y,0,1);}