資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告