代码之家 › 专栏 › 技术社区 › Will Da Silva Alex Martelli

如何确定具有s边的多边形的数字是否为多边形

number-theory language-agnostic algorithm

Will Da Silva Alex Martelli · 技术社区 · 7 年前

多边形数定义为以正多边形形状排列的点表示的数。

三角形数是0、1、3、6、10、15、21、28、36、45。。。

五边形数是0,1,5,12,22,35,51,70,92,117。。。

等等

有一些众所周知的公式可以计算这些数字中的任何一个。为了计算第n个s-角数,可以使用公式(n^2*(s-2)-(n*(s-4))/2

我想知道的是,有没有一种有效的方法来检查给定的数字对于给定的s是否是s-角的?

显而易见的方法是从生成s-角数的函数中取连续值,直到找到n或值超过n,但这具有线性时间复杂度。

我知道有一些公式可以用来确定一个数字对于s的特定值是否是s-角的,但我想要一个适用于任何s的公式。

1 回复 | 直到 7 年前

mjkaufer 5 年前

Wikipedia's article on Polygonal numbers 我可以想出以下谓词来解决OP提出的问题:

def isPolygonal(s, x):
    ''' Check if x is a s-gonal number '''
    assert s > 2 and s % 1 == 0 and x % 1 == 0
    # Determine if x is some nth s-gonal number,
    # fail if n doesn't come out a whole number
    n = (sqrt(8 * (s - 2) * x + (s - 4) ** 2) + (s - 4)) / (2 * (s - 2))
    return n % 1 == 0

推荐文章

John V · 是否存在单元测试无法发现的逻辑/流错误类型?

6 年前

Beefster · 为什么ANSI颜色转义以“m”而不是“]”结尾?

6 年前

Guillermo Gutiérrez · STR转换是如何工作的?

7 年前

RudziankoÅ · 合并排序数组算法

7 年前

user8852560 · 构造函数中的验证和构造函数冲突

7 年前

SuperHeroY · 在大于8x8的棋盘上进行象棋移动验证?[已关闭]

7 年前

jav974 · 订购产品时寻找最佳价格组合的算法

7 年前

hippietrail · 确定浮点数中前导零的数量

7 年前

Will Da Silva Alex Martelli · 如何确定具有s边的多边形的数字是否为多边形

7 年前

LaoJiu · 为什么在文本编辑器的查找函数中选择“BM算法”而不是“周日算法”?

7 年前