jonas (Normal User)
Newbie
Messaggi: 1
Iscritto: 04/12/2009
|
Salve a tutti...sono alle prese col problema Sum_It_Up(http://online-judge.uva.es/p/v5/574.html) e sto implementando un algoritmo ricorsivo utilizzando una lista concatenata...
Il codice che ho scritto è il seguente:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{ //costruzione di una struct "node", contetente un intero e un puntatore "link"
int data;
struct node *link;};
typedef struct node lista;
int length(lista * p);
void sumitup (int sum,lista *vett,lista *sol_temp);
void aggiungi(lista **plis, int elem);
void stampa(lista *pt);
struct node * concatena(lista *p,lista *q);
lista *soluzione;
void main(){
int i=0;
int nelem=0;
int sum=0;
int val=0;
lista *vett, *v;
vett=(lista*)malloc(sizeof(lista));
v=(lista*)malloc(sizeof(lista));
soluzione=(lista*)malloc(sizeof(lista));
soluzione=NULL;
v=NULL;
vett=NULL;
FILE *stream, *fopen();
stream = fopen("input.txt", "r");
if ((stream = fopen("input.txt", "r")) == NULL)
{
printf("Non posso aprire il file %s\n", "input.txt");
exit(1);
}
fscanf(stream, "%d %d", &sum , &nelem);
while(!feof(stream)){
for (i=0;i<nelem;i++){
fscanf(stream, "%d\t", &val);
aggiungi(&vett,val);
}
}
if (sum>999){ printf("La summa massima deve essere un numero minore di 1000");exit(-1);}
if (nelem>12){ printf("Il numero massimo degli elementi deve essere compreso tra 1 e 12 (incluso)"); exit(-1);}
printf("Somme di %d\n",sum);
sumitup(sum,vett,v);
}
void sumitup (int sum,lista *vett,lista *sol_temp){
int sum_part=0;
int n=sum;
int lunghezza=length(vett);
if(lunghezza>0) {
while(vett->link!=NULL){
sum_part=vett->data;
vett=vett->link;
if(sum_part<=n){
if(sum_part==n){
lista *v1;
v1=malloc(sizeof(lista));
v1->link=NULL;
memcpy(&v1,&sol_temp,sizeof(lista));
aggiungi(&v1, sum_part);
aggiungi(&v1,-1);
soluzione=concatena(soluzione,v1);
}
else{
lista *v2,*aa, *tmp;
v2=malloc(sizeof(lista));
aa=malloc(sizeof(lista));
tmp=malloc(sizeof(lista));
aa->link=NULL;
v2->link=NULL;
tmp->link=NULL;
aa=sol_temp;
aggiungi(&aa, sum_part);
v2=vett;
sumitup(n-sum_part,v2, aa);
}
}
}
}
}
void aggiungi(lista **q,int num)
{
lista *temp;
temp = *q;
if(*q==NULL)
{
*q=malloc(sizeof(struct node));
temp = *q;
}
else
{
while((temp->link)!=NULL)
{
temp=temp->link;
}
temp->link = malloc(sizeof(lista));
temp=temp->link;
}
temp->data = num;
temp->link = NULL;
}
void stampa(lista *pt) //stampa lista
{
while(pt!=NULL){
if(pt->data==-1){
pt=pt->link;
}
else{
printf("%d\t",pt->data);
pt=pt->link;
}
}
printf("\n");
}
int length(lista * p) /* Lunghezza di una lista (ricorsiva) */
{
int i=0;
while(p!=NULL){ i++; p=p->link;}
return i;
}
struct node * concatena(lista *p,lista *q){
struct node *x,*r;
if (p==NULL) r=q;
else if (q==NULL) r=p;
else
{
x=p;
r=x;
while(x->link!=NULL) {x=x->link;}
x->link=q;
}
return(r);
}
Il file input.txt ha il seguente contenuto (per esempio): 10 6 5 4 3 2 1 1 (dove il primo valore 10, indica la somma da cercare, mentre il secondo 6 indica il numero degli elementi dell'array).
usando come test l'input sopracitato, dopo che trova la prima soluzione 5 4 1, scrive un -1 per indicare la fine di una soluzione, poi ritrova l'altro 1 (qui devo scrivere una funzione di controllo per evitare di stampare due soluzioni uguali...), poi si "pianta" sulla funzione aggiungi...ma non capisco il perchè!!!!
Qualche idea?!Suggerimenti?!
Saluti!
Ultima modifica effettuata da jonas il 04/12/2009 alle 23:38 |