数据结构
网络
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 次浏览
广告