Eser231007 < Programmazione1

<h1>Programmazione 1 <small>&nbsp; &nbsp;(P-Z) a.a. 2007-08</small></h1>
<br>
<big>Docente: R. Silvestri<br>
Esercitatore: A. Carosi<br>
Tutor: J. Stefa</big>
<br>
<br>
<br>
<h2>Esercitazioni del 23 ottobre 2007</h2>

<b>Esercizio 1 (dal 16/10/2007)</b>
<div align="justify"> <blockquote>
Scrivere due funzioni che, preso in input due stringhe binarie, restituiscono rispettivamente il risultato dell'operazione di <tt>AND</tt> e di <tt>OR</tt> tra le due stringhe. Integrare le due funzioni in un programma <tt>main</tt> che prende in input due numeri interi positivi <tt>x</tt> ed <tt>y</tt> (entrambi &lt; 256), ne calcola le corrispondenti rappresentazioni binarie <tt>x<small><sub>2</sub></small></tt> e <tt>y<small><sub>2</sub></small></tt>, ed infine restituisce in output il risultato dell'operazione di <tt>x<small><sub>2</sub></small> OR (x<small><sub>2</sub></small> AND y<small><sub>2</sub></small>)</tt>.<br><strong>Nota:</strong> L'operazione <tt>AND</tt> applicata ai singoli simboli binari &egrave; tale che <tt>AND(0,1) = AND(1,0) = AND(0,0) = 0</tt>, <tt>AND(1,1) = 1</tt>; diversamente l'operazione <tt>OR</tt> &egrave; tale che <tt>OR(1,1) = OR(1,0) = OR(0,1) = 1</tt>, <tt>OR(0,0) = 0</tt>.
</blockquote>
</div>
<br>

<b>Esercizio 2 (dal 16/10/2007)</b>
<div align="justify"> <blockquote>
Scrivere una funzione che preso in input un numero intero positivo <tt>n</tt>, stampa i numeri primi <tt>p &le; n</tt>. Fornire una versione adeguatamente efficiente per la stampa dei numeri primi minori di 1000000. <br><strong>Nota:</strong> usando il comando Linux <tt>time</tt> prima di un eseguibile, &egrave; possibile tenere traccia di una stima del tempo di esecuzione del programma eseguibile (ad esempio scrivendo <tt>time ./a.out</tt>).
</blockquote>
</div>
<br>

<b>Esercizio 3</b>
<div align="justify"> <blockquote>
Scrivere una funzione che preso in argomento una stringa di caratteri alfanumerici (carattere <em>spazio</em> incluso) <tt>str</tt>, ed un intero <tt>k</tt>, stampa la stringa ottenuta eseguendo lo shift ciclico di <tt>str</tt> di esattamente <tt>k</tt> posizioni. Ad esempio se <tt>str = "Io programmo in C"</tt> e <tt>k = 3</tt>, stampa <tt>"programmo in CIo "</tt> (porta avanti la stringa di <tt>k</tt> posizioni in maniera ciclica), con <tt>-3</tt> stampa <tt>"n CIo programmo i"</tt>. La funzione deve essere integrata in un programma <tt>main</tt>, che prende in input la stringa ed il valore di <tt>k</tt> da tastiera.
</blockquote>
</div>


<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>

<big><b>Soluzioni</b></big>
<br>
<br>
<br>
<br>

<b>Esercizio 1</b> 
<div align="justify"> <blockquote><pre><tt>
#include &lt;stdio.h&gt;
#define MAX_LEN 8

void toBin(int, short int []);
void and(short int [], short int []);
void or(short int [], short int []);
void print(short int []);

int main(void) {
  int a, b;

  printf ("Inserisci due interi positivi: ");
  scanf ("%d %d", &a, &b);
  
  short int a_bin[MAX_LEN] = {0};
  toBin(a, a_bin);

  short int b_bin[MAX_LEN] = {0};
  toBin(b, b_bin);

  and(a_bin, b_bin);
  or(a_bin, b_bin);

  printf ("Il risultato e': ");
  print(b_bin);

  return 0;
}

void toBin(int k, short int bin[]) {
  int index = 0, i;
  
  while (k &gt; 0) {
    bin[MAX_LEN - index - 1] = k % 2;
    k = k/2;
    index++;
  }
}

void and(short int a[], short int b[]) {
  int index;

  for (index = 0; index &lt; MAX_LEN; index++) {
    if (a[index] && b[index]) b[index] = 1;
    else b[index] = 0; 
  }
}

void or(short int a[], short int b[]) {
  int index;

  for (index = 0; index &lt; MAX_LEN; index++) {
    if (a[index] || b[index]) b[index] = 1;
    else b[index] = 0; 
  }
}

void print(short int a[]) {
  int index;

  for (index = 0; index &lt; MAX_LEN; index++) {
    printf ("%d", a[index]);
  }
  printf ("\n");
}
</tt></pre></blockquote>
<strong>Nota:</strong> esiste un modo semplice e rapido per verificare che il risultato sia corretto.
</div>

<b>Esercizio 2</b> 
<div align="justify"> 
Valutare l'esecuzione delle seguenti funzioni:
<blockquote><pre><tt>
short int primo (int n) {
  int i;

  for (i = 2; i &lt; n; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
</tt></pre></blockquote>
<strong>Nota:</strong> questa funzione (onerosa) controlla che <tt>n</tt>non sia divisibile per tutti gli altri <tt>n-1</tt> (<tt>1</tt> escluso)  elementi precedenti.
<br>
<blockquote><pre><tt>
short int primo_v2 (int n) {
  int i;

  for (i = 2; i &le; (int)sqrt((double)n); i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
</tt></pre></blockquote>
<strong>Nota:</strong>  si puo' dimostrare che per capire se <tt>n</tt> e' primo, ci bastera' controllare che non sia divisibile per i numeri <tt>2 &le; x &le; sqrt(n)</tt>.
<br>
<blockquote><pre><tt>
void setaccio (int n, short int primi[]) {
  int index;

  if (primi[n]) {
    for (index = n + 1; index &lt; MAX_VALUE; index++) 
      if (primi[index] && index % n == 0) primi[index] = 0;
  }
}
</tt></pre></blockquote>
<strong>Nota:</strong> dato in input un numero <tt>n</tt> ed un vettore <tt>primi[]</tt>, dove <tt>primi[x] = 1</tt> se e solo se <tt>x</tt> e' un numero primo, modifica il vettore <tt>primi[]</tt> impostando <tt>primi[y] = 0</tt> se e solo se <tt>y</tt> e' divisibile per <tt>n</tt>. L'operazione corrisponde ad un setaccio, con parametro <tt>n</tt>. Ad esempio iniziando con un vettore <tt>primi[]</tt> con tutti i valori ad <tt>1</tt>, e <tt>n = 2</tt>, avremmo come risultato un vettore <tt>primi[]</tt> in cui tutti i multipli di <tt>2</tt> sono stati impostati a <tt>0</tt> (es. <tt>primi[4] = primi[6] =  primi[8] = ... = 0</tt>).
</div>

<b>Esercizio 3</b> 
<div align="justify"> <blockquote><pre><tt>
#include &lt;stdio.h&gt;
#include &lt;ctype.h&gt;

#define MAX_LEN 100

void shift(char[], int, int);

int main(void) {
  int k, i = 0;
  char str[MAX_LEN] = {'\0'}, c;

  printf ("Inserici una stringa (&lt;%d):\n", MAX_LEN);
  while ((c = getchar()) != '\n') {
    if (!(isalnum(c) || isspace(c))) {
      printf ("Carattere %c non alfanumerico! Exit con errore (1)\n", c);
      return 1;
    }
    str[i] = c;
    i++;
  }

  printf ("Inserisci un intero: ");
  scanf ("%d", &k);

  shift(str, k, i);

  return 0;
}

void shift(char str[], int k, int len) {
  char str_mod[len];
  int i = k, pos = 0;

  while (i &lt; 0) {
    str_mod[pos] = str[len + i];
    i++;
    pos++;
  }

  while (pos &lt; len) {
    if (i == len) i = 0;
    str_mod[pos] = str[i];
    i++;
    pos++;
  }
  
  printf ("Shift:\n\"");
  for (i = 0; i &lt; len; i++) {
    printf ("%c", str_mod[i]);
  }
  printf ("\"\n");
}
</tt></pre></blockquote>
</div>

-- Users.RiccardoSilvestri - 23 Oct 2007
This topic: Programmazione1 > WebHome > Prog1PZ > DiarioPZ0708 > Eser231007
Topic revision: r2 - 2007-10-26 - RiccardoSilvestri