各要素を直前の要素で割った値の配列合計を求めるアルゴリズム

今回は少しユニークな問題を紹介します。ある配列を受け取り、各要素を直前の要素で除算した値の合計を求めるというものです。

例として、配列 {5, 6, 7, 2, 1, 4} を考えてみましょう。この場合、計算結果は次のようになります。

5 + (6 / 5) + (7 / 6) + (2 / 7) + (1 / 2) + (4 / 1) = 12.15238

それでは、この問題を解くための手順を確認していきましょう。

アルゴリズム

divSum(arr, n)

begin
    sum := arr[0]
    for i := 1 to n-1, do
        sum := sum + arr[i] / arr[i-1]
    done
    return sum
end

C++による実装例

#include <iostream>
using namespace std;
float divSum(int arr[], int n){
    float sum = arr[0];
    for(int i = 1; i<n; i++){
        sum += arr[i] / float(arr[i - 1]);
    }
    return sum;
}
int main() {
    int arr[6] = {5, 6, 7, 2, 1, 4};
    int n = 6;
    cout << "Sum : " << divSum(arr, n);
}

出力結果

Sum : 12.1524

コードのポイント

このアルゴリズムのポイントは以下の通りです。

• 最初の要素 arr[0] には「前の要素」が存在しないため、そのまま合計に加算します。
• 2番目以降の要素については、直前の要素で割った値を順番に足し合わせていきます。
• C++では整数同士の除算を行うと小数点以下が切り捨てられてしまうため、float(arr[i - 1]) のように明示的にキャストし、正確な小数計算を実現しています。

計算量は O(n) で、配列を一度走査するだけで答えが求まるため、とても効率的な手法と言えます。