java - 通过连续自然数的加法或减法获得一个数

Question

我正在尝试编写一个函数，使用它可以以最少的步骤获得任何自然数。我可以从 1 开始添加或减去自然数。条件是：

1. 一个号码只使用一次

2. 您只能执行加法和减法。

3. 不允许转义任何数字

4. 找到具有最大值的整数的值以获得该数字。

例如：如果我想要的数字是 4 ，那么它会以 -1+2+ 3的形式获得，这里的答案是 3。以类似的方式，如果我想要 6 那么 1+2+ 3这里的答案是 3。对于10 = 1+2+3+ 4答案是4。
到目前为止我所拥有的：

到目前为止我所拥有的：

public void step() { 
    int n = (int)Math.sqrt(position * 2); 
    k = (position - (((n + 1) * n) / 2)); 
    l = ((((n + 1) * (n + 2)) / 2) - position); 
    System.out.println(k + " " + l); 
    System.out.println(n); 
    p = (l > k ? k : l); 
    r = (l > k ? n : n + 1); 
    System.out.println(p + " " + r); 
    if (k == 0) { 
        result = n; 
    } else { 
        result = r + (2 * p); 
    } System.out.println("__________" + result + "__________"); 
}

Answer 1

好的，让我们以这种方式进行。考虑跟随binary tree。现在您可以从每条路径中找到总和并使用sum=your number(let's say 4). 现在您可以从中获得最大值。尝试提出实现这一点。如果你尝试一些事情，我可以进一步帮助你。

      0
     /  \
    -1   1
   /  \  / \
  -2  2 -2  2

Answer 2

解决方案是：

for n=1: = 1
for n=2: = 1+2 => 1+2+3 => 1-2+3 
for n=3: = 1+2
for n=4: = 1+2+3 => -1+2+3
for n=5: = 1+2+3 => 1+2+3+4-5
for n=6: = 1+2+3
for n=7: = 1+2+3+4=>1+2+3+4+5=>1+2+3-4+5
for any n, first calculate the S(k)=1+2+3+...+k

其中 S(k)>n 且 x=S(k)-n 是偶数。然后将 x/2 的 + 翻转为 -。

S(k) = (1+k)*k/2 > n
=> k*k + k -2n > 0
=> k > (-1 + sqrt(1+8n))/2

例如，n=7, k > 3.2, 那么 k=4, S(4) = 10, 10-7=3, 奇数, 所以 k=5, S(5)=15, x=15-7=8 , 8/2=4，翻转 4 的符号，我们得到 1+2+3-4+5 = 7

在某些情况下，Sk-n 是奇数，但 S(k+1)-n 也是奇数，在这种情况下，我们需要使用 S(k+2)。代码如下：

public void step() {
        k = (int)Math.ceil(((-1 + Math.sqrt(1 + 8 * n)) / 2));
        int Sk = (1 + k) * k / 2;
        if ((Sk - n) % 2 != 0) {
            k++;
            Sk = (1 + k) * k / 2;
            if ((Sk - n) % 2 != 0) {
                k++;
                Sk = (1 + k) * k / 2;
            }
        }
        int i = (Sk - n) / 2;
        System.out.println("maximum number is : " + k + "the number with -ve sign is : " + i);
    }