蓝桥杯真题 2019第十一届 国赛JavaB组试题 B: 平方拆分 详细题解_将2019拆分为若干个两两不同

试题 B: 平方拆分

本题总分：5 分

---

【问题描述】

将 2019 拆分为若干个两两不同的完全平方数之和，一共有多少种不同的方
法？
注意交换顺序视为同一种方法，例如 13 2 + 25 2 + 35 2 = 2019 与 13 2 + 35 2 +
25 2 = 2019 视为同一种方法。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

当本题所求为5而非2019时的递归遍历层次示意图（特意花了这张图，数字代表递归层次中for的第几个i，）

思路：
用递归暴力搜索，再运用剪枝把重复的去掉，提升效率
比如当求的是20而非2019时：
一：那就从1-20开始尝试：1的平方+2的平方+3的平方+4的平方，
此时总和sum已经大于20，那么此种情况不合法，
到达4都已经大于20了，5，6，7等后面的更会大于20，
所以没有再往下去遍历的必要了。
二：所以下一步就是把4的平方从sum里去掉，再把3的平方换成4的平方，
即sum=1的平方+2的平方+4的平方，发现此时sum也大于20了，也不行。
三：那么下一步就是把4的平方也从sum里去掉，再把2的平方换成3的平方，
即sum=1的平方+3的平方，此时任小于20，那再加上4的平方，发现又大了，有去掉
四：以此类推，最终在sum=2的平方+4的平方处找到答案
（这个过程用文字描述挺不容易的，码了这么多字，但愿你能迅速看懂，不行就看代码，千言万语尽在代码中
代码是java版本，C++的也差不多，学C++的人应该也能看懂java的吧）

package 蓝桥杯真题.第十一届.国赛._2_平方拆分;

import java.util.ArrayList;

public class Main {

	static int testCount=2019;
	static int list[]=new int[2030];//存储1-n的平方
	static int ans=0;
	static ArrayList<Integer> link=new ArrayList<Integer>();//数组，记录此时那些那些书已经被加入到sum的计算里面
	public static void search(int depth,int sum,int ii) {//形参ii用来记录上次层递归中for已经在第几个i了，下一次递归是直接从i+1开始
		for (int i = ii+1; i <= testCount; i++) {
			//for循环直接从上一次的i的下一个开始，因为题目说“13 2 + 25 2 + 35 2 = 2019 与 13 2 + 35 2 +25 2 = 2019 视为同一种方法”
			//这样可以利用剪枝把会照成重复的减掉
			int temp=sum;
			sum+=list[i];//尝试加上本次情况
			if(sum>=testCount) {
				if(sum==testCount) {
					ans++;
					link.add(i);
					System.out.println(link);
					//如果恰好sum为所求2019了那本次尝试到达末尾，为下一次尝试做准备，所以需要sum变回原理，link除去最后一个
					sum-=list[i];
					link.remove(link.size()-1);
				}else {
				}
				break;//本次i已经造成sum大于2019，下一次的i更会造成sum大于2019，所以不需要往下在递进去了，在这里break掉就可以了
			}
			link.add(i);
			search(depth+1,sum,i);
			//此种情况尝试完后尝试下一种情况，为不影响下一次尝试，本次尝试需要除去，即sum回到原来的值，link除掉最后一个
			sum=temp;
			link.remove(link.size()-1);
		}
	}
	public static void main(String[] args) {
		for (int i = 1; i <= 2025; i++) {
			list[i]=i*i;
		}
		search(0,0,0);
		System.out.println(ans);	//答案输出,码字不易，觉得有收获记得点赞评论支持一下
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59