第五屆省賽（軟件類）真題—-Java大學A組答案及解析

子序列最大長度

萊布尼茨公式

n的n次冪

七對數字

勾股定理

九階數獨

矩陣射線

一、子序列最大長度

一個串的子串是指該串的一個連續的局部。如果不要求連續，則可稱為它的子序列。
比如對串： “abcdefg” 而言，”ab”,”abd”,”bdef” 等都是它的子序列。
特別地，一個串本身，以及空串也是它的子序列。
對兩個串而言，可以有許多的共同的子序列，我們關心的是：它們所共同擁有的長度最大的子序列是多長。以下代碼實現了這個問題的求解。請填寫劃線部分缺失的代碼。
注意：只填寫缺少的代碼，不要寫任何多余的內容，比如注釋或說明文字。

public class Zixulie {public static int f(String x, String y){if(x.length()==0) return 0;if(y.length()==0) return 0;String x1 = x.substring(1);String y1 = y.substring(1); if(x.charAt(0)==y.charAt(0)) return f(x1,y1)+1;return____________________;}public static void main(String[] args){System.out.println(f("ac","abcd")); //2System.out.println(f("acebbcde1133","xya33bc11de")); //5} }

答案：Math.max(f(x1, y), f(x, y1))

---

二、萊布尼茨公式

歷史上有許多計算圓周率pai的公式，其中，格雷戈里和萊布尼茨發現了下面的公式：

這個公式簡單而優美，但美中不足，它收斂的太慢了。
如果我們四舍五入保留它的兩位小數,那么：

累積1項是：4.00
累積2項是：2.67
累積3項是：3.47
。。。
請你寫出它累積100項是多少（四舍五入到小數后兩位）。
注意：只填寫該小數本身，不要填寫任何多余的說明或解釋文字。

答案：3.13

public class Main {public static void main(String[] args) {float sum = 0;float flag = 1;for (int i = 1; i <= 2*100-1; i += 2) {sum += flag * 1.0 / i;flag = -flag;}System.out.printf("%.2f", sum*4);} }

---

三、n的n次冪

如果x的x次冪結果為10（參見【圖1.png】），你能計算出x的近似值嗎？

顯然，這個值是介于2和3之間的一個數字。
請把x的值計算到小數后6位（四舍五入），并填寫這個小數值。
注意：只填寫一個小數，不要寫任何多余的符號或說明。

答案：3.162278

public class Main {public static void main(String[] args) {System.out.println(sqrt(10));}/*** 牛頓迭代法開平方* */public static double sqrt(double c){if(c < 0){return Double.NaN;}double err = 1e-15;double t = c;while(Math.abs(t - c/t) > err*t){t = (c/t + t)/2.0;}return t;} }

---

四、七對數字

今有7對數字：兩個1，兩個2，兩個3，…兩個7，把它們排成一行。
要求，兩個1間有1個其它數字，兩個2間有2個其它數字，以此類推，兩個7之間有7個其它數字。如下就是一個符合要求的排列：

17126425374635

當然，如果把它倒過來，也是符合要求的。
請你找出另一種符合要求的排列法，并且這個排列法是以74開頭的。
注意：只填寫這個14位的整數，不能填寫任何多余的內容，比如說明注釋等。

答案：74151643752362

public class Main {static int[] s;public static void main(String[] args) {s = new int[]{0, 7, 4, 0, 0, 0, 0, 4, 0, 7, 0, 0, 0, 0, 0};dfs(1);for (int i = 1; i < s.length; i++) {System.out.print(s[i]);}}public static int dfs(int n) {if (n == 4) {n++;}if (n > 6) {return 1;}for (int i = 3; i <= 14; i++) {if ( i == 7 || i == 9) {continue;}if (i+n+1 <= 14 && s[i] == 0 && s[i+n+1] == 0) {s[i] = s[i+n+1] = n;if (dfs(n+1) != 0) {return 1;}s[i] = s[i+n+1] = 0;}}return 0;} }

---

五、勾股定理

勾股定理，西方稱為畢達哥拉斯定理，它所對應的三角形現在稱為：直角三角形。

已知直角三角形的斜邊是某個整數，并且要求另外兩條邊也必須是整數。

求滿足這個條件的不同直角三角形的個數。

【數據格式】
輸入一個整數 n (0 < n< 10000000) 表示直角三角形斜邊的長度。
要求輸出一個整數，表示滿足條件的直角三角形個數。

例如，輸入：
5
程序應該輸出：
1

再例如，輸入：
100
程序應該輸出：
2

再例如，輸入：
3
程序應該輸出：
0

資源約定：
峰值內存消耗（含虛擬機） < 256M
CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。
所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。
注意：主類的名字必須是：Main，否則按無效代碼處理。

import java.util.Scanner;public class Main {static int[] s;public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int cnt = 0;for (int i = 1; i < Math.sqrt(Math.pow(n, 2)/2); i++) {int j = (int) Math.sqrt(Math.pow(n, 2) - Math.pow(i, 2));if (Math.pow(i, 2) + Math.pow(j, 2) == Math.pow(n, 2)) {cnt++;}}System.out.println(cnt);} }

---

六、九階數獨

你一定聽說過“數獨”游戲。
如【圖1.png】，玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個同色九宮內的數字均含1-9，不重復。

數獨的答案都是唯一的，所以，多個解也稱為無解。
本圖的數字據說是芬蘭數學家花了3個月的時間設計出來的較難的題目。但對會使用計算機編程的你來說，恐怕易如反掌了。
本題的要求就是輸入數獨題目，程序輸出數獨的唯一解。我們保證所有已知數據的格式都是合法的，并且題目有唯一的解。
格式要求，輸入9行，每行9個字符，0代表未知，其它數字為已知。
輸出9行，每行9個數字表示數獨的解。

例如：
輸入（即圖中題目）：
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700

程序應該輸出：
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

再例如，輸入：
800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400

程序應該輸出：
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

資源約定：
峰值內存消耗（含虛擬機） < 256M
CPU消耗 < 2000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。
所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。
注意：主類的名字必須是：Main，否則按無效代碼處理。

import java.util.Scanner;public class Main {static String[][] a = new String[9][9];public static void main(String[] args) {Scanner input = new Scanner(System.in);for (int i = 0; i < 9; i++) {String[] str = new String[9];str[i] = input.nextLine();a[i] = str[i].split("");}backtrace(0, 0);}private static void backtrace(int x, int y) {if (x == 9) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {System.out.print(a[i][j]);}System.out.println();}} else {if (a[x][y].equals("0")) {for (int i = 1; i <= 9; i++) {a[x][y] = i+"";if(check(x, y)) {if (y + 1 < 9) {backtrace(x, y+1);} else {backtrace(x+1, 0);}}a[x][y] = "0";}} else {if (y + 1 < 9) {backtrace(x, y+1);} else {backtrace(x+1, 0);}}}}private static boolean check(int x, int y) {for (int i = 0; i < 9; i++) {if (a[x][i].equals(a[x][y]) && i != y) {return false;}}for (int i = 0; i < 9; i++) {if (a[i][y].equals(a[x][y]) && i != x) {return false;}}int row = (x/3)*3;int col = (y/3)*3;for (int i = row; i < row+3; i++) {for (int j = col; j < col+3; j++) {if (a[i][j].equals(a[x][y]) && (i!=x || j !=y)) {return false;}}}return true;} }

---

七、矩陣射線★★

給定平面內平行于坐標軸的一個矩形，從矩形內選擇一些點，從這些點向右和向上各射出一條射線，請問：這些射線將矩形分成了多少份。

數據格式：

輸入的第一行包含兩個整數x, y，表示矩形是由(0, 0), (x, 0), (x, y), (0, y)四個點圍成的。
第二行包含一個整數n，表示矩形內的點的數量。
接下來n行，每個兩個整數xi, yi，表示矩形內的一個點。輸入保證所有的點都在矩形內部而且沒有兩個點有相同的橫坐標或縱坐標。

輸出一個整數，表示從給定的點射出的射線將矩形分成的份數。

例如，輸入：
10 10
3
1 3
3 1
2 4
程序應該輸出：
6

【數據規模和約定】
對于10%的數據，1<=n<=10，1<=x, y<=100；
對于30%的數據，1<=n<=1000，1<=x,y<=1000；
對于60%的數據，1<=n<=10000，1<=x,y<=1000000；
對于100%的數據，1<=n<=100000，1<=x,y<=1000000000，1 < xi < x，1 < yi < y。

資源約定：
峰值內存消耗（含虛擬機） < 256M
CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。

所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。
注意：主類的名字必須是：Main，否則按無效代碼處理。

解析：這個題目有點涉及計算機圖形學的內容，但是只要仔細觀察分析，也是能找出規律來的

按照測試用例，我們可以畫出如下的圖（顏色是丑了點，湊活著看

那么如果我們在多加一個點，圖中紅線延伸出去，我們可以看到這根線與其他的線有兩個交點，而兩個交點自然就多分出來3個獨立的面積，所以答案是6+3=9吧ヽ(￣▽￣)ﾉ），不包含紅色那個點，答案就是6

如果還是沒有明白的話，下面再加一個點，紅線與其他的線有三個交點，所以多出來4個獨立的面積

import java.util.*;public class Main {public static long x, y;public static int n;public static Point[] P;public static long count = 1;public static ArrayList<Integer> list = new ArrayList<Integer>();static class Point {public int x;public int y;public Point(int x, int y) {this.x = x;this.y = y;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);x = in.nextLong();y = in.nextLong();n = in.nextInt();/*** Point數組，存放n個坐標* */P = new Point[n];for(int i = 0;i < n;i++) {int x = in.nextInt();int y = in.nextInt();P[i] = new Point(x, y);}getResult();}public static void getResult() {/*** 內部類重寫Comparator接口，自定義排序* */Arrays.sort(P, new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {if (o1.x >o2.x) {return 1;} else if (o1.x < o2.x) {return -1;} else if (o1.x == o2.x) {if (o1.y > o1.y) {return 1;} else if (o1.y < o1.y) {return -1;} else {return 0;}}return 0;}});list.add(P[n - 1].y);count++;for(int i = n - 2;i >= 0;i--) {if(P[i].x == P[i + 1].x) {if(P[i].y < P[i + 1].y) {int j = list.indexOf(P[i + 1].y);list.remove(j);list.add(P[i].y);}/*** 當兩個坐標x相等，y由題意可知必定不等，那么必定會分割出一塊面積，p[i+1].y > p[i].y 時，更新list數的值* */count++;}else {Collections.sort(list);int j = 0;for(;j < list.size();j++) {if(P[i].y <= list.get(j)) {break;}}/*** 兩條延長線與其他延長線相交x個，那么就會分割出x+1塊面積* */count += j + 1;if (!list.contains(P[i].y)) {list.add(P[i].y);}}}System.out.println(count);} }

總結

以上是生活随笔為你收集整理的第五届省赛（软件类）真题----Java大学A组答案及解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。