[C] il mediano di due vettori ...

[MetalMassacre]

Ciao,
porgo anche a voi questo problemino..
ho due array con lo stesso numero di elementi, e sono entrambi ordinati (suppongo entrambi crescenti).

Devo torvare l'elemento mediano che si ottierrebbe facilmente creando un unico array ordinato composto dalla fusione degli elementi dei due array di partenza, ma arriva il bello...ho un vincolo di complessita..questa deve essere nella classe O(lg(n))...e ovviamente non posso ordinare sti array altrimenti sfonderei gia sto vincolo.

Vi porto un esempio..
se i vettori sono

A[1,5,8,14,22]

B[3,4,9,10,25]

1,3,4,5,8 ,9,10,14,22,25 avendo ora 2n elementi in ogni caso i mediani di per se sono sempre due per cui devo ritornare il minore..in questo caso 8

Suggerimenti?

cionci, non dubito delle tue capacità, ma magari qualcun'altro puo darci una dritta..

[Fenomeno85]

il mediano è quel valore che sta in centro alla distribuzione? non mi ricordo + :D

~§~ Sempre E Solo Lei ~§~

[repne scasb]

[repne scasb]

[MetalMassacre]

Originariamente inviato da Fenomeno85
il mediano è quel valore che sta in centro alla distribuzione? non mi ricordo + :D

~§~ Sempre E Solo Lei ~§~


si come nell'esempio..

[MetalMassacre]

Originariamente inviato da repne scasb
Questo forse e' piu' corretto:



Sono troppo stanca, c'e' "forse" un qualche elemento "discreto" da analizare meglio.


Grazie per la partecipazione anzitutto..

Mi ci vorra un po per vedere che fa questo codice di preciso preciso.
Ho visto 2 do-while, la complessità risulta cmq O(lg(n))?

[repne scasb]

[MetalMassacre]

Ha.. mi è stato consigliato di valutare una possibile variante alla ricerca binaria. Si puo quindi implementare anche diversamente quindi, magari ricorsivmente.

[MetalMassacre]

e questo come vai pare?




int cerca_mediano(int x[], int s1, int y[], int s2)
{
int count=0;
int i,j=0;

do
{if (x[i]<y[j])
while (x[i]<y[j] && count<s1)
{i++;
count++;}
else
while(y[j]<x[i] && count<s1)
{j++;
count++;}
}while (count!=(s1/2)-2);

if (x[i]<y[j])
return x[i];
else
return y[j];

}




Non riesco a provarlo.. Devc++ svanga le balle.. che altro posso usare sotto win?!? ...gratuito...

[repne scasb]

[sirus]

se vuoi un ottimo compilatore in ambiente win32 gratuito vai sul sito borland e scarica il c++builderX previa registrazione, tutto gratuito (solo inglese) ;)

[MetalMassacre]

questo funzia, ma credo sia di complessita O(n)..che dite?


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
int count=0;
int i=0;
int j=0;
int k=(6-1);/*k=n-1*/
int x[6]={2,5,7,9,23,25};
int y[6]={4,6,8,10,12,34};

do
{if (x[i]<=y[j])
while (x[i]<=y[j])
{i++;
count++;}
else
while(y[j]<x[i])
{j++;
count++;}
}while (count!=k);

if (x[i]<y[j])
printf ("Il mediano risulta: %d\n",x[i]);
else
printf ("Il mediano risulta: %d\n",y[j]);

system("PAUSE");

}

[MetalMassacre]

Originariamente inviato da sirus
se vuoi un ottimo compilatore in ambiente win32 gratuito vai sul sito borland e scarica il c++builderX previa registrazione, tutto gratuito (solo inglese) ;)


ok grazie provvedero al piu presto.. ma che versione devo prendere?
la enterprise trial o la personal? o che altro?

ho fatto riferimento a questo link (http://www.borland.com/products/downloads/download_cbuilderx.html)

[sirus]

la personal ;) ottimo compilatore (qualità borland)