C++で配列がビトニック配列かどうかを判定するプログラム

N個の整数からなる配列 arr[N] が与えられたとき、その配列がビトニック配列であるかどうかを判定するのが本記事のテーマです。ビトニック配列であれば「Yes its a bitonic array」と出力し、そうでなければ「No its not a bitonic array」と出力します。

ビトニック配列とは、まず厳密に増加し、その後厳密に減少するような配列のことです。

たとえば arr[] = {1, 2, 3, 4, 2, -1, -5} という配列は、4までは厳密に増加しており、4以降は厳密に減少しているため、ビトニック配列といえます。

入力例と出力例

入力

arr[] = {1, 3, 5, 4, 2, 0}

出力

Yes its a bitonic array

説明

1 < 3 < 5 > 4 > 2 > 0 となっているため、これはビトニック配列です。

入力

arr[] = {1, 2, 3, 4, 5, 0, -1, -2, 6, -4}

出力

No its not a bitonic array

この例では、途中で一度減少した後に再び増加（-2 → 6）しているため、ビトニック配列とはみなされません。

問題を解くためのアプローチ

• 配列の各要素を先頭から順に走査し、直前の要素が現在の要素より小さいかどうかを確認します。

• 直前の要素が現在の要素以下になった時点で、増加フェーズの終わりとしてループを抜けます。

• その後、直前の要素より現在の要素が小さい（減少している）ことを確認し、そうでない場合は false を返して処理を終了します。

• 配列の末尾まで到達できれば true を返します。

アルゴリズム

Start
Step 1→ 配列がビトニックかどうかを判定する関数を宣言
    int check(int arr[], int size)
      int i, j を宣言
      ループ: i = 1 から i < size まで i++
          IF (arr[i] > arr[i - 1])
            Continue
          End
          IF (arr[i] <= arr[i - 1])
            break
          End
          IF (i == size - 1)
            return 1
          End
          ループ: j = i + 1 から j < size まで j++
              IF (arr[j] < arr[j - 1])
                Continue
              End
              IF (arr[j] <= arr[j - 1])
                break
              End
          End
          i = j を設定
          IF (i != size)
            return 0
          End
          return 1
Step 2→ main() 内で
    int arr[] = { -3, 9, 11, 20, 17, 5, 1 } を宣言
    int size = sizeof(arr) / sizeof(arr[0]) を宣言
    check(arr, size) == 1 の場合は "Yes its a bitonic array" を、それ以外は "no its not a bitonic array" を出力
Stop

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
// ビトニック配列かどうかを判定する関数
int check(int arr[], int size){
    int i, j;
    for (i = 1; i < size; i++){
        if (arr[i] > arr[i - 1])
            continue;
        if (arr[i] <= arr[i - 1])
            break;
    }
    if (i == size - 1)
        return 1;
    for (j = i + 1; j < size; j++){
        if (arr[j] < arr[j - 1])
            continue;
        if (arr[j] >= arr[j - 1])
            break;
    }
    i = j;
    if (i != size)
        return 0;
    return 1;
}
int main(){
    int arr[] = { -3, 9, 11, 20, 17, 5, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);
    (check(arr, size) == 1) ? cout << "Yes its a bitonic array" : cout << "no its not a bitonic array";
    return 0;
}

実行結果

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

Yes its a bitonic array

このサンプルでは {-3, 9, 11, 20, 17, 5, 1} という配列を使用しています。-3 から 20 までは厳密に増加し、20 以降は厳密に減少しているため、ビトニック配列と判定されます。