OliForum Matematico

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.

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 $.

Ok

. Correggo la traccia, intendevo tutti 1 eccetto la diagonale.

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.

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).

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...

OliForum Matematico

I m possible

I m possible

Re: I m possible