打不了弟批

用户名：WDMoonMoonBird

访问量：37178

签　名：

不想当书法家的程序员不是好厨子

等　　级
排　　名	28
经　　验	15551
参赛次数	122
文章发表	77
年　　龄	24
在职情况	教师
学　　校	南宁师范大学
专　　业	计算机科学与技术

　　自我简介：

我爱学习

TA的其他文章

蓝桥杯算法训练VIP-集合运算-题解(C++代码)STL标准库
浏览：229

蓝桥杯算法训练VIP-瓷砖铺放-题解(C++代码)
浏览：164

信息学奥赛一本通T1184-明明的随机数-题解（C++代码）
浏览：1041

你可能喜欢

蓝桥杯2016年第七届真题-四平方和-题解（Java代码）

　　作者: 打不了弟批　　　　发表时间：2020-03-11 16:10:14 浏览：1171　|　评论：1　

原题链接：蓝桥杯2016年第七届真题-四平方和

**法一：暴力破解**
乍一看，可能会这么写，纯粹的暴力破解嘛，这个写法可以得出答案，但是数据规模达到了6.25e+26，会超时
```java
for (int a = 0; a < 5000000; a++) {
	for (int b = 0; b < 5000000; b++) {
		for (int c = 0; c < 5000000; c++) {
			for (int d = 0; d < 5000000; d++) {
				if ((0 <= a && a <= b && b <= c && c <= d) && a * a + b * b + c * c + d * d == num) {
					System.out.println(a+" "+b+" "+c+" "+d);
					return;
				}
			}
		}
	}
}
```
首先看看题目的数据规模，**输入的数最大不超过5000000**
我们假设最极端的情况，输入了5000000，假设前a,b,c都是0，可以推算出，第四个数d不会超过![](/image_editor_upload/20200311034900_35426.png)=2236.06797749979+1‬；再来看看c,得出了d的范围，那也可以得出c的范围是![](/image_editor_upload/20200311034900_35426.png)+1-a-b;a，b的范围很小，给50足以
由此，推算出四个数的范围：
![](/image_editor_upload/20201215091932_88957.jpg)
得到了各数的极限值，其实数据规模并不是很大，推测符合资源约定，所以就放心的上暴力破解
```java
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		for (int a = 0; a < 50; a++) {
			for (int b = 0; b < 50; b++) {
				for (int c = 0; c < 2240 - a - b; c++) {
					for (int d = 0; d < 2240; d++) {
						if ((0 <= a && a <= b && b <= c && c <= d) && a * a + b * b + c * c + d * d == num) {
							System.out.println(a+" "+b+" "+c+" "+d);
							return;
						}
					}
				}
			}
		}
	}
}

```
**法二：哈希表**
1. 先求出c,d，把c × c + d × d作为key，把c作为value存入哈希表中，这个时候，c、d已知
2. 这个时候，n - a × a + b × b = c × c + d × d，通过哈希表映射，可以把a、b以及符合条件的c、d提取出来

```java
if (table.get(num - a * a - b * b) != null) {
	int c = table.get(num - a * a - b * b);//把之前存入的c提取出来
	int d = (int)Math.sqrt(num - a * a - b * b - c * c);//把之前存入的d提取出来
	System.out.println(a + " " + b + " " + c + " " + d);
	return;
}
```

------------

#### **关于哈希表**
- Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。
- Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
- Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，Hashtable中的映射不是有序的。

```java
import java.util.Hashtable;
public class Main {
    public static void main(String[] args) {
        //创建哈希表
        Hashtable table = new Hashtable();

//将指定 key 映射到此哈希表中的指定 value
        table.put('A',1);
        table.put('B',2);
        table.put('C',3);

//返回指定键所映射到的值
        System.out.println(table.get('A'));
        System.out.println(table.get('B'));
        System.out.println(table.get('C'));
    }
}
```
- Hashtable();默认构造方法
- Hashtable(int size);创建指定大小的哈希表
- Object get(Object key);返回指定键所映射到的值
- Object put(Object key, Object value);将指定 key 映射到此哈希表中的指定 value

------------

整体代码
```java
import java.util.Hashtable;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		for (int c = 0; c * c <= num; c++) {
			for (int d = c; c * c + d * d <= num; d++) {
				if (table.get(c * c + d * d) == null) {
					table.put(c * c + d * d, c);//存入表
				}
			}
		}
		for (int a = 0; a * a <= num; a++) {
			for (int b = a; a * a + b * b <= num; b++) {
				if (table.get(num - a * a - b * b) != null) {
					int c = table.get(num - a * a - b * b);//把之前存入的c提取出来
					int d = (int)Math.sqrt(num - a * a - b * b - c * c);//把之前存入的d提取出来
					System.out.println(a + " " + b + " " + c + " " + d);
					return;
				}
			}
		}
	}
}
```

0.0分

12 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

万如意

墙都不扶，就服你

2021-01-14 12:54:19

打不了弟批

TA的其他文章

你可能喜欢

分糖果（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

计算质因子（C++代码）100以内质数直接打表就好了

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯2016年第七届真题-四平方和-题解（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

Cylinder （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

DNA （C语言代码）

剪刀石头布（C语言代码）

打不了弟批

TA的其他文章

你可能喜欢

分糖果 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）

计算质因子 （C++代码）100以内质数直接打表就好了

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

点我有惊喜！你懂得！

蓝桥杯2016年第七届真题-四平方和-题解（Java代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

Cylinder （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

DNA （C语言代码）

剪刀石头布 （C语言代码）

分糖果（C语言代码）

计算质因子（C++代码）100以内质数直接打表就好了

　　评论区

剪刀石头布（C语言代码）