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