Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

Đếm số trong khoảng chia hết cho tất cả phần tử mảng trong C++

Cho hai số START và END xác định một khoảng số. Và một mảng số dương Arr[]. Mục tiêu là tìm tất cả các số chia hết cho tất cả phần tử của Arr[] và nằm trong khoảng [START, END].

Phương pháp 1 (Đơn giản)

Ta thực hiện bằng cách duyệt số từ START đến END và với mỗi số kiểm tra xem số đó có chia hết cho tất cả phần tử của mảng không. Nếu có tăng count.

Phương pháp 2 (Kiểm tra chia hết cho BCNN của các phần tử mảng)

Ta tìm BCNN (LCM) của tất cả phần tử mảng và sau đó kiểm tra và đếm tất cả các số trong khoảng [START, END] chia hết cho BCNN đó.

Hãy hiểu qua các ví dụ.

Đầu vào

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

Đầu ra

Số chia hết cho tất cả phần tử mảng: 2

Giải thích

Các số 8 và 16 trong khoảng chia hết cho tất cả phần tử mảng.

Đầu vào

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

Đầu ra

Số chia hết cho tất cả phần tử mảng: 0

Giải thích

Không có số nào giữa 100 đến 200 chia hết cho bất kỳ phần tử mảng nào.

Phương pháp 1 (Đơn giản)

Phương pháp sử dụng trong chương trình dưới đây

  • Nhận số nguyên START và END làm biến phạm vi.
  • Hàm divisiblebyArr(int start, int end, int arr[], int len) nhận biến phạm vi và mảng, trả về số lượng số chia hết cho tất cả phần tử mảng.
  • Khởi tạo biến count = 0 cho các số như vậy.
  • Biến flag = 0.
  • Duyệt khoảng số bằng vòng lặp for. i=start đến i=end.
  • Với mỗi số num=i, dùng vòng lặp while kiểm tra số chia hết cho tất cả phần tử mảng.
  • Nếu tất cả phần tử chia hết num, đặt flag=1.
  • Ngoài while nếu flag=1 tăng count.
  • Sau tất cả vòng lặp count chứa tổng số chia hết cho tất cả phần tử mảng.
  • Trả về count làm kết quả.

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 << "Số chia hết cho tất cả phần tử mảng: " << divisiblebyArr(START, END, Arr, len);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số chia hết cho tất cả phần tử mảng: 2

Phương pháp 2 (BCNN)

Phương pháp sử dụng trong chương trình dưới đây

  • Nhận 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ề BCNN bằng cách tìm số đầu tiên chia hết cho cả hai dùng vòng lặp while.
  • Hàm getLCMArray(int arr[], int n) nhận mảng và độ dài, trả về BCNN của tất cả phần tử mảng.
  • Tính BCNN đầu tiên là getLCM(arr[0], arr[1]). Sau đó liên tiếp tìm BCNN của BCNN trước và arr[i] bằng cách gọi getLCM(lcm, arr[i]) với i=2 đến i<n.
  • Hàm divisiblebyArr(int start, int end, int arr[], int len) nhận biến phạm vi và mảng, trả về số lượng số chia hết cho tất cả phần tử mảng.
  • Khởi tạo biến count = 0 cho các số như vậy.
  • Biến lcm = getLCMArray(arr, len).
  • Duyệt khoảng số bằng vòng lặp for. i=start đến i=end.
  • Với mỗi số i, kiểm tra nếu chia hết lcm. Nếu đúng tăng count.
  • Sau tất cả vòng lặp count chứa tổng số chia hết cho tất cả phần tử mảng.
  • Trả về count làm kết quả.

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 << "Số chia hết cho tất cả phần tử mảng: " << divisiblebyArr(START, END, Arr, len);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số chia hết cho tất cả phần tử mảng: 2