欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java B组蓝桥杯第十届国赛:平方拆分

程序员文章站 2022-04-22 11:33:14
试题 B: 平方拆分本题总分:5 分【问题描述】将 2019 拆分为若干个两两不同的完全平方数之和,一共有多少种不同的方法?注意交换顺序视为同一种方法,例如 13 2 + 25 2 + 35 2 = 2019 与 13 2 + 35 2 +25 2 = 2019 视为同一种方法。【答案提交】这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。答案:7public class Main { publ....

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

尴尬,感谢大佬的指正,我还以为是只要三位平方数,太马虎了。

题目上要若干个,需要利用深度搜索进行统计。

这里值得注意的是,起始位置应该是从1开始,如果从0开始就会造成下列情况:(用题目的例子举例子)

从0开始深度搜索,会得到 :( 0 , 13  ,  25   , 35) 和(13  ,  25    , 35)

而从1开始深度搜索,只会得到:(13  ,  25    , 35)

这两种情况因为没有具体答案,我个人感觉应该第二种,得到的答案:

答案:26287

public class Main {
    int sum; 
	public Main() {
		dfs(2019,1,45);
		System.out.println(sum);
	}
    public void dfs(int num, int min, int max) {
	    if (num < 0) {
	        return;
	    }
	    if (num == 0) {
	        sum ++;
	        return;
	    }
	    for (int i = min; i < max; i++) {
	         dfs(num - i * i, i + 1, max);
	    }
	} 
	public static void main(String[] args) {
		new Main();
	}
}

Java B组蓝桥杯第十届国赛:平方拆分

 

本文地址:https://blog.csdn.net/qq_43319748/article/details/109627750