paint-brush
日常编码问题:三角数和大除数经过@nicolam94
1,155 讀數
1,155 讀數

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

经过 Nicola Moro8m2023/07/13
Read on Terminal Reader

太長; 讀書

三角数是数字的一个特定子集,由直到某一特定数的所有自然数之和形成。它们被称为三角形,因为**您始终可以将它们排列为三角形。前七个三角形数的前十项为:1,3,6,10,15,21,28,36,45,55,…。数字 28 是第一个因数超过 5 的三角形数。
featured image - 日常编码问题:三角数和大除数
Nicola Moro HackerNoon profile picture

欢迎大家回来,还有另一个问题需要解决!今天,我们将讨论三角数及其约数:尤其是大三角数!


虽然我们可以欣赏我对自然界中三角形数字的精彩艺术表现,但让我们先声明一下我们通常的免责声明:


  1. 这个问题由精彩网站提供欧拉计划.net ,您可以订阅这里!有 800 多个数学和编码问题需要解决,并且有大量关于这些问题的讨论档案。它确实是一个让你绞尽脑汁学习新东西的完美工具!去看看并尝试解决你的挑战!


  2. 我不是一个专业的程序员:只是一个喜欢写这类东西并喜欢分享他的镜头的人。我确信这不是最佳解决方案,因此,如果您有更好的解决方案或任何有关如何优化它的想法,我们非常欢迎您分享!


废话说得够多了,让我们看看今天的问题是什么:


三角形数序列是通过自然数相加生成的。所以第 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 的除数(或因子)的定义非常简单:它是一个数字j ,可以乘以另一个整数k再次给出n例如,3是18的约数,因为我们可以将3和6相乘再次得到18。


然而,5 不是 18 的约数,因为没有数字k与 5 相乘得出 18。


通过定义,我们还得到一个重要的性质:如果jn的约数,因为它可以乘以k得到n,那么k也是n的约数,因为它可以乘以j得到n。


这样我们就可以确定数字n总是至少有两个约数jk (事实上, j可以总是 1 并且k可以是n )。


另外,换句话说,如果n / j的余数等于 0 ,则数字j是数字n的除数。例如,18/3 = 6,余数为 0。


我们可以用模算术更好地形式化这个概念,即如果n % j = 0,则jn的除数。换句话说,我们获得第二个属性:


我们感兴趣的第三个也是最后一个性质是,不存在大于 n/2 的数字n的约数而不是n本身。这很容易理解。从第一个属性,我们知道因子在 1,…,n 范围内以某种方式“链接”在一起。


这是因为,如果j \ n,那是因为j * k = n。因此,也k\n。让我们再次以 18 为例,找到它的除数,并给它们着色以反映这个属性。


因此,举例来说,如果j = 3,k = 6,反之亦然,如果j = 6,k = 3,这意味着除了 1 之外,我们可以使用的最小j是 2,这给了我们最大的k可能, n/2 (在我们的例子中为 9) 这有效:


  • 对于偶数,在这种情况下最大的因子将恰好等于n 的一半;


  • 对于奇数:如果我们不能将n除以 2(因为奇数会给我们一个有理数);这意味着我们只能使用j > 2,这将始终给我们结果k < n/2。


最后,只有一种情况jk可以相等:当n是平方数时。例如,当n = 36 时,一个可能的因子j = 6将产生另一个因子k = 6。稍后我们将在代码部分中详细讨论这种情况。


当然,这些概念非常琐碎,但它们在我们的解决方案中非常重要!


代码

代码将用Go编写,因为它确实是一种快速语言,但仍然保持很高的可读性。我们将解决方案分为两部分:首先,我们将创建一个函数来查找数字的除数,然后将其应用于三角形数字


我们先看一下这个函数:

我们创建接受整数n并返回整数数组out的函数,其中将包含我们的除数。之后,我们out一些琐碎的因子,即 1 和n本身。


然后我们开始从 2 到n/2循环j (从第二个属性开始;还要注意,我们对n/2本身不感兴趣,因为如果n是偶数, k = n/2将被j = 2添加到除数中) j = 2次迭代:这就是为什么我们停在j<n/2而不是j≤ n/2 )。


这样,我们只能在n的前半部分检查除数,从而大大加快了过程。


在每个循环中,我们检查 3 件事:

  • 第三个 if 语句实际上检查是否n%j==0 ,换句话说,是否 0 ≠ n (mod j)。如果是这样,我们找到一个因素,并将j添加到列表中。我们还可以通过计算n/j然后移动到下一个j将其对应项k添加到列表中;


  • 第二个 if 语句检查n是否为平方,因此jn的根。如果是,则仅将一个除数j添加到out中,以避免重复,然后算法继续。


    假设n = 36 :如果这个小块丢失,第三个 if 语句将被触发,导致out接收j = 6k = n/j = 36/6 = 6 ,从而创建一个副本。


  • 第一个 if 语句是最复杂的:它的目的是检查我们是否开始出现重复的jk对。如果是这样,我们可以立即中断循环,因为我们的因子都已经存在于out中。


具体来说,关于第三点,有两种情况需要检查:是否out[len(out)-1] == jout[len(out)-2] == j


第一种情况是经典的:以数字 T₇ = 28 为例:

j = 7时,它将等于最后插入的值。因此,我们可以打破循环。


第二种情况仅在我们找到平方n时发生。再以36为例:

j = 9时,它将等于n的平方根之前附加的最后一个值,该值仅出现一次。因此,此时我们可以打破循环。


最后,我们可以简单地return out得到我们的除数。


应用结果

现在我们有了函数,我们可以将它应用于每个三角形数。我们将创建一个计数器c ,它将用作三角数的生成器。我们用高斯方程计算相关的三角数tn并检查它有多少个除数。


如果超过 500,我们将返回该tn作为结果。

但是……有一个问题!


ProjectEuler.net 确实是一个可爱的项目:除了呈现数学谜语和问题之外,他们的主要重点是提供一个开始学习、思考和推理数学的工具


我喜欢这一点:他们如此坚定,以至于实际上禁止发布针对他们的问题的结果和指南(这是前 100 个问题之一,所以我知道这是允许的)。


鉴于此,我认为仅仅给出复制粘贴的解决方案并获得成就是不公平的。出于这个原因,我不会给你实际的解决方案:你自己尝试一下,并尝试想出一个比我的算法更好的算法(有很多算法)。对不起大家! 😅


时间复杂度

我相信有很多更好的解决方案,因为我觉得这个镜头非常糟糕!

FindDivisor函数以线性时间运行:因为它取决于实例n的大小,并且它最多运行n/2个循环;我们可以将其视为 O(n)。


然而,我们必须先计算每个三角数,这也需要 O(tn) 时间,其中 tn 是结果(我们实际计算的最后一个)。鉴于此,整个算法的时间复杂度大约应为 O(tn*n)。


由于tn成为参数或我们的函数,并且我们在其中最多运行n/2个循环,因此我们可以将时间复杂度重写为 O(tn*tn/2) = O(tn²/2) = O(tn²)。不幸的是,这是一个二次时间解


但令我惊讶的是,即使该算法具有这种复杂性,它的运行速度仍然相当快。为了在我的机器(AMD Ryzen 5,平均频率 2700 MHz)上给出结果,需要 322.564227 毫秒。


不过,尝试找到第一个超过 1000 因数的三角数花费了 3.827144472 秒,因此可以清楚地看到时间消耗正在迅速增加。


结论

我们终于成功了!我希望你们喜欢这篇文章,也希望你们能从中得到一些有趣的东西:如果是这样,请拍一两下,并与可能对这个主题感兴趣的人分享这篇文章!


再次对 ProjectEuler 的出色工作表示大力赞扬:我真的想建议你去看看他们能提供什么;我相信你会发现它超级有趣!


一如既往,感谢您的阅读。


尼古拉