เราได้รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและภารกิจคือการค้นหาลำดับย่อยจากอาร์เรย์ที่กำหนดซึ่งมี 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)
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ป้อนอาร์เรย์ขององค์ประกอบจำนวนเต็มทุกขนาดที่กำหนด
-
คำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชันเพื่อการประมวลผลต่อไป
-
ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บการนับของลำดับย่อยด้วย GCD เป็น 1
-
เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์
-
ภายในลูปเริ่มลูปอื่น FOR จาก 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
