华为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的复杂度应该能过了