题目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
| 题目:广场上有一队士兵，如果排成10 列纵队，最后剩下a 个人(0 <= a <= 9)；如果排成9 列纵队，最后剩下b 个人(0 <= b <= 8)；如果排成8 列纵队，最后剩下c 个人(0 <= c <= 7)……如果排成2 列纵队，最后剩下i 个人(0 <= i <= 1)，输入a, b, c,…, i，输出广场上士兵的最少可能人数，分别用蛮力法和数学建模及中国中值定理(又称老子定理)方法求解。
请帮我补全下面的代码,写出数学建模法
package org.hantou;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void getData(int num){
StringBuilder result = new StringBuilder();
for (int i = 10; i >= 2; i--) {
int remainder = num % i;
result.append(remainder).append(" ");
}
System.out.println(result.toString().trim());
}
public static int violentWay(int[] a){
int result = 1;
while (true) {
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(int a[]){
}
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++) {
a[soldiersString.length-i-1] = Integer.parseInt(soldiersString[i]);
}
System.out.println(violentWay(a));
System.out.println(mathWay(a));
}
}
|
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
| 题目:广场上有一队士兵，如果排成10 列纵队，最后剩下a 个人(0 <= a <= 9)；如果排成9 列纵队，最后剩下b 个人(0 <= b <= 8)；如果排成8 列纵队，最后剩下c 个人(0 <= c <= 7)……如果排成2 列纵队，最后剩下i 个人(0 <= i <= 1)，输入a, b, c,…, i，输出广场上士兵的最少可能人数，分别用蛮力法和数学建模及中国中值定理(又称老子定理)方法求解。
对于数学建模法报错了Exception in thread "main" java.lang.ArithmeticException: / by zero
请帮我解决
public static int mathWay(int a[]) {
int[] m = new int[a.length];
int[] M = new int[a.length];
int[] M1 = new int[a.length];
int[] M2 = new int[a.length];
int M0 = 1;
int M1Sum = 0;
int M2Sum = 0;
for (int i = 0; i < a.length; i++) {
int columns = i + 2;
m[i] = columns - a[i];
M0 *= columns;
}
for (int i = 0; i < a.length; i++) {
int columns = i + 2;
int Mi = M0 / columns;
M[i] = Mi;
M1[i] = inverse(Mi, columns);
M1Sum += M1[i] * Mi * m[i];
M2[i] = M1[i] * Mi;
M2Sum += M2[i];
}
int x = M1Sum % M0;
int k = 0;
while (true) {
int result = x + k * M2Sum;
boolean valid = true;
for (int i = 0; i < a.length; i++) {
int columns = i + 2;
if (result % columns != a[i]) {
valid = false;
break;
}
}
if (valid) {
return result;
}
k++;
}
}
public static int inverse(int a, int b) {
int b0 = b, t, q;
int x0 = 0, x1 = 1;
if (b == 1) {
return 1;
}
while (a > 1) {
q = a / b;
t = b;
b = a % b;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) {
x1 += b0;
}
return x1;
}
|
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
| 这个错误通常是因为在求解Mi时，如果某个列数为0，那么Mi会变成0，从而导致除数为0的错误。所以需要在计算Mi之前，先判断列数是否为0。
修改后的mathWay方法如下：
```
public static int mathWay(int a[]) {
int[] m = new int[a.length];
int[] M = new int[a.length];
int[] M1 = new int[a.length];
int[] M2 = new int[a.length];
int M0 = 1;
int M1Sum = 0;
int M2Sum = 0;
for (int i = 0; i < a.length; i++) {
int columns = i + 2;
m[i] = columns - a[i];
M0 *= columns;
}
for (int i = 0; i < a.length; i++) {
int columns = i + 2;
int Mi = 0;
if (columns != 0) {
Mi = M0 / columns;
}
M[i] = Mi;
M1[i] = inverse(Mi, columns);
M1Sum += M1[i] * Mi * m[i];
M2[i] = M1[i] * Mi;
M2Sum += M2[i];
}
int x = M1Sum % M0;
int k = 0;
while (true) {
int result = x + k * M2Sum;
boolean valid = true;
for (int i = 0; i < a.length; i++) {
int columns = i + 2;
if (result % columns != a[i]) {
valid = false;
break;
}
}
if (valid) {
return result;
}
k++;
}
}
```
这样就可以避免除数为0的错误了。
|
