查找最大匹配3个三角形数

z5btuh9x  于 2021-07-08  发布在  Java
关注(0)|答案(2)|浏览(393)

众所周知,任何正数最多只能用三个三角形数来表示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;
}
5gfr0r5j

5gfr0r5j1#

据我所知,没有直接的公式。需要一个算法。例如,贪婪的方法不起作用。以值90为例:
不大于90的最大三角形数是78。仍然是12
不大于12的最大三角形数是10。剩余2
现在很明显,我们需要4个条件,这是不可接受的。
所以我会提出一个递归/回溯算法,其中每个递归调用只处理一个求和。递归中的每一级首先取尽可能高的三角形数,但是如果递归调用失败,它将取第二大的三角形数,然后再次进入递归,直到有一个可接受的和为止。
我们可以使用math.stackexchange.com上提到的公式:
设tm是小于或等于c的最大三角形数。实际上可以得到m的显式公式,即:

下面是一个实现递归的代码段。在运行它时,可以引入一个值,并为它生成三角形求和。

function getTriangularTerms(n, maxTerms) {
    if (maxTerms === 0 && n > 0) return null; // failure: too many terms
    if (n == 0) return []; // Ok! Return empty array to which terms can be prepended
    // Allow several attempts, each time with a
    //   lesser triangular summand:
    for (let k = Math.floor((Math.sqrt(1+8*n) - 1) / 2); k >= 1; k--) {
        let term = k * (k+1)/2;
        // Use recursion
        let result = getTriangularTerms(n - term, maxTerms - 1);
        // If result is not null, we have a match
        if (result) return [term, ...result]; // prepend term
    }
}

// I/O handling
let input = document.querySelector("input");
let output = document.querySelector("span");

(input.oninput = function () { // event handler for any change in the input
    let n = input.value;
    let terms = getTriangularTerms(n, 3); // allow 3 terms max.
    output.textContent = terms.join("+");
})(); // execute also at page load.
Enter number: <input type="number" value="14"><br>
Terms: <span></span>
9rbhqvlz

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个三角形数构成任意数,所以可以找到最大的三角形数 tt<=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的唯一方法就是用这些。

相关问题