Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Algortirmo ricorsivo..
Forum - C/C++ - Algortirmo ricorsivo..

Avatar
jonas (Normal User)
Newbie


Messaggi: 1
Iscritto: 04/12/2009

Segnala al moderatore
Postato alle 15:20
Venerdì, 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?!:asd:

Saluti!


Ultima modifica effettuata da jonas il 04/12/2009 alle 23:38
PM Quote