Số lượng ước số có nhiều bit đặt hơn thương số trên phép chia N trong C ++

Chúng ta được cho với một số nguyên, giả sử N được coi là một số chia và nó sẽ được chia với các số bắt đầu từ 1 - N và nhiệm vụ là tính số lượng các ước số có số bit bộ nhiều hơn thương khi chia cho số N.

đã cho

Ví dụ

Đầu vào - int N =6

Đầu ra - Tổng số ước số có nhiều bit đặt hơn thương trên phép chia N là:5

Giải thích - Đầu tiên, chúng ta sẽ chia số N với các số bắt đầu từ 1 - N và tính toán các bit đã đặt của số chia và thương, tức là

1-> N =6/1 (1) =6 (2) =1 <2 =không được xét

2-> N =6/2 (1) =3 (2) =2 =2 =coi

3-> N =6/3 (2) =2 (1) =2> 1 =coi

4 -> N =6/4 (1) =1 (1) =1 =1 =được xem xét

5-> N =6/5 (2) =1 (1) =2> 1 =được xem xét

6-> N =6/6 (2) =1 (1) =2> 1 =được xem xét

Như chúng ta thấy, chúng ta sẽ xem xét các trường hợp và kết quả đầu ra sẽ là 5.

Đầu vào - int N =10

Đầu ra - Tổng số ước số có nhiều bit đặt hơn thương trên phép chia N là:8

Giải thích - Đầu tiên, chúng ta sẽ chia số N với các số bắt đầu từ 1 - N và tính toán các bit đã đặt của số chia và thương, tức là

1-> N =10/1 (1) =10 (2) =1 <2 =không được xét

2-> N =10/2 (1) =5 (2) =2 =2 =coi

3-> N =10/3 (2) =3 (2) =2 =2 =coi

4-> N =10/4 (1) =2 (1) =1 <2 =không được xét

5-> N =10/5 (2) =2 (1) =2> 2 =coi

6-> N =10/6 (2) =1 (1) =2> 1 =được xem xét

7-> N =10/7 (3) =1 (1) =3> 1 =được xem xét

8-> N =10/8 (1) =1 (1) =1 =1 =được xem xét

9-> N =10/9 (2) =1 (1) =2> 2 =được xem xét

10-> N =10/10 (2) =1 (1) =2> 1 =được xem xét

Như chúng ta thấy, chúng ta sẽ xem xét các trường hợp được xem xét và kết quả đầu ra sẽ là 8.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Nhập một số nguyên dương N và chuyển nó vào hàm divisors_quotient () làm đối số.
Bên trong hàm divisors_quotient ()
- Trả lại lệnh gọi N cho hàm set_quo (N) + 1 và chuyển đến hàm set_quo ()
Bên trong hàm set_quo ()
- Tạo một biến tạm thời ở dạng bắt đầu và kết thúc và khởi tạo bắt đầu bằng 1 và kết thúc bằng sqrt (N).
- Bắt đầu vòng lặp WHILE đến start
- Kiểm tra IF (gọi hàm verify () và chuyển temp và N làm đối số) sau đó đặt end là temp
- ELSE, đặt bắt đầu là tạm thời + 1
- IF (! gọi hàm verify () và chuyển temp và N làm đối số) rồi trả về start + 1.
- ELSE, quay lại bắt đầu
Bên trong hàm verify ()
- Kiểm tra IF (lệnh gọi hàm val_bit (temp / val) nhỏ hơn lệnh gọi hàm val_bit (val)) sau đó trả về true nếu không trả về False
Bên trong hàm val_bit ()
- Khai báo số lượng biến tạm thời để lưu trữ kết quả.
- Vòng lặp bắt đầu WHILE val có giá trị. Trong vòng lặp, đặt val là val / 2 và tăng số lượng lên 1.
- Số lượt trả lại.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int val_bit(int val) {
   int count = 0;
   while (val) {
      val = val / 2;
      count++;
   }
   return count;
}
bool verify(int val, int temp) {
   if (val_bit(temp / val) <= val_bit(val)) {
      return true;
   }
   return false;
}
int set_quo(int N) {
   int start = 1;
   int end = sqrt(N);
   while (start < end) {
      int temp = (start + end) / 2;
      if (verify(temp, N)) {
         end = temp;
      } else {
         start = temp + 1;
      }
   }
   if (!verify(start, N)) {
      return start + 1;
   } else {
      return start;
   }
}

int divisors_quotient(int N) {
   return N - set_quo(N) + 1;
}
int main() {
   int N = 10;
   cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
   return 0;
}

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Đầu ra

Count of divisors having more set bits than quotient on dividing N are: 8