八十二、Java算法练习打卡（三题）
文章目录
题目一
题目描述
年龄巧合
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小明和他的表弟一起去看电影，有人问他们的年龄。小明说：今年是我们的幸运年啊。我出生年份的四位数字加起来刚好是我的年龄。表弟的也是如此。已知今年是 2014 年，并且，小明说的年龄指的是周岁。
请推断并填写出小明的出生年份。
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
题解
-
public class Main {
-
public static void main(String[] args) {
-
for (int i = 2014; i > 1950; i--) {
-
if ((2014 - i) == (i % 10 + (i / 10) % 10 + (i / 100) % 10 + (i / 1000) % 10))
-
System.out.println(i);
-
}
-
}
-
}
注：确定区间（1950，2014），结果为2006，1988，他是我表弟，故为2006年出生
答案： 我 ：1988 他 ：2006
题目二
题目描述
纸牌三角形
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
A,2,3,4,5,6,7,8,9共 9 张纸牌排成一个正三角形（A 按 1 计算）。要求每个边的和相等。 下图就是一种排法。
这样的排法可能会有很多。
如果考虑旋转、镜像（对称）后相同的算同一种，一共有多少种不同的排法呢？
请你计算并提交该数字。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
题解
-
public class Main {
-
static int ans = 0;
-
static int[] A = new int[9];// 用来存数据
-
static int[] B = new int[9];// 用来表示该数组的位置是否有被遍历过
-
-
public static void main(String[] args) {
-
dfs(0);
-
-
// 因为旋转和镜像代表的是同一种，但是它们各重复三次，即重复六次，所以最后要除以六
-
System.out.println(ans / 6);
-
}
-
-
public static void dfs(int num) {
-
if (num == 9 && ((A[0] + A[1] + A[2] + A[3]) == (A[3] + A[4] + A[5] + A[6]))
-
&& ((A[3] + A[4] + A[5] + A[6]) == (A[6] + A[7] + A[8] + A[0]))) {
-
ans++;
-
return;
-
}
-
for (int i = 0; i < 9; i++) {
-
if (B[i] == 0) {
-
A[num] = i + 1;// 对数组进行赋值
-
B[i] = 1;// 表示该位置已经赋值
-
dfs(num + 1);
-
B[i] = 0;// 回溯
-
}
-
}
-
}
-
}
注：dfs搜索，全排列，抓住三个要素最为关键
- 入口的参数设置
- dfs的出口设置
- 是否需要回溯
答案：144
题目三
题目描述
取球游戏
今盒子里有 n个小球，A、B 两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。
我们约定：
每个人从盒子中取出的球的数目必须是：1，3，7 或者 8 个。轮到某一方取球时不能弃权！A 先取球，然后双方交替取球，直到取完。被迫拿到最后一个球的一方为负方（输方）
请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A 是否能赢？
输入描述
先是一个整数 n (n<100)，表示接下来有 n 个整数。
然后是 n个整数，每个占一行（整数< 10^4），表示初始球数。
输出描述
程序则输出 n 行，表示 A 的输赢情况（输为 0，赢为 1）。
输入样例
输出样例
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
题解
(暴力求解)
-
import java.util.ArrayList;
-
import java.util.List;
-
import java.util.Scanner;
-
-
//类似于爬楼梯的递归模式
-
public class Main {
-
public static void main(String[] args) {
-
Scanner scanner = new Scanner(System.in);
-
int n = scanner.nextInt();
-
List<Integer> l = new ArrayList<>();
-
for (int i = 0; i < n; i++) {
-
l.add(scanner.nextInt());
-
}
-
for (int j = 0; j < n; j++) {
-
if (A(l.get(j))) {
-
System.out.println(1);
-
} else {
-
System.out.println(0);
-
}
-
}
-
}
-
-
public static boolean A(int m) {
-
if (m >= 1) {
-
switch (m) {
-
case 1:
-
return false;// 当你要去拿球时，并且最后只剩下1个球时，输
-
case 3:
-
return false;// 当你要去拿球时，并且最后只剩下3个球时，输
-
case 7:
-
return false;// 输
-
case 8:
-
return true;// 赢
-
default:
-
return (!A(m - 1) || !A(m - 3) || !A(m - 7) || !A(m - 8));// 这个时候表示自己拿1或3或7或8个球，然后这时对象变成了对面的一个人，所以要加！
-
}
-
}
-
return false;
-
}
-
}
（dp求解）
-
import java.util.Scanner;
-
-
//dp解法
-
public class Main {
-
public static void main(String[] args) {
-
Scanner scanner = new Scanner(System.in);
-
int n = scanner.nextInt();
-
boolean[] A = new boolean[10009];// 因为n<10^4
-
A[0] = true;
-
for (int i = 1; i < 10009; i++) {
-
A[i] = (!(A[i - 1]) || (i >= 3 && !A[i - 3]) || (i >= 7 && !A[i - 7]) || (i >= 8 && !A[i - 8]));// 这个时候表示自己拿1或3或7或8个球，然后这时对象变成了对面的一个人，所以要加！
-
}
-
// 为了方便输出
-
int[] B = new int[n + 1];
-
for (int i = 1; i <= n; i++) {
-
int j = scanner.nextInt();
-
if (!A[j]) {
-
B[i] = 0;
-
} else {
-
B[i] = 1;
-
}
-
}
-
for (int k = 1; k <= n; k++) {
-
System.out.println(B[k]);
-
}
-
}
-
}
暴力求解：代码冗余，重复率较高，显得笨重且繁琐
dp求解：结果只有两种 ，他赢或我赢，是非的关系，用“||”来选择四种取法，表示只要有一种取法能够赢，那我最后就是赢的，取法都是最优值。
eg:4个球
1，1，1，1（我输了）
3，1（我赢了）
遍历计算结果，进行累计
文章来源: tuomasi.blog.csdn.net，作者：托马斯-酷涛，版权归原作者所有，如需转载，请联系作者。
原文链接：tuomasi.blog.csdn.net/article/details/123565978
- 点赞
- 收藏
- 关注作者
评论（0）