我想找到对等式 a^3 + b^3 = c^3 + d^3的所有正整数解决方案，其中 a, b, c, d是 1 to 1000
蛮力解决方案继续计算每对（a，b）对的全部（c，d）对。我想改进该算法。我只想创建一次（c，d）对的列表。然后，当我们有一个（a，b）对时，在（c，d）列表中找到匹配项。我们可以通过将每对（C，d）对插入一个从总和到对的哈希表（或者，而具有该总和的对列表）
来快速找到匹配。n= 1000
for c from 1 to n
for d from 1 to n
result = c^3 + d^3
append (c,d) to list at value map[result]
for a from 1 to n
for b from 1 to n
result = a^3 + b^3
list = map.get(result)
foreach pair in list
print a,b, pair
我对我们有O（n^2）解决方案是对吗？为什么？我们如何改进它？什么是C＃实现？
另外，也许一旦我们拥有所有（C，d）对的地图，我们就可以直接使用它。我们不需要生成（a，b）对。每个（a，b）已经在地图中。如何实现这个想法？
您可以通过 组所有可能的总和，并打印出包含多于一个项目的组。这是O(N**2)算法：
// key is sum and value is a list of representations
Dictionary<int, List<Tuple<int, int>>> solutions =
new Dictionary<int, List<Tuple<int, int>>>();
for (int a = 1; a <= 1000; ++a)
for (int b = a; b <= 1000; ++b) {
int sum = a * a * a + b * b * b;
List<Tuple<int, int>> list = null;
if (!solutions.TryGetValue(sum, out list)) {
list = new List<Tuple<int, int>>();
solutions.Add(sum, list);
}
list.Add(new Tuple<int, int>(a, b));
}
String report = String.Join(Environment.NewLine,
solutions.Values
.Where(list => list.Count > 1) // more than one item
.Select(list => String.Join(", ",
list.Select(item => String.Format("({0}, {1})", item.Item1, item.Item2)))));
Console.Write(report);
输出（ 1585 行）是
(1, 12), (9, 10)
(1, 103), (64, 94)
(1, 150), (73, 144)
(1, 249), (135, 235)
(1, 495), (334, 438)
...
(11, 493), (90, 492), (346, 428) // <- notice three representations of the same sum
...
(663, 858), (719, 820)
(669, 978), (821, 880)
(692, 942), (720, 926)
(718, 920), (816, 846)
(792, 901), (829, 870)
所以我们有
1**3 + 12**3 == 9**3 + 10**3
...
11**3 + 493**3 == 90**3 + 492**3 == 346**3 + 428**3
...
792**3 + 901**3 == 829**3 + 870**3
我们有 8 triple 表示可能很有趣：
(11, 493), (90, 492), (346, 428)
(15, 930), (198, 927), (295, 920)
(22, 986), (180, 984), (692, 856)
(70, 560), (198, 552), (315, 525)
(111, 522), (359, 460), (408, 423)
(167, 436), (228, 423), (255, 414)
(300, 670), (339, 661), (510, 580)
(334, 872), (456, 846), (510, 828)
在纯linq中重述 @dmitry的答案（谁应该获得所有信用）：
from a in Enumerable.Range(1, 1000)
from b in Enumerable.Range(a, 1000 - a + 1)
let sum = a * a * a + b * b * b
group $"{a}^3 + {b}^3" by sum into g
where g.Count() > 1
orderby g.Key // just for niceness
select $"{g.Key} = " + String.Join(" = ", g)
我们可以实现更简单的解决方案计算" A"one_answers" b"的所有不同选项，然后将它们添加到 Dictionary<int, List<Tuple<int,int>>>中为@dimitry状态，但是，然后将报告生成更改为：
foreach (List<Tuple<int,int>> l in solutions.Values) {
foreach(Tuple<int,int> t1 in l) {
foreach(Tuple<int,int> t2 in l) {
Console.Write("({0},{1})({2},{3})", t1.Item1, t1.Item2, t2.Item1, t2.Item2);
}
}
}
无需检查其中一种解决方案在 list 中是否包含超过1个元组。单个元组列表也是有效的解决方案，因此也应将其包括在报告中。
以这种方式，您还解决了通过具有三重表示的解决方案引起的不一致性。
@dmitry的答案是一个很好的第一步，但缺少几个方案。@pau提到了一个方案，其中a == b-即使在迭代期间只能计算一次。
另外，第二个循环需要将变量b重置为1，而不是a。否则，您将不会捕获（1,2）=（2,1）的组合。
更新：您可以将第二个循环按原样保留，并确保自动包含（a，b）的倒数。因此，从本质上讲，由于它的倒对对（b，a），每个（a，b）对应自动包括在内。
我在python上制作的，它的打印解决方案比以前的解决方案更亮，如果可以进一步优化，我会添加一些注释来帮助解释
找到1,000至A3 B3 = C3 D3以下的所有正整数解决方案（A B）（A2-AB B2）=（C D）（C2-CD D2）;
enter code here
#find all positive integer solutions under 1,000 to a3 + b3 = c3 + d3
# (a+b)(a2-ab+b2) = (c+d)(c2-cd+d2);
n = 1000
dict1={}
solution = []
solution_visual =[]
k=0
#cycle for finding the cube sums of pairs c and d
for c in range(n):
for d in range(n):
result = (c**3) + (d**3)
if result not in dict1:
dict1[result] =(c,d)
else:
list = dict1[result]
#check that the numbers of the quadruplet are unique
if (list[0]!=list[1] and list[0]!=c and list[0]!=d and list[1]!=c
and list[1]!=d and c!=d):
tuple1 = (list[0],list[1],c,d)
#check that the two pairs are unique (we exclude the same number with different order)
srtd_tp=sorted(tuple1)
srtd_tp = tuple(srtd_tp)
#add to the final list only if they are not there before
if srtd_tp not in solution:
solution.append(srtd_tp)
solution_visual.append(tuple1) #we visualize them in the correct
order.
k+=1 #keep the count of the solutions
#sorting the solutions to better visualize
solution.sort()
solution_visual.sort()
#print the solutions quadruplets
for tuple in solution_visual:
print(tuple)