C++で配列のBitonicity（ビトニック性）を計算するプログラム

配列のBitonicityとは

本記事では、整数型の配列が与えられたとき、その配列の「Bitonicity（ビトニック性）」を関数を使って計算するC++プログラムを紹介します。

配列のBitonicityは以下のように定義されます。

• 初期値は 0
• 隣接する次の要素が前の要素より大きい場合に 1 増加する
• 隣接する次の要素が前の要素より小さい場合に 1 減少する
• 隣接する要素が等しい場合は変化しない

実行例

入力: arr[] = { 1, 4, 3, 5, 2, 9, 10, 11 }
出力: 配列のBitonicity : 3

処理の流れ

• Bitonicityを格納する変数（ここでは temp）を 0 で初期化します。
• 配列の先頭要素である 1 から処理を開始し、順番に arr[i] と arr[i-1] を比較していきます。まず 4 と 1 を比較すると、4 の方が大きいため temp を 1 増やします。次に 4 と 3 を比較すると、3 の方が小さいため temp を 1 減らします。これを配列の末尾まで繰り返します。
• 最終的に得られた temp の値（この例では 3）を出力します。

アルゴリズムの考え方

• 配列 arr[n]（n は配列のサイズ）の全要素を先頭から順に走査します。
• arr[i] > arr[i-1] の場合： bitonicity = bitonicity + 1
• arr[i] < arr[i-1] の場合： bitonicity = bitonicity − 1
• arr[i] = arr[i-1] の場合： bitonicity は変化なし

アルゴリズムの手順

Start
Step 1→ 配列のBitonicityを計算する関数を宣言する
    int cal_bitonicity(int arr[], int n)
        int temp = 0 で初期化
        for (int i = 1; i < n; i++) ループを実行
            IF (arr[i] > arr[i - 1])
                temp をインクリメント（temp++）
            End
            ELSE IF (arr[i] < arr[i - 1])
                temp をデクリメント（temp--）
            End
        temp を返す
Step 2→ main() 内で
    int arr[] = { 1, 4, 3, 5, 2, 9, 10, 11 } を宣言
    int n = sizeof(arr) / sizeof(arr[0]) を設定
    cal_bitonicity(arr, n) を呼び出す
Stop

C++サンプルコード

#include <iostream>
using namespace std;

// Bitonicityを計算する関数
int cal_bitonicity(int arr[], int n) {
    int temp = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1])
            temp++;
        else if (arr[i] < arr[i - 1])
            temp--;
    }
    return temp;
}

int main() {
    int arr[] = { 1, 4, 3, 5, 2, 9, 10, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "配列のBitonicity : " << cal_bitonicity(arr, n);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

配列のBitonicity : 3

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加で必要なメモリ領域は変数1個のみであり、空間計算量は O(1) となります。配列の要素数が増えても効率的にBitonicityを求められる点が特徴です。