数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用 C++ 统计满足 a[i] 和 a[j] 的乘积为 2 的幂次的无序对 (i,j) 的数量
给定一个包含 N 个元素的数组。目标是找到所有对 (Arr[i],Arr[j]) 的数量，这些对的和是完全平方数，其中 i!=j。也就是说，Arr[i]+Arr[j] 是一个完全平方数。
我们将通过计算对的和并检查该和的平方根是否等于平方根的向下取整值来做到这一点。sqrt(Arr[i]+Arr[j])-floor( sqrt(Arr[i]+Arr[j] )==0。
让我们通过例子来理解。
输入 − Arr[]= { 4,3,2,1,2,4 } N=6
输出 − 和为完全平方数的对的数量 − 2
解释 −
Arr[1]+Arr[3]=4, sqrt(4)-floor(4)=0 4 is a perfect square. Arr[2]+Arr[4]=4, sqrt(4)-floor(4)=0 4 is a perfect square. Rest all pairs have sum 7,6,5,8 which are not perfect squares.
输入 − Arr[]= { 3,3,3,3,3} N=5
输出 − 和为完全平方数的对的数量 − 0
解释 − 所有对的和都等于 6，它不是完全平方数。
下面程序中使用的方法如下
我们使用随机数初始化一个整数数组 Arr[]。
使用一个变量 n 来存储 Arr[] 的长度。
函数 countPairs(int arr[], int n) 以数组及其长度作为输入，并返回和为完全平方数的对。
使用两个 for 循环遍历数组中的每个元素对。
外循环从 0<=i<n-1，内循环 i<j<n
计算 arr[i] 和 arr[j] 的和（均为正数）。
计算和的平方根为 sqrt(sum)。
现在检查 sqr-floor(sqr)==0。这意味着和是一个完全平方数。如果为真，则递增计数。
在所有循环结束时，count 将包含和为完全平方数的对的总数。
返回计数作为结果。
示例
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
int count=0;
int prod=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
prod=arr[i]*arr[j];
if( ceil(log2(prod))==floor(log2(prod)) ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
}
}
}
return count;
}
int main(){
int arr[] = { 2, 5, 8, 16, 128 };
int n = sizeof(arr) / sizeof(arr[0]);
cout <<endl<<"Pairs whose product is power of 2:"<<countPairs(arr, n);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Pairs whose product is power of 2:6
更新于：2020年8月29日
326 次浏览
广告