คำชี้แจงปัญหา
เรามีจำนวนเต็ม N เราจำเป็นต้องแสดง N เป็นผลรวมของจำนวนเต็ม K โดยการเพิ่มจำนวนเต็มเหล่านี้บางส่วนหรือทั้งหมดเราจะได้ตัวเลขทั้งหมดในช่วง 1 ถึง N ภารกิจคือการหาค่าต่ำสุดของ K
ตัวอย่าง
ถ้า N =8 คำตอบสุดท้ายคือ K จะเป็น 3
ถ้าเรานำจำนวนเต็ม 1, 2, 3 และ 4 แล้วบวกกลุ่มเหล่านี้บางส่วนหรือทั้งหมด เราจะได้ตัวเลขทั้งหมดในช่วง 1 ถึง N
e.g. 1 = 1 2 = 2 3 = 3 4 = 4 5 = 1 + 5 6 = 4 + 2 7 = 4 + 3 8 = 1 + 3 + 4
อัลกอริทึม
Count number of bits from given integer
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int getMinNumbers(int n) {
int cnt = 0;
while (n) {
++cnt;
n = n >> 1;
}
return cnt;
}
int main() {
int n = 8;
cout << "Minimum required numbers = " <<getMinNumbers(n) << endl;
return 0;
} เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ดังต่อไปนี้
ผลลัพธ์
Minimum required numbers = 4
