สมมติว่าเรามีอาร์เรย์ A[] โดยมีองค์ประกอบ n รายการ เราต้องหาอาร์เรย์ B[] อื่นซึ่งมีขนาดเป็น n+1 ดังนั้น GCD ของ B[i] และ B[i + 1] คือ A[i] หากมีหลายวิธีแก้ปัญหา ให้พิมพ์หนึ่งในนั้นที่มีผลรวมอาร์เรย์น้อยที่สุด ดังนั้นหาก A =[1, 2, 3] ผลลัพธ์จะเป็น [1, 2, 6, 3]
เมื่อ A มีองค์ประกอบเพียงตัวเดียวให้พูดว่า K แล้ว B =[K, K] ดังนั้น B[0] จะเป็น A[0] ตอนนี้ พิจารณาว่าเราทำได้ถึงดัชนี i ดังนั้นเราจึงได้ประมวลผลดัชนี i และคำนวณ B[i + 1] แล้ว ตอนนี้ GCD ของ B[i + 1] และ B[i + 2] =A[i + 1] จากนั้น GCD ของ B[i + 2] และ B[i + 3] =A[i + 2] ดังนั้น B[i + 2]>=LCM ของ A[i + 1], A[i + 2] เมื่อเราต้องการผลรวมขั้นต่ำ เราก็อยากได้ค่าต่ำสุดของ B[i + 2] ดังนั้น B[i + 2] – LCM ของ A[i + 2] และ A[i + 3]
ตัวอย่าง
#include <iostream>
#include <algorithm>
using namespace std;
int getLCM(int a, int b) {
return (a * b) / __gcd(a, b);
}
void gcdArray(int A[], int n) {
cout << A[0] << " ";
for (int i = 0; i < n - 1; i++)
cout << getLCM(A[i], A[i + 1]) << " ";
cout << A[n - 1];
}
int main() {
int A[] = { 1, 2, 3 };
int n = sizeof(A) / sizeof(A[0]);
cout << "Constructed array: ";
gcdArray(A, n);
} ผลลัพธ์
Constructed array: 1 2 6 3
