配列を指定された数値 K だけ左右に回転させる C プログラム

このブログ投稿では、指定された数値 K だけ配列を左右に回転させる C プログラムを作成する方法を学びます。そこでここでは、指定された数 K だけ配列を左右に回転させる C プログラムを作成します。

「arr」がサイズ N の整数配列であり、配列を左または右に k ステップ (k は非負数) 回転させるタスクであるとします。ここで、配列の回転とは、指定された位置だけ配列要素を配列の左または右にシフトすることを意味します。

Input: int arr[] = {1,2,3,4,5,6,7}, k = 3

Output: {5,6,7,1,2,3,4}

Explanation:

rotate 1 steps to the right-> {7,1,2,3,4,5,6}
rotate 2 steps to the right-> {6,7,1,2,3,4,5}
rotate 3 steps to the right-> {5,6,7,1,2,3,4}

与えられた数 K だけ配列を左右に回転させる解決策を見てみましょう。ただし、最初にこの問題を自分で解決してみるとよいでしょう。

解決策 1:

このソリューションでは、まず、配列要素を左右に 1 つずつシフトする 2 つの関数を作成します。これら 2 つの関数を作成した後、「k」の値に応じてループ内で呼び出される他の関数でそれらを呼び出します。

1 つの左シフト関数では、最初の要素 ( arr[0] ) 配列を格納する中間一時変数を作成します。ここで、arr[1] を arr[0] に、arr[2] を arr[1] に移動し、最後に temp を arr[n-1] に移動します。この手法は、配列要素 1 の位置を回転させます。

右シフトでは、配列の最後の要素を temp 変数に格納し、arr[n-2] を arr[n-1] に、arr[n-3] を arr[n-2] に移動する必要があります…そして最後に arr[0].

に移動します。

C 言語についてさらに詳しく知りたい場合は、このコースをチェックしてください。無料トライアルが利用可能です。

無料トライアルを入手

配列要素を k 番目の位置で左右に回転させる C プログラムを見てみましょう。

#include <stdio.h>
#include <stdint.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


// Function to right-rotate an array by one position
void rightRotateByOne(int arr[], int arr_size)
{
    int i;
    //take last element of the array
    int last = arr[arr_size - 1];
    for (i = arr_size - 2; i >= 0; i--)
    {
        arr[i + 1] = arr[i];
    }
    // Now store the last element
    // at 0th index of the array
    arr[0] = last;
}

// Function to left-rotate an array by one position
void leftRotatebyOne(int arr[], int arr_size)
{
    //get first element of the array
    int first = arr[0], i;
    for (i = 0; i < arr_size - 1; i++)
    {
        arr[i] = arr[i + 1];
    }

    arr[i] = first;
}


//Function to left rotate an array by 'k' positions
void leftRotate(int arr[], int k, int arr_size)
{
    int i;
    for (i = 0; i < k; i++)
    {
        leftRotatebyOne(arr, arr_size);
    }
}


// Function to right-rotate an array by 'k' positions
void rightRotate(int arr[], int k, int arr_size)
{
    int i;
    for (i = 0; i < k; i++)
    {
        rightRotateByOne(arr, arr_size);
    }
}




//print the array elements
void printArray(int arr[], int arr_size)
{
    int i;
    for (i = 0; i < arr_size; i++)
    {
        printf("%d ", arr[i]);
    }

    printf("\n\n");
}



int main()
{
    //array must be sorted
    int arr[] = {8, 11, 13, 15, 1, 4, 6};

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    printf("Original Array = ");
    printArray(arr, 7);

    printf("Left shift array by 2 = ");
    leftRotate(arr, 2, arr_size);
    printArray(arr, 7);


    printf("Right shift array by 2 = ");
    rightRotate(arr, 2, arr_size);
    printArray(arr, 7);

    return 0;
}

解決策 2 (ジャグリング アルゴリズム):

このソリューションでは、要素を 1 つずつ回転させる以外に、配列をセットで回転させます。ここで、セットの数は、n (配列サイズ) と K (配列要素を回転させる位置) の GCD に等しくなります。

arr が整数配列で、サイズが 7 だとします。これを 2 回転させたいとします。ここでは、n=7、k =2、配列要素は {1,2,3,4,5,6,7};

7 と 2 の GCD を計算すると、1 になります。したがって、要素は 1 つのセット内でのみ移動されます。temp =arr[0] から開始し、arr[I+d] を arr[I] に移動し続けます。最終的に適切な場所に温度を保存します。

#include <stdio.h>
#include <stdint.h>

//Calculate array size
#define ARRAY_SIZE(arr)  sizeof(arr)/sizeof(arr[0])


//Calculate the calculateGcd
int calculateGcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }
    else
    {
        return calculateGcd(b, a % b);
    }
}

//Function to left rotate array of size n by k
void leftRotate(int arr[], int k, int n)
{
    int i, a, b, temp;
    // To handle if k >= n
    k = k % n;
    const int gcd = calculateGcd(k, n);
    for (i = 0; i < gcd; i++)
    {
        /* move i-th values of blocks */
        temp = arr[i];
        a = i;
        while (1)
        {
            b = a + k;
            if (b >= n)
                b = b - n;
            if (b == i)
                break;
            arr[a] = arr[b];
            a = b;
        }
        arr[a] = temp;
    }
}

//print array elements
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}


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

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    printf("Original Array = ");
    printArray(arr, arr_size);

    printf("Left shift array by 2 = ");
    leftRotate(arr, 2, arr_size);
    printArray(arr, arr_size);

    return 0;
}

出力: 3 4 5 6 7 1 2

おすすめの記事:

  • プログラマーへの最高の贈り物
  • プログラマー向けの最高の電子キット
  • C では、偶数位置の要素が奇数要素よりも大きくなるように配列を再配置します。
  • ソートされた配列から重複を削除する C プログラム
  • C コードを使用して、サイズの異なる 2 つの並べ替えられた配列の中央値を見つけます。
  • ソートされた配列内の要素の最初と最後の位置を見つける C プログラム
  • 与えられた 1 から n までの整数配列から欠落している数を見つける C プログラムを作成してください
  • 配列内で最も人気のある要素を見つける C プログラム
  • C プログラミングを使用して、配列内の最大要素と最小要素を見つける
  • 限定された範囲の配列内で偶数個の要素を見つける C プログラム
  • 指定された配列のすべての部分配列の合計を求めます。
  • 偶数と奇数を分離する C プログラム
  • 左側の配列の合計が右側の配列の合計と等しくなるように、配列内の要素を見つけます。
  • 配列内の偶数要素と奇数要素の数を見つける C プログラム
  • 配列要素の合計を求める C プログラムを作成する