当前位置: 首页 > >

第七届蓝桥杯 (javaB组)四*方和

发布时间:

第七届蓝桥杯 (javaB组)四*方和
四*方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多4个正整数的*方和。如果把0包括进去,就正好可以表示为4个数的*方和。
比如:

5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
(^符号表示乘方的意思)


对于一个给定的正整数,可能存在多种*方和的表示法。
要求你对4个数排序:
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法


程序输入为一个正整数N (N<5000000)
要求输出4个非负整数,按从小到大排序,中间用空格分开


例如,输入:
5
则程序应该输出:
0 0 1 2


再例如,输入:
12
则程序应该输出:
0 2 2 2


再例如,输入:
773535
则程序应该输出:
1 1 267 838


资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。


所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。


注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。


提交时,注意选择所期望的编译器类型。


解题思路

本题的重点在于如何找出这四个整数,因为只有找出这四个整数才能判断这四个数能否满足题目的要求,找出这四个数可以转化为排列组合的问题。即从n个数中找出4个数的全排,注意这个全排是有条件限制的,条件就是题目所说的



要求你对4个数排序:
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法



我们首先要定义一个计数变量对用n个数中已经找出的数进行计数,然后定义一个数组进行存储


public static int count = 0;//计数变量表示第几个数的下标
public static int[] a = new int[4];//使用数组来存储取出的4个数

这四个数必须是从小到大进行排列,可以相等但是前面的数永远不大于后面的数。
所以我们的判断条件必须要考虑到这一点,


public static boolean check(int count) {
//遍历数组
for (int i = 0; i < count; i++) {
//限制数组的应该是从小到大进行排列
if (a[i]>a[count]) {
return false;
}
}
return true;
}

当我们取出四个数后接下来的一步就是进行判断这四个的*方和是否满足题意



四*方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多4个正整数的*方和。
如果把0包括进去,就正好可以表示为4个数的*方和。



判断的代码如下


if ((int)Math.pow(a[0], 2) + (int)Math.pow(a[1], 2) + (int)Math.pow(a[2], 2) + (int)Math.pow(a[3], 2) == n) {
//如果满足题意则输出这四个数
for (int k : a) {
System.out.print(k + " ");
}
//题目要求只输出第一组数据,则输出后需要退出程序
System.exit(1);
}

这里面有一个需要注意的地方就是题目要求只输出第一个表示法



并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法



所以当我们找到第一个满足目条件的4个数并输出后,下一步应该终止该程序避免程序继续运行并输出下一个结果。


解题完整代码如下:


import java.util.Scanner;
/**
* 四*方和
* @author 小章与阿曦
*
*/
public class Main {
public static int count = 0;//计数变量表示第几个数的下标
public static int[] a = new int[4];//使用数组来存储取出的4个数
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
backTrack(count, n);
}

public static void backTrack(int count ,int n) {
if (count == 4) {
//判断是否满足题目4个数*方是否等于输入的正整数n
if ((int)Math.pow(a[0], 2) + (int)Math.pow(a[1], 2) + (int)Math.pow(a[2], 2) + (int)Math.pow(a[3], 2) == n) {
//如果满足题意则输出这四个数
for (int k : a) {
System.out.print(k + " ");
}
//题目要求只输出第一组数据,则输出后需要退出程序
System.exit(1);
}
return;
}else {
for (int i = 0; i < 3000; i++) {
a[count] = i;
if (check(count)) {
backTrack(count+1, n);
}
}
}
}

public static boolean check(int count) {
for (int i = 0; i < count; i++) {
//限制数组的应该是从小到大进行排列
if (a[i]>a[count]) {
return false;
}
}
return true;
}

}

以上纯属本人的理解,如有错误或者不妥地方欢迎大佬提意见。我会虚心接受并改正的!!!
2019.11.13 来自小白程序员 小章与阿曦的第一篇博客。



友情链接: