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

ในส่วนนี้เราจะดูว่าเราสามารถแสดงตัวเลขหนึ่งเป็นผลรวมของตัวเลขสามเหลี่ยมสองตัวได้หรือไม่ ตัวเลขสามเหลี่ยมด้านล่าง −

จากตัวอย่าง เราจะเห็นว่า 1, 3, 6, 10 เป็นจำนวนสามเหลี่ยมบางจำนวน เราจำเป็นต้องแสดงตัวเลข N (พูด 16) เป็นผลรวมของตัวเลขสามเหลี่ยมสองตัว (6, 10)

วิธีการนั้นง่ายมาก เราต้องได้จำนวนสามเหลี่ยมทั้งหมดที่น้อยกว่า N สร้างเซตจากค่าเหล่านี้ ตอนนี้เราต้องนำตัวเลข X จากเซตมา และตรวจสอบว่ามี N – X อยู่ในเซตหรือไม่ จากนั้น X สามารถแสดงเป็นผลรวมของตัวเลขสามเหลี่ยมสองจำนวนได้

ตัวอย่าง

#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";
   }
}

ผลลัพธ์

Can be represented