I m possible

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

I m possible

Messaggio da rand »

E' data in input una matrice quadrata A[1...N,1...N] antisimmetrica, cioè A[i,j] = - A[j,i] ed A[i,i] = 0 per ogni i,j, e nella quale ogni elemento può essere uguale a 1, -1 o 0. Scrivere una procedura che in tempo lineare in N scopre se esiste una riga di A avente tutti gli elementi uguali a 1 tranne quello sulla diagonale.
Ultima modifica di rand il 14 mar 2008, 10:19, modificato 1 volta in totale.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Re: I m possible

Messaggio da Marco »

rand ha scritto:Scrivere una procedura che in tempo lineare in N scopre se esiste una riga di A avente tutti gli elementi uguali a 1.
Ce n'ho una in tempo costante:

Codice: Seleziona tutto

return false
Infatti, $ a_{i,i} = 0 $. ;-)
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Ok :). Correggo la traccia, intendevo tutti 1 eccetto la diagonale.
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa »

innanzitutto notare che se la riga i e' di 1 la colonna i e' di -1, quindi puo' esistere una sola riga con questa proprieta'.
procediamo cosi':

Codice: Seleziona tutto

i = 0; j = 1;
while(i < n && j < n)
{
  if(a[i][j] == 1)
    {
       rigaEsclusa[j] = true; //per l'antisimmetria nella riga j ci sara' un -1
       ++j;
    }
  else if(a[i][j] == -1)
    {
       rigaEsclusa[i] = true;
       while(!rigaEsclusa[i] && i < n)
         {
            ++i;
         }
        j = i+1;
    }
  else
    {
        rigaEsclusa[i] = rigaEsclusa[j] = true;
         while(!rigaEsclusa[i] && i<n)
           {
              ++i;
            }
          j = i+1;
    }
}
for(int i = 0; i < n; ++i)
{
  if(!rigaEsclusa[i])
    {
       for(int j = 0; j < n; ++j)
        {
           if(a[i][j] == -1 || (a[i][j] == 0 && i != j))
             {
                  return false;
              }
         }
    }
}
return true;
l'idea e' questa:
a ogni ciclo del while piu' esterno si esclude almeno una riga possibile quindi non verra' eseguito piu' n volte e la parte al suo interno in tempo costante ammortizzato( mi sembra si dica cosi') perche' i cicli al suo interno non fanno piu' di n iterazioni in TOTALE.
alla fine puo' rimanermi al massimo una riga possibile che penso rivada controllata.
paolo
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Ok, funziona ed ha tempo O(N). Ma è inefficiente in spazio, che è O(N) perchè deve mantenere l'array rigaEsclusa. Questo si può evitare mediante una piccola variante, la cui l'implementazione è anche più corta.
Quindi, come estensione dell'esercizio, trovare la soluzione che usa tempo O(N) e spazio O(1).
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa »

capito:

Codice: Seleziona tutto

int i = 0; j = 1;
while(i < n && j < n)
{
  if(a[i][j] == 1)
    {
      ++j;
    }
  else if(a[i][j] == -1)
    {
      i = j;
      j =i+1;
    }
  else
    {
      i = j+1;
      j = i+1;
    }
}
for(j = 0; j < n; ++j)
{
  if(a[i][j] == -1 || (a[i][j] == 0 && i != j))
    return false;
}
return true;
magari e' sbagliato e c'e' qualche off-by-one pero' non ho tempo di rivederlo ora... :D
paolo
Rispondi