I m possible
I m possible
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.
Re: I m possible
Ce n'ho una in tempo costante: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.
Codice: Seleziona tutto
return false
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
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':
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.
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;
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
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).
Quindi, come estensione dell'esercizio, trovare la soluzione che usa tempo O(N) e spazio O(1).
capito:
magari e' sbagliato e c'e' qualche off-by-one pero' non ho tempo di rivederlo ora...
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;
paolo