Trong phần này, chúng ta sẽ xem liệu chúng ta có thể biểu thị một số dưới dạng tổng của hai số tam giác hay không. Các số hình tam giác như dưới đây -
Từ ví dụ này, chúng ta có thể thấy rằng 1, 3, 6, 10 là một số hình tam giác. Chúng ta cần biểu diễn một số N (chẳng hạn 16) dưới dạng tổng của hai số tam giác (6, 10).
Cách tiếp cận rất đơn giản. Chúng ta phải nhận tất cả các số tam giác nhỏ hơn N. Lập một tập hợp từ các giá trị này. Bây giờ chúng ta phải lấy một số như X từ tập hợp và kiểm tra xem N - X có trong tập hợp hay không, khi đó X có thể được biểu diễn dưới dạng tổng của hai số tam giác.
Ví dụ
#include <iostream>
#include <set>
using namespace std;
bool isSumTriangularNum(int n) {
set<int> s;
int i = 1;
while (1) { //find and store all triangular numbers below n, and store into set
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";
}
} Đầu ra
Can be represented