题目1: 中国剩余定理

广场上有一队士兵，如果排成10 列纵队，最后剩下a 个人(0 <= a <= 9)；如果排成9 列纵队，最后剩下b 个人(0 <= b <= 8)；如果排成8 列纵队，最后剩下c 个人(0 <= c <= 7)……如果排成2 列纵队，最后剩下i 个人(0 <= i <= 1)，输入a, b, c,…, i，输出广场上士兵的最少可能人数，分别用蛮力法和数学建模方法求解。

4396 -> 6 4 4 0 4 1 0 1 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package org.hantou.test1;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class test1 {
    public static int x, y;

    //暴力方法
    public static int violentWay(int[] a){
        int result = 1;
        while (true) {
//            System.out.println(result);
            boolean valid = true;
            for (int i = 0; i < a.length; i++) {
                int remaining = a[i];
                int columns = i + 2;
                if (result % columns != remaining) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return result;
            }
            result++;
        }
    }

    public static int mathWay(Map<Integer,Integer> a,int[] w){
        //1.计算所有模数的积(2,3,5,7)
        int M = 210;

        //2.计算第i个方程的Ci=M/key
        int[] c1 = new int[11];
        for(Map.Entry<Integer,Integer> entry :a.entrySet()){
            c1[entry.getKey()]=M/entry.getKey();
        }
        //3.计算c1i在模mi意义下的逆元c2i
        int[] c2 = new int[11];
        for(Map.Entry<Integer,Integer> entry :a.entrySet()){
            ex_gcd(c1[entry.getKey()],entry.getKey());
            //这里得到的逆元为x,若x为负数,则需要将x+mi再取余
            c2[entry.getKey()]=((x+entry.getKey())%entry.getKey());
        }

        //计算最终ans
        int ans=0;
        for(Map.Entry<Integer,Integer> entry :a.entrySet()){
            ans+=a.get(entry.getKey())*c1[entry.getKey()]*c2[entry.getKey()]%M;
        }

        while(!check(w,ans)) ans+=M;
        return ans;
    }

    public static int ex_gcd(int a, int b) {
        if (b == 0) {
            x = 1; y = 0;
            return a;
        }
        int d = ex_gcd(b, a%b);
        int temp = x;
        x = y;
        y = temp - a/b * y;
        return d;
    }

    public static boolean check(int a[],int x){
        for (int i = 0; i < a.length; i++) {
            if(x%(i+2)!=a[i]) return false;
        }
        return true;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("请输入剩余人数a到i：");
        String input = scanner.nextLine();
        String[] soldiersString = input.split(" ");
        int[] a = new int[soldiersString.length];
        //将输入转为字符串
        for (int i = 0; i < soldiersString.length; i++) {
            //这里翻转,从2开始而不是10
            a[soldiersString.length-i-1] = Integer.parseInt(soldiersString[i]);
        }

//        //6 0 2 1 0 1 2 0 0 -> 666
        System.out.println(violentWay(a));
        Map<Integer,Integer> t = new HashMap<Integer,Integer>();
        t.put(2,a[0]);
        t.put(3,a[1]);
        t.put(5,a[3]);
        t.put(7,a[5]);

        System.out.println(mathWay(t,a));
    }
}

题目2: 对角线的之字形方针

给定一个正整数n，输出如下 n ´ n “之字形”方阵。

例： 8 ´ 8 方阵。

img

选作：输入任意的两个正整数m 和n(m ¹ n)，构造m ´ n “之字形”矩阵，以下示例为3 ´ 5 矩阵：

img

image-20231012202611527

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Scanner;

public class test2 {
    public static int[][] a = new int[1000][1000];
    public static void main(String[] args) {
        System.out.println("请输入m n;若要求n*n的方阵,请输入n n:");
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String s[] = str.split(" ");
        int m = Integer.parseInt(s[0]);
        int n = Integer.parseInt(s[1]);

        getmatrix(m,n);

    }

    private static void getmatrix(int m, int n) {
        int cnt = 1;//计数器
        for (int i = 0; i < m + n - 1; i++) {
            //i记录走过的斜线次数
            if (i % 2 == 0) {
                //↗
                for (int j = Math.min(i, m - 1); j >= 0; j--) {
                    int k = i - j;
                    if (k < n) {
                        a[j][k] = cnt++;
                    }
                }
            } else {
                //↙
                for (int j = Math.min(i, n - 1); j >= 0; j--) {
                    int k = i - j;
                    if (k < m) {
                        a[k][j] = cnt++;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(a[i][j]+" ");
            }
            System.out.println();
        }
    }

}

题目3: ab*cde=fijk

用1、2、3、4、5、6、7、8、9这9 个数字，填入 ? 中使等式??*???=????成立，每个数字恰好只用一次。

以下是所有的7 个答案供参考：

12 483 = 5796、18 297 = 5346、27 * 198 = 5346、

28 157 = 4396、39 186 = 7254、42 * 138 = 5796、

48 * 159 = 7632。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class test3 {
    private static boolean check(int a, int b, int product) {
        int[] num = new int[10];
        num[a / 10]++;
        num[a % 10]++;
        num[b / 100]++;
        num[(b / 10) % 10]++;
        num[b % 10]++;
        num[product / 1000]++;
        num[(product / 100) % 10]++;
        num[(product / 10) % 10]++;
        num[product % 10]++;

        for (int i = 1; i <= 9; i++) {
            if (num[i] != 1) {
                return false;
            }
        }
        return true;
    }
    //爆搜
    //第一个数12~98
    //第二个数123~987
    //双重遍历后check求解
    public static void main(String[] args) {
        for (int a = 12; a <= 98; a++) {
            for (int b = 123; b <= 987; b++) {
                int product = a * b;
                if (product > 9999) {
                    break;
                }
                if (check(a, b, product)) {
                    System.out.println(a + " * " + b + " = " + product);
                }
            }
        }
    }
}

题目4: 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.Scanner;

public class test4 {
    public static void main(String[] args) {
        System.out.println("请输入正整数n:");
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = Integer.parseInt(s);

        getAns(n);
    }

    private static void getAns(int n) {
        int cnt = 0;
        int st = 1, ed = 1;
        int sum=1;

        //滑动窗口求解,操作窗口头尾的同时维护窗口内的sum
        while(st<=n/2){
            if(sum<n){
                sum+=++ed;
            }else if(sum>n){
                sum-=st++;
            }else{
                cnt++;
                for(int i=st;i<ed;i++)
                    System.out.print(i+"+");
                System.out.println(ed);
                sum-=st++;
            }
        }
        System.out.println("共有"+cnt+"个不同连续自然段");
    }
}

题目5:

一个整数n(n <= 30)可以有多种分划，分划的整数之和为n，在不区分分划出各整数的次序时，字典序递减输出n 的各详细分划方案和分划总数。

例如n = 6，程序输出为：

6

5 1

4 2

4 1 1

3 3

3 2 1

3 1 1 1

2 2 2

2 2 1 1

2 1 1 1 1

1 1 1 1 1 1

total = 11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.ArrayList;
import java.util.Scanner;

public class test5 {
    public static void main(String[] args) {
        System.out.println("请输入正整数n:");
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int n = Integer.parseInt(s);

        getAns(n);
    }

    private static void getAns(int n) {
        int cnt = 0;
        for (int i=n;i>0;i--){

            //每层开始时,要对第一次进行特殊处理,给出初步的数组
            ArrayList<Integer> a = new ArrayList<>();
            a.add(i);
            if(i!=n){
                int m=i,g=n;
                while(g-m>m){
                    a.add(m);
                    g-=m;
                }
                a.add(g-m);
            }

            for (int k = 0; k < a.size(); k++) {
                System.out.print(a.get(k)+" ");
            }
            System.out.println();
            cnt++;

            //处理尾巴
            for (int j = a.size()-1; j >0; j--) {
                if (a.get(j)>1){
                    a.set(j, a.get(j)-1);
                    a.add(1);
                    for (int k = 0; k < a.size(); k++) {
                        System.out.print(a.get(k)+" ");
                    }
                    System.out.println();
                    j++;//注意这里的j++,就是把尾巴上的非1的数反复拆解
                    cnt++;
                }
            }

        }
        System.out.println("total = "+cnt);
    }
}