数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中计算除以 N 后商的 set bits 数小于除数的 set bits 数的除数个数
给定一个整数 N，将其视为除数，并用从 1 到 N 的数字除以它，任务是计算那些除数的个数，这些除数的 set bits 数大于除以给定数字 N 后的商的 set bits 数。
例如
输入 - int N = 6
输出 - 除以 N 后商的 set bits 数小于除数的 set bits 数的除数个数为：5
解释 - 首先，我们将数字 N 除以从 1 到 N 的数字，并计算除数和商的 set bits 数，即
1-> N = 6 /1(1) = 6(2) = 1 < 2 = 不考虑
2-> N = 6 /2(1) = 3(2) = 2 = 2 = 考虑
3-> N = 6 /3(2) = 2(1) = 2 > 1 = 考虑
4-> N = 6 /4(1) = 1(1) = 1 = 1 = 考虑
5-> N = 6 /5(2) = 1(1) = 2 > 1 = 考虑
6-> N = 6 /6(2) = 1(1) = 2 >1 = 考虑
如我们所见，我们将考虑这些情况，输出将为 5。
输入 - int N = 10
输出 - 除以 N 后商的 set bits 数小于除数的 set bits 数的除数个数为：8
解释 - 首先，我们将数字 N 除以从 1 到 N 的数字，并计算除数和商的 set bits 数，即
1-> N = 10 /1(1) = 10(2) = 1 < 2 = 不考虑
2-> N = 10 /2(1) = 5(2) = 2 = 2 = 考虑
3-> N = 10 /3(2) = 3(2) = 2 = 2 = 考虑
4-> N = 10 /4(1) = 2(1) = 1 < 2 = 不考虑
5-> N = 10 /5(2) = 2(1) = 2 > 2 = 考虑
6-> N = 10 /6(2) = 1(1) = 2 >1 = 考虑
7-> N = 10 /7(3) = 1(1) = 3 >1 = 考虑
8-> N = 10 /8(1) = 1(1) = 1 = 1 = 考虑
9-> N = 10 /9(2) = 1(1) = 2 > 2 = 考虑
10-> N = 10 /10(2) = 1(1) = 2 > 1 = 考虑
如我们所见，我们将考虑这些情况，输出将为 8。
下面程序中使用的算法如下
- 输入一个正整数 N，并将其作为参数传递给函数 divisors_quotient()。
- 在函数 divisors_quotient() 内部
- 返回 N - 对函数 set_quo(N) 的调用 + 1，并跳转到函数 set_quo()
- 在函数 set_quo() 内部
- 创建一个名为 start 和 end 的临时变量，并将 start 初始化为 1，end 初始化为 sqrt(N)。
- 启动循环 WHILE 直到 start < end，并创建一个名为 temp 的临时变量，将其设置为 (start + end) / 2
- 检查 IF(对函数 verify() 的调用并传递 temp 和 N 作为参数)，然后将 end 设置为 temp
- 否则，将 start 设置为 temp + 1
- IF(!对函数 verify() 的调用并传递 temp 和 N 作为参数)，则返回 start + 1。
- 否则，返回 start
- 在函数 verify() 内部
- 检查 IF(对函数 val_bit(temp/val) 的调用小于对函数 val_bit(val) 的调用)，则返回 true，否则返回 False
- 在函数 val_bit() 内部
- 声明一个名为 count 的临时变量来存储结果。
- 启动循环 WHILE val 有值。在循环内部，将 val 设置为 val / 2 并将 count 增加 1。
- 返回 count。
示例
#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;
}如果我们运行上述代码，它将生成以下输出：
输出
Count of divisors having more set bits than quotient on dividing N are: 8
86 次查看
