用 C++ 统计满足条件的 (i, j) 对数：arr[i] 能被 arr[j] 整除 或 arr[j] 能被 arr[i] 整除。

给定一个包含 N 个元素的数组 arr[]。目标是找到所有满足条件的索引对 (i,j) 的数量，条件是 arr[i] 能被 arr[j] 整除 或 arr[j] 能被 arr[i] 整除，并且 i!=j。

我们将使用两个 for 循环遍历数组 arr[] 中的每个数字对，并检查当 i!=j 时，是否 arr[i]%arr[j]==0 或 arr[j]%arr[i]==0。如果是，则增加配对计数。

让我们通过示例来理解。

输入 − Arr[]= { 2,4,3,6 } N=4

输出 − 有效对的数量 − 3

说明 − 有效对为 −

Arr[0] & Arr[1] → (2,4) here 4%2==0 0!=1
Arr[0] & Arr[1] → (2,6) here 6%2==0 0!=3
Arr[2] & Arr[3] → (3,6) here 6%3==0 2!=3

输入 − Arr[]= { 2,5,7,9,11 } N=5

输出− 有效对的数量 − 0

说明 − 没有一个数能完全整除另一个数。无法形成任何对。

下面程序中使用的算法如下：

  • 我们使用一个用随机数初始化的整型数组 Arr[]。

  • 使用变量 n 存储 Arr[] 的长度。

  • 函数 countPairs(int arr[], int n) 以数组及其长度作为输入，并返回满足所需条件的有效对。

  • 使用两个 for 循环遍历每个元素对。

  • 外循环从 0<=i<n-1，内循环 i<j<n

  • 检查 arr[i]%arr[j]==0 或 arr[j]%arr[i]==0 是否成立。如果任一条件为真，则计数加一。

  • 所有循环结束后，count 将包含有效对的总数。

  • 返回计数作为结果。

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[], int n){
   // Count of pairs
   int count = 0;
   for (int i = 0; i < n-1; i++){
      for (int j = i + 1; j < n; j++){
         if(arr[i]%arr[j]==0 || arr[j]%arr[i]==0)
            { count++; }
      }
   }
   return count;
}
int main(){
   int Arr[] = { 2,3,4,5,6 };
   int len = sizeof(Arr) / sizeof(Arr[0]);
   cout << "Count of number of pairs : "<< countPairs(Arr, len);
   return 0;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

如果我们运行上面的代码，它将生成以下输出：

Count of number of pairs : 3

更新于：2020-08-29

979 次浏览

启动你的职业生涯

完成课程并获得认证

开始学习
广告