Tìm số hạng thứ n của quan hệ truy hồi cho trước trong C++

Khái niệm

Cho dãy số bn với b₁=1 và bₙ₊₁/bₙ = 2ⁿ. Tìm giá trị log₂(bₙ) cho n cho trước.

Ví dụ 1

Đầu vào: 6

Đầu ra: 15

Giải thích: log₂(bₙ) = n(n-1)/2 = 6*5/2 = 15

Ví dụ 2

Đầu vào: 200

Đầu ra: 19900

Phương pháp

bₙ₊₁/bₙ = 2ⁿ, bₙ/bₙ₋₁ = 2ⁿ⁻¹, ..., b₂/b₁ = 2¹. Nhân tất cả: bₙ₊₁/b₁ = 2^(n(n+1)/2). Với b₁=1 → bₙ₊₁ = 2^(n(n+1)/2). Thay n+1 bằng n: bₙ = 2^(n(n-1)/2). Lấy log₂: log₂(bₙ) = n(n-1)/2.

Ví dụ

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

int sum(int n1) {
    int ans1 = (n1 * (n1 - 1)) / 2;
    return ans1;
}

int main() {
    int n = 200;
    cout << sum(n);
    return 0;
}

Đầu ra

19900