logo

الخلايا النشطة وغير النشطة بعد k أيام

بالنظر إلى مجموعة ثنائية من الحجم n حيث ن > 3 . القيمة الحقيقية (أو 1) في المصفوفة تعني نشط والخطأ (أو 0) تعني غير نشط. بالنظر إلى الرقم k، تتمثل المهمة في العثور على عدد الخلايا النشطة وغير النشطة بعد k من الأيام. بعد كل يوم، تصبح حالة الخلية i نشطة إذا كانت الخلايا اليسرى واليمنى غير متماثلة وغير نشطة إذا كانت الخلية اليسرى واليمنى متماثلة (كلاهما 0 أو كليهما 1). 

نظرًا لعدم وجود خلايا قبل أقصى اليسار وبعد الخلايا الموجودة في أقصى اليمين، فإن خلايا القيمة قبل أقصى اليسار وبعد الخلايا الموجودة في أقصى اليمين تعتبر دائمًا 0 (أو غير نشطة).



أمثلة:  

Input : cells[] = {1 0 1 1} k = 2 Output : Active cells = 3 Inactive cells = 1 After 1 day cells[] = {0 0 1 1} After 2 days cells[] = {0 1 1 1} Input : cells[] = {0 1 0 1 0 1 0 1} k = 3 Output: Active Cells = 2  Inactive Cells = 6 Explanation : After 1 day cells[] = {1 0 0 0 0 0 0 0} After 2 days cells[] = {0 1 0 0 0 0 0 0} After 3 days cells[] = {1 0 1 0 0 0 0 0} Input : cells[] = {0 1 1 1 0 1 1 0} k = 4 Output: Active Cells = 3  Inactive Cells = 5

الشيء المهم الوحيد هو التأكد من أننا نحتفظ بنسخة من المصفوفة المحددة لأننا نحتاج إلى تحديث القيم السابقة لليوم التالي. وفيما يلي خطوات مفصلة. 

  1. أولاً نقوم بنسخ صفيف الخلايا[] إلى صفيف temp[] وإجراء تغييرات في صفيف temp[] وفقًا لشرط معين.
  2. في الحالة يُعطى أنه إذا كانت الخلية اليسرى واليمنى المباشرة للخلية الأولى إما غير نشطة أو نشطة في اليوم التالي، تصبح غير نشطة، أي؛ (الخلايا[i-1] == 0 والخلايا[i+1] == 0) أو (الخلايا[i-1] == 1 والخلايا[i+1] == 1) ثم الخلايا[i] = 0 يمكن تطبيق هذه الشروط باستخدام XOR للخلايا[i-1] والخلايا[i+1].
  3. بالنسبة لخلية الفهرس رقم 0 temp[0] = 0^cells[1] ولـ (n-1)'درجة حرارة خلية الفهرس[n-1] = 0^cells[n-2].
  4. الآن بالنسبة للفهرس من 1 إلى n-2، قم بالعملية التالية temp[i] = cell[i-1] ^ cell[i+1]
  5. كرر العملية حتى اكتمال k أيام.

وفيما يلي تنفيذ الخطوات المذكورة أعلاه. 



C++
// C++ program to count active and inactive cells after k // days #include   using namespace std; // cells[] - store current status of cells // n - Number of cells // temp[] - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days void activeAndInactive(bool cells[] int n int k) {  // copy cells[] array into temp [] array  bool temp[n];  for (int i=0; i<n ; i++)  temp[i] = cells[i];  // Iterate for k days  while (k--)  {  // Finding next values for corner cells  temp[0] = 0^cells[1];  temp[n-1] = 0^cells[n-2];  // Compute values of intermediate cells  // If both cells active or inactive then temp[i]=0  // else temp[i] = 1.  for (int i=1; i<=n-2; i++)  temp[i] = cells[i-1] ^ cells[i+1];  // Copy temp[] to cells[] for next iteration  for (int i=0; i<n; i++)  cells[i] = temp[i];  }  // count active and inactive cells  int active = 0 inactive = 0;  for (int i=0; i<n; i++)  (cells[i] == 1)? active++ : inactive++;  printf('Active Cells = %d Inactive Cells = %d'  active inactive); } // Driver program to check the test case int main() {  bool cells[] = {0 1 0 1 0 1 0 1};  int k = 3;  int n = sizeof(cells)/sizeof(cells[0]);  activeAndInactive(cells n k);  return 0; } 
Java
// Java program to count active and  // inactive cells after k days class GFG {   // cells[] - store current status  // of cells n - Number of cells // temp[] - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days static void activeAndInactive(boolean cells[]   int n int k) {  // copy cells[] array into temp [] array  boolean temp[] = new boolean[n];  for (int i = 0; i < n; i++)  temp[i] = cells[i];  // Iterate for k days  while (k-- > 0) {    // Finding next values for corner cells  temp[0] = false ^ cells[1];  temp[n - 1] = false ^ cells[n - 2];  // Compute values of intermediate cells  // If both cells active or inactive then   // temp[i]=0 else temp[i] = 1.  for (int i = 1; i <= n - 2; i++)  temp[i] = cells[i - 1] ^ cells[i + 1];  // Copy temp[] to cells[] for next iteration  for (int i = 0; i < n; i++)  cells[i] = temp[i];  }  // count active and inactive cells  int active = 0 inactive = 0;  for (int i = 0; i < n; i++)  if (cells[i] == true)  active++;  else  inactive++;  System.out.print('Active Cells = ' + active + ' ' +   'Inactive Cells = ' + inactive); } // Driver code public static void main(String[] args)  {  boolean cells[] = {false true false true  false true false true};  int k = 3;  int n = cells.length;  activeAndInactive(cells n k); } } // This code is contributed by Anant Agarwal. 
Python3
# Python program to count # active and inactive cells after k # days # cells[] - store current # status of cells # n - Number of cells # temp[] - to perform # intermediate operations # k - number of days # active - count of active # cells after k days # inactive - count of active # cells after k days def activeAndInactive(cellsnk): # copy cells[] array into temp [] array temp=[] for i in range(n+1): temp.append(False) for i in range(n): temp[i] = cells[i] # Iterate for k days while (k >0): # Finding next values for corner cells temp[0] = False^cells[1] temp[n-1] = False^cells[n-2] # Compute values of intermediate cells # If both cells active or # inactive then temp[i]=0 # else temp[i] = 1. for i in range(1n-2+1): temp[i] = cells[i-1] ^ cells[i+1] # Copy temp[] to cells[] # for next iteration for i in range(n): cells[i] = temp[i] k-=1 # count active and inactive cells active = 0 inactive = 0; for i in range(n): if(cells[i] == True): active+=1 else: inactive+=1 print('Active Cells ='active'  '  'Inactive Cells =' inactive) # Driver code cells = [False True False True False True False True] k = 3 n =len(cells) activeAndInactive(cells n k) # This code is contributed # by Anant Agarwal. 
C#
// C# program to count active and  // inactive cells after k days using System; class GFG {   // cells[] - store current status  // of cells n - Number of cells // temp[] - to perform intermediate  // operations k - number of days // active - count of active cells  // after k days inactive - count // of active cells after k days static void activeAndInactive(bool []cells   int n int k) {    // copy cells[] array into  // temp [] array  bool []temp = new bool[n];  for (int i = 0; i < n; i++)  temp[i] = cells[i];  // Iterate for k days  while (k-- > 0) {    // Finding next values   // for corner cells  temp[0] = false ^ cells[1];  temp[n - 1] = false ^ cells[n - 2];  // Compute values of intermediate cells  // If both cells active or inactive then   // temp[i]=0 else temp[i] = 1.  for (int i = 1; i <= n - 2; i++)  temp[i] = cells[i - 1] ^ cells[i + 1];  // Copy temp[] to cells[]   // for next iteration  for (int i = 0; i < n; i++)  cells[i] = temp[i];  }  // count active and inactive cells  int active = 0 inactive = 0;  for (int i = 0; i < n; i++)  if (cells[i] == true)  active++;  else  inactive++;  Console.Write('Active Cells = ' + active + ' ' +   'Inactive Cells = ' + inactive); } // Driver code public static void Main()  {  bool []cells = {false true false true  false true false true};  int k = 3;  int n = cells.Length;  activeAndInactive(cells n k); } } // This code is contributed by Nitin Mittal. 
PHP
 // PHP program to count active  // and inactive cells after k // days // cells[] - store current status  // of cells n - Number of cells // temp[] - to perform intermediate  // operations k - number of days // active - count of active cells  // after k days inactive - count of // active cells after k days function activeAndInactive($cells $n $k) { // copy cells[] array into // temp [] array $temp = array(); for ($i = 0; $i < $n ; $i++) $temp[$i] = $cells[$i]; // Iterate for k days while ($k--) { // Finding next values  // for corner cells $temp[0] = 0 ^ $cells[1]; $temp[$n - 1] = 0 ^ $cells[$n - 2]; // Compute values of  // intermediate cells // If both cells active  // or inactive then temp[i]=0 // else temp[i] = 1. for ($i = 1; $i <= $n - 2; $i++) $temp[$i] = $cells[$i - 1] ^ $cells[$i + 1]; // Copy temp[] to cells[]  // for next iteration for ($i = 0; $i < $n; $i++) $cells[$i] = $temp[$i]; } // count active and  // inactive cells $active = 0;$inactive = 0; for ($i = 0; $i < $n; $i++) ($cells[$i] == 1)? $active++ : $inactive++; echo 'Active Cells = ' $active ' Inactive Cells = ' $inactive; } // Driver Code $cells= array(0 1 0 1 0 1 0 1); $k = 3; $n = count($cells); activeAndInactive($cells $n $k); // This code is contributed by anuj_67. ?> 
JavaScript
<script> // javascript program to count active and  // inactive cells after k days  // cells - store current status  // of cells n - Number of cells  // temp - to perform intermediate operations  // k - number of days  // active - count of active cells after k days  // inactive - count of active cells after k days  function activeAndInactive(cells  n  k)   {    // copy cells array into temp array  var temp = Array(n).fill(false);  for (i = 0; i < n; i++)  temp[i] = cells[i];  // Iterate for k days  while (k-- > 0)  {  // Finding next values for corner cells  temp[0] = false ^ cells[1];  temp[n - 1] = false ^ cells[n - 2];  // Compute values of intermediate cells  // If both cells active or inactive then  // temp[i]=0 else temp[i] = 1.  for (i = 1; i <= n - 2; i++)  temp[i] = cells[i - 1] ^ cells[i + 1];  // Copy temp to cells for next iteration  for (i = 0; i < n; i++)  cells[i] = temp[i];  }  // count active and inactive cells  var active = 0 inactive = 0;  for (i = 0; i < n; i++)  if (cells[i] == true)  active++;  else  inactive++;  document.write('Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive);  }  // Driver code  var cells = [ false true false true false true false true ];  var k = 3;  var n = cells.length;  activeAndInactive(cells n k); // This code is contributed by Rajput-Ji </script> 

الإخراج
Active Cells = 2 Inactive Cells = 6

تعقيد الوقت: يا (ن * ك) حيث N هو حجم المصفوفة وK هو عدد الأيام.
المساحة المساعدة: O(N)

تمت مراجعة هذه المقالة بواسطة فريق geeksforgeeks. إذا كان لديك نهج أفضل لهذه المشكلة يرجى المشاركة.