华为od-C卷100分题目-3用连续自然数之和来表达整数

华为od-C卷100分题目-3用连续自然数之和来表达整数

题目描述

一个整数可以由连续的自然数之和来表示给定一个整数，计算该整数有几种连续自然数之和的表达式，且打印出每种表达式

输入描述

一个目标整数T(1<=T<=1000)

输出描述

该整数的所有表达式和表达式的个数。如果有多种表达式，输出要求为:

自然数个数最少的表达式优先输出

每个表达式中按自然数递增的顺序输出，具体的格式参见样例。

在每个测试数据结束时，输出一行”Result:X”，其中X是最终的表达式个数

输入
9

输出
9=9
9=4+5
9=2+3+4
Result:3

说明 整数9有三种表达方法：

示例二
输入
10
输出
10=10
10=1+2+3+4
Result:2

public class Main {
    public static void main(String[] args) {
        int num = new Scanner(System.in).nextInt();
        int count = 0;
        for (int i = num; i > 0; i--) {
            List<Integer> answer = getAnswer(i, num);
            if (!answer.isEmpty()) {
                count++;
                System.out.printf("" + num + "=");
                for (int j = 0; j < answer.size(); j++) {
                    System.out.printf("" + answer.get(j));
                    if (j != answer.size() - 1) {
                        System.out.printf("+");
                    }
                }
                System.out.println();
            }
        }
        System.out.println("Result:" + count);
    }

    public static List<Integer> getAnswer(int an, int num) {
        LinkedList<Integer> list = new LinkedList<>();
        double data = Math.sqrt(4 * (an * an + an - (2 * num)) + 1.0);
        double a = (-1 - data) / -2;
        double b = (-1 + data) / -2;
        if (Math.floor(a) - a == 0) {
            for (int i = (int) a; i <= an; i++) {
                list.add(i);
            }
        }
        return list;
    }
}

思路：等差数列，可以使用求和公式，(An-A1+1)来表示个数，则结果为（A1+An)*(An-A1+1)/2 = 输入的数(num)

展开得到： - A1^2 + A1 + An - 2*num + An^2 = 0

通过二元一次方程的通解，得到公式

A1 = -b ± sqrt(b * b - 4 * a * c) / (2 * a)

​ = -1 ± sqrt(1 * 1 - 4 * (-1) * (An - 2*num + An * 2)) / (2 * (-1))

得到的A1只要是整数就说明结果是对的，并且一定是唯一解
根据题意要求，从大到小遍历就行了。其实还可以优化，只是没有测试数据，并且On的复杂度应该能过了