Computer >> Máy Tính >  >> Lập trình >> C ++

Đếm các số trong một phạm vi chia hết cho tất cả các phần tử của mảng trong C ++

Chúng tôi được cung cấp hai số START và END để xác định một dải số. Và cũng là một mảng các số dương Arr []. Mục đích là tìm tất cả các số chia hết cho tất cả các phần tử của Arr [] và nằm trong phạm vi [START, END].

Phương pháp 1 (Phương pháp tiếp cận ngây thơ)

Chúng ta sẽ làm điều này bằng cách duyệt các số từ BẮT ĐẦU đến KẾT THÚC và đối với mỗi số, chúng ta sẽ kiểm tra xem số đó có chia hết cho tất cả các phần tử của mảng hay không. Nếu có, số lượng tăng dần.

Phương pháp 2 (kiểm tra tính chia hết theo LCM của các phần tử mảng)

Chúng tôi sẽ tìm LCM của tất cả các phần tử mảng, sau đó kiểm tra và đếm tất cả các số trong phạm vi [START, END] chia hết cho LCM đó.

Hãy cùng hiểu với các ví dụ.

Đầu vào 

START=1 END=20 Arr[]= { 2, 4, 8 }

Đầu ra 

Numbers that are divisible by all array elements: 2

Giải thích 

Numbers 8 and 16 are in the range that are divisible by all array elements.

Đầu vào 

START=100 END=200 Arr[]= { 230, 321, 490, 521 }

Đầu ra 

Numbers that are divisible by all array elements: 0

Giải thích 

No number between 100 to 200 divisible by any array element.

Phương pháp 1 (Phương pháp tiếp cận ngây thơ)

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Chúng tôi lấy số nguyên START và END làm biến phạm vi.

  • Hàm diviblebyArr (int start, int end, int arr [], int len) nhận các biến phạm vi và mảng và trả về tổng số các số chia hết cho tất cả các phần tử của mảng.

  • Lấy số lượng biến ban đầu là 0 cho những số như vậy.

  • Lấy cờ biến là 0

  • Dải số theo chiều ngang bằng cách sử dụng vòng lặp for. i =start to i =end

  • Bây giờ đối với mỗi số num =i, sử dụng vòng lặp while kiểm tra xem số có chia hết cho tất cả các phần tử mảng hay không.

  • Nếu tất cả các phần tử chia hết num, hãy đặt cờ =1.

  • Bên ngoài trong khi nếu cờ =1 số gia tăng

  • Ở cuối tất cả các số vòng lặp sẽ có một số tổng chia hết cho tất cả các phần tử của mảng.

  • Trả lại kết quả là số lượng.

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
int divisiblebyArr(int start, int end, int arr[], int len){
   int count = 0;
   int flag=0;
   int index=0;
   for (int i = start; i <= end; i++){
      int num = i;
      index=0;
      while(index<len){
         if(num % arr[index++] == 0)
            { flag=1; }
         else{
            flag=0;
            break;
         }
      }
      if (flag == 1)
         { count++; }
      }
   return count;
}
int main(){
   int START = 5, END = 20;
   int Arr[] = {2,4,8 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers that are divisible by all array elements: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau - 

Numbers that are divisible by all array elements: 2

Phương pháp 2 (Phương pháp LCM)

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Chúng tôi lấy số nguyên START và END làm biến phạm vi.

  • Hàm getLCM (int a, int b) nhận hai số và trả về LCM của chúng bằng cách tìm số đầu tiên chia hết cho cả hai bằng cách sử dụng vòng lặp while.

  • Hàm getLCMArray (int arr [], int n) nhận một mảng và độ dài của nó làm đầu vào và trả về LCM của tất cả các phần tử của mảng.

  • Tính LCM đầu tiên dưới dạng getLCM (arr [0], arr [1]). Sau đó, tìm liên tiếp lcm của lcm trước đó và arr [i] bằng cách gọi getLCM (lcm, arr [i]) trong đó i =2 đến i

  • Hàm diviblebyArr (int start, int end, int arr [], int len) nhận các biến phạm vi và mảng và trả về tổng số các số chia hết cho tất cả các phần tử của mảng.

  • Lấy số lượng biến ban đầu là 0 cho những số như vậy.

  • Lấy biến lcm dưới dạng getLCMArray (int arr [], int len).

  • Dải số theo chiều ngang bằng cách sử dụng vòng lặp for. i =start to i =end

  • Bây giờ với mỗi số i, hãy kiểm tra xem nó có chia hết được không lcm. Nếu đúng, hãy đếm gia số.

  • Ở cuối tất cả các số vòng lặp sẽ có một số tổng chia hết cho tất cả các phần tử của mảng.

  • Trả lại kết quả là số lượng.

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
int getLCM(int a, int b){
   int m;
   m = (a > b) ? a : b;
   while(true){
      if(m % a == 0 && m % b == 0)
         return m;
      m++;
   }
}
int getLCMArray(int arr[], int n){
   int lcm = getLCM(arr[0], arr[1]);
   for(int i = 2; i < n; i++){
      lcm = getLCM(lcm, arr[i]);
   }
   return lcm;
}
int divisiblebyArr(int start, int end, int arr[], int len){
   int count = 0;
   int flag=0;
   int lcm=getLCMArray(arr,len);
   for (int i = start; i <= end; i++){
      if(i%lcm==0)
         { count++; }
      }
   return count;
}
int main(){
   int START = 5, END = 20;
   int Arr[] = {2,4,8 };
   int len=sizeof(Arr)/sizeof(Arr[0]);
   cout <<"Numbers that are divisible by all array elements: "<< divisiblebyArr(START,END,Arr,len);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau - 

Numbers that are divisible by all array elements: 2