欢迎大家回来，还有另一个问题需要解决！今天，我们将讨论三角数及其约数：尤其是大三角数！ 虽然我们可以欣赏我对自然界中三角形数字的精彩艺术表现，但让我们先声明一下我们通常的免责声明： 这个问题由精彩网站提供  ，您可以订阅 ！有 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

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

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

About Author

註釋

標籤

这篇文章刊登在

Related Stories

成功云迁移的完整指南：策略和最佳实践

从论坛到信息流：社交媒体算法如何塑造数字互动

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

加密货币增长：创建有效的用户角色

成功云迁移的完整指南：策略和最佳实践

从论坛到信息流：社交媒体算法如何塑造数字互动

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

加密货币增长：创建有效的用户角色

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps