Funzione c++ con array

[giuliomontenero]

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?

[apatriarca]

L'algoritmo naive per fare quello che desideri è confrontare ogni elemento di a con ogni possibile somma di elementi di b.

[giuliomontenero]

potresti scrivermi il codice?
o almeno un abbozzo

[apatriarca]

E' possibile scriverlo abbastanza facilmente con una funzione ricorsiva che chiama se stessa due volte per ogni elemento dell'array e che aggiunge o meno l'elemento alla somma che si sta calcolando. Osserva che però questo algoritmo richiede un tempo esponenziale nella dimensione di \(b\). Una qualche soluzione migliore è quindi probabilmente necessaria, ma non mi sono per ora venute idee migliori.

[giuliomontenero]

se puoi scrivimelo senza usare funzioni ricorsive
se proprio non è possibile scrivimi la funzione ricorsiva
grazie mille

[apatriarca]

L'idea dell'algoritmo è quella che le somme di elementi di \(b\) si possono scrivere nella forma \(\sum c_i\,b_i\) dove i \(b_i\) sono gli elementi di \(b\) e \(c_i \in \{ 0, 1 \} \). Ma si tratta di un algoritmo lentissimo ed è quindi meglio trovare una qualche idea migliore. Di certo non ho comunque l'intenzione di darti direttamente la soluzione in termini di codice in C o C++.

[giuliomontenero]

questo è un algoritmo ma non funziona per tutte le possibili combinazioni
come si può aggiustare?
in questo caso non funziona per 8 in quanto è somma di almeno due elementi ma che non sono in sequenza nel vettore bensì distinti

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;
}

[apatriarca]

in questo caso non funziona per 8 in quanto è somma di almeno due elementi ma che non sono in sequenza nel vettore bensì distinti.

In che senso? Nella descrizione del problema non si fa riferimento a questo ulteriore vincolo sulle somme di elementi di b. Se le somme sono tra elementi adiacenti tutto diventa più facile..

[giuliomontenero]

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 .

[apatriarca]

Per prima cosa preferirei se la prossima volta scrivessi l'intero codice sorgente (includendo quindi l'inclusione delle librerie e i prototipi delle funzioni in modo da poterlo compilare più facilmente). Per quanto riguarda il tuo problema invece non c'è molto di cui discutere, l'algoritmo non è corretto. E' abbastanza evidente che sono ammesse solo somme di elementi contigui (è sufficiente dare un occhiata a somma). Ti scrivo la funzione ricorsiva del metodo che ho descritto prima:

#include <iostream>

bool are_subsums(int * a, int lenA, int * b, int lenB);
bool is_subsum(int value, int * b, int lenB);
bool is_subsum2(int value, int * b, int lenB, int nadd, int sum);

int main(void)
{
     int a[] = {4, 15, 24, 8};
     const int lenA = sizeof(a)/sizeof(int);

     int b[] = {2, 1, 1, 13, 18, 3, 2};
     const int lenB = sizeof(b)/sizeof(int);

     if (are_subsums(a, lenA, b, lenB))
        std::cout << "Ogni elemento di a e' somma di almeno due elementi"
            "di b.\n";
     else
        std::cout << "Esiste almeno un elemento di a che non è somma"
            "di almeno due elementi di b.\n";
     return 0;
}

bool are_subsums(int * a, int lenA, int * b, int lenB)
{
    for (int i = 0; i < lenA; ++i) {
        if (!is_subsum(a[i], b, lenB)) {
            std::cout << a[i] << " non e' somma di elementi di b.\n";
            return false;
        }
    }
    return true;
}

bool is_subsum(int value, int * b, int lenB)
{
    return is_subsum2(value, b, lenB, 0, 0);
}

bool is_subsum2(int value, int * b, int lenB, int nadd, int sum)
{
    if (lenB <= 0) {
        if (sum == value && nadd > 1) {
            return true;
        }
        return false;
    }

    return is_subsum2(value, b+1, lenB-1, nadd+1, sum+*b)
        || is_subsum2(value, b+1, lenB-1, nadd, sum);
}

[giuliomontenero]

siccome al compito non posso usare la ricorsione, come posso scrivere il codice senza ricorsione?

[giuliomontenero]

potresti anche darmi una spiegazione invece della funzione ricorsiva?

[apatriarca]

Inizio con la spiegazione della funzione ricorsiva. L'obiettivo è quello di generare tutte le somme possibili a partire dagli elementi di \(b\). Per ogni \(i\), \(b_i\) può essere presente o meno nella somma. L'idea generale è quindi quella di scorrere un elemento per volta di \(b\) e richiamare ricorsivamente il metodo sugli elementi successivi dell'array considerando o meno l'elemento nella somma.

L'algoritmo iterativo si basa invece sull'idea di generare tutti vettori di booleani della stessa lunghezza di \(b\) e calcolare quindi il "prodotto scalare" tra questi vettori e \(b\). Detto più semplicemente, se \(n\) è la lunghezza di \(b\), allora devi generare tutti i vettori \( c = (c_0, \dotsc, c_{n-1}\) e calcolare quindi tutte le somme \( c_0\,b_0 + \dotsb c_{n-1}\,b_{n-1}. \) Un metodo per calcolare questi vettori, se \(n < 64\)* è quello di incrementare un contatore finché ha meno di \(n+1\) cifre e utilizzare le operazioni bit-a-bit per sapere se sommare o meno un certo elemento dell'array.

* Considerando il numero di possibilità in un array di \(64\) elementi è una restrizione abbastanza sensata (non riusciresti comunque a calcolare quel valore in un tempo utile se ci fossero più di \(64\) elementi..)

[giuliomontenero]

ok, ma potresti darmi una spiegazione più dettagliata sulle tre funzioni che hai utilizzato?
ti ringrazio nuovamente per l'aiuto che mi stai dando