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

เราได้รับอาร์เรย์ของความยาว N ที่มี 0 และ 1 เท่านั้น ค่า 1 หมายถึงรถที่กำลังมุ่งหน้าไปทางทิศตะวันตก และค่า 0 หมายถึงรถที่กำลังมุ่งหน้าไปทางทิศตะวันออก

เรานับรถที่ผ่านเป็น 1 ถ้าคู่ของรถ A และรถ B เป็นจำนวนที่ 0<=A

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − 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

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

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

• ใช้อาร์เรย์ arr[] ที่มี 0 และ 1

• ฟังก์ชัน count_cars(int arr[], int size) ใช้อาร์เรย์และความยาวเป็นอินพุตและคืนค่าจำนวนรถที่ผ่าน

• นับเริ่มต้นเป็น 0

• อาร์เรย์การเคลื่อนที่จากดัชนี i=0 ถึง i

• ถ้า arr[i] เป็น 0 ให้ข้ามอาร์เรย์อีกครั้งจากดัชนี j=i+1 ถึง j

• สำหรับแต่ละ arr[j] เพิ่มขึ้น 1 ครั้ง นับเป็นคู่ (arr[i],arr[j]) คือ (0,1) และ i

• ในที่สุดเราก็ได้ยอดรวมแล้ว

• ผลตอบแทนนับเป็นผลลัพธ์

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

ในแนวทางนี้ เราจะสำรวจอาร์เรย์จากจุดสิ้นสุด นับ 1 ทั้งหมดจากจุดสิ้นสุด สำหรับแต่ละ 0 แรก (จากจุดสิ้นสุด) ไม่ใช่ ของคู่จะนับเป็น 1 ที่เป็นอุณหภูมิ

• ใช้อาร์เรย์ arr[] ที่มี 0 และ 1

• ฟังก์ชัน count_cars(int arr[], int size) ใช้อาร์เรย์และความยาวเป็นอินพุตและคืนค่าจำนวนรถที่ผ่าน

• นับเริ่มต้นเป็น 0

• Traverse array จาก end โดยใช้ while loop จนถึง size>=1.

• ถ้า arr[size-1] เป็น 1 ให้เพิ่มค่า temp ของตัวแปรสำหรับจำนวน 1 ที่พบ

• มิฉะนั้นจะเป็น 0 (ซึ่งมีดัชนีต่ำกว่า 1 ทั้งหมดซึ่งเป็นการทำซ้ำ) คู่จะเป็นอุณหภูมิ ตั้งนับ =นับ+อุณหภูมิ

• ลดขนาดสำหรับองค์ประกอบถัดไป

• ในที่สุดเราก็ได้ยอดรวมแล้ว

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง (แนวทางไร้เดียงสา)

#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