第五届省赛(软件类)真题----Java大学C组答案及解析
- 杨辉三角
- 调和级数
- 回文素数
- 过大年
- 位平方和
- 单位分数
- n级台阶
一、杨辉三角
二项式的系数规律，我国数学家很早就发现了。 如【图1.png】，我国南宋数学家杨辉1261年所著的《详解九章算法》一书里就出现了。 其排列规律： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 如下的程序，用来建立N行的杨辉三角形。请填写划线部分缺少的代码。 注意：只填写划线部分的代码，不要填写任何多余的内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class A
{
public static void main(String[] args)
{
int N = 8;
int[][] a = new int[N][N] ;
for(int i=0; i<N; i++){
a[i][0] = 1;
a[i][i] = 1;
}
for(int i=1; i<N; i++){
for(int j=1; j<i; j++)
__________________; //填空
}
for(int i=0; i<N; i++){
for(int j=0; j<=i; j++) System.out.print(String.format("%-5d", a[i][j]));
System.out.println();
}
}
}
答案：a[i][j] = a[i-1][j] + a[i-1][j-1]
二、调和级数
1/1 + 1/2 + 1/3 + 1/4 + ... 在数学上称为调和级数。 它是发散的，也就是说，只要加上足够多的项，就可以得到任意大的数字。 但是，它发散的很慢： 前1项和达到 1.0 前4项和才超过 2.0 前83项的和才超过 5.0 那么，请你计算一下，要加多少项，才能使得和达到或超过 15.0 呢？ 请填写这个整数。 注意：只需要填写一个整数，不要填写任何多余的内容。比如说明文字。
答案：1835421
1
2
3
4
5
6
7
8
9
10
11
12
13
14public class Main
{
public static void main(String[] args)
{
double sum = 0.0;
int i = 1;
do {
sum += 1.0/i;
i++;
}while (sum < 15.0);
System.out.println(sum);
System.out.println(i);
}
}
三、回文素数
10301是个5位的素数。它有个特点，把数字倒过来还是它本身，具有这样特征的素数，我们称之为：回文素数。
10501 10601 11311
这些都是5位的回文素数。 请你计算一下，像这样的5位数的回文素数，一共有多少个？ 请填写这个表示个数的整数，注意不要写任何其它多余的内容，比如说明或解释文字，也不要列出所有的回文素数。
答案：95
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
28public class Main
{
public static boolean prime(int i) {
//求素数不能等于开方结果
for(int j = 2;j<Math.sqrt(i);j++) {
if(i % j == 0) {
return false;
}
}
return true;
}
public static void main(String[] args)
{
int cnt = 0;
for (int i = 10000; i <= 99999; i++) {
if(!prime(i)) {
continue;
}
String s = i + "";
String[] arr = s.split("");
if (arr[0].equals(arr[4]) && arr[1].equals(arr[3])) {
cnt++;
}
}
System.out.println(cnt);
}
}
四、过大年
有如下的加法算式。其中每个汉字代表一个数字。
请填写“让我怎能过大年” 所代表的整数。
所有数字连在一起，中间不要空格。例如："3125697"。当然，这个不是正确的答案。
注意：只填写一个整数，不要填写任何多余的内容。
答案：1572836
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class Main {
public static void main(String[] args) {
int a,b,c,d,e,f,g;
int t,temp;
for (int i = 1000000; i<9999999;i++) {
a=i%10;
b=i%100;
c=i%1000;
d=i%10000;
e=i%100000;
f=i%1000000;
g=i%10000000;
t=i/1000%10;
temp=t*1000000+t*100000+t*10000+t*1000+t*100+t*10+t*1;
int sum=a+b+c+d+e+f+g;
if(sum == temp) {
System.out.println(i);
}
}
}
}
五、平方和
把一个整数的每个数位都平方后求和，又得到一个整数，我们称这个整数为：位平方和。 对新得到的整数仍然可以继续这一运算过程。 比如，给定整数为4，则一系列的运算结果为： 16,37,58,89,.... 本题的要求是，已知一个整数x，求第n步的运算结果。
数据格式要求： 输入，两个整数x n，中间以空格分开。表示求x的第n步位平方和。其中，x，n都大于0，且小于100000。 输出，一个整数，表示所求结果。
例如， 输入： 4 3 则程序应该输出： 58
再例如， 输入： 1314 10 则程序应该输出： 20
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public class Main {
public static int f(int x) {
int sum = 0;
while (x > 0) {
int t = x%10;
sum += t*t;
x/=10;
}
return sum;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int x = input.nextInt();
int n = input.nextInt();
for (int i = 0; i < n; i++) {
x = f(x);
}
System.out.println(x);
}
}
六、单位分数
形如：1/a 的分数称为单位分数。 可以把1分解为若干个互不相同的单位分数之和。 例如： 1 = 1/2 + 1/3 + 1/9 + 1/18 1 = 1/2 + 1/3 + 1/10 + 1/15 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231 等等，类似这样的分解无穷无尽。 我们增加一个约束条件：最大的分母必须不超过30 请你求出分解为n项时的所有不同分解法。 数据格式要求： 输入一个整数n，表示要分解为n项（n<12） 输出分解后的单位分数项，中间用一个空格分开。 每种分解法占用一行，行间的顺序按照分母从小到大排序。
例如， 输入： 4 程序应该输出： 1/2 1/3 1/8 1/24 1/2 1/3 1/9 1/18 1/2 1/3 1/10 1/15 1/2 1/4 1/5 1/20 1/2 1/4 1/6 1/12
再例如， 输入： 5 程序应该输出： 1/2 1/3 1/12 1/21 1/28 1/2 1/4 1/6 1/21 1/28 1/2 1/4 1/7 1/14 1/28 1/2 1/4 1/8 1/12 1/24 1/2 1/4 1/9 1/12 1/18 1/2 1/4 1/10 1/12 1/15 1/2 1/5 1/6 1/12 1/20 1/3 1/4 1/5 1/6 1/20
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。
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
33class Main {
public static void f(int[] p, int n, int fm, int end) {
if (n == end) {
int sum = 1;
int sum1 = 0;
for (int i = 0; i < n; i++) {
sum *= p[i];
}
for (int j = 0; j < n; j++) {
sum1 +=sum/p[j];
}
/*控制输出*/
if (sum == sum1) {
for (int i = 0; i < n; i++) {
System.out.print("1/" + p[i] + " ");
}
System.out.println();
}
} else {
for (int i = fm; i < 30; i++) {
p[end] = i;
f(p, n, i+1,end+1);
}
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] p = new int[n];
f(p,n,2,0);
}
}
七、n级台阶
有n级台阶。从地面（第0级）出发，首先连续的上台阶，上到不超过第n级的某一个位置后再连续的下台阶，直到回到地面。若每次上下台阶只允许走1级或2级，请问可能的上下台阶的方案数是多少？ 特别地，在0级站着不动也算一种方案。
数据格式： 输入一行包含两个正整数n和m。 输出一个整数，表示n级台阶有多少种合法的走楼梯方案，答案对m取余。
例如：输入： 2 10007 程序应该输出 6
【样例说明1】 共有6种方案(其中+表示上台阶，-表示下台阶)： (1) 原地不动 (2) +1 -1 (3) +2 -2 (4) +2 -1 -1 (5) +1 +1 -2 (6) +1 +1 -1 -1
再例如，输入： 3 14 程序应该输出： 1
【样例说明2】 共有15种方案，对14取余后得1。
【数据规模】 对于30%的数据，n<=10000； 对于100%的数据，n<=1017，m<=2*109。
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。 注意：主类的名字必须是：Main，否则按无效代码处理。
解析：典型的斐波那契数列问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int sum=1;
for(int i=0;i<=n;i++){
sum+=i*i;
}
System.out.println(sum%m);
}
}