使用C++编写，找到满足方程的六元组的数量

王林转载: 2023-09-11 17:17:11 250浏览

在本文中，我们将描述一种寻找满足方程的六元组的方法。因此，我们以一个方程为例，需要找到满足下面方程的a、b、c、d、e和f的值。

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

让我们重新排序方程 −

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

这是给定问题的一个简单示例 -

Input : arr [ ] = { 1, 3 }
Output : 4
Explanation : ( 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

Input : arr [ ] = { 2, 5 }
Output : 3

找到解决方案的方法

我们将使用一种天真的方法来找到给定问题的解决方案。

天真的方法

在这个问题中，通过观察LHS和RHS，我们可以找到所有可能的LHS结果并将其存储在一个数组中，同样地，创建一个RHS的数组，并将其填充为所有可能的RHS结果。

检查这两个数组是否有相同的值，并对每个找到的值递增计数，最后显示结果。

示例

#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]);
    // Generating all possible values of LHS array
    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];
            }
        }
    }
    // Generating all possible value of RHS array
    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<<"Number of sextuplets that satisfy an equation: "<<result;
    return 0;
}

输出

Number of sextuplets that satisfy an equation: 3

上述程序的解释

在这个程序中，我们创建了两个数组来保存LHS和RHS的每个结果。我们使用三个嵌套循环来将(a, b, c)的每个可能值放入LHS，将(d, e, f)的每个可能值放入RHS。之后，我们对这两个数组进行排序，以比较它们并找到两个数组中相同的值，将这两个数组传递给findsamenumber()函数。

在findsamenumber()函数中，我们使用两个嵌套循环来检查相同的值。当我们找到两个相同的元素时，我们检查该数字在两个数组中的频率，以便计算每个可能值的次数。

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