เซลล์ที่ใช้งานและไม่ใช้งานหลังจาก 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