数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 统计 GCD 为 1 的子序列个数
给定一个整数元素数组，任务是从给定数组中找到 GCD 为 1 的子序列。GCD 是两个或多个整数的最大公约数，它可以完全整除这些数，并且是所有公约数中最大的。
输入 − int arr[] = {3, 4, 8, 16}
输出 − GCD 为 1 的子序列个数为 - 7
说明 −
从给定数组中可以形成的 GCD 为 1 的子序列为 (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8)
输入 − int arr[] = {5, 7, 10}
输出 − GCD 为 1 的子序列个数为 - 3
说明 −
从给定数组中可以形成的 GCD 为 1 的子序列为 (5, 7), (7, 10), (5, 7, 10)
下面程序中使用的方法如下
输入任意大小的整数元素数组。
计算数组的大小并将数据传递给函数以进行进一步处理
声明一个临时变量 count 用于存储 GCD 为 1 的子序列的计数
从 i 为 0 开始循环到数组的大小
在循环内部，从 j 为 0 开始另一个循环到数组的大小
在循环内部，检查 IF GCD(arr[i], arr[j]) = TRUE，则将计数加 1
返回计数
打印结果。
示例
# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a == 0)
return b;
return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
int count = 0;
for(int i=0;i<size;i++){
for(int j=0;j<=size;j++){
if(gcd(arr[i],arr[j])==1){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {3, 4, 8, 16};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
return 0;
}输出
如果我们运行上述代码，它将生成以下输出 -
Count of number of sub-sequences with GCD 1 are: 7
更新于: 2020-08-31
287 次浏览
广告