Funzione con array

di il
5 risposte

Funzione con array

Scrivere una funzione che dati due array a e b monodimensionali di dimensione da e db, restituisce true se ogni elemento di a è pari alla somma di almeno due elementi di b, false altrimenti.
Il mio algoritmo è sbagliato, perchè scorre l'array b linearmente e non va a vedere se ci sono altre possibili combinazioni quindi non funziona

#include<iostream>
using namespace std;
bool funzione(int [],int ,int [],int );
bool funz(int ,int [],int );
int main()
{
    int da=4;
    int db=7;
    int a[]={4,15,24,8};
    int b[]={2,1,1,13,18,3,2};
    if(!(funzione(a,da,b,db)))
    cout<<"NON  ";
    cout<<" E' VERIFICATA LA CONDIZIONE DELL'ESERCIZIO "<<endl;

return 0;
}

bool condizione(int n,int b[],int db)
{
    int num=n;
    bool c[db];
    for(int t=0;t<db;t++) c[t]=false;
    int contatore=0,quoziente=0;
    int i=0;
    while(i<db)
    {
        quoziente=num/b[i];
        if(quoziente==1)
        {
            if(contatore>2)
            return true;
            else
            return false;
        }
        if(quoziente>1)
        {
            if(c[i]==false)
            {
                c[i]=true;
                contatore++;
                num=num-b[i];
            }
            i++;
        }
        else
        i++;
    }
}

bool funzione(int a[],int da,int b[],int db)
{
    bool cond=true;
    for(int s=0;s<da && cond;s++)
    {
        if(!condizione(a[s],b,db))
        cond=false;
    }
    return cond;
}

Potreste dirmi come fareste voi?

5 Risposte

  • Re: Funzione con array

    E' sbagliato si, almeno nella funzione condizione(). A che serve quoziente? direi a nulla se devi verificare che l'elemento risulta essere almeno la SOMMA di due elementi di b.
  • Re: Funzione con array

    Il quoziente lo utilizza per dire semplicemete che se il primo elemento è uguale all' elemento del vettore a allora chiudi fin dall' inizio ( cosa che comunque potresti fare con una ugualianza ^^ ) Allora io ho fatto uno schizzetto per aumentare le possibili combinazioni ma , non sono tutte infatti con l' esempio che hai fatto non uscirà true , però ho aumentato le possibilità xD , il problema consiste nel trovare un algoritmo che ti faccia avere tutte le possibili combinazioni
    
    int main ()
    {
    	  int da=4;
    	  int db=7;
    	  int a[]={4,15,24,8};
    	  int b[]={2,1,1,13,18,3,2};
    	  cout << "Creati gli array "<<endl;
    	  if ( Ricerca(a,b,da,db) )
    	       cout << "Ogni elemento di a e' somma di almeno due elementi di b"<<endl;
    	  else
    		  cout << "Ogni elemento di a non e' somma di almeno due elementi di b"<<endl;
    	  return 0;
    }
    
    
    bool Ricerca ( int a[], int b[], const int riemp_a , const int riemp_b ) {
    	for ( int i = 0 ; i < riemp_a ; i++ )
    		if ( !Ricerca_elemento(a[i],b,riemp_b) )
    			return false;
    	return true;
    }
    
    
    bool Ricerca_elemento( int elem , int b[] , const int riemp_b) {
    	bool continuo = false;
    	int operandi=1;
    	while ( !continuo )
    	{
    		for ( int i = 0; i < riemp_b ; i++ )
    		{
    			for ( int j = i+1 ; j < riemp_b ; j++)
    			{
    				if ( (j+operandi) <= riemp_b )
    				{
    					if ( somma(operandi,b,j,i) == elem )
    					{
    						return true;
    					}
    				}
    				else
    					break;
    			}
    		}
    		operandi++;
    		if ( operandi > riemp_b-1 )
    			continuo = true;
    	}
    	return false;
    }
    
    int somma ( const int op, int b[], const int pos, const int primo_op) {
    	int somma=b[primo_op];
    	for ( int i = pos; i < pos+op ; i++)
    		somma += b[i];
    	return somma;
    }
    
    questo algoritmo ti vede se ogni elemento di a è somma di almeno due elemtni ( quindi possono essere anche sommma di 3 operando o anche di tutto il vettore b ^^ ) però il numero 8 , il quale è combinazione di elementi di b ma non sequenziali ma in posizioni distinte tra loro , non lo visualizza come elemento uguale alla somma di almeno due .
  • Re: Funzione con array

    Secondo me, dato che bisogna valutare OGNI possibile combinazione dei valori di B per OGNI valore di a, sarebbe utile utilizzare un vettore temporaneo che contenga tutte le possibili combinazioni di b, per poi utilizzarle successivamente per il confronto con a, se poi il vettore temporaneo è ordinato e non contiene duplicati ancora meglio.
  • Re: Funzione con array

    Quindi come verrebbe il codice?
    proprio non riesco a capire come far girare tutte le possibili combinazioni di somme!!!
  • Re: Funzione con array

    A dir la verità ho provato a fare una funzione che mi trova tutte le combinazioni, ho provato e apparentemente funziona. In poche parole, come ho detto prima, sarebbe utile utilizzare un array temporaneo che contiene tutti i possibili valori combinati (almeno 2) di b. Io ho implementato una lista minimale chiamata IntLista, una struttura composta da due campi, uno contiene il numero, l'altro il puntatore al successivo. Insieme ad essa ho utilizzato delle funzioni per l'inserimento ordinato (crescente) ed una funzione che mi elimina le occorrenze, inoltre quest'ultima ritorna il nuovo numero di elementi non duplicati presenti in lista. Oltre a ciò, per calcolare tutti i possibili valori, ho utilizzato una funzione che restituisce la lista appunto con tutti i possibili valori (già ordinata e senza duplicati). Per tale funzione ho fatto uso di tre cicli for, almeno per l'algoritmo che ho pensato di utilizzare . Infatti il codice può essere scritto meglio oppure si potrebbe scegliere un algoritmo diverso, però questo mi è venuto facile a farlo. Ecco il codice:
    
    struct IntList{
        int value;
        IntList* next;
    };
    
    void insList(IntList* &l,int n){
        if(l==0){
            l=new IntList;
            l->value=n;
            l->next=0;
        }else{
             if(l->value >= n){
                 IntList* p=l;
                 l=new IntList;
                 l->value=n;
                 l->next=p;
             }else insList(l->next,n);
        }
    }
    
    int removeDuplicated(IntList* &l,int n){
        if (l!=0){
            if(n==-1){
                n=l->value;
                return removeDuplicated(l->next,n) + 1;
            }else{
                if(l->value == n){
                    IntList* p=l;
                    l=l->next;
                    delete p;
                    return removeDuplicated(l,n);
                }else return removeDuplicated(l->next,l->value)+1;
            }
        }else return 0;
    }
    
    IntList* compareValues(const int* vet,int n){
        IntList* l=0;
        int i,j,z;
        int sum;
        for(z=1;z<n;++z){
            for(j=0;j<n-z;++j){
                sum=vet[j];
                for(i=j+z;i<n;++i){
                    sum+=vet[i];
                    insList(l,sum);
                }
            }
        }
        removeDuplicated(l,-1);
        return l;
    }
    
    int main()
    {
        int a[5]={3,6,7,10,78};
        int b[6]={2,6,4,3,5,5};
        IntList* l=compareValues(b,6);
        for(int i=0;i<5;++i){
            IntList* p=l;
            while(p!=0){
                if(p->value==a[i]){
                    cout<<"\nl'elemento a["<<i<<"] è la somma dei valori di b, di valore "<<a[i];
                    break;
                }else if(p->value > a[i]) p=0;
                else p=p->next;
            }
            if (p==0) cout<<"\nl'elemento a["<<i<<"] NON è la somma dei valori di b, di valore "<<a[i];
        }
        system("PAUSE");
    }
    
    Ripeto, il codice può essere scritto meglio, ad esempio si potrebbero utilizzare le STL vector, queue, liste ordinate, ecc.
Devi accedere o registrarti per scrivere nel forum
5 risposte