ในปัญหานี้ เราจะได้รับสองอาร์เรย์ arr1[] และ arr2[] งานของเราคือสร้างโปรแกรมเพื่อค้นหา องค์ประกอบของอาร์เรย์ที่ไม่สามารถหารด้วยองค์ประกอบใดๆ ของอาร์เรย์อื่นได้
คำอธิบายปัญหา: ในที่นี้ เราจำเป็นต้องค้นหาองค์ประกอบทั้งหมดจาก arr1 ที่ไม่หารด้วยองค์ประกอบใดๆ ของ arr2
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: arr1[] ={17, 15, 5, 12, 8} arr2[] ={5, 4}
ผลลัพธ์: 17
คำอธิบาย −
องค์ประกอบของ arr1 และองค์ประกอบที่แบ่งมัน
17 -> ไม่มีองค์ประกอบใดสามารถแบ่งได้
15 -> 5 แบ่งองค์ประกอบ
5 -> 5 แบ่งองค์ประกอบ
12 -> 4 แบ่งองค์ประกอบ
8 -> 4 แบ่งองค์ประกอบ
แนวทางการแก้ปัญหา -
แนวทางที่เรียบง่ายและไร้เดียงสาในการแก้ปัญหาคือการใช้วิธีการโดยตรง เราจะวนซ้ำผ่าน arr1 และสำหรับแต่ละองค์ประกอบของ arr1 เราจะตรวจสอบว่าองค์ประกอบใด ๆ ของ arr2 แบ่งองค์ประกอบนั้นหรือไม่ หากไม่มีองค์ประกอบใดแบ่งออก ให้พิมพ์องค์ประกอบนั้น
อัลกอริทึม −
ขั้นตอนที่ 1: วนซ้ำสำหรับ arr1, i -> 0 ถึง n-1
ขั้นตอนที่ 2.1: สำหรับแต่ละ arr1[i], วน arr2, สำหรับ j -> 0 ถึง n-1
ขั้นตอนที่ 2.2.1 : ถ้า arr1[i] % arr2[j] ==0 ตั้งค่าสถานะต่อไป =-1
ขั้นตอนที่ 2.3: if flag !=-1 พิมพ์ arr1[i].
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {
int flag = 0;
for (int i = 0; i < arr1Size; i++) {
flag = 0;
for (int j = 0; j < arr2Size; j++){
if( arr1[i] % arr2[j] == 0 ) {
flag = -1;
break;
}
}
if ( flag == 0 )
cout<<arr1[i]<<"\t";
}
}
int main()
{
int arr1[] = {17, 15, 5, 12, 23, 8};
int arr2[] = {5, 4};
int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
cout<<"Elements of an array that are not divisible by any element of another array are ";
findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
return 0;
} ผลลัพธ์ -
Elements of an array that are not divisible by any element of another array are 17 23
วิธีแก้ปัญหานี้ใช้ได้แต่ไม่ได้ผล มาดูวิธีแก้ปัญหาที่มีประสิทธิภาพกัน
ในวิธีนี้ เราจะสร้างอาร์เรย์ isDivisible[] ขององค์ประกอบของ arr1 สำหรับองค์ประกอบทั้งหมดของ arr2 ให้ทำเครื่องหมายผลคูณทั้งหมดจนถึงองค์ประกอบที่ใหญ่ที่สุดของ arr1 และพิมพ์องค์ประกอบทั้งหมดที่ทำเครื่องหมายเป็นเท็จในอาร์เรย์ isDisible
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {
int maxEle = 0;
for (int i = 0; i < arr1Size; i++)
if (arr1[i] > maxEle)
maxEle = arr1[i];
int mark[maxEle];
for (int i = 0; i < arr2Size; i++)
for (int j = arr2[i]; j <= maxEle; j += arr2[i])
mark[j] = 1;
for (int i = 0; i < arr1Size; i++)
if ( mark[arr1[i]] != 1)
cout << arr1[i] << endl;
}
int main()
{
int arr1[] = {17, 15, 5, 12, 8};
int arr2[] = {5, 4};
int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
cout<<"Elements of an array that are not divisible by any element of another array are ";
findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
return 0;
} ผลลัพธ์ -
Elements of an array that are not divisible by any element of another array are 17
