数据结构
网络
关系数据库管理系统 (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 次查看
广告