k दिनों के बाद सक्रिय और निष्क्रिय सेल?

यहां हम एक दिलचस्प समस्या देखेंगे। मान लीजिए कि एक बाइनरी ऐरे आकार n का दिया गया है। यहां n> 3. एक सही मान या 1 मान इंगित करता है कि सक्रिय स्थिति है, और 0 या गलत निष्क्रिय को इंगित करता है। एक अन्य संख्या k भी दी गई है। हमें k दिनों के बाद सक्रिय या निष्क्रिय कोशिकाओं को खोजना होगा। प्रतिदिन के बाद ith सेल की स्थिति सक्रिय हो जाएगी यदि बाएँ और दाएँ कोशिकाएँ समान नहीं हैं, यदि वे समान हैं, तो यह निष्क्रिय हो जाएगी। सबसे बाएं और दाएं अधिकांश सेल में इसके पहले और बाद में कोई सेल नहीं है। तो सबसे बाएँ और दाएँ ज़्यादातर सेल हमेशा 0 होते हैं।

आइए विचार प्राप्त करने के लिए एक उदाहरण देखें। मान लीजिए कि एक सरणी {0, 1, 0, 1, 0, 1, 0, 1} की तरह है, और k =3 का मान है। तो आइए देखें कि यह दिन-ब-दिन कैसे बदलता है।

• 1 दिन के बाद सरणी {1, 0, 0, 0, 0, 0, 0, 0}
होगी
• 2 दिनों के बाद सरणी होगी {0, 1, 0, 0, 0, 0, 0, 0}
• 3 दिनों के बाद सरणी {1, 0, 1, 0, 0, 0, 0, 0}
होगी

तो 2 सक्रिय सेल और 6 निष्क्रिय सेल

एल्गोरिदम

activeCellKdays(arr, n, k)

begin
   make a copy of arr into temp
   for i in range 1 to k, do
      temp[0] := 0 XOR arr[1]
      temp[n-1] := 0 XOR arr[n-2]
      for each cell i from 1 to n-2, do
         temp[i] := arr[i-1] XOR arr[i+1]
      done
      copy temp to arr for next iteration
   done
   count number of 1s as active, and number of 0s as inactive, then return the values.
end

उदाहरण

#include <iostream>
using namespace std;
void activeCellKdays(bool arr[], int n, int k) {
   bool temp[n]; //temp is holding the copy of the arr
   for (int i=0; i<n ; i++)
      temp[i] = arr[i];
   for(int i = 0; i<k; i++){
      temp[0] = 0^arr[1]; //set value for left cell
      temp[n-1] = 0^arr[n-2]; //set value for right cell
      for (int i=1; i<=n-2; i++) //for all intermediate cell if left and
         right are not same, put 1
      temp[i] = arr[i-1] ^ arr[i+1];
      for (int i=0; i<n; i++)
         arr[i] = temp[i]; //copy back the temp to arr for the next iteration
   }
   int active = 0, inactive = 0;
   for (int i=0; i<n; i++)
      if (arr[i])
         active++;
      else
         inactive++;
   cout << "Active Cells = "<< active <<", Inactive Cells = " << inactive;
}
main() {
   bool arr[] = {0, 1, 0, 1, 0, 1, 0, 1};
   int k = 3;
   int n = sizeof(arr)/sizeof(arr[0]);
   activeCellKdays(arr, n, k);
}

आउटपुट

Active Cells = 2, Inactive Cells = 6