寻找最大匹配的3个三角形数

huangapple go评论77阅读模式
英文:

Find max matching 3 Triangular numbers

问题

以下是翻译后的内容:

已知任何正数最多可以表示为不超过3个三角数之和。(链接: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;
}

如果你还有其他问题或需要进一步帮助,请随时提问。

英文:

It's well known that any positive number can be expressed through at most 3 Triangular numbers. (
https://oeis.org/A000217 )

Example:

11 := 10 + 1

12 := 10 + 1 + 1

13 := 10 + 3

14 := 10 + 3 + 1

15 := 15

I am searching the representation of the positive number n through at most 3 possible Triangular summands. There can exist more than one representation of n. I am interested in the one with the greatest summands.

Is there a more effective way than 2 decreasing for and 1 increasing for loops to find the summands?

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&gt;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 &lt;= 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&lt;=n;i++){
    out[i] = sum += i;
  }
  return out;
}

答案1

得分: 2

根据我所看到的情况,没有直接的公式。需要使用算法。例如,贪婪法不起作用。以值 90 为例:

  • 不大于 90 的最大三角数是 78。剩下 12。
  • 不大于 12 的最大三角数是 10。剩下 2。
  • 现在清楚我们需要 4 个数相加,这是不可接受的。

因此,我建议使用递归/回溯算法,其中每个递归调用仅处理一个加数。递归中的每个层级首先采用最大可能的三角数,但如果递归调用失败,它将尝试次大的三角数并再次递归,直到得到可接受的和。

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

T<sub>m</sub> 是不大于 c 的最大三角数。
实际上可以得到 m 的显式公式,即:
寻找最大匹配的3个三角形数

下面是一个实现递归的代码片段。运行它时,您可以输入一个值,然后将为其生成三角形式的加数。

function getTriangularTerms(n, maxTerms) {
    if (maxTerms === 0 && n > 0) return null; // 失败:太多的加数
    if (n == 0) return []; // 好的!返回空数组,可以在其前面添加加数
    // 允许多次尝试,每次都使用较小的三角形加数:
    for (let k = Math.floor((Math.sqrt(1+8*n) - 1) / 2); k >= 1; k--) {
        let term = k * (k+1)/2;
        // 使用递归
        let result = getTriangularTerms(n - term, maxTerms - 1);
        // 如果结果不为空,则匹配成功
        if (result) return [term, ...result]; // 在前面添加加数
    }
}

// 输入/输出处理
let input = document.querySelector("input");
let output = document.querySelector("span");

(input.oninput = function () { // 任何输入变化的事件处理程序
    let n = input.value;
    let terms = getTriangularTerms(n, 3); // 最多允许 3 个加数
    output.textContent = terms.join("+");
})(); // 也在页面加载时执行。
输入数字: <input type="number" value="14"><br>
加数: <span></span>
英文:

As far as I can see, there is no direct formula. An algorithm is needed. For instance, a greedy method does not work. Take for example the value 90:

  • The greatest triangular number not greater than 90 is 78. Remains 12
  • The greatest triangular number not greater than 12 is 10. Remains 2
  • And now it becomes clear we will need 4 terms which is not acceptable.

So I would propose a recursive/backtracking algorithm, where each recursive call deals with one summand only. Each level in the recursion takes first the highest possible triangular number, but if the recursive call fails, it will go for the second largest and dive into recursion again, until there is an acceptable sum.

We can use the formula mentioned at maths.stackexchange.com:

> Let T<sub>m</sub> be the largest triangular number less than or equal to c.
> You can actually get an explicit formula for m, namely:
> 寻找最大匹配的3个三角形数

Here is a snippet that implements the recursion. When running it, you can introduce a value, and the triangular summands will be produced for it.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function getTriangularTerms(n, maxTerms) {
    if (maxTerms === 0 &amp;&amp; n &gt; 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 &gt;= 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(&quot;input&quot;);
let output = document.querySelector(&quot;span&quot;);

(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(&quot;+&quot;);
})(); // execute also at page load.

<!-- language: lang-html -->

Enter number: &lt;input type=&quot;number&quot; value=&quot;14&quot;&gt;&lt;br&gt;
Terms: &lt;span&gt;&lt;/span&gt;

<!-- end snippet -->

答案2

得分: 0

由于三角形数是满足对于任意自然数x,t=x(x+1)/2的任意数字t,你所询问的是要解决以下方程:

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个三角形数构成任何数字,你可以找到不超过n的最大三角形数t,然后有 n=t+d,其中d=n-td 是一个大于等于0的自然数,因此它本身可以由3个三角形数构成。由于你对最大的加数感兴趣,最大的加数将是t,可以用公式 t=x(x+1)/2 计算,其中 x=floor((sqrt(1+8n)-1)/2)(通过解方程 n=x(x+1)/2+d 获得)。

作为一个实际例子,取 n=218。使用这个公式,我们得到 x=20t=210,事实上这是218之前最大的三角形数。在这种情况下,其他的三角形数将是 611,因为计算出8的唯一方法就是使用这些数字。

英文:

Since a triangular number is any number t that satisfies t=x(x+1)/2 for any natural number x, what you're asking is to solve

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

and to find the solution (a,b,c) with greatest possible max(a,b,c). You didn't specify that you only allow solutions with 3 triangular numbers, so I will assume you also allow solutions of the form (a,b,c,d) and look for the one with the greatest max(a,b,c,d).

There might be multiple solutions, but one with at most 3 triangular numbers always exists. Since it's possible to form any number with 3 triangular numbers, you can find the largest triangular number t with t&lt;=n, and then it will follow n=t+d, where d=n-t. d is a natural number >=0 and therefore can be composed by 3 triangular numbers itself. Since you're interested in the largest summand, the largest will be t, which can be computed with t=x(x+1)/2 where x=floor((sqrt(1+8n)-1)/2) (obtained by solving the formula n=x(x+1)/2+d).

As a practical example, take n=218. With the formula, we get x=20 and t=210, which indeed is the largest triangular number before 218. The other triangular numbers, in this case, will be 6, 1, 1 since the only way to compute 8 is with those.

huangapple
  • 本文由 发表于 2020年8月21日 02:08:30
  • 转载请务必保留本文链接:https://go.coder-hub.com/63510921.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定