Trovare a,b,c tali che 1 ≤ a+b+c ≤ 2 in O(n)

Trovare a,b,c tali che 1 ≤ a+b+c ≤ 2 in O(n)

Messaggioda marco il mar 18 set 2012, 12:21

Dato un array A di n numeri positivi descrivere un algoritmo con complessità O(n) che trovi, se presenti, tre elementi di A la cui somma è compresa tra 1 e 2. Se non esistono tali elementi l'algoritmo deve riportarlo.
The first rule of first order logic is you can't talk about first order logic
marco
 
Messaggi: 26
Iscritto il: mer 2 lug 2008, 16:27

....

Messaggioda Pater92 il gio 20 set 2012, 9:10

// scrivo in pseudocodice bertossi spero che sia conprensible, è un mix c++ /pascal

se l'array fosse fatto solo di interi positivi ti basterebbe prendere tre
contatori uno per gli zeri uno per gli uno e uno per i due

scorri tutto l'array e per ogni elemento incrementi il contatore relativo
se A[i]=0 zero++
se A[i]=1 uno++
se A[i]=2 due++

finito di scorrere controlli...

if zero>0 then
if uno>1 or (due>0 and zero>1) then return trovato
else return non trovato
else return non trovato
Pater92
 
Messaggi: 1
Iscritto il: gio 20 set 2012, 8:59

Messaggioda marco il gio 20 set 2012, 10:23

Ciao Pater, attento che l'array non è di interi positivi ma di numeri positivi, ovvero possono essere frazionari.
The first rule of first order logic is you can't talk about first order logic
marco
 
Messaggi: 26
Iscritto il: mer 2 lug 2008, 16:27

Messaggioda pasquale89 il lun 11 feb 2013, 7:48

in matlab

Codice: Seleziona tutto
n=Numero_di_Valori;

% [tuo array] = array degli n valori da controllare

a=[tuo array];
b=[tuo array];
c=[tuo array];

r=1;
results=zeros(n,n);

% Equazioni base
% a=>1-b-c;
% a<=2-b-c;

for i=0:n
      for j=1:n
           for k=1:n
               a_t=a(i);
               b_t=b(j);
               c_t=c(k);
               if((a_t+b_t+c_t>=1) && (a_t+b_t+c_t<=2))
                    results(r,:)=[a_t b_t c_t];
                    r=r+1;
               end
           end
      end
end

if(r==0)
    display('nessun valore soddisfa la disuguagliana');
else
    display(strcat(int2str(r),' terne di valori soddisfano l'equazione');
    results
end


Adattato un po può funzionare anche in C++
pasquale89
 
Messaggi: 3
Iscritto il: lun 11 feb 2013, 7:17

Re: Trovare a,b,c tali che 1 ≤ a+b+c ≤ 2 in O(n)

Messaggioda Gottinger95 il mer 14 mag 2014, 14:08

@pasquale89: Sbaglio o l'algoritmo che hai presentato è \(O(n^3) \)?
Gottinger95
 
Messaggi: 16
Iscritto il: lun 12 mag 2014, 21:32

Re: Trovare a,b,c tali che 1 ≤ a+b+c ≤ 2 in O(n)

Messaggioda Lord K il lun 24 nov 2014, 14:08

Gottinger95 ha scritto:@pasquale89: Sbaglio o l'algoritmo che hai presentato è \(O(n^3) \)?


Infatti non sbagli!
"La realtà è una invenzione di chi ha dimenticato come si sogna!" C.M.
"Il mio libro nero non ha un insieme di pagine ma una classe di pagine" C.M.
Lord K
 
Messaggi: 402
Iscritto il: gio 23 ott 2008, 14:31
Località: Trieste, Ferrara


Torna a Algoritmi e strutture dati

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite