欢迎大家回来，还有另一个问题需要解决！今天，我们将讨论三角数及其约数：尤其是大三角数！ 虽然我们可以欣赏我对自然界中三角形数字的精彩艺术表现，但让我们先声明一下我们通常的免责声明： 这个问题由精彩网站提供  ，您可以订阅 ！有 800 多个数学和编码问题需要解决，并且有大量关于这些问题的讨论档案。它确实是一个让你绞尽脑汁学习新东西的完美工具！去看看并尝试解决你的挑战！ 欧拉计划.net 这里 我不是一个专业的程序员：只是一个喜欢写这类东西并喜欢分享他的镜头的人。我确信这不是最佳解决方案，因此，如果您有更好的解决方案或任何有关如何优化它的想法，我们非常欢迎您分享！ 废话说得够多了，让我们看看今天的问题是什么： 三角形数序列是通过自然数相加生成的。所以第 7 个三角形数是 1+2+3+4+5+6+7=28。前十项为：1,3,6,10,15,21,28,36,45,55,...   让我们列出前七个三角形数的因数： 我们可以看到 28 是第一个拥有超过 5 个约数的三角形数。 第一个因数超过五百的三角形数的值是多少？ 问题非常简单：我们被要求了解第一个具有超过 500 个 是什么。首先，让我们更好地了解什么是三角数以及什么是除数。 除数的 三角数 三角形数字 三角数是数字的一个特定子集，由直到某一特定数的所有自然数之和形成。它们被称为三角形，因为 。这里有些例子：  您总是可以将它们排列成三角形 在上图中，它是第三个、第四个和第五个三角形数字。因此，例如，第三个数字的形式为 1+2+3 = 6，第四个数字的形式为 1+2+3+4 = 10，依此类推。一般来说，nᵗʰ 三角数 Tₙ 等于 当然，这是数学中最著名的级数之一，也是由 提出的，他指出连续整数的总和等于： 高斯 所以基本上，例如，如果我们想计算第三个三角形数，我们只需计算 3*4/2 = 6。一旦我们开始编写解决方案，这将非常有帮助！ 除数 要给出数字 n 的 （或 ）的定义 非常简单：它是 例如，3是18的约数，因为我们可以将3和6相乘再次得到18。 除数 因子 ， 一个数字  ，可以乘以另一个整数 再次给出  。 j k n 然而，5 不是 18 的约数，因为没有数字 与 5 相乘得出 18。 k 通过定义，我们还得到一个重要的性质：如果 是 的约数，因为它可以乘以 得到 那么 也是 的约数，因为它可以乘以 得到 j n k n， k n j n。  （事实上，  可以总是 1 并且 可以是  ）。 这样我们就可以确定数字 总是至少有两个约数 和 n j k j k n 另外，换句话说， 。例如，18/3 = 6，余数为 0。 如果 的余数等于 0 ，则数字 是数字 的除数 n / j j n 我们可以用 更好地形式化这个概念，即如果 是 的除数。换句话说，我们获得第二个属性：  模算术 n % j = 0，则 j n 我们感兴趣的第三个也是最后一个性质是， 这很容易理解。从第一个属性，我们知道因子在 1,…,n 范围内以某种方式“链接”在一起。 不存在大于 n/2 的数字 的约数 而不是 本身。 n ， n 这是因为，如果 那是因为 因此，也 让我们再次以 18 为例，找到它的除数，并给它们着色以反映这个属性。  j \ n， j * k = n。 k\n。 因此，举例来说，如果 反之亦然，如果 这意味着除了 1 之外，我们可以使用的最小 是 2，这给了我们最大的 可能，   （在我们的例子中为 9）  这有效： j = 3，k = 6， j = 6，k = 3， j k n/2 。 对于偶数，在这种情况下最大的因子将恰好等于 n 的一半； 对于奇数：如果我们不能将 除以 2（因为奇数会给我们一个有理数）；这意味着我们只能使用 这将始终给我们结果 n j > 2， k < n/2。 最后， 例如，当 一个可能的因子 将产生另一个因子 稍后我们将在代码部分中详细讨论这种情况。 只有一种情况 和 可以相等：当 是平方数时。 j k n n = 36 时， j = 6 k = 6。 当然，这些概念非常琐碎，但它们在我们的解决方案中非常重要！ 代码 代码将用 编写，因为它确实是一种快速语言，但仍然保持很高的可读性。我们将解决方案分为两部分：首先，我们将创建 。 Go 一个函数来查找数字的除数，然后将其应用于三角形数字 我们先看一下这个函数：   https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true 我们创建接受整数 并返回整数数组 的函数，其中将包含我们的除数。之后，我们 一些琐碎的因子，即 1 和 本身。 n out out n 然后我们开始从 2 到 循环  （从第二个属性开始；还要注意，我们对 本身不感兴趣，因为如果 是偶数，  将被 添加到除数中）  次迭代：这就是为什么我们停在 而不是  ）。 n/2 j n/2 n k = n/2 j = 2 j = 2 j<n/2 j≤ n/2 这样，我们只能在 的前半部分检查除数，从而大大加快了过程。 n 在每个循环中，我们检查 3 件事： 第三个 if 语句实际上检查是否  ，换句话说，是否 0 ≠ n (mod j)。如果是这样，我们找到一个因素，并将 添加到列表中。我们还可以通过计算 然后移动到下一个 将其对应项 添加到列表中； n%j==0 j n/j j k 第二个 if 语句检查 是否为平方，因此 是 的根。如果是，则仅将一个除数 添加到 中，以避免重复，然后算法继续。 n j n j out 假设  ：如果这个小块丢失，第三个 if 语句将被触发，导致 接收 和  ，从而创建一个副本。 n = 36 out j = 6 k = n/j = 36/6 = 6 第一个 if 语句是最复杂的：它的目的是检查我们是否开始出现重复的 对。如果是这样，我们可以立即中断循环，因为我们的因子都已经存在于 中。 jk out 具体来说，关于第三点，有两种情况需要检查：是否 或  。 out[len(out)-1] == j out[len(out)-2] == j 第一种情况是经典的：以数字 T₇ = 28 为例： 当 时，它将等于最后插入的值。因此，我们可以打破循环。 j = 7 第二种情况仅在我们找到平方 时发生。再以36为例： n 当 时，它将等于 的平方根之前附加的最后一个值，该值仅出现一次。因此，此时我们可以打破循环。 j = 9 n 最后，我们可以简单地 得到我们的除数。 return out 应用结果 现在我们有了函数，我们可以将它应用于每个三角形数。我们将创建一个计数器  ，它将用作三角数的生成器。我们用高斯方程计算相关的三角数 并检查它有多少个除数。 c tn 如果超过 500，我们将返回该 作为结果。 tn   https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go 但是……有一个问题！   除了呈现数学谜语和问题之外， 。 ProjectEuler.net 确实是一个可爱的项目： 他们的主要重点是提供一个开始学习、思考和推理数学的工具 我喜欢这一点：他们如此坚定，以至于实际上禁止发布针对他们的问题的结果和指南（这是前 100 个问题之一，所以我知道这是允许的）。 鉴于此， 。出于这个原因，我不会给你实际的解决方案：你自己尝试一下，并尝试想出一个比我的算法更好的算法（有很多算法）。对不起大家！ 😅 我认为仅仅给出复制粘贴的解决方案并获得成就是不公平的 时间复杂度 我相信有很多更好的解决方案，因为我觉得这个镜头非常糟糕！   函数以线性时间运行：因为它取决于实例 的大小，并且它最多运行 个循环；我们可以将其视为 O(n)。 FindDivisor n n/2 然而，我们必须先计算每个三角数，这也需要 O(tn) 时间，其中 tn 是结果（我们实际计算的最后一个）。鉴于此，整个算法的时间复杂度大约应为 O(tn*n)。 由于 成为参数或我们的函数，并且我们在其中最多运行 个循环，因此我们可以将时间复杂度重写为 O(tn*tn/2) = O(tn²/2) = O(tn²)。不幸的是，这是一个 ！ tn n/2 二次时间解 但令我惊讶的是，即使该算法具有这种复杂性，它的运行速度仍然相当快。为了在我的机器（AMD Ryzen 5，平均频率 2700 MHz）上给出结果，需要 322.564227 毫秒。 不过，尝试找到第一个超过 1000 因数的三角数花费了 3.827144472 秒，因此可以清楚地看到时间消耗正在迅速增加。 结论 我们终于成功了！我希望你们喜欢这篇文章，也希望你们能从中得到一些有趣的东西：如果是这样，请拍一两下，并与可能对这个主题感兴趣的人分享这篇文章！ 再次对 ProjectEuler 的出色工作表示大力赞扬：我真的想建议你去看看他们能提供什么；我相信你会发现它超级有趣！ 一如既往，感谢您的阅读。 尼古拉

Read My Stories

該音頻是用故事的原始語言製作的！

太長; 讀書

Make resilience your competitive advantage

日常编码问题：三角数和大除数

About Author

註釋

標籤

这篇文章刊登在

Related Stories

看不见的层面：为什么用户访谈是不可替代的资产

使用这 18 种开发工具来提高你的工作效率 🚀🔥

如何将您的工作流程提高 10 倍：17 个必备应用程序

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

看不见的层面：为什么用户访谈是不可替代的资产

使用这 18 种开发工具来提高你的工作效率 🚀🔥

如何将您的工作流程提高 10 倍：17 个必备应用程序

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps