Kiểm tra số có phải tổng n số tự nhiên đầu tiên trong C++

Cho số num. Nhiệm vụ: kiểm tra num có phải tổng của n số tự nhiên đầu tiên không.

Ví dụ:

Đầu vào: num = 55

Đầu ra: yes, 10

Giải thích: 55 = 1+2+...+10.

Phương pháp giải

Cách 1: Lặp cộng dồn - Cộng 1+2+... cho đến khi sum >= num. Nếu bằng => trả về n, nếu lớn => -1.

Cách 2: Công thức toán học - Tổng n số đầu = n(n+1)/2. Giải phương trình bậc 2: n^2 + n - 2*num = 0. Nghiệm n = (-1 + sqrt(1+8*num))/2. Kiểm tra n có phải nguyên không.

Chương trình minh họa (Cách 1)

Ví dụ

#include <iostream>
using namespace std;

int isNatSum(int num) {
    int sum = 0;
    for (int n = 1; sum < num; n++) {
        sum += n;
        if (sum == num)
            return n;
    }
    return -1;
}

int main() {
    int num = 55;
    int n = isNatSum(num);
    if (n == -1)
        cout << "The value is not sum of natural numbers";
    else
        cout << "The value is a sum of first " << n << " natural numbers";
    return 0;
}

Kết quả

The value is a sum of first 10 natural numbers

Chương trình minh họa (Cách 2 - tối ưu)

Ví dụ

#include <iostream>
#include <math.h>
using namespace std;

int isNatSum(int num) {
    int n = (-1 + sqrt(1 + (8 * num))) / 2;
    if (ceil(n) == floor(n)) {
        return n;
    }
    return -1;
}

int main() {
    int num = 55;
    int n = isNatSum(num);
    if (n == -1)
        cout << "The value is not sum of natural numbers";
    else
        cout << "The value is a sum of first " << n << " natural numbers";
    return 0;
}

Kết quả

The value is a sum of first 10 natural numbers