ให้เลขหนึ่งจำนวน เราต้องหาสองคู่ ที่สามารถแสดงเลขนั้นเป็นผลรวมของสองเลขยกกำลังสาม นั่นคือหา (a, b) และ (c, d) ที่ทำให้ n = a³ + b³ = c³ + d³
แนวคิดคือ ทุกตัวเลข a, b, c, d ต่ำกว่า n^(1/3) สำหรับทุกคู่ที่แตกต่างกัน (x, y) ที่สร้างจากตัวเลขน้อยกว่า n^(1/3) หากผลรวม (x³ + y³) เท่ากับเลขที่กำหนด เราเก็บไว้ใน hash table โดยใช้ผลรวมเป็น key หากผลรวมเดิมซ้ำขึ้นมา ให้พิมพ์คู่ทั้งสอง
อัลกอริทึม
getPairs(n): begin cube_root := cube root of n map as int type key and pair type value for i in range 1 to cube_root, do for j in range i + 1 to cube_root, do sum = i³ + j³ if sum is not same as n, then skip next part, go to second iteration if sum is present into map, then print pair, and (i, j), else insert (i,j) with corresponding sum into the map done done end
ตัวอย่าง
#include <iostream> #include <cmath> #include <map> using namespace std; int getPairs(int n){ int cube_root = pow(n, 1.0/3.0); map<int, pair<int, int> > my_map; for(int i = 1; i<cube_root; i++){ for(int j = i + 1; j<= cube_root; j++){ int sum = i*i*i + j*j*j; if(sum != n) continue; if(my_map.find(sum) != my_map.end()){ cout << "(" << my_map[sum].first << ", " << my_map[sum].second << ") and (" << i << ", " << j << ")" << endl; }else{ my_map[sum] = make_pair(i, j); } } } } int main() { int n = 13832; getPairs(n); }ผลลัพธ์
(2, 24) and (18, 20)
