1

这里的问题是仅使用 FOR 循环来获得幂的总和 (m^0 + m^1 + m^2 + m^3.... + m^n)。意思是，不使用任何其他循环以及 Math.pow();

甚至可能吗？到目前为止，我只能解决获得 m^n 的问题，但不能解决其他问题。

    public static void main(String[] args){
    Scanner scn = new Scanner(System.in);
    int total  = 1;

    System.out.print("Enter value of m: ");
    int m = scn.nextInt(); 
    System.out.print("Enter value of n: ");
    int n = scn.nextInt();

        for (int i = 1; i <= n; i++){   
        total * m;
        }
    System.out.print(total);
}

假设 m =8; n = 4;

我给了我'1,2,3,4'，这是我需要的，但我无法为 m ^ i 供电。

如果有人可以指导我如何完成它会很好，因为我对 Java 的了解有限，似乎无法继续前进。

提前致谢！

4

7 回答 7

6

您可能想像这样重写它：

m^0 + m^1 + m^2 + m^3.... + m^n = 1 + m * (1 + m * (1 + m * (.... ) ) )

你在一个 for 循环中完成它。

这应该可以完成工作（请参阅评论中的解释）：

public long count(long m, int pow) {
  long result = 1;
  for(int i = 0;i<pow; i++) {
    result*=m +1;
  }
  return result;
}
于 2013-09-06T13:29:08.180 回答
4

您可以嵌套循环。用一个来计算幂，另一个来求和。

于 2013-09-06T13:26:55.727 回答
2

您可以执行以下操作：

int mul = 1;
total = 1;
for(int i=1;i<=n;i++) {
    mul *= m;
    total += mul;
}
System.out.println(total);
于 2013-09-06T13:39:58.133 回答
1

您还可以使用几何级数的公式：

Sum[i = k..k+n](a^i) = (a^k - a^(k+n+1)) / (1 - a)
                     = a^k * (1 - a^(n+1)) / (1 - a)

有了这个，实现可以在一个for循环（或 2 个简单for循环）中完成：或者使用 O(n) 简单循环，或者使用 O(log n)通过平方取幂。

但是，缺点是数据类型必须至少能够容纳(1 - a^(n+1))，而通常求和只需要结果适合数据类型。

于 2013-09-06T13:42:37.787 回答
1

您可以使用 O(N) 的单个循环而不是 O(N^2) 的嵌套循环

long total = 1, power = m
for (int i = 1; i <= n; i++){   
    total += power;
    power *= m;
}
System.out.print(total);
于 2013-09-06T13:42:48.703 回答
0

这是解决方案：

for(int i=0;i<n;i++){
temp=1;
for(int j=0;j<=i;j++){
    temp *= m;
}
total += temp;
}
System.out.println(total+1);
于 2013-09-06T13:30:59.827 回答
0

您可以使用自己的pow函数轻松计算幂，例如：

private static long power(int a, int b) {
    if (b < 0) {
        throw new UnsupportedOperationException("Negative powers not supported.");
    }
    if (b == 0) {
        return 1;
    }
    if (b == 1) {
        return a;
    }
    return a * power(a, b - 1);
}

然后简单地遍历所有值并将它们相加：

long out = 0;
for (int i = 0; i <= n; ++i) {
    out += power(m, i);
}
System.out.println(out);

m^n我要补充一点，这是一个经典的动态规划问题m * m^(n-1)。因此，我会添加先前计算的幂的缓存，这样您就不必重新计算。

private static Map<Integer, Long> powers;

public static void main(String args[]) {
    int m = 4;
    int n = 4;
    powers = new HashMap<>();
    long out = 0;
    for (int i = 0; i <= n; ++i) {
        out += power(m, i);
    }
    System.out.println(out);
    System.out.println(powers);
}

private static long power(int a, int b) {
    if (b < 0) {
        throw new UnsupportedOperationException("Negative powers not supported.");
    }
    if (b == 0) {
        return 1;
    }
    if (b == 1) {
        return a;
    }
    Long power = powers.get(b);
    if (power == null) {
        power = a * power(a, b - 1);
        powers.put(b, power);
    }
    return power;
}

这会缓存计算的值，以便您每次只计算下一个倍数。

于 2013-09-06T13:39:17.457 回答