Corso LP 98/99 Esercizi cartacei

Esercizio 1
  1. Qual'è il valore della funzione Ric data sotto per n=5 e n=7?
    int Ric(int n)
    { 
      if(n <= 0)  return 0;
      else if((n == 1) || (n == 2)   return 1;
      else return (Ric(n - 2) + Ric(n - 3));
    }
  2. Scrivere una versione non ricorsiva della funzione Ric.

Esercizio 2
  1. Trasformare il numero ottale 103 in un numero decimale.
  2. Trasformare il numero decimale 505 in un numero ottale.

Esercizio 3
Sono equivalenti le seguenti funzioni C,
cioè ritornano gli stessi risultati quando ricevono in input gli stessi valori.
int F1(int a, int b)
{
   int c = 0;
    
   for(c=a; c > 0; c--)
      if(a % c == 0) 
         if(c == b) return 1;
   return 0;
}

int F2(int x, int y)
{   return (x % y ? 1 : 0);   }

Esercizio 4
Dire che cosa è l'output dei seguenti programmi C:
  1. #include <stdio.h>
    
    int z = 0;
    void sss(void);
    void ttt(void);
    
    main( )  
    {  int z = 1;
       sss();
       ttt();
    }
    
    void ppp(void);
    
    void sss(void)  
    {   ppp();   }
    
    void ttt(void)  
    {
        int z = 2;
        ppp();
    }
    
    void ppp(void)  
    {   printf("%d     \n", z);   }
  2. #include <stdio.h>
    #include <stdlib.h>
    
    void sss(int * x);
    
    main()  
    {
        int * p, * q;    
        p = (int*) malloc(sizeof(int));
        *p = 5;
        q = p;
        sss(q);
        printf("%d \n", *p);
    }
    
    void sss(int * x)    
    {   *x = 3;    }
  3. #include <stdio.h>
    #define  Z  3
    				
    int x = 1;					
    void p1(void);
    void p2(int);
    
    main()  
    {  int x = 2;   
       p1();    
       p2(x);    
    }
    
    void p1(void)  
    {   printf("%d \n", x);  }
    
    int y = Z + 1;  
     
    void p2(int a)  
    {   printf("%d  %d \n", a, y); }
  4. #include <stdio.h>
    
    void ppp(int * x, int  *y);
    
    main()  
    {   int a = 2; 
        ppp(&a, &a);
        printf("%d\n", a);
    }
    
    void ppp(int * x, int *y)   
    {   *y = - *y;
        *x = *x + *y;
    }

Esercizio 5
Si consideri il seguente codice C:
#include <stdio.h>

main( )
{    
   int a = 2; b = 4;     
   cambia(&a, &b);
   printf("%d ,  %d\n", a, b);
}

void cambia(int * x, * y)
{   
   y = x;
   *y = 3;						 
}
  1. Dire quali errori ci sono e correggerli.
  2. Dire poi qual'è l'output della versione corretta ?

Esercizio 6
Si consideri la seguente procedura scritta in pseudo codice:
procedura somma(aa: array [1..n] di interi, parametro variabile;
                sin, des: interi che servono da indici, parametri valore)
variabili locali: sum, centro, k di tipo intero

if sin <= des then
   {   sum <- 0
       for k =  sin, sin+1,..., des
          sum <- sum + aa[k]
       scrivi sum  e vai a capo sull'output
       centro <- (sin + des) divisione intera 2 
       somma(aa, sin, centro-1)
       somma(aa, centro+1, des)
   }
  1. Scrivere una procedura C corrispondente.
  2. Discutere della sua complessità in tempo.
  3. Dire qual'è l'output prodotto dalla chiamata
    somma(aa, 1, 6) se n = 6 ed aa = 1, 1, 1, 1, 1, 1.

Esercizio 7
Si consideri il seguente codice C:
#include <stdio.h>
#include <stdlib.h>

main( )   
{
   int n;
   scanf("%d", &n);
   {   char *y;
       int  k;
       
       y = (char *) calloc(n,sizeof(char));
       for(k = 0; k < n; k++)   
          *(y+k) = k; 
       for(k = n-1; k >= 0; --k)  
          printf("%d, ", y[k]);
   };
   printf("\n");
}
Qual'è l'output se in input, per n, diamo 9 ?
Esercizio 8
Discutere l'effetto dell'esecuzione del seguente frammento al variare del valore di a e di b.
int a,b;
....
if(a>0) 
  if(b>0) printf("ok"); 
else printf("ok");

Esercizio 9
Modificare il ciclo nel seguente frammento di codice C, dove N è una costante,
in modo che se cond(i,j) è soddisfatta per un qualche i e j
  1. si esce dal "for" più interno ma non da quello più esterno.
  2. si esce da entrambi i cicli "for".
int cond(int i, int j); /*boolean function*/

main()
{
   int i, j, r;
   for(i=0;i < N;i++)
      for(j=0;j < N;j++) 
         r = cond(i,j);

Esercizio 10
Si consideri il seguente frammento di programma C:
#define N 120

main()
{
   char a[N], b[N]; int i;

   for(i=0; a[i]; i++) 
      b[i]=a[i];
   b[i]='\0';
  1. Che cosa fa?
  2. Utilizzate l'istruzione "while" per ottenere lo stesso risultato;
  3. Utilizzate l'istruzione "do ... while" per ottenere lo stesso risultato.

Esercizio 11
Cosa fanno i seguenti frammenti di codice C?
  1. int i=0;
    while(i < 50){
       if(i%2) 
          printf("%d\n",i);
       i++; 
    }
  2. int i;
    for(i=0; i < 50;i++);
       if(i%2) 
          printf("%d\n",i);
  3. int p(int x, int n) {  return(x-n);  } 
       
    main()
    {
       int x;
       while(p(x++,4)) 
          printf("%d ",x); 
     }
  4. int cond(void){ return cond();}
    
    main()
    {   int a;
        scanf("%d",&a);
        if((a>0) && cond()) printf("ciao");
    }
  5. int cond(void){ return cond();}
    
    main()
    {   int a;
        scanf("%d",&a);
        if(cond() && (a>0)) printf("ciao");
    }
  6. int x = 5;
    void f(int x){   x++;   }
    
    main()
    { 
       f(x++);
       printf("%d",x);  
    }
  7. int x[10]={1,2,3,4,5,6,7,8,9,10};   
    void f(int *x){   x++;  }
    
    main()
    { 
       f(x);
       printf("%d",*x);  
    }
  8. int x[10]={1,2,3,4,5,6,7,8,9,10};
    
    main()
    { 
        int *p;
        printf("%d",*p++);  
    }

Esercizio 12
Si consideri il seguente ciclo for:
int a[N], i;

for(i=0; i < N && a[i] && a[i]!=4; i++) 
   printf("%d\n",a[i]);
Scrivete una versione equivalente senza utilizzare && e ||.
Esercizio 13
Siano x, y, z variabili di tipo int: Qual è l'effetto delle assegnazioni:
  1. x=(y=0,z=1);
  2. x=(y=0,z=y+1,z+1);

Esercizio 14
SI consideri il seguente frammento di programma:
char a[N], temp;
int i, j;
for(i=0,j=1;  a[i] && a[j]; i++,j++ )
{ 
   temp=a[i];   
   a[i]=a[j];
   a[j]=temp;
}
  1. Cosa fa?
  2. Scrivete una versione più efficiente (cioè con meno operazioni).

Esercizio 15
Trovate esempi di utilizzo per i casi limite dell'istruzione for, cioè:
  1. for(e; ; ) istr; dove e è una qualche espressione
  2. for( ;e; ) istr;
  3. for( ; ;e) istr;

Esercizio 16
Il seguente programma mostra un uso scorretto delle stringhe.
Individuate i punti critici:
int i;
char a[]="abcd";
char b[10]="do";
   
for(i=0;b[i];i++) 
   b[i]=a[i];

Esercizio 17
Studiate i vari casi particolari delle istruzioni C
(ad esempio while e for senza istruzioni nel corpo) e trovate esempi in cui si possono utilizzare.
Esercizio 18
Studiate il comportamento delle assegnazioni all'interno di espressioni.
Per esempio, definire un programma di prova per verificare la differenza tra (a=c++)>0 e (a=++c)>0, ecc.
Esercizio 19
Data una sequenza di N numeri in input,
produrre una tabella con il numero di occorrenze di ogni componente nell'input
Per esempio, se l'input è 12 9 4 9: l'output sarà
12 --> 1 
9 --> 2
4 --> 1

Esercizio 20
Data una stringa in input, produrre una tabella con il numero di occorrenze di ogni caratere in tale stringa
Per esempio, se l'input è "aiuola": l'output sarà
a --> 2 
i --> 1
l --> 1
o --> 1
u --> 1

Esercizio 21
Leggere n ed x, e calcolare la parte intera (inferiore) del logaritmo in base n di x.
Esercizio 22
Leggere una stringa di caratteri e produrre come output la stringa ottenuta togliendo tutti i caratteri compresi tra due *
(scorrendo la lista da sinistra a destra).
Ad esempio: dato "abc*fgh*ert*il*koo*" si ottiene "abcertkoo".

Aggiungere il controllo di bilanciamento degli *
(cioè se gli * sono in numero pari).


Esercizio 23
Date due stringhe in input a1 a2...an e b1 b2...bm, produrre come output la stringa
a1 b1...ak bk, dove k=min(n,m).
Esercizio 24
Data una stringa in input controllare se ha la seguente forma:
a1 a2 ... ai ai+1 ai ... a2 a1
cioè se è palindroma.
Esercizio 25
Data una stringa definire una procedura che produce la stringa rovesciata.
Scrivere poi anche la versione ricorsiva.
Esercizio 26
Realizzare in C il tipo di dato stack (o pila) di elementi generici; come esempio non informatico pensate ad una pila di piatti.
Lo stack è caratterizzato dalle operazioni pop (elimina l'elemento in cima alla pila), top (ritorna l'elemento in cima alla pila, la pila non è modificata), push (mette un elemento in cima alla pila).
Si considerino i due casi, quando esiste un limite al numero di elementi dello stack e quando no.
Esercizio 27
Data una matrice di 0 (casella vuota) e di 1 (casella libera) che rappresenta un labirinto, e date le coordinate dell'entrata e dell'uscita, definire un programma che trova il cammino dall'entrata all'uscita (se esiste) e stampa in successione le coordinate delle caselle che compongono il cammino.
Esercizio 28
Definire una versione generalizzata di mergesort nella quale si spezza la sequenza da ordinare in k-parti (k>=2).
Esercizio 29
Dato n maggiore o uguale a 2 intero in input produrre il seguente output:
Per n=1
     1
Per n=2
      2
     212
    22222
Per n=3
      3
     323
    32123     
   3222223
  333333333
ecc.
Cioè dato il triangolo interno costruito al passo i-esimo, al passo i+1-esimo occorre aggiungere un ulteriore triangolo che ha come lati sequenze del numero i+1.
Esercizio 30
Dire che cosa differenzia la memoria di massa da quella centrale in un calcolatore.
Esercizio 31
Quanti caratteri possono essere conservati in un dispositivo di dimensione 3 K ?