[Cpp-STL] Bitset-CheckActivity 3

Bài tập.

Các nhà khoa học đang nghiêm cứu một loại vius, loại virus này có đặc điểm là sẽ tự động nhân đôi số lượng mỗi ngày. Các nhà khoa học muốn có n (1 ≤ n ≤ 109) con virus như trên nên họ đã tiến hành như sau: Họ lấy một chiệc hộp sạch (Không có con virus nào), mỗi ngày họ chỉ được thả nhiều nhất 1 con virus vào hộp. Các nhà khoa học muốn biết những ngày nào cần thả virus vào hộp. Hãy trả về một dãy v thể hiện hoạt động đó, v[i] = 1 nếu ngày đó các nhà khoa học thả virus vào và ngược lại.

Ví dụ:

• Với n = 2, thì checkActivity(n) = [1, 0].
  Giải thích:
  Họ sẽ thả một con virus vào hộp ở ngày thứ nhất, ngày thứ 2 họ không thả.
  
  
• Với n = 5, thì checkActivity(n) = [1, 0, 0, 1].
  Giải thích:
  Họ sẽ thả một con virus vào hộp ở ngày thứ nhất, 2 ngày sau họ không thả, ngày thứ 4 họ thả 1 con nữa là có được đúng 5 con virus.

Hướng dẫn.

Chuyển n về chuỗi nhị phân. Với các bit 1 thì thêm và dãy là true và ngược lại.

Sử dụng hàm test() để thuận lợi làm việc trên.

Code mẫu:

std::vector<int> checkActivity(int n)
{
    std::vector<int> v;
    int k;
    bitset<32> foo(n);
    for (k = foo.size()-1; k >= 0; k--){
        if (foo.test(k)){
            break;
        }
    }
    for (int i = 0; i <= k; i++){
        v.push_back(foo.test(i));
    }
    return v;
}