Chúng ta được đưa ra một dãy 0 và 1 biểu thị trạng thái của các bóng đèn được nối với cùng một dây theo thứ tự. 0 đại diện cho bóng đèn TẮT và 1 đại diện cho bóng đèn là KHÔNG. Đối với chuỗi N bóng đèn như vậy, nếu công tắc của bóng đèn được nhấn thì tất cả các bóng đèn bên phải, (thứ i + 1 cho đến thứ n) thay đổi cách nhìn trước đó của chúng, từ BẬT sang TẮT hoặc từ TẮT sang BẬT.
Đối với trạng thái nhất định của tất cả các bóng đèn, mục tiêu là tìm các công tắc tối thiểu được nhấn để BẬT tất cả chúng. [có thể nhấn cùng một công tắc bất kỳ số lần nào]. Nó cũng giống như việc lật trạng thái của các giá trị chỉ mục bên phải trong một mảng để đặt tất cả chúng là 1.
Đầu vào
Bulbs[]= { 1,0,1,0 } Đầu ra
Minimum right flips: 3
Giải thích
Trạng thái ban đầu 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
Đầu vào
Bulbs[]= { 1,0,0,0 } Đầu ra
Minimum right flips: 1
Giải thích
Original state 1000 Press switch 2:- 1:111 flip count=1
Tất cả các bóng đèn bên phải đều BẬT.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Số nguyên lưu trữ trạng thái của N. số bóng đèn.
-
Hàm minFlips (int arr [], int n) nhận một mảng và độ dài n của nó làm đầu vào và trả về số lần lật phải tối thiểu để đặt các giá trị của mảng (bật tất cả các bóng đèn)
-
Đếm biến được sử dụng để lưu trữ số lần lật, ban đầu là 0.
-
Công tắc mảng [] được sử dụng để lưu trữ trạng thái ban đầu của tất cả các công tắc tương ứng với bóng đèn thứ i. Tất cả đều là 0 (switch [] ={0}.)
-
Bắt đầu từ i =0 đến n, chúng tôi thực hiện theo sau -
-
Nếu bóng đèn BẬT và công tắc tắt, không làm gì cả (tăng i)
-
Nếu bóng đèn TẮT và công tắc đang bật, không làm gì (tăng i) vì tắt công tắc sẽ không ảnh hưởng gì đến trạng thái của bóng đèn
-
Nếu bóng đèn TẮT và công tắc tắt, hãy tăng số lượng và trạng thái bật của tất cả các bóng đèn ở bên phải. (vòng lặp while)
-
-
Sau khi kết thúc vòng lặp for, trả về kết quả ở dạng "count" khi lật xong.
- Số lượt trả lại.
Ví dụ
// 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;
} Đầu ra
Minimum right flips to set all values in an array: 4