ค้นหา Cube Pairs - (A n^ (2/3) Solution) ใน C++

ตัวเลขจะได้รับ เราต้องหาคู่สองคู่ ที่สามารถแทนจำนวนนั้นเป็นผลรวมของลูกบาศก์สองก้อนได้ ดังนั้นเราต้องหาคู่สองคู่ (a, b) และ (c, d) เพื่อให้จำนวนที่กำหนด n สามารถแสดงเป็น n =a ³ + b ³ =c ³ + ง ³

ความคิดนั้นง่าย ในที่นี้ทุกจำนวน a, b, c และ d ล้วนน้อยกว่า n ^1/3 . สำหรับทุกคู่ที่แตกต่างกัน (x, y) ที่เกิดขึ้นจากจำนวนที่น้อยกว่า n ^1/3 , ถ้าผลรวมของพวกเขา (x ³ + y ³ ) เท่ากับตัวเลขที่กำหนด เราจัดเก็บไว้ในตารางแฮชโดยมีค่าผลรวมเป็นคีย์ จากนั้นหากผลรวมเดิมกลับมาอีกครั้ง ก็แค่พิมพ์แต่ละคู่

อัลกอริทึม

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 = i3 + j3
         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)