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