众所周知,任何正数最多只能用三个三角形数来表示https://oeis.org/a000217 )
例子: 11 := 10 + 1
12 := 10 + 1 + 1 13 := 10 + 3
14 := 10 + 3 + 1 15 := 15
我正在搜索正数的表示 n
最多通过3个可能的三角形和。可以存在多个 n
. 我对最棒的那个感兴趣。
有没有比2减1增循环更有效的方法来求和呢?
public void printMaxTriangularNumbers(int n){
int[] tri = createTriangularNumbers(1000);
lbl: for(int i = tri.length-1; ; i--){
int tmp = n - tri[i];
if(tmp == 0){
System.out.println(tri[i]);
break;
}
for(int j=i; j>0; j--){
int tmp2 = tmp - tri[j];
if(tmp2 ==0){
System.out.println(tri[i]);
System.out.println(tri[j]);
break lbl;
}
for(int k=1; k <= j;k++){
if(tmp2 - tri[k] == 0){
System.out.println(tri[i]);
System.out.println(tri[j]);
System.out.println(tri[k]);
break lbl;
}
}
}
}
}
public int[] createTriangularNumbers(int n){
int[] out = new int[n+1];
for(int i=1,sum=0; i<=n;i++){
out[i] = sum += i;
}
return out;
}
2条答案
按热度按时间5gfr0r5j1#
据我所知,没有直接的公式。需要一个算法。例如,贪婪的方法不起作用。以值90为例:
不大于90的最大三角形数是78。仍然是12
不大于12的最大三角形数是10。剩余2
现在很明显,我们需要4个条件,这是不可接受的。
所以我会提出一个递归/回溯算法,其中每个递归调用只处理一个求和。递归中的每一级首先取尽可能高的三角形数,但是如果递归调用失败,它将取第二大的三角形数,然后再次进入递归,直到有一个可接受的和为止。
我们可以使用math.stackexchange.com上提到的公式:
设tm是小于或等于c的最大三角形数。实际上可以得到m的显式公式,即:
下面是一个实现递归的代码段。在运行它时,可以引入一个值,并为它生成三角形求和。
9rbhqvlz2#
因为三角数是任意数
t
满足t=x(x+1)/2
对于任何自然数x
,你要的是解决n = a(a+1)/2 + b(b+1)/2 + c(c+1)/2
找到解决办法(a,b,c)
尽可能地max(a,b,c)
. 您没有指定只允许3个三角形数的解,所以我假设您也允许这种形式的解(a,b,c,d)
找一个最好的max(a,b,c,d)
.可能有多个解决方案,但一个最多有3个三角形数字总是存在的。因为可以用3个三角形数构成任意数,所以可以找到最大的三角形数
t
与t<=n
,然后它就会随之而来n=t+d
,在哪里d=n-t
.d
是一个大于等于0的自然数,因此可以由3个三角形数组成。既然你对最大的summand感兴趣,那么最大的summand就是t
,可以用t=x(x+1)/2
哪里x=floor((sqrt(1+8n)-1)/2)
(通过求解公式得出)n=x(x+1)/2+d
).举一个实际例子
n=218
. 通过这个公式,我们得到x=20
以及t=210
,这确实是218之前最大的三角形数。在本例中,其他三角形数字6
,1
,1
因为计算8的唯一方法就是用这些。