Quelles sont les cellules actives et inactives après k jours ?-C++-php.cn

Quelles sont les cellules actives et inactives après k jours ?

PHPz

Libérer： 2023-08-25 15:57:06

avant

1027 Les gens l'ont consulté

Quelles sont les cellules actives et inactives après k jours ?

Ici, nous verrons une question intéressante. Supposons que vous receviez un tableau binaire de taille n. Ici n > 3. Une valeur vraie ou 1 indique un état actif, et une valeur 0 ou faux indique un état inactif. Un autre nombre k est également donné. Il faut retrouver les cellules actives ou inactives après k jours. après chaque fois L'état diurne de la ième cellule est actif si les cellules gauche et droite ne sont pas identiques, et inactif si elles sont identiques. Il n’y a aucune cellule avant ou après les cellules les plus à gauche et à droite. Par conséquent, les cellules les plus à gauche et les plus à droite valent toujours 0.

Regardons un exemple pour comprendre cette idée. Supposons qu'un tableau ressemble à {0, 1, 0, 1, 0, 1, 0, 1} avec la valeur k = 3. Voyons comment cela évolue de jour en jour.

Après 1 jour, le tableau sera {1, 0, 0, 0, 0, 0, 0, 0}
Après 2 jours, le tableau sera {0, 1, 0, 0, 0, 0 , 0, 0 }
Après 3 jours, le tableau sera {1, 0, 1, 0, 0, 0, 0, 0}

Donc 2 cellules actives et 6 cellules inactives

Algorithme

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

Copier après la connexion

Exemple

#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);
}

Copier après la connexion