Ricerca…


introduzione

Nel mio percorso di studio della programmazione ci sono stati problemi semplici ma interessanti da risolvere come esercizi. Uno di questi problemi era ruotare un array (o un'altra raccolta) di un certo valore. Qui condividerò con voi una semplice formula per farlo.

Esempio di un metodo generico che ruota un array per un dato turno

Vorrei sottolineare che ruotiamo a sinistra quando il valore di spostamento è negativo e ruotiamo a destra quando il valore è positivo.

    public static void Main()
    {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int shiftCount = 1;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]

        array = new []{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = 15;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]

        array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = -1;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]

        array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        shiftCount = -35;
        Rotate(ref array, shiftCount);
        Console.WriteLine(string.Join(", ", array));
        // Output: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5]
    }

    private static void Rotate<T>(ref T[] array, int shiftCount)
    {
        T[] backupArray= new T[array.Length];

        for (int index = 0; index < array.Length; index++)
        {
            backupArray[(index + array.Length + shiftCount % array.Length) % array.Length] = array[index];
        }

        array = backupArray;
    }

La cosa importante in questo codice è la formula con cui troviamo il nuovo valore di indice dopo la rotazione.

(index + array.Length + shiftCount% array.Length)% array.Length

Ecco alcune informazioni in più:

(shiftCount% array.Length) -> normalizziamo il valore di spostamento in modo che sia nella lunghezza dell'array (poiché in un array con lunghezza 10, lo spostamento 1 o 11 è la stessa cosa, lo stesso vale per -1 e -11) .

array.Length + (shiftCount% array.Length) -> questo viene fatto a causa delle rotazioni a sinistra per assicurarsi che non entriamo in un indice negativo, ma ruotarlo fino alla fine dell'array. Senza di esso per una matrice di lunghezza 10 per l'indice 0 e una rotazione -1 dovremmo inserire un numero negativo (-1) e non ottenere il valore dell'indice di rotazione reale, che è 9. (10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length) -> Non c'è molto da dire qui quando applichiamo la rotazione all'indice per ottenere il nuovo indice. (0 + 10 + (-1% 10) = 9)

index + array.Length + (shiftCount% array.Length)% array.Length -> la seconda normalizzazione si sta accertando che il nuovo valore di indice non vada fuori dalla matrice, ma ruoti il ​​valore all'inizio dell'array. È per le giuste rotazioni, poiché in un array con lunghezza 10 senza esso per l'indice 9 e una rotazione 1 dovremmo andare nell'indice 10, che è al di fuori dell'array, e non ottenere il valore dell'indice di rotazione reale è 0. ((9 + 10 + (1% 10))% 10 = 0)



Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow