找到最大匹配的 3 个三角数

Question

众所周知，任何正数最多可以用3个三角数表示。 ( https://oeis.org/A000217)

示例：

11 := 10 + 1

12 := 10 + 1 + 1

13 := 10 + 3

14 := 10 + 3 + 1

15 := 15

我正在通过最多 3 个可能的三角加数搜索正数 n 的表示。 n 可以存在不止一种表示。我对加数最大的感兴趣。

是否有比 2 递减 for 和 1 递增 for 循环更有效的方法来找到被加数？

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;
}

Answer 1

因为三角数是任意数t满足任意自然数t=x(x+1)/2x，所以你要的是求解

n = a(a+1)/2 + b(b+1)/2 + c(c+1)/2

并找到具有最大可能 max(a,b,c) 的解决方案 (a,b,c)。您没有指定您只允许具有 3 个三角数的解决方案，因此我假设您也允许 (a,b,c,d) 形式的解决方案并寻找具有最大 max(a,b,c,d).

的解决方案

可能有多种解法，但总是存在至多3个三角数的解法。因为可以用3个三角数组成任何数，所以你可以用t<=n找到最大的三角数t，然后它会跟着n=t+d，其中d=n-t。 d是一个>=0的自然数，因此可以由3个三角数本身组成。由于您对最大的被加数感兴趣，因此最大的将是 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 的唯一方法是那些。

Answer 2

据我所知，没有直接的公式。需要一个算法。例如，贪婪的方法是行不通的。以值 90 为例：

不大于90的最大三角数为78，仍为12
不大于12的最大三角数为10，余数为2
现在很明显我们需要 4 个术语，这是不可接受的。

所以我会提出一个 recursive/backtracking 算法，其中每个递归调用只处理一个被加数。递归中每一层取最大的三角数，如果递归调用失败，则取第二大的三角数，再次递归，直到有可接受的和。

我们可以使用maths.stackexchange.com中提到的公式：

Let T_m be the largest triangular number less than or equal to c. You can actually get an explicit formula for m, namely:

这是实现递归的片段。当运行它时，你可以引入一个值，它会产生三角加数。

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>

找到最大匹配的 3 个三角数

Find max matching 3 Triangular numbers

java

algorithm

math

numbers

triangular