Trong bài toán này, chúng ta được cung cấp hai mảng arr1 [] và arr2 []. Nhiệm vụ của chúng ta là tạo một chương trình để tìm các phần tử của mảng mà không chia hết cho bất kỳ phần tử nào của mảng khác.
Mô tả sự cố: Ở đây, chúng ta cần tìm tất cả các phần tử từ arr1 mà không chia hết cho bất kỳ phần tử nào của arr2.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: arr1 [] ={17, 15, 5, 12, 8} arr2 [] ={5, 4}
Đầu ra: 17
Giải thích -
Các phần tử của arr1 và các phần tử phân chia chúng,
17 -> không phần tử nào có thể chia nó.
15 -> 5 chia phần tử.
5 -> 5 chia phần tử.
12 -> 4 chia phần tử.
8 -> 4 chia phần tử.
Phương pháp tiếp cận Giải pháp -
Một cách tiếp cận đơn giản và ngây thơ để giải quyết vấn đề là sử dụng phương pháp trực tiếp. Chúng tôi sẽ lặp qua arr1 và đối với mỗi phần tử của arr1, chúng tôi sẽ kiểm tra xem có phần tử nào của arr2 chia phần tử đó hay không. Nếu không có phần tử nào chia nó, hãy in phần tử đó.
Thuật toán -
Bước 1: vòng lặp cho arr1, i -> 0 đến n-1.
Bước 2.1: cho mỗi arr1 [i], vòng lặp arr2, cho j -> 0 đến n-1.
Bước 2.2.1: nếu arr1 [i]% arr2 [j] ==0, tiếp tục cờ =-1.
Bước 2.3: if flag! =-1, print arr1 [i].
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra -
Elements of an array that are not divisible by any element of another array are 17 23
Giải pháp này hợp lệ nhưng không hiệu quả. Vì vậy, hãy xem một giải pháp hiệu quả cho vấn đề,
Trong phương thức này, chúng ta sẽ tạo một mảng isDivible [] gồm các phần tử của arr1. Đối với tất cả các phần tử của arr2, hãy đánh dấu tất cả các bội số của chúng cho đến phần tử lớn nhất của arr1. Và in tất cả các phần tử được đánh dấu sai trong mảng có thể phân chia được.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra -
Elements of an array that are not divisible by any element of another array are 17