Рубрики

Алгоритм блочного обмена для вращения массива

Напишите функцию rotate (ar [], d, n), которая вращает arr [] размера n на d элементов.

Вращение вышеуказанного массива на 2 сделает массив

Алгоритм:

Initialize A = arr[0..d-1] and B = arr[d..n-1]
1) Do following until size of A is equal to size of B

  a)  If A is shorter, divide B into Bl and Br such that Br is of same 
       length as A. Swap A and Br to change ABlBr into BrBlA. Now A
       is at its final place, so recur on pieces of B.  

   b)  If A is longer, divide A into Al and Ar such that Al is of same 
       length as B Swap Al and B to change AlArB into BArAl. Now B
       is at its final place, so recur on pieces of A.

2)  Finally when A and B are of equal size, block swap them.

Рекурсивная реализация:

C ++

#include <bits/stdc++.h>

using namespace std;

  
/ * Прототип для служебных функций * /

void printArray(int arr[], int size); 

void swap(int arr[], int fi, int si, int d); 

  

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

    / * Возврат, если число элементов, которые будут повернуты

    равен нулю или равен размеру массива * /

    if(d == 0 || d == n) 

        return

          

    / * Если число элементов должно быть повернуто

    ровно половина размера массива * /

    if(n - d == d) 

    

        swap(arr, 0, n - d, d); 

        return

    

          

    / * Если А короче * /        

    if(d < n - d) 

    

        swap(arr, 0, n - d, d); 

        leftRotate(arr, d, n - d);     

    

    else / * Если B короче * /        

    

        swap(arr, 0, d, n - d); 

        leftRotate(arr + n - d, 2 * d - n, d); / * Это сложно * /

    

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * функция для печати массива * /

void printArray(int arr[], int size) 

    int i; 

    for(i = 0; i < size; i++) 

        cout << arr[i] << " "

    cout << endl; 

  
/ * Эта функция меняет d элементов, начиная с индекса fi
с d элементами, начинающимися с индекса 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; 

    

  
// Код драйвера

int main() 

    int arr[] = {1, 2, 3, 4, 5, 6, 7}; 

    leftRotate(arr, 2, 7); 

    printArray(arr, 7); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include<stdio.h>

  
/ * Прототип для служебных функций * /

void printArray(int arr[], int size);

void swap(int arr[], int fi, int si, int d);

  

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

  / * Возврат, если число элементов для поворота

    ноль или равен размеру массива * /  

  if(d == 0 || d == n)

    return;

      

  / * Если количество вращаемых элементов точно

    половина размера массива * /  

  if(n-d == d)

  {

    swap(arr, 0, n-d, d);   

    return;

  }  

      

 / * Если А короче * /              

  if(d < n-d)

  {  

    swap(arr, 0, n-d, d);

    leftRotate(arr, d, n-d);    

  }    

  else / * Если B короче * /              

  {

    swap(arr, 0, d, n-d);

    leftRotate(arr+n-d, 2*d-n, d); / * Это сложно * /

  }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * функция для печати массива * /

void printArray(int arr[], int size)

{

  int i;

  for(i = 0; i < size; i++)

    printf("%d ", arr[i]);

  printf("\n ");

  
/ * Эта функция меняет d элементов, начиная с индекса fi

  с d элементами, начинающимися с индекса 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;

   }     

}     

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

   int arr[] = {1, 2, 3, 4, 5, 6, 7};

   leftRotate(arr, 2, 7);

   printArray(arr, 7);

   getchar();

   return 0;

}    

Джава

import java.util.*;

  

class GFG 

{

    public static void leftRotate(int arr[], int i, 

                                  int d, int n)

    {

        / * Возврат, если число элементов, которые будут повернуты

        равен нулю или равен размеру массива * /

        if(d == 0 || d == n) 

            return

          

        / * Если число элементов должно быть повернуто

        ровно половина размера массива * /

        if(n - d == d) 

        

            swap(arr, i, n - d + i, d); 

            return

        

          

        / * Если А короче * /    

        if(d < n - d) 

        

            swap(arr, i, n - d + i, d); 

            leftRotate(arr, i, d, n - d);     

        

        else / * Если B короче * /    

        

            swap(arr, i, d, n - d); 

            leftRotate(arr, n - d + i, 2 * d - n, d); / * Это сложно * /

        

    }

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * функция для печати массива * /

public static void printArray(int arr[], int size) 

    int i; 

    for(i = 0; i < size; i++) 

        System.out.print(arr[i] + " "); 

    System.out.println(); 

  
/ * Эта функция меняет d элементов
начиная с индекса fi с d элементами
начиная с индекса si * /

public static 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; 

    

  
// Код драйвера

public static void main (String[] args) 

{

    int arr[] = {1, 2, 3, 4, 5, 6, 7}; 

    leftRotate(arr,0, 2, 7); 

    printArray(arr, 7);     

}
}

  
// Этот код предоставлен codeseeker

Итеративная реализация:
Вот итерационная реализация того же алгоритма. Здесь используется та же функция swap ().

С

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

{

  int i, j;

  if(d == 0 || d == n)

    return;

  i = d;

  j = n - d;

  while (i != j)

  {

    if(i < j) / * А короче * /

    {

      swap(arr, d-i, d+j-i, i);

      j -= i;

    }

    else / * B короче * /

    {

      swap(arr, d-i, d, j);

      i -= j;

    }

    // printArray (arr, 7);

  }

  / * Наконец, поменять местами A и B * /

  swap(arr, d-i, d, i);

}

Джава

// Java-код для реализации выше

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

int i, j; 

if(d == 0 || d == n) 

    return

i = d; 
j = n - d; 

while (i != j) 

    if(i < j) / * А короче * /

    

    swap(arr, d-i, d+j-i, i); 

    j -= i; 

    

    else / * B короче * /

    

    swap(arr, d-i, d, j); 

    i -= j; 

    

    // printArray (arr, 7);


/ * Наконец, поменять местами A и B * /
swap(arr, d-i, d, i); 

python3

# Python3 код для реализации выше

  

def leftRotate(arr, d, n): 

    if(d == 0 or d == n): 

        return

    i =

    j = n -

    while (i != j): 

          

        if(i < j): # А короче

            swap(arr, d - i, d + j - i, i) 

            j -=

          

        else: # B короче

            swap(arr, d - i, d, j) 

            i -=

      

    swap(arr, d - i, d, i)

  
# Этот код добавлен
# by Adarsh_Verma

C #

// C # код для вышеуказанной реализации

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

    int i, j; 

    if(d == 0 || d == n) 

        return

    i = d; 

    j = n - d; 

    while (i != j) 

    

        if(i < j) / * А короче * /

        

            swap(arr, d-i, d+j-i, i); 

            j -= i; 

        

        else / * B короче * /

        

            swap(arr, d-i, d, j); 

            i -= j; 

        

          

    

      

    / * Наконец, поменять местами A и B * /

    swap(arr, d-i, d, i); 

  
// Этот код предоставлен Rajput-Ji


Сложность времени: O (n)

Пожалуйста, смотрите следующие сообщения для других методов вращения массива:
http://espressocode.top/array-rotation/
http://espressocode.top/program-for-array-rotation-continued-reversal-algorithm/

Ссылки:
http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеупомянутых программах / алгоритмах или хотите поделиться какой-либо дополнительной информацией об алгоритме замены блоков.

Рекомендуемые посты:

Алгоритм блочного обмена для вращения массива

0.00 (0%) 0 votes