資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中求陣列中和為完全平方數的數對個數
給定一個包含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[]，用隨機數初始化，陣列大小大於0。
使用一個變數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。這意味著和是一個完全平方數。如果是，則計數器加1。
在所有迴圈結束後，計數器將包含和為完全平方數的數對的總數。
返回計數作為結果。
示例
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
int count=0;
int sum=0;
double sqr=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
sum=arr[i]+arr[j];
sqr=sqrt(sum);
if( sqr-floor(sqr)==0 ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
}
}
}
return count;
}
int main(){
int arr[] = { 1, 2, 4, 8, 5, 6 };
// Size of arr[]
int n = sizeof(arr) / sizeof(int);
cout <<endl<<"Pairs whose sum is perfect square :"<<countPairs(arr, n);
return 0;
}輸出
如果執行以上程式碼，將生成以下輸出：
Pairs whose sum is perfect square :2
更新於：2020年8月29日
560 次檢視
廣告