通过在递归方法中将 N/2 与 N/2 加到 N 来计算 1 到 N 的总和

Question

我在制作计算 1,2,3 与 N 之和的递归方法时遇到问题，但是通过将 (1,2,3... 到 N/2) 与 (N/2+1...到N).

目前我管理的代码是这样的：

public static void main(String[] args) {

    System.out.println(sum(10, 1));
}

public static int sum(int n, int start) {

    if (start == n){
        return n;
    }

    if (start > n / 2){
        return start + sum(n, start + 1);
    }

    return start + sum(n, start + 1);

}

我认为这是错误的，这是学校的一项作业，我们必须激发将递归分解成多个部分是 more/lesser 计算总和的有效方法。（从 1 到 N/2 加上 N/2 到 N，而不是直接从 1 到 N）。

他让我们这样做是为了让我们更难，但我根本无法理解如何做到这一点。这是正确的吗？

谢谢

Answer 1

在某些情况下可能有助于减少递归深度。

计算内部步数 n/2 时需要考虑开始，代码可能类似于：

public static int sum(int n, int start) {
  if (start > n) {
    return 0;
  }

  if (start == n){
      return n;
  }

  int n2 = (start + n) / 2;
  return sum(n2, start) + sum(n, n2 + 1);
}

start > n 检查只是避免在 start 和 n 相差小于 2 的情况下在末尾进行额外检查。

Answer 2

检查您是否将 n 声明为 int。 n/2并不总是会给你期望的价值。我认为这就是你的老师希望你遵守的把戏。

Answer 3

我相信，这段代码越简单越好，你可以在一个循环中检查性能。我看不出复杂性有什么不同。

class Sums {

    public static int sumHelp(int n, int start){
        if (n == start) return;
        else return (n + sumHelp(n - 1, start));
    }

    public static int sumByHalf(int n){
        return sumHelp(n/2, 0) + sumHelp(n, n/2);
    }

    public static int sum(int n){
        return sumHelp(n, 0);
    }

    public static void main(String[] args) {
        System.out.println(sumByHalf(100));
        System.out.println(sum(100));
    }
}

通过在递归方法中将 N/2 与 N/2 加到 N 来计算 1 到 N 的总和

Calculating sum 1 to N by adding 1 to N/2 with N/2 to N in a recursive method

java

algorithm

recursion

addition