資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中計算將陣列所有值設定為1所需的最少右翻轉次數
我們得到一個由 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 為輸入，並返回將陣列值設定為 1（將所有關閉的燈泡開啟）所需的最少右翻轉次數。
變數 count 用於儲存翻轉次數，初始值為 0。
陣列 switch[] 用於儲存與第 i 個燈泡對應的所有開關的初始狀態。所有開關都關閉 (switch[]={0}.)
從 i=0 到 n 開始，我們執行以下操作：
如果燈泡開啟且開關關閉，則不做任何操作（增加 i）
如果燈泡關閉且開關開啟，則不做任何操作（增加 i），因為關閉開關不會改變燈泡的狀態
如果燈泡關閉且開關關閉，則增加計數並翻轉右側所有燈泡的狀態。（while 迴圈）
for 迴圈結束後，返回 'count' 中的結果作為已執行的翻轉次數。
- 返回 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
更新於：2020年7月28日
201 次瀏覽
廣告