Esercizio c++ con array
Salve a tutti, avrei urgentemente bisogno di una mano per risolvere questo esercizio che mi sono inventato
Ho un array di N elementi reali, devo stampare tutti i possibili sottoarray,tale che la somma degli elementi di questi sia minore della media tra l'elemento massimo e l'elemento minimo.
Io riesco a stamparmi solo il primo,gli altri non ci riesco
ecco qui il mio codice dove l'ultimo while più esterno l'avevo messo per stamparmi tutti i sottoarray che verificano la condizione ma come immaginavo è un ciclo infinito
Ho un array di N elementi reali, devo stampare tutti i possibili sottoarray,tale che la somma degli elementi di questi sia minore della media tra l'elemento massimo e l'elemento minimo.
Io riesco a stamparmi solo il primo,gli altri non ci riesco
ecco qui il mio codice dove l'ultimo while più esterno l'avevo messo per stamparmi tutti i sottoarray che verificano la condizione ma come immaginavo è un ciclo infinito
#include<iostream>
using namespace std;
const int N=10;
int main()
{
double a[N]={4,4.5,4.8,36,7,8,9,11,5,6.1};
int i,j;
double min,max;
min=max=a[0];
i=0;
while(i<N)
{
if(a[i]<min)min=a[i];
i++;
}
j=0;
while(j<N)
{
if(a[j]>max)max=a[j];
j++;
}
cout<<"Gli elementi dell'array sono: "<<endl;
for(int k=0;k<N;k++)
cout<<a[k]<<" ";
cout<<endl<<endl;
cout<<"Gli elementi minimo e massimo dell'array sono rispettivamente"<<endl<<min<<" e "<<max<<endl<<endl;
double media=(min+max)/2;
cout<<endl<<"La media dei due numeri minimo e massimo è: "<<media<<endl<<endl;
bool c[N];
for(int d=0;d<N;d++)
c[d]=false;
int p=0,q=0;
double temp=media;
bool verifica=true;
while(verifica)
{
double somma=0;
while(p<N)
{
if(somma+a[p]<=media && a[p]!=min && a[p]!=max){
if(c[p]==false){
somma+=a[p];
c[p]=false;
cout<<a[p]<<" - ";
}
}
verifica=true;
p++;
}
cout<<endl;
}
return 0;
}
Risposte
Ciao,
ho dato un'occhiata veloce al codice, il principio che utilizzi per la risoluzione è simile a quello che vorrei proporti, ma scritto in un'altra maniera (per la verità non ho molta voglia di cercare l'errore...).
Per il problema bisogna conoscere max e min per calcolare la media (forse si può pensare ad un algoritmo che sfrutti qualche proprietà particolare di "euristica" visitando una volta l'array, ma non penso sia lo scopo di ciò) e qui lo hai già scritto il codice, si potrebbero raggruppare in un unico ciclo, ma non c'è nessun guadagno.
Il problema di stampare tutti i possibili sottoarray, è lo stesso che elencare tutti i possibili sottoinsiemi di un insieme, cioè la proprietà dell'insieme delle parti \(\wp(A)\) di un insieme $A$, con una proprità da mantenere.
Io andrei di forza bruta con backtracking senza pensarci molto.
E' noto che l'insieme delle parti è equipotente all'insieme $2^A$ (si può scrivere in vari modi di solito $A->{0,1}$), cioè sono identici. Perciò il codice risulta essere con due cicli annidati sull'algoritmo di "enumerazione" (in parole povere stampare tutti i numeri da $0$ a $2^|A|$) che equivalente ad una funzione di scelta di un elemento da $A$:
con constante media e variabile temp che mantiene la proprietà della somma minore della media:
circa il codice dovrebbe essere questo...
In pratica esploro tutto lo spazio delle soluzioni, stampando solo gli elementi che mantengono la proprietà.
pensandoci forse si può trovare qualche algoritmo migliore formulandolo come problema di ottimizzazione, tipo: trovare il massimo numero di sottoarray che hanno la somma degli elementi minore o uguale alla media (ci si penserà domani).
EDIT:
corretto errore nel codice, così funziona.
ho dato un'occhiata veloce al codice, il principio che utilizzi per la risoluzione è simile a quello che vorrei proporti, ma scritto in un'altra maniera (per la verità non ho molta voglia di cercare l'errore...).
Per il problema bisogna conoscere max e min per calcolare la media (forse si può pensare ad un algoritmo che sfrutti qualche proprietà particolare di "euristica" visitando una volta l'array, ma non penso sia lo scopo di ciò) e qui lo hai già scritto il codice, si potrebbero raggruppare in un unico ciclo, ma non c'è nessun guadagno.
Il problema di stampare tutti i possibili sottoarray, è lo stesso che elencare tutti i possibili sottoinsiemi di un insieme, cioè la proprietà dell'insieme delle parti \(\wp(A)\) di un insieme $A$, con una proprità da mantenere.
Io andrei di forza bruta con backtracking senza pensarci molto.
E' noto che l'insieme delle parti è equipotente all'insieme $2^A$ (si può scrivere in vari modi di solito $A->{0,1}$), cioè sono identici. Perciò il codice risulta essere con due cicli annidati sull'algoritmo di "enumerazione" (in parole povere stampare tutti i numeri da $0$ a $2^|A|$) che equivalente ad una funzione di scelta di un elemento da $A$:
con constante media e variabile temp che mantiene la proprietà della somma minore della media:
for j = 0 to (2^n − 1)
for i = 0 to n − 1 do
if j & 2^i then //bitwise AND
temp=temp + a[i]
if(temp<media)
print a[i]
else temp=temp-a[i]
print endl
temp = 0
circa il codice dovrebbe essere questo...
In pratica esploro tutto lo spazio delle soluzioni, stampando solo gli elementi che mantengono la proprietà.
pensandoci forse si può trovare qualche algoritmo migliore formulandolo come problema di ottimizzazione, tipo: trovare il massimo numero di sottoarray che hanno la somma degli elementi minore o uguale alla media (ci si penserà domani).
EDIT:
corretto errore nel codice, così funziona.
A volte in questi esercizi si chiedono sottoarray nel senso di sequenze di elementi consecutivi. Il problema in quel caso diventa molto più interessante e computazionalmente fattibile.
Per intenderci... Supponiamo che in un array di 10 elementi la somma dei primi 3 sia minore della media e che sia massimale. Allora si ha che i seguenti sottoarray di elementi consecutivi rispettano la condizione scelta:
[1]
[1,2]
[2]
[1,2,3]
[2,3]
[3]
A questo punto però si sa che:
[1,2,3,4]
senza dubbio non la rispetta e quindi si testerà [2,3,4].
Il tutto può essere fatto abbastanza efficaciemente.
Per quanto riguarda il caso generale penso possa valer la pena riordinare gli elementi dell'array (senza spostamento perché devi tenere conto dell'ordine quando stampi a video)
Per esempio nel caso:.[4, 4.5, 4.8, 36, 7, 8, 9, 11, 5, 6.1] (mi piace di più con le quadre :p)
Allora l'array ordinato sarà [4, 4.5, 4.8, 5, 6.1, 7, 8, 9, 11, 36] e la permutazione usata è stata \(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 3 & 10 & 6 & 7 & 8 & 9 & 4 & 5\end{pmatrix} \)
La cui inversa è \(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 3 & 9 & 10 & 5 & 6 & 7 & 8 & 4\end{pmatrix} \)
Ora consideriamo [4, 4.5, 4.8, 5, 6.1, 7, 8, 9, 11, 36]. Sappiamo che la media è (36+4)/2 = 20.
Per comodità segnamo con \(\displaystyle \wp_{\le a}\langle i,j\rangle \) il problema di trovare i sottoinsiemi con somma \(\displaystyle \le a \) nel range \(\displaystyle \langle i,j\rangle \).
Ora quindi il problema grande è \(\displaystyle \wp_{\le 20}\langle 1,N\rangle \). D'altra parte dato che abbiamo ordinato e senza dubbio il massimo è maggiore della media. Quindi \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-1 \rangle\).
Consideriamo ora \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-1 \rangle\) e l'elemento (N-1)-esimo. Se quest'ultimo è maggiore della media allora \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-2 \rangle\), altrimenti \(\displaystyle \wp_{\le 20}\langle 1,N-1\rangle = \wp_{\le 20}\langle 1,N-2 \rangle \cup [N-1]\cup\left\{ [N-1]\cup A \mid A \in \wp_{\le 20- a(N-1)}\langle 1,N-2 \rangle\right\}\).
Usando questa formula è possibile calcolarlo ricorsivamente. Non sono però sicuro sia così più efficiente (controlla più di una volta molti insiemi tra l'altro).
Per intenderci... Supponiamo che in un array di 10 elementi la somma dei primi 3 sia minore della media e che sia massimale. Allora si ha che i seguenti sottoarray di elementi consecutivi rispettano la condizione scelta:
[1]
[1,2]
[2]
[1,2,3]
[2,3]
[3]
A questo punto però si sa che:
[1,2,3,4]
senza dubbio non la rispetta e quindi si testerà [2,3,4].
Il tutto può essere fatto abbastanza efficaciemente.
Per quanto riguarda il caso generale penso possa valer la pena riordinare gli elementi dell'array (senza spostamento perché devi tenere conto dell'ordine quando stampi a video)
Per esempio nel caso:.[4, 4.5, 4.8, 36, 7, 8, 9, 11, 5, 6.1] (mi piace di più con le quadre :p)
Allora l'array ordinato sarà [4, 4.5, 4.8, 5, 6.1, 7, 8, 9, 11, 36] e la permutazione usata è stata \(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 3 & 10 & 6 & 7 & 8 & 9 & 4 & 5\end{pmatrix} \)
La cui inversa è \(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 3 & 9 & 10 & 5 & 6 & 7 & 8 & 4\end{pmatrix} \)
Ora consideriamo [4, 4.5, 4.8, 5, 6.1, 7, 8, 9, 11, 36]. Sappiamo che la media è (36+4)/2 = 20.
Per comodità segnamo con \(\displaystyle \wp_{\le a}\langle i,j\rangle \) il problema di trovare i sottoinsiemi con somma \(\displaystyle \le a \) nel range \(\displaystyle \langle i,j\rangle \).
Ora quindi il problema grande è \(\displaystyle \wp_{\le 20}\langle 1,N\rangle \). D'altra parte dato che abbiamo ordinato e senza dubbio il massimo è maggiore della media. Quindi \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-1 \rangle\).
Consideriamo ora \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-1 \rangle\) e l'elemento (N-1)-esimo. Se quest'ultimo è maggiore della media allora \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-2 \rangle\), altrimenti \(\displaystyle \wp_{\le 20}\langle 1,N-1\rangle = \wp_{\le 20}\langle 1,N-2 \rangle \cup [N-1]\cup\left\{ [N-1]\cup A \mid A \in \wp_{\le 20- a(N-1)}\langle 1,N-2 \rangle\right\}\).
Usando questa formula è possibile calcolarlo ricorsivamente. Non sono però sicuro sia così più efficiente (controlla più di una volta molti insiemi tra l'altro).
scusa @hamming_burst
che proprietà è quella che mi hai scritto
mi sa che l'esercizio che mi sono inventato presenta aspetti che non fanno parte del corso
comunque ti ringrazio molto e se mi puoi dare una spiegazione più dettagliata riguardo al fatto che l'insieme delle parti è equipotente all'insieme 2A ne sarei molto curioso
grazie mille
che proprietà è quella che mi hai scritto
mi sa che l'esercizio che mi sono inventato presenta aspetti che non fanno parte del corso
comunque ti ringrazio molto e se mi puoi dare una spiegazione più dettagliata riguardo al fatto che l'insieme delle parti è equipotente all'insieme 2A ne sarei molto curioso
grazie mille
Intuitivamente se tu hai un insieme \(\displaystyle A \) e un suo sottoinsieme \(\displaystyle S \) esiste una funzione che manda gli elementi di \(\displaystyle S \) in 1 e tutti gli altri in 0. Al variare di \(\displaystyle S \) cambia questa funzione. La presenza o meno di un elemento in un sottoinsieme è indipendente dalla presenza o meno nel sottoinsieme di un altro. Quindi per ogni elemento di A ci sono due possibilità ‘dentro’ e ‘fuori’. A questo punto ci sono \(\displaystyle |A| \) elementi di \(\displaystyle A \) e per tutti si hanno \(\displaystyle 2 \) possibilità. Moltiplicando tra loro queste possibilità si ricava \(\displaystyle 2^{|A|} \).
Un modo alternativo è farlo ricorsivamente. Nel senso che \(\displaystyle \wp\bigl(\{A, a\}\bigr) = 2\wp\bigl(\{A\}\bigr) \) in quanto consiste nella somma degli insiemi che contengono \(\displaystyle a \) più gli insiemi che non contengono \(\displaystyle a \) e il loro numero è \(\displaystyle \wp\bigl(\{A\}\bigr) \). Dubbi su questo?
P.S: Caso infinito a parte ovviamente... Quello lo lascio ai logici...
Un modo alternativo è farlo ricorsivamente. Nel senso che \(\displaystyle \wp\bigl(\{A, a\}\bigr) = 2\wp\bigl(\{A\}\bigr) \) in quanto consiste nella somma degli insiemi che contengono \(\displaystyle a \) più gli insiemi che non contengono \(\displaystyle a \) e il loro numero è \(\displaystyle \wp\bigl(\{A\}\bigr) \). Dubbi su questo?
P.S: Caso infinito a parte ovviamente... Quello lo lascio ai logici...
"maschulillo":
scusa @hamming_burst
che proprietà è quella che mi hai scritto
mi sa che l'esercizio che mi sono inventato presenta aspetti che non fanno parte del corso
quello che ho scritto non è propriamente "backtracking" perchè non c'è effettivamente un passo di backtrack non si torna indietro; più correttamente è una "ricerca sistematica completa" (la vera e propria "forza bruta"
).comunque ti ringrazio molto e se mi puoi dare una spiegazione più dettagliata riguardo al fatto che l'insieme delle parti è equipotente all'insieme 2A ne sarei molto curioso
EDIT: ti ha risposto vict85
"vict85":
A volte in questi esercizi si chiedono sottoarray nel senso di sequenze di elementi consecutivi. Il problema in quel caso diventa molto più interessante e computazionalmente fattibile.
ah non ci avevo fatto caso, le sottosequenze si chiamano allora. Sì mi pare siano la stessa cosa
Per esempio nel caso:.[4, 4.5, 4.8, 36, 7, 8, 9, 11, 5, 6.1] (mi piace di più con le quadre :p)
Allora l'array ordinato sarà [4, 4.5, 4.8, 5, 6.1, 7, 8, 9, 11, 36] e la permutazione usata è stata \(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 3 & 10 & 6 & 7 & 8 & 9 & 4 & 5\end{pmatrix} \)
La cui inversa è \(\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 2 & 3 & 9 & 10 & 5 & 6 & 7 & 8 & 4\end{pmatrix} \)
perchè ci serve sapere l'inversa? (cursiosità: ha un nome questa notazione delle permutazioni in forma matriciale?)
Ora consideriamo [4, 4.5, 4.8, 5, 6.1, 7, 8, 9, 11, 36]. Sappiamo che la media è (36+4)/2 = 20.
Per comodità segnamo con \(\displaystyle \wp_{\le a}\langle i,j\rangle \) il problema di trovare i sottoinsiemi con somma \(\displaystyle \le a \) nel range \(\displaystyle \langle i,j\rangle \).
Ora quindi il problema grande è \(\displaystyle \wp_{\le 20}\langle 1,N\rangle \). D'altra parte dato che abbiamo ordinato e senza dubbio il massimo è maggiore della media. Quindi \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-1 \rangle\).
Consideriamo ora \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-1 \rangle\) e l'elemento (N-1)-esimo. Se quest'ultimo è maggiore della media allora \(\displaystyle \wp_{\le 20}\langle 1,N\rangle = \wp_{\le 20}\langle 1,N-2 \rangle\), altrimenti \(\displaystyle \wp_{\le 20}\langle 1,N-1\rangle = \wp_{\le 20}\langle 1,N-2 \rangle \cup [N-1]\cup\left\{ [N-1]\cup A \mid A \in \wp_{\le 20- a(N-1)}\langle 1,N-2 \rangle\right\}\).
Usando questa formula è possibile calcolarlo ricorsivamente. Non sono però sicuro sia così più efficiente (controlla più di una volta molti insiemi tra l'altro).
Mi piace questa soluzione
Direi che utilizzando la programmazione dinamica si possa fare qualche ottimizzazione, sui casi in cui si visita lo stesso insieme.
Comunque se lo trovi difficile prova con la versione in cui devi trovare sequenze di elementi consecutivi minori di una certa somma. Oppure prova a cercare sequenze massimali di questo tipo. A me questo problema era stato dato nel corso di informatica e penso possa fornire ampi spazi di riflessione. Non ha tra l'altro bisogno di conoscenze specifiche di teoria degli insiemi.
P.S: puoi anche semplicemente mettere che deve essere minore di un certo valore eventualmente inserito dall'utente.
P.S2: un suggerimento: non usare variabili globali, metti const tutto ciò che sai che non cambia (è meglio per varie ragioni ma una è proprio che il compilatore controlla che sia effettivamente così) e infine definisci le cose solo quando ti servono e rendili esistenti non più del necessario. Inoltre è generalmente meglio se costruisci funzioni ad hoc per le tue operazioni invece di infilare tutto nel main. Per concludere se il tuo ciclo è di fatto un for non usare un while e viceversa (ci sono ragioni per usare l'uno invece dell'altro).
P.S: puoi anche semplicemente mettere che deve essere minore di un certo valore eventualmente inserito dall'utente.
P.S2: un suggerimento: non usare variabili globali, metti const tutto ciò che sai che non cambia (è meglio per varie ragioni ma una è proprio che il compilatore controlla che sia effettivamente così) e infine definisci le cose solo quando ti servono e rendili esistenti non più del necessario. Inoltre è generalmente meglio se costruisci funzioni ad hoc per le tue operazioni invece di infilare tutto nel main. Per concludere se il tuo ciclo è di fatto un for non usare un while e viceversa (ci sono ragioni per usare l'uno invece dell'altro).
"hamming_burst":
perchè ci serve sapere l'inversa? (cursiosità: ha un nome questa notazione delle permutazioni in forma matriciale?)
No, con notazione matriciale si intende il sottogruppo del gruppo delle matrici ortogonali. Quello penso sia tipo notazione in colonna o qualcosa del genere. Non si usa spesso. Personalmente io avrei segnato la permutazione come \(\displaystyle (4\;10\;5\;6\;7\;8\;9) \) e la sua inversa come \(\displaystyle (4\;9\;8\;7\;6\;5\;10) \) ma per persone che non hanno mai studiato algebra questa notazione è un po' oscura. Si chiama rappresentazione in cicli disgiunti (in questo caso si tratta di un ciclo). Deriva dal fatto che le permutazioni possono essere fattorizzate in questo modo in modo unico. Quando ci prendi dimestichezza diventano molto utili. D'altra parte non lo sono tantissimo se ci devi creare una classe
. Io per la decomposizione LU ho usato una "lista di pivot" in altre parole ho rappresentato la permutazione come \(\displaystyle (n-1\;m)\dotsb (2\;b)(1\;a) \) (non sono disgiunti come scambi ed è un po' tedioso da invertire ma è molto veloce applicare la permutazione). Tieni presente che \(\displaystyle (1\;a) \) vuoli dire scambia \(\displaystyle 1 \) con \(\displaystyle a \) e che le permutazione vengono spesso lette da destra a sinistra come le funzioni.L'ho invertito per passare velocemente da uno all'altro. Ma serve più che altro passare dall'ordinato all'originale.
**************************
Riguardo al metodo penso che si possa migliorare se durante l'ordinamento si salva un array con le somme parziali. In questo modo se la somma di tutto il pezzo è minore di quella richiesta si ritorna direttamente l'insieme delle parti di quel pezzo.
Detto questo ci sono delle cose nell'implementazione che vedo tediose senza l'uso di vector o list (ma preferisco vector)
"vict85":
No, con notazione matriciale si intende il sottogruppo del gruppo delle matrici ortogonali. Quello penso sia tipo notazione in colonna o qualcosa del genere. Non si usa spesso. Personalmente io avrei segnato la permutazione come \(\displaystyle (4\;10\;5\;6\;7\;8\;9) \) e la sua inversa come \(\displaystyle (4\;9\;8\;7\;6\;5\;10) \) ma per persone che non hanno mai studiato algebra questa notazione è un po' oscura.
dici bene, di Algebra conosco poco (a parte alcune teorie che si legano con la mia tesi), penso che questa sia Teoria dei gruppi, dove non conosco nulla
Si chiama rappresentazione in cicli disgiunti (in questo caso si tratta di un ciclo). Deriva dal fatto che le permutazioni possono essere fattorizzate in questo modo in modo unico. Quando ci prendi dimestichezza diventano molto utili. D'altra parte non lo sono tantissimo se ci devi creare una classe
L'ho invertito per passare velocemente da uno all'altro. Ma serve più che altro passare dall'ordinato all'originale.
molto interessante, ti ringrazio vict
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo