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

子序列最大長度

萊布尼茨公式

n的n次冪

七對數(shù)字

勾股定理

九階數(shù)獨

矩陣射線

一、子序列最大長度

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

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的公式，其中，格雷戈里和萊布尼茨發(fā)現(xiàn)了下面的公式：

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

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

答案：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次冪結(jié)果為10（參見【圖1.png】），你能計算出x的近似值嗎？

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

答案：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;} }

---

四、七對數(shù)字

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

17126425374635

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

答案：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;} }

---

五、勾股定理

勾股定理，西方稱為畢達(dá)哥拉斯定理，它所對應(yīng)的三角形現(xiàn)在稱為：直角三角形。

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

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

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

例如，輸入：
5
程序應(yīng)該輸出：
1

再例如，輸入：
100
程序應(yīng)該輸出：
2

再例如，輸入：
3
程序應(yīng)該輸出：
0

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 1000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內(nèi)容。
所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
注意：不要使用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);} }

---

六、九階數(shù)獨

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

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

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

程序應(yīng)該輸出：
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

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

程序應(yīng)該輸出：
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 2000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內(nèi)容。
所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
注意：不要使用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;} }

---

七、矩陣射線★★

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

數(shù)據(jù)格式：

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

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

例如，輸入：
10 10
3
1 3
3 1
2 4
程序應(yīng)該輸出：
6

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

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 1000ms

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

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

解析：這個題目有點涉及計算機(jī)圖形學(xué)的內(nèi)容，但是只要仔細(xì)觀察分析，也是能找出規(guī)律來的

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

那么如果我們在多加一個點，圖中紅線延伸出去，我們可以看到這根線與其他的線有兩個交點，而兩個交點自然就多分出來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數(shù)組，存放n個坐標(biāo)* */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() {/*** 內(nèi)部類重寫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);}/*** 當(dāng)兩個坐標(biāo)x相等，y由題意可知必定不等，那么必定會分割出一塊面積，p[i+1].y > p[i].y 時，更新list數(shù)的值* */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);} }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。