ตรวจสอบว่าเลขสามารถเขียนเป็นผลรวมของเลขสามเหลี่ยมสองจำนวนได้หรือไม่ ใน C++

เลขสามเหลี่ยม (Triangular numbers): 1, 3, 6, 10, 15, ... สูตร Tᵢ = i(i+1)/2

ตรวจสอบว่า N = Tₐ + T_b ได้หรือไม่

วิธี: หาเลขสามเหลี่ยมทั้งหมด < N ใส่ใน Set แล้ววนหา x ใน Set ว่า N-x อยู่ใน Set หรือไม่

ตัวอย่างโค้ด

#include <iostream>
#include <set>
using namespace std;

bool isSumTriangularNum(int n) {
    set<int> s;
    int i = 1;
    while (1) {
        int x = i * (i + 1) / 2;
        if (x >= n) break;
        s.insert(x);
        i++;
    }
    for (auto x : s)
        if (s.find(n - x) != s.end()) return true;
    return false;
}

int main() {
    int num = 16;
    if (isSumTriangularNum(num)) cout << "Can be represented";
    else cout << "Cannot be represented";
}

ผลลัพธ์

Can be represented