第一题 三角形面积
已知三角形三个顶点在直角坐标系下的坐标分别为:
(2.3, 2.5)
(6.4, 3.1)
(5.1, 7.2)
求该三角形的面积。
注意,要提交的是一个小数形式表示的浮点数。
要求精确到小数后3位,如不足3位,需要补零。
1 // 方法: 推理 2 /* 3 这是已知三角形3顶点坐标A(x1,y1),B(x2,y2),C(x3,y3) ,求三角形ABC的面积的公式 4 A为(2.3, 2.5) B为(6.4, 3.1) C为(5.1, 7.2) 5 6 我的方法: 把这个三角形看出是一个正方形减3个三角形即可 然后就是计算然后相减 7 s = (x2 - x1)*(y3 - y1) - (x3 - x1) * (y3 - y1) * 0.5 - (x2 - x3) * (y3 - y2) * 0.5 - (x2 - x1) * (y2 - y1) * 0.5; 8 9 */ 10 public class t1 { 11 12 public static void main(String[] args) { 13 14 double x1 = 2.3, y1 = 2.5; 15 double x2 = 6.4, y2 = 3.1; 16 double x3 = 5.1, y3 = 7.2; 17 18 double s = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y3 - y1) * 0.5 - (x2 - x3) * (y3 - y2) * 0.5 19 - (x2 - x1) * (y2 - y1) * 0.5; 20 System.out.println(s); 21 // answer: 8.795 22 } 23 24 }
第二题 最大乘积
把 1~9 这9个数字分成两组,中间插入乘号,
有的时候,它们的乘积也只包含1~9这9个数字,而且每个数字只出现1次。
比如:
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...
符合这种规律的算式还有很多,请你计算在所有这些算式中,乘积最大是多少?
注意,需要提交的是一个整数,表示那个最大的积,不要填写任何多余的内容。
(只提交乘积,不要提交整个算式)
思路:全排列(用烂的套路)
1 import java.util.HashSet; 2 import java.util.Set; 3 4 public class t2 { 5 6 public static int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 7 public static int max; 8 9 public static int transfer(int start, int end) { 10 int n = 1; 11 int res = 0; 12 for (int i = end - 1; i >= start; i--) { 13 res += arr[i] * n; 14 n *= 10; 15 } 16 17 return res; 18 } 19 20 public static void check() { 21 22 for (int i = 1; i < 9; i++) { 23 int a = transfer(0, i); 24 int b = transfer(i, 9); 25 int c = a * b; 26 Set<Integer> set = new HashSet<>(); 27 int d = c; 28 boolean flag = false; // 标志是否其中含有0 29 while (d != 0) { 30 if (d % 10 == 0) { 31 flag = true; 32 } 33 set.add(d % 10); 34 d = d / 10; 35 } 36 37 if (set.size() == 9 && c > max && !flag) { 38 max = c; 39 } 40 } 41 42 } 43 44 public static void f(int x) { 45 46 if (x == 9) { 47 check(); 48 49 return; 50 } 51 52 for (int i = x; i < 9; i++) { 53 int temp = arr[x]; 54 arr[x] = arr[i]; 55 arr[i] = temp; 56 f(x + 1); 57 temp = arr[x]; 58 arr[x] = arr[i]; 59 arr[i] = temp; 60 } 61 62 } 63 64 public static void main(String[] args) { 65 66 f(0); 67 System.out.println(max); // answer: 839542176 68 69 } 70 71 }
第三题 全排列
全排列
对于某个串,比如:“1234”,求它的所有全排列。
并且要求这些全排列一定要按照字母的升序排列。
对于“1234”,应该输出(一共4!=24行):
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
下面是实现程序,请仔细分析程序逻辑,并填写划线部分缺少的代码。
// 轮换前k个,再递归处理
import java.util.*;
public class A
{
static void permu(char[] data, int cur){
if(cur==data.length-1){
System.out.println(new String(data));
return;
}
for(int i=cur; i<data.length; i++){
char tmp = data[i];
for(int j=i-1; j>=cur; j--) data[j+1] = data[j];
data[cur] = tmp;
permu(data, cur+1);
tmp = data[cur];
__________________________________________ ;
data[i] = tmp;
}
}
static void permu(String x){
permu(x.toCharArray(),0);
}
public static void main(String[] args){
permu("1234");
}
}
请注意:只需要填写划线部分缺少的内容,不要抄写已有的代码或符号。
思路:
全排列中的回溯代码,答案如下:for(int j=cur; j<=i-1; j++) data[j] = data[j+1]
第四题 整理玩具
小明有一套玩具,一共包含NxM个部件。这些部件摆放在一个包含NxM个小格子的玩具盒中,每个小格子中恰好摆放一个部件。
每一个部件上标记有一个0~9的整数,有可能有多个部件标记相同的整数。
小明对玩具的摆放有特殊的要求:标记相同整数的部件必须摆在一起,组成一个矩形形状。
如以下摆放是满足要求的:
00022
00033
44444
12244
12244
12233
01234
56789
以下摆放不满足要求:
11122
11122
33311
111111
122221
122221
111111
11122
11113
33333
给出一种摆放方式,请你判断是否符合小明的要求。
输入
----
输入包含多组数据。
第一行包含一个整数T,代表数据组数。 (1 <= T <= 10)
以下包含T组数据。
每组数据第一行包含两个整数N和M。 (1 <= N, M <= 10)
以下包含N行M列的矩阵,代表摆放方式。
输出
---
对于每组数据,输出YES或者NO代表是否符合小明的要求。
【样例输入】
3
3 5
00022
00033
44444
3 5
11122
11122
33311
2 5
01234
56789
【样例输出】
YES
NO
YES
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是:Main,否则按无效代码处理