计算无序对(i,j),以使a [i]和a [j]的乘积在C ++中为2的幂
给我们一个由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
说明-所有对都具有sum=6,这不是理想的平方。
以下程序中使用的方法如下
我们采用用随机数初始化的整数数组Arr[]。
取一个变量n,它存储Arr[]的长度。
函数countPairs(intarr[],intn)接受一个数组,将其长度作为输入,并返回其和为完美平方的对。
对数组中的每个元素使用两个for循环遍历数组。
外循环从0<=i<n-1,内循环i<j<n
计算arr[i]和arr[j]的和为正。
计算总和的平方根为sqrt(sum)。
现在检查sqr-floor(sqr)==0。这意味着sum是一个完美的平方。如果为真,则递增计数。
在所有循环的末尾,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<<"乘积为2的乘方对:"<<countPairs(arr, n); return 0; }
输出结果
如果我们运行上面的代码,它将生成以下输出-
乘积为2的乘方对:6