알고리즘 주어진 문제를 해결하기 위해 수행되는 일련의 명령입니다. 여기서 우리는 배열 회전을 위한 반전 알고리즘에 대해 논의하고 반전 알고리즘을 위한 프로그램을 만들 것입니다.
이제 이 문제를 해결하기 위해 알아야 할 몇 가지 용어를 살펴보겠습니다. −
배열 - 동일한 데이터 유형의 요소 컨테이너. 배열의 크기(요소의 수)는 배열 선언 시 고정됩니다.
배열 회전 − 배열을 회전하면 배열 요소의 순서가 변경됩니다. 요소의 인덱스를 1씩 늘리고 마지막 요소의 인덱스를 0으로 변경하는 식입니다.
배열 회전의 예
Array[] = {3, 6, 8,1, 4, 10}
Rotated 2 times gives,
Array[] = {4, 10, 3, 6, 8, 1, 4} 반전 알고리즘
배열 회전을 위한 알고리즘 중 하나는 반전 알고리즘입니다. 이 알고리즘에서 하위 배열이 생성되고 배열의 회전을 수행하기 위해 반전됩니다. 하위 배열이 생성되고 개별적으로 회전한 다음 함께 결합되고 다시 반전되어 회전된 배열을 얻습니다.
알고리즘
Input : array arr[] , positions that are needed to be rotated r , length of array n. Step 1: Split the array into two sub arrays of 0 - (d-1) and d - (n-1) size, a1 [d] and a2[n-d]; Step 2: Reverse both arrays using the reverse method. Step 3: Join a1 and a2 back to get an array of original size. Step 4: Reverse this joined array to get the rotated array. Step 5: Print the array using the standard output method.
예
arr[] = {1 ,4, 2, 8, 3, 6, 5}, d = 3, n = 7
a1[] = {1,4,2} ; a2 = {8,3,6,5}
a1r[] = {2,4,1} // reversed a1
a2r[] = {5,6,3,8} // reversed a2
ar[] = {2,4,1,5,6,3,8} // a1r+a2r
arr[] = {8,3,6,5,1,4,2} // final answer. 예시
#include <stdio.h>
void reverse(int arr[], int start, int end){
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
int main(){
int arr[] = { 54, 67, 12, 76, 25, 16, 34 };
int n = 7;
int d = 2;
printf("The initial array is :\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
reverse(arr, 0, d - 1);
reverse(arr, d, n - 1);
reverse(arr, 0, n - 1);
printf("\nThe left reversed array by %d elements is:\n",d);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
} 출력
The initial array is : 54 67 12 76 25 16 34 The left reversed array by 2 elements is: 12 76 25 16 34 54 67