C言語で配列が回文かどうかを判定するプログラム

回文とは

任意のサイズ n の配列 arr[] が与えられたとき、その配列が回文（パリンドローム）かどうかを判定するのが本記事の目的です。回文とは、前から読んでも後ろから読んでも同じになる並びのことで、MADAM や NAMAN といった文字列が代表的な例として挙げられます。

配列が回文かどうかを確認するには、配列を先頭からと末尾から同時に走査し、対応する要素同士を比較していきます。

入力例と出力例

Input: arr[] = {1, 0, 0, 1}
Output: 配列は回文です

Input: arr[] = {1, 2, 3, 4, 5}
Output: 配列は回文ではありません

考え方（アプローチ）

配列の先頭からと末尾から同時に走査し、先頭側の要素と末尾側の要素が一致しているかどうかを順に確認します。すべての比較で要素が一致すればその配列は回文であり、1つでも一致しない要素が見つかれば回文ではないと判定します。

アルゴリズム

開始
関数 int pallindrome(int arr[], int n) 内
    ステップ1→ i、j、flag を宣言し、flag に 0 を代入
    ステップ2→ i = 0、j = n-1 から始め、i < n/2 かつ j >= n/2 の間、i++、j-- を行いながらループ
        もし arr[i] != arr[j] であれば、
            flag に 1 を設定
            break
        If 終了
    ループ終了
    ステップ3→ flag == 1 であれば、
        0 を返す
    ステップ4→ それ以外の場合、
        1 を返す
関数終了
関数 int main(int argc, char const *argv[]) 内
    ステップ1→ arr[] を {1, 0, 2, 3, 2, 2, 1} として宣言・初期化
    ステップ2→ n を sizeof(arr)/sizeof(arr[0]) として宣言・初期化
    ステップ3→ pallindrome(arr, n) が真であれば、
        「配列は回文です」と出力
    If 終了
    ステップ4→ それ以外の場合、
        「配列は回文ではありません」と出力
    0 を返す
main 終了
終了

C言語による実装例

#include <stdio.h>
int pallindrome(int arr[], int n) {
    int i, j, flag = 0;
    for(i = 0, j=n-1; i< n/2, j>=n/2; i++, j--) {
        if(arr[i]!=arr[j]) {
            flag = 1;
            break;
        }
    }
    if (flag == 1)
    return 0;
    else
    return 1;
}
int main(int argc, char const *argv[]) {
    int arr[] = {1, 0, 2, 3, 2, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(pallindrome(arr, n)) {
        printf("Array is pallindrome\n");
    }
    else
        printf("Array is not pallindrome\n");
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次のような出力が得られます。

Array is not palindrome

この配列では、先頭から2番目の要素（0）と末尾から2番目の要素（2）が一致しないため、回文ではないと判定されます。

計算量

このアルゴリズムは配列を先頭と末尾から同時に走査するため、時間計算量は O(n) です。また、比較のために必要なのは変数 i、j、flag のみなので、補助的なメモリ使用量は O(1) に抑えられます。そのため、要素数が多い配列でも効率的に回文判定を行うことができます。