#include <bits/stdc++.h> 
using namespace std; 

/*Prototype for utility functions */
void printArray(int arr[], int size); 
void swap(int arr[], int fi, int si, int d); 

void leftRotate(int arr[], int d, int n) 
{ 
    /* Return If number of elements to be rotated 
    is zero or equal to array size */
    if(d == 0 || d == n) 
        return; 
        
    /*If number of elements to be rotated 
    is exactly half of array size */
    if(n - d == d) 
    { 
        swap(arr, 0, n - d, d); 
        return; 
    } 
        
    /* If A is shorter*/        
    if(d < n - d) 
    { 
        swap(arr, 0, n - d, d); 
        leftRotate(arr, d, n - d);   
    } 
    else /* If B is shorter*/       
    { 
        swap(arr, 0, d, n - d); 
        leftRotate(arr + n - d, 2 * d - n, d); /*This is tricky*/
    } 
} 

/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size) 
{ 
    int i; 
    for(i = 0; i < size; i++) 
        cout << arr[i] << " "; 
    cout << endl; 
} 

/*This function swaps d elements starting at index fi 
with d elements starting at index si */
void swap(int arr[], int fi, int si, int d) 
{ 
    int i, temp; 
    for(i = 0; i < d; i++) 
    { 
        temp = arr[fi + i]; 
        arr[fi + i] = arr[si + i]; 
        arr[si + i] = temp; 
    } 
} 

// Driver Code 
int main() 
{ 
    int arr[] = {1, 2, 3, 4, 5, 6, 7}; 
    leftRotate(arr, 2, 7); 
    printArray(arr, 7); 
    return 0; 
} 

// This code is contributed by Rath Bhupendra 

J'ai trouvé ce code sur le site geek for geeks. Le code est utilisé pour faire pivoter les éléments d'un tableau. Il est mentionné comme algorithme d'échange de blocs sur le site Web, mes questions sont:

Pouvons-nous ajouter des entiers à un tableau en c ++ comme indiqué dans la partie else de la fonction de rotation gauche tout en passant les arguments (arr + n-d)?

Comment pouvons-nous ajouter des entiers à un tableau?

J'ai essayé d'ajouter un entier à un tableau dans un compilateur en ligne et cela n'a pas fonctionné. Mais le code ci-dessus fonctionne parfaitement pour donner la sortie souhaitée 34567.

Le lien vers le site Web est https://www.geeksforgeeks.org / block-swap-algorithm-for-array-rotation /.

1
gm lohith 30 août 2020 à 12:58

2 réponses

Meilleure réponse

Pouvons-nous ajouter des entiers à un tableau en c ++ comme indiqué dans la partie else de la fonction de rotation gauche tout en passant les arguments (arr + n-d)?

Comment pouvons-nous ajouter des entiers à un tableau?

La réponse est que vous ne pouvez pas, et ce n'est pas ce qui se passe ici.

L'argument int arr[] se désintègre en un pointeur vers le premier élément du tableau. C'est la même chose que d'avoir int* arr donc ce que vous faites dans arr + n - d est une simple arithmétique de pointeur.

Le pointeur sera déplacé n - d positions par rapport à la position où il se trouve avant que l'expression ne soit évaluée.

Supposons que le résultat de n - d soit 4, et arr pointe vers le début du tableau passé en argument, c'est-à-dire vers &arr[0] (en notation tableau) ou arr + 0 (en notation pointeur), qui est l'endroit où il pointe dans son état initial, vous aurez arr + 4 ou &arr[4], après l'évaluation, l'expression donne accès à l'adresse de l'index 4 (le 5e élément du tableau). Pour accéder à la valeur de cette adresse, vous utiliserez *(arr + 4) ou arr[4].

En passant, je ne conseillerais pas l'utilisation de geeksforgeeks.com pour apprendre le C ++, ou tout autre langage, d'ailleurs, cela devrait être fait en lisant un bon livre.

2
anastaciu 30 août 2020 à 16:38

Un paramètre de fonction ayant un type de tableau est ajusté par le compilateur pour pointer vers le type d'élément de tableau. Autrement dit, ces deux déclarations de fonction sont équivalentes et déclarent la même fonction.

void leftRotate(int arr[], int d, int n);

Et

void leftRotate(int *arr, int d, int n);

Vous pouvez même écrire par exemple

void leftRotate(int arr[100], int d, int n);
void leftRotate(int arr[10], int d, int n);
void leftRotate(int arr[1], int d, int n);

Encore une fois, ces déclarations déclarent la fonction

void leftRotate(int *arr, int d, int n);

Donc dans la fonction cette expression

arr + n - d

Utilise l'arithmétique du pointeur appliquée au pointeur arr.

Par exemple, l'expression arr + 0 est équivalente à arr et pointe vers le premier élément du tableau. L'expression arr + n pointe vers l'élément n-th du tableau.

Voici un programme démonstratif où l'on utilise l'arithmétique du pointeur pour sortir les éléments d'un tableau dans une boucle.

#include <iostream>

int main() 
{
    int a[] = { 1, 2, 3, 4, 5 };
    
    for ( size_t i = 0; i < sizeof( a ) / sizeof( *a ); i++ )
    {
        std::cout << *( a + i ) << ' ';
    }
    std::cout << '\n';
    
    return 0;
}

La sortie du programme est

1 2 3 4 5

Dans l'expression *( a + i ), le désignateur de tableau a est implicitement converti en pointeur vers son premier élément.

Voici un autre programme démonstratif qui montre qu'un paramètre de fonction ayant un type de tableau est ajusté par le compilateur pour pointer vers le type d'élément de tableau.

#include <iostream>
#include <iomanip>
#include <type_traits>

const size_t N = 100;

void f( int a[N] )
{
    std::cout << "\nin function\n";
    std::cout << "sizeof( a ) = " << sizeof( a ) << '\n';
    std::cout << "a is a pointer " << std::boolalpha <<std:: is_same<decltype( a ), int *>::value << '\n';
}

int main() 
{
    int a[N];
    
    std::cout << "In main\n";
    std::cout << "sizeof( a ) = " << sizeof( a ) << '\n';
    std::cout << "a is an array " << std::boolalpha <<std:: is_same<decltype( a ), int [N]>::value << '\n';

    f( a );
    
    return 0;
}

La sortie du programme est

In main
sizeof( a ) = 400
a is an array true

in function
sizeof( a ) = 8
a is a pointer true
1
Vlad from Moscow 30 août 2020 à 10:35