Non credo sia sbagliato, eseguendo le istruzioni passo passo partendo da un insieme di 15 valori totali che vanno da 0 14
pos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
val 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
rad diventerà quindi 4 e le deque saranno:
A[0]={ 0, 1, 2, 3}
A[1]={4, 5, 6, 7}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}
Simulando un’operazione di scambio “s 5 8”
primo=5, secondo=8, primadeq=1, secondadeq=2
val=A[1][1]=5 ed è corretto
A.erase(A.begin()+1): quindi toglie il 5 ed le deque diventano:
A[0]={ 0, 1, 2, 3}
A[1]={4, 6, 7}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}
pos=secondo%rad 8%4=0 ed è corretto
A[secondadeq].insert(A[secondadeq].begin()+pos,val); A[2].insert(A[2]+0, 5) e quindi diventeranno:
A[0]={ 0, 1, 2, 3}
A[1]={4, 6, 7}
A[2]={5, 8, 9, 10, 11}
A[3]={12, 13 ,14}
for(int j=primadeq;j<secondadeq;j++)
– A[j].push_back(A[j+1].front());
– A[j+1].pop_front();
A[0]={ 0, 1, 2, 3}
A[1]={4, 6, 7, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}
ed è corretto, e credo di poter affermare la stessa cosa anche con primo>secondo ma provo lo stesso
Partendo dal caso corrente effettuo un s 6 1
primo=6 secondo=1 primadeq=6/1 =1 secondadeq1=1/4=0
val=A[1][6%4]=A[1][2]=7 ed è corretto
pos=secondo%rad= 1
A[secondadeq].insert(A[secondadeq].begin()+pos,val);= inser(A[0]+1, val)
e diventa:
A[0]={ 0,7, 1, 2, 3}
A[1]={4, 6, 7, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}
A[primadeq].erase(A[primadeq].begin()+primo%rad);
A[1].erase(A[1]+2) e diventa
A[0]={ 0,7, 1, 2, 3}
A[1]={4, 6, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}
for(int j=secondadeq;j<primadeq;j++)
{
A[j+1].push_back(A[j].back());
A[j].pop_back();
}
quindi solo in questo caso for(int j=0;j<1;j++)
A[0]={ 0,7, 1, 2,}
A[1]={3, 4, 6, 5}
A[2]={8, 9, 10, 11}
A[3]={12, 13 ,14}
Ed è corretto, quindi sono ancora più perplesso, ripeto che comunque mi sembra strano che il mio worst_case sia solo 0,130s e quindi credo ci sia qualche errore che non è legato alle operazioni sulle deque [quote=“VashTheStampede, post:60, topic:3800”]
n questo momento non sono a casa quindi non riesco ad aiutarti molto,
[/quote]
Nessun problema