Soluzioni esercizi Homework 4

Esercizio 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Factor {
  unsigned long f;
  long m;
  struct Factor* next;
} Factor, *FactorList;

/* Crea un puntatore ad una copia di element */
Factor* copy_factor (Factor element){
  Factor* new = (Factor*) calloc(1, sizeof(Factor));
  new->f = element.f;
  new->m = element.m;
  new->next = NULL;
  return new;
}

FactorList insert_in_order(FactorList N, Factor element){
  Factor* itr = NULL;  // iteratore alla lista
  Factor* previous_itr = NULL;  // elemento precedente a quello da cancellare
  Factor* to_insert = copy_factor(element);
  if ((N == NULL) || (N->f > element.f)){ // inserimento in testa alla lista
    to_insert->next = N;
    N = to_insert;
    return N;
  }

  itr = N;
  previous_itr = N;
  while ((itr != NULL) && (itr->f < element.f)){
    if (itr != N) previous_itr = previous_itr->next;
    itr = itr->next;
  }
  // inserisce tra' previous_itr e il suo next
  previous_itr->next = to_insert;
  to_insert->next = itr;
  return N;
}

FactorList cancel_zero_factor (FactorList N) {
  Factor* temp = NULL;  // puntatore all'elemento da cancellare
  Factor* previous = NULL;
  if (N->m == 0){  // L'elemento da cancellare e' il primo
    temp = N;
    N = temp->next;
    temp->next = NULL;
    free(temp);
    return N;
  }
  if ((N->next)->m == 0){  // L'elemento da cancellare e' il secondo
    temp = N->next;
    N->next = temp->next;
    temp->next = NULL;
    free(temp);
    return N;
  }
  previous = N;
  while((previous->next != NULL) && ((previous->next)->m != 0)){
    previous = previous->next;
  }
  temp = previous->next;
  previous->next = temp->next;
  temp->next = NULL;
  free(temp);
  return N;
}

/* Scorre N in cerca di un fattore x con x.f == element.f.
   Se lo trova, lo modifica in modo appropriato. 
   Ritorna -1 in caso la ricerca non abbia successo.
   Ritorna 1 in caso la modifica abbia successo.
   Ritorna 0 in caso x debba essere cancellato dopo la modifica*/ 
int search_modify (FactorList N, Factor element){
  Factor* current = NULL;
  if (N == NULL){
    return -1;
  }
  current = N;
  // Scorre N
  while ((current != NULL) && (current->f < element.f))
    current = current->next;
  // Elemento non trovato
  if ((current == NULL) || (current->f > element.f))
    return -1;
  current->m = current->m + element.m;
  // Elemento da cancellare
  if (current->m == 0) return 0;
  return 1;
}


FactorList MultDiv (FactorList N, FactorList M) {
  Factor *current= NULL;
  for (current = M; current != NULL; current = current->next) {
    int result = search_modify(N, (*current));
    if (result == 0) // L'elemento modificato va' cancellato
      N = cancel_zero_factor(N);  
    if (result == -1)  // In N va' inserita una copia di *current_factor
      N = insert_in_order(N, (*current));
  }
  return N;
}

Esercizio 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <MultDiv.cc>  // primo esercizio

typedef struct Values {
  unsigned x;
  unsigned y;
  unsigned long z;
  struct Values* next;
} Values, *ValuesList;


/*Legge i valori di una riga di input e ritorna un puntatore 
  ad una struttura Values. */
Values* leggi_riga(){
  Values* elemento = (Values*) calloc(1,sizeof(Values));
  unsigned x = 0, y = 0;
  unsigned long z = 0;
  int c = getchar();
  if (c == '\n') c = getchar();
  if (c != '(') return NULL;
  if (scanf("%u %u", &x, &y) != 2) return NULL; 
  if (getchar() != ')') return NULL;
  if (scanf(" %lu", &z) != 1) return NULL;
  //printf("z = %lu\n", z);
  elemento->x = x;
  elemento->y = y;
  elemento->z = z;
  return elemento;
}

/*Legge l'input e crea una ValuesList. */
ValuesList leggi_input (){
  ValuesList lista = NULL;
  Values* new = NULL;
  Values* last = NULL;
  int temp = 0;
  scanf("%d", &temp);
  while (temp > 0){
    new = leggi_riga();
    if (new == NULL) return NULL;
    if (lista == NULL){
      lista = new;
      new->next = NULL;
      last = new;
    } else {
      last->next = new;
      new->next = NULL;
      last = new;
    }
    temp--;
  }
  return lista;
}


/*Inverte i segni del campo m di ogni fattore della lista. */
FactorList inverti_segni(FactorList lista){
  Factor* corrente = lista;
  while (corrente != NULL){
    corrente->m = 0 - corrente->m;
    corrente = corrente->next;
  }
  return lista;
}

/* Calcola il logaritmo in "base" del "value". */
unsigned long my_log(unsigned long base, unsigned long value){
  unsigned long power = 0;
  while ((value % base) == 0){
    value = value / base;
    power = power + 1;
  }
  return power;
}

/* Ritorna la fattorizzazione in primi di n. */
FactorList scomponi_in_primi (unsigned long n) {
  unsigned long current = 2;
  unsigned long to_check = n;
  FactorList lista = NULL;
  FactorList last_element = lista;
  FactorList prime_factor = NULL;
  while (current < (n/2+1)){
    if ((to_check % current) == 0){
      if ((prime_factor = (Factor*) calloc(1, sizeof(Factor))) == NULL)
        return NULL;
      prime_factor->f = current;
      prime_factor->m = my_log(current, to_check);
      prime_factor->next = NULL;
      to_check = to_check / pow(current, prime_factor->m);
      if (lista == NULL){
        lista = prime_factor;
        last_element = prime_factor;
      } else {
        last_element->next = prime_factor;
        last_element = last_element->next;
      }
    }
    current = current + 1;
  }
  if (lista == NULL){
    lista = (Factor*) calloc(1, sizeof(Factor));
    lista->f = n;
    lista->m = 1;
    lista->next = NULL;
  }
  return lista;
}

/* Ritorna la fattorizzazione in primi di n! .*/
FactorList crea_lista_fattori (unsigned int n){
  long corrente = 2;
  FactorList lista = NULL;
  while (corrente <= n){
    if ((lista = MultDiv (lista, scomponi_in_primi(corrente))) == NULL)
      return NULL;
    corrente = corrente + 1;
  }
  return lista;
}


/* Cancella una lista di fattori. */
void cancella_lista (FactorList N) {
  while (N != NULL){
    Factor* next = N;
    N = N->next;
    if (next != NULL) free(next);
  }
  return;
}



/* Gestisce i tre valori correnti. */
int gestisci_corrente (Values* corrente){
  FactorList Z = inverti_segni (scomponi_in_primi (corrente->z));
  FactorList N = crea_lista_fattori (corrente->x);
  FactorList K = crea_lista_fattori (corrente->y);
  FactorList N_meno_K = crea_lista_fattori (corrente->x - corrente->y);
  Factor *nfactor = NULL;

  K = MultDiv (K, N_meno_K);
  K = inverti_segni(K);
  N = MultDiv (N, K);
  N = MultDiv (N, Z);
  nfactor = N;
  while (nfactor!= NULL){
    if (nfactor->m < 0){
      cancella_lista(N);
      cancella_lista(K);
      cancella_lista(N_meno_K);
      cancella_lista(Z);
      return 0; 
    }
    nfactor = nfactor->next;
  }
  cancella_lista(N);
  cancella_lista(K);
  cancella_lista(N_meno_K);
  cancella_lista(Z);
  return 1;
}


/* Prende in input una lista di "Values" e stampa l'output relativo 
   a ciascuna tripla di valori. */
void divisibile(ValuesList lista){
  Values* corrente = lista;
  while (corrente != NULL){
    if (gestisci_corrente(corrente) == 1) 
      printf("(%u %u) %lu SI\n",corrente->x,corrente->y,corrente->z);
    else printf("(%u %u) %lu NO\n",corrente->x,corrente->y,corrente->z);
    corrente = corrente->next;
  }
  return;
}



/* Cancella una lista di valori */
void cancella_valori (ValuesList lista){
  while(lista != NULL){
    Values* corrente = lista;
    lista = lista->next;
    if (corrente != NULL) free(corrente);
  }
  return;
}


int main(){
  ValuesList lista = leggi_input();
  divisibile(lista);
  cancella_valori(lista);
  return 1;

}

-- JulindaStefa - 18 Jan 2008