Java程序循环迭代异常：指定输入无法生成目标迭代结果

问题现象 #

输入6个数字7,5,3,4,8,2时，期望生成4组迭代结果：

• (7,5,3,4,8,2)
• (12,8,7,12,10,2)
• (19,20,17,14,10,2)
• (29,22,17,14,10,2)
  但当前程序仅能正确计算每组结果的首个数字，其余数值均不符合预期。

问题代码 #

package sumas;

import java.util.Scanner;

public class SumaPrefijo {
    private static Scanner input = new Scanner(System.in);

    private static void printArray(int[] array) {
        System.out.print(" [");
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%2d | ", array[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n; // 数组长度
        int[] array; // 待求和数字
        int steps; // 并行加法步骤数
        int PUs; // 处理单元数量

        System.out.print("你想求和多少个数字？ ");
        n = input.nextInt();
        array = new int[n];

        System.out.print("请输入要求和的数值");
        for (int i = 0; i < n; i++) {
            System.out.println("");
            System.out.printf(" 第%d个数字？ = ", (i + 1));
            array[i] = input.nextInt();
        }

        System.out.println("初始数组");
        printArray(array);

        steps = (int) Math.ceil(Math.log(n) / Math.log(2));
        System.out.println(" 步骤数 = " + steps);
        PUs = n / 2;
        System.out.println("处理单元数 = " + PUs);

        for (int j = 0; j < steps; j++) {
            System.out.println("步骤" + (j + 1));
            
            for (int i = 0; i < PUs; i++) { // 遍历所有处理单元
                if (2 * i + (int) Math.pow(2, j) < n) {
                    array[2 * i] = array[2 * i] + array[2 * i + (int) Math.pow(2, j)];
                }
            }
            printArray(array);
        }
        System.out.println(" 求和结果 = " + array[0]);
    }
}

问题根源 #

1. 步长计算风险：使用Math.pow(2,j)做步长计算，存在浮点转换精度误差，且效率低于位运算。
2. 索引逻辑错误：内层循环固定操作2*i位置的元素，不符合并行前缀和的分组计算规则，正确规则应为按步长分组，每组内元素累加前一个步长位置的数值。
3. 处理单元数错误：PUs = n/2的固定值不符合步骤变化的需求，并行前缀和的有效处理元素数量随步长动态变化。
4. 结果输出错误：前缀和的最终结果应为数组最后一个元素，而非第一个元素。

修复后的代码 #

package sumas;

import java.util.Scanner;

public class SumaPrefijo {
    private static Scanner input = new Scanner(System.in);

    private static void printArray(int[] array) {
        System.out.print(" [");
        for (int i = 0; i < array.length; i++) {
            System.out.printf("%2d | ", array[i]);
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int n; // 数组长度
        int[] array; // 待求和数字
        int steps; // 并行加法步骤数

        System.out.print("你想求和多少个数字？ ");
        n = input.nextInt();
        array = new int[n];

        System.out.print("请输入要求和的数值");
        for (int i = 0; i < n; i++) {
            System.out.println("");
            System.out.printf(" 第%d个数字？ = ", (i + 1));
            array[i] = input.nextInt();
        }

        System.out.println("初始数组");
        printArray(array);

        // 计算所需步骤数，向上取整log2(n)
        steps = (int) Math.ceil(Math.log(n) / Math.log(2));
        System.out.println(" 步骤数 = " + steps);

        for (int j = 0; j < steps; j++) {
            System.out.println("步骤" + (j + 1));
            int step = 1 << j; // 当前步长，等价于2^j，用位运算避免浮点误差
            // 遍历需要更新的元素，从step开始，每次递增2*step
            for (int i = step; i < n; i += 2 * step) {
                array[i] = array[i - step] + array[i];
            }
            printArray(array);
        }

        System.out.println(" 求和结果 = " + array[n - 1]);
    }
}

修复说明 #

1. 步长计算改用位运算1 << j，完全替代Math.pow(2,j)，避免浮点精度问题，提升运算效率。
2. 内层循环调整为从step开始，每次递增2*step，符合并行前缀和的分组累加规则：每个元素i累加前一个步长位置i-step的数值。
3. 修正最终结果输出，前缀和的最终结果为数组最后一个元素array[n-1]。
4. 优化printArray方法，补充闭合的]，输出格式更规范。

内容的提问来源于stack exchange，提问作者Isaias Chavez