Giới thiệu
Cho số nguyên N. Tìm số hạng thứ N của dãy: 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8…
Ví dụ minh họa
Đầu vào
N = 7
Đầu ra
4
Phương pháp 1: Mô phỏng - O(√N)
Mỗi giá trị 2ᵏ xuất hiện 2ᵏ lần. Duyệt k từ 0, cộng dồn số lượng cho đến khi vượt quá N.
Chương trình minh họa
#include <iostream>
using namespace std;
int calcNthTerm(int N) {
int termCounter = 0, termValue = 1, k = 1;
while (termCounter < N) {
termCounter += k;
termValue *= 2;
k *= 2;
}
return termValue / 2;
}
int main() {
int N = 10;
cout << N << "th term of the series is " << calcNthTerm(N);
return 0;
}
Đầu ra
10th term of the series is 8
Phương pháp 2: Công thức toán học - O(1)
Vị trí cuối cùng của giá trị 2ᵐ là 2^(m+1) - 1. Tìm m lớn nhất sao cho 2^(m+1) - 1 < N. ⇒ m = floor(log₂(N+1)) - 1 ⇒ T(N) = 2^floor(log₂(N+1))
Chương trình minh họa
#include <iostream>
#include <cmath>
using namespace std;
int calcNthTerm(int N) {
return pow(2, floor(log2(N + 1)));
}
int main() {
int N = 10;
cout << N << "th term of the series is " << calcNthTerm(N);
return 0;
}
Đầu ra
10th term of the series is 8