时间戳

首页 > 解决方案 > Cracking The Coding Interview - 打印方程的所有正整数解

algorithm - Cracking The Coding Interview - 打印方程的所有正整数解

问题描述

在《Cracking The Coding Interview》一书中

有一个例子：

打印方程的所有正整数解

a^3 + b^3 = c^3 + d^3

其中a, b,c和是和d之间的整数。11000

图片

在书中它说“只有一个人可以工作”，但我不明白。

正如我所看到的，只要所有这些变量都相等，它就会起作用

例子：

a = 1, b = 1, c = 1, d = 1
a = 2, b = 2, c = 2, d = 2
a = 3, b = 3, c = 3, d = 3

标签： algorithm

解决方案

作为一种猜测（问题是什么？），让我展示如何解决这些问题（以便在采访中展示）；你说得很对，有很多明显的解决方案，比如

  1**3 + 1**3 = 1**3 + 1**3
  1**3 + 2**3 = 2**3 + 1**3

我们所要做的就是设置a = candb = d或a = dand b = c。像下面这样的非平凡解决方案呢？

   1**3 +  12**3 =   9**3 +  10**3
  84**3 + 280**3 = 217**3 + 231**3

请注意，我们可以交换 aandb或 / and cand d，并有一个衍生解决方案，如

  12**3 + 1**3 = 10**3 + 9**3

排除它们让我们假设a <= b,c <= d和a < c

带有嵌套循环的幼稚代码（书中提到）持续时间太长：我们需要1000 * 1000 * 1000 * 1000 = 1e12计算操作。但是，我们可以在中间技术中使用 meet 并在几分之一秒内得到结果（删除了两个最里面的循环）：

  1. 计算所有a**3 + b**3值（仅1000 * 1000 = 1e6操作 - 上限）
  2. 将它们分组
  3. 过滤掉感兴趣的组

C#代码：

  Dictionary<long, List<(long, long)>> cubes = new Dictionary<long, List<(long, long)>>();

  for (long a = 1; a < 1000; ++a) {
    long a3 = a * a * a;

    for (long b = a; b < 1000; ++b) {
      long key = b * b * b + a3;

      if (cubes.TryGetValue(key, out var list))
        list.Add((a, b));
      else
        cubes.Add(key, new List<(long, long)>() { (a, b) });
    }
  }

现在我们已经cubes是这样了

  {2, {(1, 1)}} // group with one (a, b) pair
  {9, {(1, 2)}} // another group with one (a, b) pair
   ...
  {1729, {(1, 12), (9, 10)}} // <- the group we are looking for!
   ...

查询组的时间：

var report = string.Join(Environment.NewLine, cubes
  .Where(pair => pair.Value.Count >= 2)
  .Select(pair => $"{string.Join(" = ", pair.Value.Select(t => $"{t.Item1}**3 + {t.Item2}**3"))}"));

Console.Write(report);

结果：

1**3 + 12**3 = 9**3 + 10**3
1**3 + 103**3 = 64**3 + 94**3
1**3 + 150**3 = 73**3 + 144**3
1**3 + 249**3 = 135**3 + 235**3
... 
22**3 + 986**3 = 180**3 + 984**3 = 692**3 + 856**3
...
802**3 + 987**3 = 883**3 + 924**3

推荐阅读