Se poi non si vogliono usare gli alberi di ricerca è sufficiente ordinare l'array di input all'inizio e memorizzarlo in un array c.
Ad ogni passo per verificare se abbiamo già inserito in b un elemento maggiore di a eseguiamo una ricerca binaria in c, tenendo conto del fatto che dobbiamo cercare elementi già inseriti (per esempio è possibile assegnare ad ogni elemento di c un altro campo che ci dice a quale indice nell'array di input corrispondeva).
Oppure ora che si penso l'array b è già ordinato e quindi si effettua la ricerca binaria su quest'ultimo.
La domanda è ora: si può fare meglio di O(nlogl)?
Per esempio in tempo lineare?
piccole sottosequenze crescono
hmm... se interpreto bene sembra tutto ok. 
Il trucco di fare ricerca binaria su un array ordinato è proprio quello a cui avevo pensato io.
Ora che hai tutti i diversi "pezzi" se hai voglia potresti provare a scrivere l'algoritmo su un messaggio solo (anche solo descrivendolo, senza stare a farsi del male con lo pseudo-codice
).
Non credo che si riesca a scendere sotto n log n, sembra tanto che ci vogliano troppi confronti (anche se non ho cercato una dimostrazione di questo fatto).
ciao,
Il trucco di fare ricerca binaria su un array ordinato è proprio quello a cui avevo pensato io.
Ora che hai tutti i diversi "pezzi" se hai voglia potresti provare a scrivere l'algoritmo su un messaggio solo (anche solo descrivendolo, senza stare a farsi del male con lo pseudo-codice
).Non credo che si riesca a scendere sotto n log n, sembra tanto che ci vogliano troppi confronti (anche se non ho cercato una dimostrazione di questo fatto).
ciao,
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Faccio di più, scrivo un programmino C per il problema:
---------
#include <stdio>
int a[1000];
typedef struct {
int i;
int p;
} s;
s b[1000];
int c[1000];
int out[1000];
int main(void){
int n=0;
int j=0;
int x,y,i,m;
while(scanf("%d",&a[n])!=-1)n++;
b[0].i=a[0];
b[0].p=0;
c[0]=-1;
for (i=1;i<n>=a) y--;
else x++;
}
if (b[x].i>=a){
if (x>0)
c=b[x-1].p;
else c=-1;
b[x].p=i;
b[x].i=a;
} else {
j++;
if (j>0)
c=b[j-1].p;
else c=-1;
b[j].p=i;
b[j].i=a;
}
}
n=j;
for (x=b[j].p;x!=-1;x=c[x])out[n--]=a[x];
for (x=0;x<=j;x++)printf("%d ",out[x]);
printf("\n");
return 0;
}
--------
Il programmino prende in input una sequenza di numeri terminata da EOF (cioè se lo si esegue da console, dopo aver inserito i numeri bisogna premere CTRL+D (almeno sotto linux/unix) o altrimenti passargli in input un file).
E restituisce UNA tra le sequenze più lunghe ascendenti.
Esempio:
linux:~ # ./a.out
6 10000 2 3 37 5 39 11 29 13 14 1
2 3 5 11 13 14
linux:~ #
Ciao!
Nota: io scrivo "stdio punto h" ma quando invio il messaggio il forum mi togli il "punto h".
Se il vostro compilatore vi segnala un errore aggiungete "punto h" dopo "stdio" (in ogni caso potete anche eliminare quella riga perché è solo una banale inclusione di prototipi).
Aggiungo post scriptum un'osservazione che mi è venuta in mente ora:
All'inizio avevo pensato di usare gli alberi di ricerca, in tal modo si avrebbe avuto un tempo O(nlogn) se si fosser ousati gli alberi di ricerca con operazioni in tempo O(logn), ma se si usano i cosiddetti sqrt(n)-trees con operazioni in tempo O(log(logn)) si ha un algoritmo di tempo O(nlog(logn))!!!!
---------
#include <stdio>
int a[1000];
typedef struct {
int i;
int p;
} s;
s b[1000];
int c[1000];
int out[1000];
int main(void){
int n=0;
int j=0;
int x,y,i,m;
while(scanf("%d",&a[n])!=-1)n++;
b[0].i=a[0];
b[0].p=0;
c[0]=-1;
for (i=1;i<n>=a) y--;
else x++;
}
if (b[x].i>=a){
if (x>0)
c=b[x-1].p;
else c=-1;
b[x].p=i;
b[x].i=a;
} else {
j++;
if (j>0)
c=b[j-1].p;
else c=-1;
b[j].p=i;
b[j].i=a;
}
}
n=j;
for (x=b[j].p;x!=-1;x=c[x])out[n--]=a[x];
for (x=0;x<=j;x++)printf("%d ",out[x]);
printf("\n");
return 0;
}
--------
Il programmino prende in input una sequenza di numeri terminata da EOF (cioè se lo si esegue da console, dopo aver inserito i numeri bisogna premere CTRL+D (almeno sotto linux/unix) o altrimenti passargli in input un file).
E restituisce UNA tra le sequenze più lunghe ascendenti.
Esempio:
linux:~ # ./a.out
6 10000 2 3 37 5 39 11 29 13 14 1
2 3 5 11 13 14
linux:~ #
Ciao!
Nota: io scrivo "stdio punto h" ma quando invio il messaggio il forum mi togli il "punto h".
Se il vostro compilatore vi segnala un errore aggiungete "punto h" dopo "stdio" (in ogni caso potete anche eliminare quella riga perché è solo una banale inclusione di prototipi).
Aggiungo post scriptum un'osservazione che mi è venuta in mente ora:
All'inizio avevo pensato di usare gli alberi di ricerca, in tal modo si avrebbe avuto un tempo O(nlogn) se si fosser ousati gli alberi di ricerca con operazioni in tempo O(logn), ma se si usano i cosiddetti sqrt(n)-trees con operazioni in tempo O(log(logn)) si ha un algoritmo di tempo O(nlog(logn))!!!!