นับคู่รถที่ผ่านกันใน C++

มาดูตัวอย่าง

อินพุต − arr[] = {1,0,1,0,1}

เอาต์พุต − จำนวนคู่รถที่ผ่านกัน คือ 3

คำอธิบาย − คู่ของ (0,1) ที่ดัชนีของ 0 น้อยกว่า 1 คือ − (arr[1],arr[2]), (arr[1],arr[4]), (arr[3],arr[4])

อินพุต − arr[] = {1,0,0,0,0}

เอาต์พุต − จำนวนคู่รถที่ผ่านกัน คือ 0

คำอธิบาย − ไม่มีคู่ของ (0,1) ที่ดัชนีของ 0 น้อยกว่า 1

แนวทางที่ใช้ในโปรแกรม

เราจะใช้สองวิธี วิธีแรกแบบง่ายด้วยลูป FOR สองชั้น เริ่มเดินทางอาเรย์ เมื่อเจอ 0 เดินทางอาเรย์จากจุดนั้นถึงท้ายอีกครั้งและเพิ่ม count เมื่อเจอ 1

• รับอาเรย์ arr[] ที่มี 0 และ 1
• ฟังก์ชัน count_cars(int arr[], int size) รับอาเรย์และความยาว คืนจำนวนรถที่ผ่านกัน
• กำหนด count เริ่มต้น 0
• เดินทางอาเรย์จากดัชนี i=0 ถึง i<length-1
• ถ้า arr[i] เป็น 0 เดินทางอาเรย์อีกครั้งจากดัชนี j=i+1 ถึง j<length
• สำหรับแต่ละ arr[j] เป็น 1 เพิ่ม count เพราะคู่ (arr[i],arr[j]) เป็น (0,1) และ i<j
• ท้ายสุดเราจะได้จำนวนรวม
• คืน count

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้เราจะเดินทางอาเรย์จากท้าย นับ 1 ทั้งหมดจากท้าย สำหรับ 0 แรก (จากท้าย) จำนวนคู่จะเป็นจำนวน 1 ที่นับได้คือ temp

• รับอาเรย์ arr[] ที่มี 0 และ 1
• ฟังก์ชัน count_cars(int arr[], int size) รับอาเรย์และความยาว คืนจำนวนรถที่ผ่านกัน
• กำหนด count เริ่มต้น 0
• เดินทางอาเรย์จากท้ายด้วยลูป while จน size>=1
• ถ้า arr[size-1] เป็น 1 เพิ่มตัวแปร temp สำหรับจำนวน 1 ที่เจอมาแล้ว
• มิฉะนั้น เป็น 0 (ซึ่งมีดัชนีต่ำกว่า 1 ทั้งหมดคือ temp) คู่จะเป็น temp กำหนด count = count+temp
• ลด size สำหรับสมาชิกถัดไป
• ท้ายสุดเราจะได้จำนวนรวม
• คืน count

ตัวอย่าง (วิธีง่าย)

#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;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of passing car pairs are: 2

ตัวอย่าง (แนวทางมีประสิทธิภาพ)

#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;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of passing car pairs are: 2