資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究查詢立方對 - C++ 中的 (A n^(2/3) 解決方案)
給定一個數字。我們必須找到兩對，可以用兩個立方體的和表示該數字。所以，我們必須找到兩對 (a, b) 和 (c, d)，使得給定的數字 n 可表示為 n = a3 + b3 = c3 + d3
這個想法很簡單。這裡每個數字 a、b、c 和 d 都小於 n1/3。對於每個 由小於 n1/3 的數字形成的不同對(x, y)，如果它們的和 (x3 + y3) 等於給定的數字，我們將它們儲存到雜湊表中，其中總和值作為鍵，然後如果再次出現相同的總和，則只打印每一對
演算法
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)
更新於： 2019-9-25
91 次瀏覽
廣告