C++で方程式を満たす6つ組の数を求める方法を解説

この記事では、方程式を満たす6つ組（セクステュプレット）の個数を求めるアルゴリズムについて解説します。例として、次の方程式を満たす a、b、c、d、e、f の組み合わせがいくつ存在するかを求める問題を取り上げます。

( a + b + c ) * e / d = f

まず、この式を次のように変形してみましょう。

( a + b + c ) = ( f * d ) / e

入力例と出力例

入力 : arr [ ] = { 1, 3 }
出力 : 4
説明 :
　・( a, b, c, e, f ) = 1、d = 3
　・( a, b, c, d, e ) = 1、f = 3
　・( a, b, c ) = 1、( d, e, f ) = 3
　・( a, b, c, d, f ) = 3、e = 1

入力 : arr [ ] = { 2, 5 }
出力 : 3

解法のアプローチ

ここでは、シンプルで分かりやすい「素朴なアプローチ（Naive Approach）」を用いて問題を解きます。

素朴なアプローチの考え方

式の左辺（LHS）と右辺（RHS）に注目するのがポイントです。

左辺については、( a + b + c ) のすべての組み合わせの計算結果を配列に格納します。同様に、右辺についても ( f * d ) / e のすべての組み合わせの計算結果を別の配列に格納します。

その後、両方の配列をソートして突き合わせ、一致する値が見つかるたびにカウントを増やしていき、最終的な件数を出力します。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
int findsamenumbers(int *arr1, int *arr2, int n){
    int i = 0, j = 0, k = 0, count=0;
    while(( i < n*n*n+1) && (j < n*n*n+1)){
        if(arr1[i] < arr2[j])
            i++;
        else if(arr1[i] == arr2[j]){
            count++;
        int temp = arr1[i];
        while(temp==arr1[++i]){
            count++;
        }
        while(temp==arr2[++j]){
            count++;
        }
    }
    else
        j++;
    }  
    return count;
}
int main(){
    int arr[] = {2,5};
    int n = sizeof(arr)/sizeof(arr[0]);
    // 左辺（LHS）の全パターンを生成
    int index = 0,i;
    int LHS[n*n*n ];
    for ( i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                LHS[index++] = (arr[i] * arr[j]) / arr[k];
            }
        }
    }
    // 右辺（RHS）の全パターンを生成
    int RHS[n*n*n ];
    index=0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = 0; k < n; k++){
                RHS[index++] = (arr[i] + arr[j] + arr[k]);
            }
        }
    }
    sort(RHS, RHS + (n*n*n));
    sort(LHS, LHS + (n*n*n));
    int result = findsamenumbers(LHS, RHS, n);
    cout<<"方程式を満たす6つ組の数: "<<result;
    return 0;
}

実行結果

方程式を満たす6つ組の数: 3

プログラムの解説

このプログラムでは、左辺と右辺のすべての計算結果を保持するために、2つの配列（LHS と RHS）を用意しています。三重のネストされたループを使い、左辺には ( a, b, c ) の全組み合わせの値を、右辺には ( d, e, f ) の全組み合わせの値を格納していきます。

その後、両方の配列をそれぞれソートし、共通する値を効率よく見つけられるようにしてから、findsamenumbers() 関数に渡します。

findsamenumbers() 関数では、2つの配列を先頭から順に比較しながら一致する値を探します。一致する要素が見つかった場合は、その値が両方の配列内で何回出現するか（出現頻度）を確認することで、すべての有効な組み合わせをもれなくカウントできるようにしています。

if(arr1[i] == arr2[j]){
    count++;
    int temp = arr1[i];
    while(temp==arr1[++i]){
        count++;
    }
    while(temp==arr2[++j]){
        count++;
    }

まとめ

この記事では、与えられた配列の要素を使って、6変数の方程式 ( a + b + c ) * e / d = f を満たす6つ組の個数を求める問題を解きました。左辺と右辺の全組み合わせを事前に生成し、ソート後に照合するというシンプルな手法により、効率よく答えを導き出せます。なお、このアプローチはC++だけでなく、C、Java、Python など他のプログラミング言語でも同様に実装することが可能です。