資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
