Rotazione di un array utilizzando l'algoritmo di giocoleria

Question

Recentemente ho appreso come l'algoritmo di giocoleria ruota un array in tempo lineare mentre stavo leggendo la soluzione nel libro Programmazione perle.

Il codice per risolverlo è stato il seguente:

/*Function to left rotate arr[] of siz n by d*/ 
void leftRotate(int arr[], int d, int n) 
{ 
    int i, j, k, temp; 
    for (i = 0; i < gcd(d, n); i++) 
    { 
    /* move i-th values of blocks */ 
    temp = arr[i]; 
    j = i; 
    while(1) 
    { 
     k = j + d; 
     if (k >= n) 
     k = k - n; 
     if (k == i) 
     break; 
     arr[j] = arr[k]; 
     j = k; 
    } 
    arr[j] = temp; 
    } 
} 

Ho due domande riguardanti questo algoritmo -

1. Come si fa il MCD decidere il numero di cicli necessari per ruotare il array?
2. Perché una volta terminato un ciclo, iniziamo il nuovo ciclo dall'elemento successivo, ad es. il prossimo elemento non può essere già una parte di di un ciclo elaborato?

mi sento, mi manca qualcosa di fondamentale per quanto riguarda il funzionamento del GCD, modulo ei cicli.

La seguente domanda aveva una risposta alla mia prima domanda, ma ancora non ero in grado di capirlo.

Juggling algorithm of string rotation

Quindi, sarebbe utile se qualcuno può spiegare in termini profani e il principio alla base il modo in cui tutto il gel insieme per fare questo lavoro algoritmo.

Answer 1

In che modo il GCD decide il numero di cicli necessari per ruotare l'array?

Poiché gli incrementi anello interno con passi di d, e si arresta quando si torna al punto di partenza, cioè un intervallo totale che è un multiplo di n. Questo multiplo è LCM(n, d). Quindi il numero di elementi in quel ciclo è LCM(n, d)/d. Il numero totale di tali cicli è n/(LCM(n, d)/d), che è uguale a GCD(n, d).

Per quale motivo una volta terminato un ciclo, iniziamo il nuovo ciclo dall'elemento successivo in cui l'elemento successivo non può già essere una parte di un ciclo elaborato?

No. Gli incrementi ciclo interno con passi di d, che è un multiplo di GCD(n, d). Pertanto, quando avvieremo il ciclo i -th, per un successo avremo bisogno di (k*GCD + z) % n == i (per 0 <= z < i). Questo porta a (k*GCD) % n == (i - z). Questo chiaramente non ha soluzioni.

Answer 2

GCD è davvero un esempio della bellezza della matematica. A volte, quando prendi la cosa nella tua mente, la tua mente risponderebbe a se stessa per le cose che mette mettendo da parte ciò che è successo.

Ora venendo alla domanda, l'attività di rotazione, avrebbe potuto semplicemente funzionare con un ciclo for. L'algoritmo di giocoleria potrebbe avere alcuni vantaggi (non ho trovato cosa).

Ora arrivando al punto Perché GCD. Il GCD fornisce una figura esatta di rotazione da eseguire. In realtà riduce al minimo il numero di rotazioni.

Ad esempio,

se si desidera eseguire la rotazione di 30 numeri

con d = 1 l'anello esterno ruoterà volta interna sarebbe ruotare 30 volte 1*30=30

con d = 2 il ciclo esterno ruoterà due volte e interno ruoterebbe 15 volte 2*15=30

con d = 3 th Il ciclo esterno ruoterà tre volte e l'interno ruoterà 10 volte 3*10=30

Quindi, il GCD qui assicurerebbe che le rotazioni non superino il valore 30. E come si ottiene un numero che è il divisore di elementi totali, non lascerà saltare qualsiasi elemento

Answer 3

è possibile fare riferimento al video tutorial su codewhoop, che vi aiuterà a capire giocoleria algoritmo in un modo migliore :)

link al tutorial: Array rotation using juggling algorithm