小明和小强
题目描述
有两个自然数2<=x,y<=99，老师告诉小明两个数的和M，告诉小强两个数的积N。已知小明和小强都是超级无敌天才。
下面是两个人的对话：
小强：我不知道这两个数是多少，你肯定也不知道。
小明：本来我不知道，但你这么说我就知道了。
小强：那我也知道了。
问这两个数是多少？
思路
根据哥德巴赫猜想：如果一个数是偶数，那么它可以分解为两个素数之和，而且两个素数之积是唯一的。也就是说，小明拿到的数一定不是偶数，否则小明就能知道这两个数了。
我们可以尝试枚举小明拿到的数M，然后枚举其中一个数x，用M-x得到另一个数y，如果x和y的积的拆分组合数量为1，小强是能知道这个数的，所以排除掉这种情况。
用一个函数f2来计算一个数的积的拆分组合数量，如果这个数的拆分组合数量为1，说明这个数是两个素数的积，否则不是。
// 用积拆分n的组合数量
public static int f2(int n) {
int cnt = 0;
for (int i = 2; i <= Math.sqrt(n); i++) {
int j = n / i;
if (j <= 99 && i != j && i * j == n) {
cnt++;
}
}
return cnt;
}然后这里用一个映射来存储满足条件的小明拿到的数M和其对应的拆分成两个数的积的所有结果。
Map<Integer, ArrayList<Integer>> map = new TreeMap<>();
lable2:
for (int i = 5; i <= 197; i += 2) {
for (int j = 2; j <= i / 2; j++) {
int k = i - j;
if (k <= 99 && k != j) {
int cnt = f2(k * j);
if (cnt == 1) continue lable2;
}
}
map.put(i, new ArrayList<>());
for (int l = 2; l <= i / 2; l++) {
map.get(i).add(l * (i - l));
}
}于是我们筛选出如下的结果：
11: 18 24 28 30
17: 30 42 52 60 66 70 72
23: 42 60 76 90 102 112 120 126 130 132
27: 50 72 92 110 126 140 152 162 170 176 180 182
29: 54 78 100 120 138 154 168 180 190 198 204 208 210
35: 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306
37: 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342
41: 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420
47: 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552
53: 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702 不难发现像18、24、28、50等数都是两数的积唯一出现的数。
“本来我不知道，但你这么说我就知道了。”
说明小明的数M的拆分出的两个数的积只有一种情况，所以小强拿的数一定在只出现一次的数中。
int[] cnt = new int[10000];
for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
ArrayList<Integer> list = entry.getValue();
for (Integer num : list) {
cnt[num]++;
}
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < cnt.length; i++) {
if (cnt[i] == 1) {
res.add(i);
System.out.print(i+ " ");
}
}最后我们进一步筛选出这些：
18 24 28 50 52 54 76 92 96 100 110 112 114
124 130 138 140 148 152 154 160 162 168 170
172 174 176 182 186 190 198 204 208 216 232
234 238 240 246 250 252 270 276 280 282 288
294 304 306 310 336 340 348 360 364 370 378
390 400 408 414 418 430 442 480 492 496
510 520 522 532 540 550 552 570 592 612
630 646 660 672 682 690 696 700 702“那我也知道了。”
我们通过第一次筛选小明所拿到的和分解所对应的所有的积放在了map里，然后我们再次遍历map，同时遍历上面刚刚筛选出的只出现一次的数，如果这个数在map中出现，且也只出现一次，那么这个数就是小强拿到的数。
所以我们既知道了小明拿到的数，也知道了小强拿到的数，然后我们再次遍历小明拿到的数，找到这两个数的组合。最后输出即可。
for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
ArrayList<Integer> list = entry.getValue();
int count = 0;
int ji = 0;
for (Integer re : res) {
if (list.contains(re)) {
count++;
ji = re;
}
}
if (count == 1) {
for (int i = 5; i <= 198; i++) {
for (int j = 2; j <= i / 2; j++) {
int k = i - j;
if (k + j == entry.getKey() && k * j == ji) {
System.out.println(k + " " + j);
}
}
}
}
}完整代码
package 实践学期.第四节课;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class 你知道我不知道 {
/*
2<=x,y<=99 x!=y x+y=M x*y=N
*/
public static void main(String[] args) {
f3();
}
// 用和拆分n的组合数量
public static int f1(int n) {
int cnt = 0;
for (int i = 2; i <= n / 2; i++) {
int j = n - i;
if (j <= 99 && i != j) {
cnt++;
}
}
return cnt;
}
// 用积拆分n的组合数量
public static int f2(int n) {
int cnt = 0;
for (int i = 2; i <= Math.sqrt(n); i++) {
int j = n / i;
if (j <= 99 && i != j && i * j == n) {
cnt++;
}
}
return cnt;
}
public static void f3() {
Map<Integer, ArrayList<Integer>> map = new TreeMap<>();
lable2:
for (int i = 5; i <= 197; i += 2) {
for (int j = 2; j <= i / 2; j++) {
int k = i - j;
if (k <= 99 && k != j) {
int cnt = f2(k * j);
if (cnt == 1) continue lable2;
}
}
map.put(i, new ArrayList<>());
for (int l = 2; l <= i / 2; l++) {
map.get(i).add(l * (i - l));
}
}
int[] cnt = new int[10000];
for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
ArrayList<Integer> list = entry.getValue();
// System.out.print(entry.getKey() + ": ");
for (Integer num : list) {
// System.out.print(num + " ");
cnt[num]++;
}
// System.out.println();
}
// System.out.println();
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < cnt.length; i++) {
if (cnt[i] == 1) {
res.add(i);
}
}
for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
ArrayList<Integer> list = entry.getValue();
int count = 0;
int ji = 0;
for (Integer re : res) {
if (list.contains(re)) {
count++;
ji = re;
}
}
if (count == 1) {
for (int i = 5; i <= 198; i++) {
for (int j = 2; j <= i / 2; j++) {
int k = i - j;
if (k + j == entry.getKey() && k * j == ji) {
System.out.println(k + " " + j);
}
}
}
}
}
}
}输出结果
13 4方格填数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下的10个格子：
+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）
求一共有多少种可能的填数方案？
解答思路
模型建立
我们可以通过创建一个3*4的矩阵，然后用一个boolean数组来记录数字是否被使用过，然后用一个递归函数来遍历所有的可能性。
static int[][] matrix = new int[3][4];
static boolean[] flag = new boolean[10];因为这个矩阵左上角和右下角是不用的，那么我们可以创建一个二维数组来记录有效的位置
static int[][] b = {
{0, 1}, {0, 2}, {0, 3},
{1, 0}, {1, 1}, {1, 2}, {1, 3},
{2, 0}, {2, 1}, {2, 2}};那么实际递归的时候我们遍历这个数组，然后判断这个位置是否可以填入数字，如果可以填入数字，那么我们就填入数字，然后递归到下一个位置，如果递归到最后一个位置，那么我们就可以得到一个有效的方案。
位置检查
检查当前位置是否可以填入数字，只需要检查当前位置的上，左上，右上，左和右这五个位置和当前数字是连续的，如果是连续的，那么就不能填入这个数字。
我们枚举所有的位置，然后检查这个位置是否可以填入数字。
// 获取位置为n在矩阵中的数字
public static int f(int n) {
return matrix[b[n][0]][b[n][1]];
}
// 检查两个数字是否是连续的
public static boolean g(int x, int y) {
return Math.abs(x - y) == 1;
}
public static boolean test(int n) {
switch (n) {
case 1:
return !g(f(1), f(0));
case 2:
return !g(f(2), f(1));
case 3:
return !g(f(0), f(3));
case 4:
return !(g(f(4), f(3)) ||
g(f(4), f(0)) ||
g(f(4), f(1)));
case 5:
return !(g(f(5), f(2)) ||
g(f(5), f(1)) ||
g(f(5), f(4)) ||
g(f(5), f(0)));
case 6:
return !(g(f(6), f(5)) ||
g(f(6), f(2)) ||
g(f(6), f(1)));
case 7:
return !(g(f(7), f(3)) ||
g(f(7), f(4)));
case 8:
return !(g(f(8), f(7)) ||
g(f(8), f(4)) ||
g(f(8), f(3)) ||
g(f(8), f(5)));
case 9:
return !(g(f(9), f(4)) ||
g(f(9), f(5)) ||
g(f(9), f(6)) ||
g(f(9), f(8)));
default:
return true;
}
}递归函数
public static void dfs(int i) {
if (i == 10) {
cnt++;
return;
}
for (int j = 0; j < 10; j++) {
int x = b[i][0], y = b[i][1];
matrix[x][y] = j + 1;
if (!flag[j] && test(i)) {
flag[j] = true;
matrix[x][y] = j + 1;
dfs(i + 1);
flag[j] = false;
}
matrix[x][y] = 0;
}
}递归出口
当i达到10，也就是数填够了的时候，是一种合法的答案，所以我们将答案加一。
递归体
然后我们枚举填哪个数，先看填没填过，如果没填过，那么先填上这个数字，然后调用test(i)检查当前位置是否合理，如果合理进入下一层递归，填下一个数。
完整代码
public class Main {
static int[][] matrix = new int[3][4];
static int[][] b = {
{0, 1}, {0, 2}, {0, 3},
{1, 0}, {1, 1}, {1, 2}, {1, 3},
{2, 0}, {2, 1}, {2, 2}};
static boolean[] flag = new boolean[10];
static int cnt = 0;
public static void main(String[] args) {
matrix[0][0] = 99;
matrix[2][3] = 99;
dfs(0);
System.out.println(cnt);
}
public static void dfs(int i) {
if (i == 10) {
cnt++;
return;
}
for (int j = 0; j < 10; j++) {
int x = b[i][0], y = b[i][1];
matrix[x][y] = j + 1;
if (!flag[j] && test(i)) {
flag[j] = true;
matrix[x][y] = j + 1;
dfs(i + 1);
flag[j] = false;
}
matrix[x][y] = 0;
}
}
public static boolean test(int n) {
switch (n) {
case 1:
return !g(f(1), f(0));
case 2:
return !g(f(2), f(1));
case 3:
return !g(f(0), f(3));
case 4:
return !(g(f(4), f(3)) ||
g(f(4), f(0)) ||
g(f(4), f(1)));
case 5:
return !(g(f(5), f(2)) ||
g(f(5), f(1)) ||
g(f(5), f(4)) ||
g(f(5), f(0)));
case 6:
return !(g(f(6), f(5)) ||
g(f(6), f(2)) ||
g(f(6), f(1)));
case 7:
return !(g(f(7), f(3)) ||
g(f(7), f(4)));
case 8:
return !(g(f(8), f(7)) ||
g(f(8), f(4)) ||
g(f(8), f(3)) ||
g(f(8), f(5)));
case 9:
return !(g(f(9), f(4)) ||
g(f(9), f(5)) ||
g(f(9), f(6)) ||
g(f(9), f(8)));
default:
return true;
}
}
public static int f(int n) {
return matrix[b[n][0]][b[n][1]];
}
public static boolean g(int x, int y) {
return Math.abs(x - y) == 1;
}
}输出答案
1580反幻方
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
我国古籍很早就记载着
2 9 4
7 5 3
6 1 8这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。
下面考虑一个相反的问题。 可不可以用 1~9的数字填入九宫格。
使得：每行每列每个对角线上的数字和都互不相等呢？
这应该能做到。 比如：
9 1 2
8 4 3
7 5 6你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。 旋转或镜像算同一种。
比如：
9 1 2
8 4 3
7 5 6
7 8 9
5 4 1
6 3 2
2 1 9
3 4 8
6 5 7都算作同一种情况。
请问三阶反幻方一共多少种？
思路
模型建立
我们可以用一个列表path来记录递归的路径，res来记录是反幻方的答案。
检查是否是反幻方
我们可以用一个函数check来检查是否是反幻方，我们将每一行、每一列、每一个对角线的和（共八个）放入到一个set中，如果其中有相等的，那么一定set.size() < 8，说明不是反幻方。
// 0 1 2
// 3 4 5
// 6 7 8
public static boolean check(List<Integer> matrix) {
int a = matrix.get(0) + matrix.get(1) + matrix.get(2);
int b = matrix.get(3) + matrix.get(4) + matrix.get(5);
int c = matrix.get(6) + matrix.get(7) + matrix.get(8);
int d = matrix.get(0) + matrix.get(3) + matrix.get(6);
int e = matrix.get(1) + matrix.get(4) + matrix.get(7);
int f = matrix.get(2) + matrix.get(5) + matrix.get(8);
int g = matrix.get(0) + matrix.get(4) + matrix.get(8);
int h = matrix.get(2) + matrix.get(4) + matrix.get(6);
Set<Integer> set = new HashSet<>();
set.add(a);
set.add(b);
set.add(c);
set.add(d);
set.add(e);
set.add(f);
set.add(g);
set.add(h);
return set.size() == 8;
}递归搜索
public static void dfs(int[] arr) {
if (path.size() == arr.length) {
if (check(path)) {
res.add(new ArrayList<>(path));
}
}
for (int i : arr) {
if (!path.contains(i)) {
path.add(i);
dfs(arr);
path.remove(path.size() - 1);
}
}
}当路径长度为给定数组长度时，说明找到了一个答案，然后检查是否是反幻方，如果是，那么就加入到res中。
我们枚举所有的可能性，利用回溯算法，然后继续调用dfs函数。
这里因为可以通过path中是否包含这个数来判断这个数是否被使用过，所以我们不需要额外的flag数组。
一点小注意
因为题目提到了旋转或镜像算同一种。
所以最后的答案数量要除以4*2=8。
public static void main(String[] args) {
int[] matrix = {1, 2, 3, 4, 5, 6, 7, 8, 9};
dfs(matrix);
System.out.println(res.size() / 8);
}完整代码
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static List<List<Integer>> res = new ArrayList<>();
public static List<Integer> path = new ArrayList<>();
public static void main(String[] args) {
int[] matrix = {1, 2, 3, 4, 5, 6, 7, 8, 9};
dfs(matrix);
System.out.println(res.size() / 8);
}
public static void dfs(int[] arr) {
if (path.size() == arr.length) {
if (check(path)) {
res.add(new ArrayList<>(path));
}
}
for (int i : arr) {
if (!path.contains(i)) {
path.add(i);
dfs(arr);
path.remove(path.size() - 1);
}
}
}
// 0 1 2
// 3 4 5
// 6 7 8
public static boolean check(List<Integer> matrix) {
int a = matrix.get(0) + matrix.get(1) + matrix.get(2);
int b = matrix.get(3) + matrix.get(4) + matrix.get(5);
int c = matrix.get(6) + matrix.get(7) + matrix.get(8);
int d = matrix.get(0) + matrix.get(3) + matrix.get(6);
int e = matrix.get(1) + matrix.get(4) + matrix.get(7);
int f = matrix.get(2) + matrix.get(5) + matrix.get(8);
int g = matrix.get(0) + matrix.get(4) + matrix.get(8);
int h = matrix.get(2) + matrix.get(4) + matrix.get(6);
Set<Integer> set = new HashSet<>();
set.add(a);
set.add(b);
set.add(c);
set.add(d);
set.add(e);
set.add(f);
set.add(g);
set.add(h);
return set.size() == 8;
}
}平方末尾
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
能够表示为某个整数的平方的数字称为“平方数”
虽然无法立即说出某个数是平方数，但经常可以断定某个数不是平方数。 因为平方数的末位只可能是：[0,1,4,5,6,9]这6个数字中的某个。 所以，4325435332必然不是平方数。
如果给你一个22位或22位以上的数字，你能根据末位的两位来断定它不是平方数吗？
请计算一下，一个2位以上的平方数的最后两位有多少种可能性？
思路
因为需要根据末位的两位来断定它不是平方数，所以我们可以先把0~99的平方数的末位两位都算出来:
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < 100; i++) {
arr.add((int) Math.pow(i, 2));
}然后我们用一个set来存储这些平方数的末位两位，最后输出set.size()即可。
Set<String> set = new HashSet<>();
for (int i = 4; i < 100; i++) {
String s = String.valueOf(arr.get(i));
set.add(s.substring(s.length() - 2));
}
System.out.println(set.size());完整代码
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Main {
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>();
Set<String> set = new HashSet<>();
for (int i = 0; i < 100; i++) {
arr.add((int) Math.pow(i, 2));
}
for (int i = 4; i < 100; i++) {
String s = String.valueOf(arr.get(i));
set.add(s.substring(s.length() - 2));
}
System.out.println(set.size());
}
}平方怪圈
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如果把一个正整数的每一位都平方后再求和，得到一个新的正整数。 对新产生的正整数再做同样的处理。
如此一来，你会发现，不管开始取的是什么数字， 最终如果不是落入1就是落入同一个循环圈。
请输出这个循环圈中最大的那个数字。
实现
很简单的题，模拟就好了
public class 平方怪圈 {
public static void main(String[] args) {
int num = 2;
int max = Integer.MIN_VALUE;
for (int i = 0; i < 100; i++) {
int sum = 0;
while (num != 0) {
sum += (int) Math.pow(num % 10, 2);
num /= 10;
}
if (i != 0) max = Math.max(max, sum);
num = sum;
System.out.print(sum + " ");
}
System.out.println();
System.out.println(max);
}
}