เราได้รับอาร์เรย์ของ 0 และ 1 ซึ่งแสดงถึงสถานะของหลอดไฟที่เชื่อมต่อกับสายเดียวกันตามลำดับ 0 แสดงว่าหลอดไฟปิดอยู่ และ 1 แสดงว่าหลอดไฟเปิดอยู่ สำหรับลำดับของหลอดไฟ N เช่นนี้ หากกดสวิตช์ของหลอดไฟ หลอดไฟทั้งหมดจะอยู่ทางด้านขวา (i+1 ถึง n) จะเปลี่ยนการจ้องมองก่อนหน้าจากเปิดเป็นปิดหรือจากปิดเป็นเปิด
สำหรับสถานะของหลอดไฟทั้งหมดที่กำหนด เป้าหมายคือการค้นหาสวิตช์ขั้นต่ำที่ต้องกดเพื่อเปิดสวิตช์ทั้งหมด [ สวิตช์เดียวกันสามารถกดกี่ครั้งก็ได้ ] เหมือนกับการพลิกสถานะของค่าดัชนีที่ถูกต้องในอาร์เรย์เพื่อตั้งค่าทั้งหมดเป็น 1
อินพุต
Bulbs[]= { 1,0,1,0 } ผลลัพธ์
Minimum right flips: 3
คำอธิบาย
สถานะเดิม 1010
Press switch 2:- 1:101 flip count=1 Press switch 3:- 11:10 flip count=2 Press switch 4:- 111:1 flip count=3
อินพุต
Bulbs[]= { 1,0,0,0 } ผลลัพธ์
Minimum right flips: 1
คำอธิบาย
Original state 1000 Press switch 2:- 1:111 flip count=1
เปิดหลอดไฟทั้งหมดทางขวาแล้ว
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
จำนวนเต็มเก็บสถานะของจำนวน N จำนวนหลอด
-
ฟังก์ชัน minFlips(int arr[],int n) รับอาร์เรย์และความยาว n เป็นอินพุตและส่งกลับจำนวนขั้นต่ำของการพลิกขวาเพื่อตั้งค่าอาร์เรย์ ( ปิด bulbs ทั้งหมดบน )
-
การนับตัวแปรใช้เพื่อเก็บจำนวนการพลิก เริ่มแรก 0
-
Array switch[] ใช้เพื่อเก็บสถานะเริ่มต้นของสวิตช์ทั้งหมดที่สอดคล้องกับหลอดไฟที่ i ทั้งหมดเป็น 0 ( switch[]={0}.)
-
เริ่มจาก i=0 ถึง n เราทำตาม −
-
หากหลอดไฟเปิดอยู่และสวิตช์ปิดอยู่ ไม่ต้องทำอะไร (เพิ่ม i)
-
หากหลอดไฟดับและเปิดสวิตช์อยู่ ไม่ต้องทำอะไร (เพิ่ม i) เนื่องจากการปิดสวิตช์จะไม่ทำอะไรกับสถานะของหลอดไฟ
-
หากหลอดไฟดับและสวิตช์ดับ ให้เพิ่มจำนวนและเปลี่ยนสถานะของหลอดไฟทั้งหมดทางด้านขวา ( ขณะวนซ้ำ )
-
-
หลังจากสิ้นสุด for loop ให้ส่งคืนผลลัพธ์ใน 'count' เมื่อพลิกเสร็จสิ้น
- นับคืน
ตัวอย่าง
// C++ program to find minimum number of move-to-front
// moves to arrange items in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int minFlips(int arr[], int n){
int count = 0;
int swich[n] = {0}; //Initially we don't flip the states, so flip is false
for(int i=0;i<n;i++){
if(arr[i]==1 && swich[i]==0)
i++;
if(arr[i]==0 && swich[i]==1)
i++;
if(arr[i]==0 && swich[i]==0){
count++;
int j=i;
while(j<n){
if(arr[j]==0)
arr[j++]=1;
else
arr[j++]=0;
}
}
}
return count;
}
int main(){
int Arr[] = {0,1,0,1};
int N = 4;
cout <<”Minimum right flips to set all values in an array:"<<
minFlips(Arr, N);
return 0;
} ผลลัพธ์
Minimum right flips to set all values in an array: 4
