ランダムに選んだ3つの数が等差数列(AP)になる確率を求めるC++プログラム

問題の概要

数値の配列が与えられたとき、その中からランダムに選んだ3つの数が等差数列(AP: Arithmetic Progression)をなす確率を求めることが本記事の課題です。

等差数列(AP)とは、隣り合う項同士の差が常に一定である数列のことです。例えば「2, 4, 6」のように、各項の間に共通の差が存在します。

入出力例

入力: arr[] = { 2,3,4,7,1,2,3 }
出力: ランダムに選んだ3つの数が等差数列になる確率: 0.107692

入力: arr[] = { 1, 2, 3, 4, 5 }
出力: ランダムに選んだ3つの数が等差数列になる確率: 0.151515

解き方のアプローチ

• 正の整数からなる配列を入力として受け取る
• 配列のサイズ(n)を計算する
• 次の公式を用いて確率を求める
  3n / (4(n²) − 1)
• 計算結果を出力する

アルゴリズム

開始
ステップ1 → 3つのランダムな数が等差数列になる確率を計算する関数を定義
    double probab(int n)
        return (3.0 * n) / (4.0 * (n * n) - 1)
ステップ2 → main() 関数内で
    配列を宣言する: int arr[] = { 2,3,4,7,1,2,3 }
    配列のサイズを計算する: int size = sizeof(arr)/sizeof(arr[0])
    確率を計算する関数を呼び出す: probab(size)
終了

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// 3つのランダムな数が等差数列(AP)になる確率を計算する関数
double probab(int n) {
    return (3.0 * n) / (4.0 * (n * n) - 1);
}
int main() {
    int arr[] = { 2,3,4,7,1,2,3 };
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"ランダムに選んだ3つの数が等差数列になる確率: "<<probab(size);
    return 0;
}

実行結果

ランダムに選んだ3つの数が等差数列になる確率: 0.107692

まとめ

このプログラムでは、配列の要素数 n を用いた公式「3n / (4n² − 1)」により、ランダムに選んだ3つの数が等差数列をなす確率を効率的に計算できます。配列の各要素の値に依存せず、要素数だけで確率が決まる点がこの手法の大きな特徴です。計算量は O(1) と非常に軽量なため、大規模なデータセットに対しても高速に動作します。