仅使用 For 循环的两个整数的幂和

Question

这里的问题是仅使用 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 的了解有限，似乎无法继续前进。

提前感谢！

Answer 1

你可能想像这样重写它：

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

Answer 2

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

Answer 3

您可以在下面执行以下操作：

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

Answer 4

您可以使用 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);

Answer 5

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

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))，而通常求和只需要结果适合数据类型。

Answer 6

这是解决方案：

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

Answer 7

您可以使用

自己的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;
}

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