Programmazione 1    (P-Z) a.a. 2007-08

Scrivere due funzioni che, preso in input due stringhe binarie, restituiscono rispettivamente il risultato dell'operazione di AND e di OR tra le due stringhe. Integrare le due funzioni in un programma main che prende in input due numeri interi positivi x ed y (entrambi < 256), ne calcola le corrispondenti rappresentazioni binarie x₂ e y₂, ed infine restituisce in output il risultato dell'operazione di x₂ OR (x₂ AND y₂).
Nota: L'operazione AND applicata ai singoli simboli binari è tale che AND(0,1) = AND(1,0) = AND(0,0) = 0, AND(1,1) = 1; diversamente l'operazione OR è tale che OR(1,1) = OR(1,0) = OR(0,1) = 1, OR(0,0) = 0.

Scrivere una funzione che preso in input un numero intero positivo n, stampa i numeri primi p ≤ n. Fornire una versione adeguatamente efficiente per la stampa dei numeri primi minori di 1000000.
Nota: usando il comando Linux time prima di un eseguibile, è possibile tenere traccia di una stima del tempo di esecuzione del programma eseguibile (ad esempio scrivendo time ./a.out).

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

#include <stdio.h>
#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 > 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 < 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 < 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 < MAX_LEN; index++) {
    printf ("%d", a[index]);
  }
  printf ("\n");
}

Nota: esiste un modo semplice e rapido per verificare che il risultato sia corretto.

Valutare l'esecuzione delle seguenti funzioni:

short int primo (int n) {
  int i;

  for (i = 2; i < n; i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}

Nota: questa funzione (onerosa) controlla che nnon sia divisibile per tutti gli altri n-1 (1 escluso) elementi precedenti.

short int primo_v2 (int n) {
  int i;

  for (i = 2; i ≤ (int)sqrt((double)n); i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}

Nota: si puo' dimostrare che per capire se n e' primo, ci bastera' controllare che non sia divisibile per i numeri 2 ≤ x ≤ sqrt(n).

void setaccio (int n, short int primi[]) {
  int index;

  if (primi[n]) {
    for (index = n + 1; index < MAX_VALUE; index++) 
      if (primi[index] && index % n == 0) primi[index] = 0;
  }
}

Nota: dato in input un numero n ed un vettore primi[], dove primi[x] = 1 se e solo se x e' un numero primo, modifica il vettore primi[] impostando primi[y] = 0 se e solo se y e' divisibile per n. L'operazione corrisponde ad un setaccio, con parametro n. Ad esempio iniziando con un vettore primi[] con tutti i valori ad 1, e n = 2, avremmo come risultato un vettore primi[] in cui tutti i multipli di 2 sono stati impostati a 0 (es. primi[4] = primi[6] = primi[8] = ... = 0).

#include <stdio.h>
#include <ctype.h>

#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 (<%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 < 0) {
    str_mod[pos] = str[len + i];
    i++;
    pos++;
  }

  while (pos < len) {
    if (i == len) i = 0;
    str_mod[pos] = str[i];
    i++;
    pos++;
  }
  
  printf ("Shift:\n\"");
  for (i = 0; i < len; i++) {
    printf ("%c", str_mod[i]);
  }
  printf ("\"\n");
}