ในส่วนนี้เราจะดูโจทย์น่าสนใจ สมมติเรามีอาร์เรย์ N องค์ประกอบ เราต้องหาจำนวนจุดตัด (insertion points) น้อยที่สุดเพื่อทำให้อาร์เรย์นี้กลายเป็น co-prime array ใน co-prime array GCD ของทุกคู่ที่ติดกันคือ 1 เราต้องพิมพ์อาร์เรย์ด้วย
สมมติอาร์เรย์คือ {5, 10, 20} นี่ไม่ใช่ co-prime array โดยการแทรก 1 ระหว่าง 5,10 และ 10,20 จะกลายเป็น co-prime array อาร์เรย์จะกลายเป็น {5, 1, 10, 1, 20}
อัลกอริทึม
makeCoPrime(arr, n): begin count := 0 for i in range 1 to n, do if gcd of arr[i] and arr[i – 1] is not 1, then increase count by 1 done display count value display the first element of arr for i in range 1 to n, do if gcd of arr[i] and arr[i – 1] is not 1, then display 1 display element arr[i] done end
ตัวอย่าง
#include <iostream> #include <algorithm> using namespace std; int makeCoPrime(int arr[], int n){ int count = 0; for(int i = 1; i<n; i++){ if(__gcd(arr[i], arr[i - 1]) != i){ count++; } } cout << "Number of intersection points: " << count << endl; cout << arr[0] << " "; for(int i = 1; i<n; i++){ if(__gcd(arr[i], arr[i - 1]) != i){ cout << 1 << " "; } cout << arr[i] << " "; } } int main() { int A[] = {2, 7, 28}; int n = sizeof(A)/sizeof(A[0]); makeCoPrime(A, n); }ผลลัพธ์
Number of intersection points: 1 2 7 1 28
