Đếm các cặp ô tô đi qua trong C ++

Đầu vào - arr [] ={1,0,1,0,1}

Đầu ra - Số cặp ô tô đi qua là:3

Giải thích - Các cặp (0,1) trong đó chỉ số 0 nhỏ hơn 1 là - (arr [1], arr [2]), (arr [1], arr [4]), (arr [3], arr [4])

Đầu vào - arr [] ={1,0,0,0,0}

Đầu ra - Số cặp ô tô đi qua là:0

Giải thích - không có cặp (0,1) trong đó chỉ số của 0 nhỏ hơn 1.

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 sẽ sử dụng hai cách tiếp cận. Cách tiếp cận ngây thơ đầu tiên sử dụng hai vòng lặp for. Bắt đầu duyệt qua mảng, ngay khi gặp số 0, đi qua mảng từ điểm đó đến điểm kết thúc một lần nữa và số lượng tăng dần khi gặp 1.

• Lấy một mảng arr [] chứa 0 và 1.

• Hàm count_cars (int arr [], int size) nhận mảng và độ dài làm đầu vào và trả về số lượng xe chạy qua.

• Lấy số lượng ban đầu là 0.

• Đảo ngược mảng từ chỉ mục i =0 đến i

• Nếu arr [i] là 0, duyệt lại mảng từ chỉ số j =i + 1 đến j

• Đối với mỗi arr [j] là 1 số gia tăng dưới dạng cặp (arr [i], arr [j]) là (0,1) và i

• Cuối cùng, chúng tôi sẽ nhận được tổng số.

• Kết quả là số lượt trả lại.

Phương pháp tiếp cận hiệu quả

Trong cách tiếp cận này, chúng tôi sẽ duyệt qua mảng từ cuối. Đếm tất cả 1 từ cuối. Đối với mỗi số 0 đầu tiên (từ cuối), không. trong số các cặp sẽ được tính bằng 1 là tạm thời.

• Lấy một mảng arr [] chứa 0 và 1.

• Hàm count_cars (int arr [], int size) nhận mảng và độ dài làm đầu vào và trả về số lượng xe chạy qua.

• Lấy số lượng ban đầu là 0.

• Đảo ngược mảng từ cuối bằng vòng lặp while cho đến kích thước> =1.

• Nếu arr [size-1] là 1, hãy tăng nhiệt độ biến cho số lượng 1 được tìm thấy cho đến nay.

• Nếu không, nó là 0 (có chỉ số thấp hơn tất cả các chỉ số 1 được remp). Các cặp sẽ được tạm thời. Đặt count =count + temp.

• Kích thước giảm dần cho phần tử tiếp theo.

• Cuối cùng, chúng tôi sẽ nhận được tổng số.

• Kết quả là số lượt trả lại.

Ví dụ (cách tiếp cận ngây thơ)

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
   int count = 0;
   for (int i=0; i<size-1; i++){
      if(arr[i] == 0){
         for (int j=i+1; j<size; j++)
         if (arr[j]==1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {1, 1, 0, 0, 1};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
   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 -

Count of passing car pairs are: 2

Ví dụ (Phương pháp Tiếp cận Hiệu quả)

#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
   int count = 0;
   int temp = 0;
   while (size >= 1){
      if (arr[size-1] == 1){
         temp++;
      }
      else{
         count = count + temp;
      }
      size--;
   }
   return count;
}
int main(){
   int arr[] = {1, 1, 0, 1, 1};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
   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 -

Count of passing car pairs are: 2