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 ?