首页 > 代码库 > 算法笔记_216:第六届蓝桥杯软件类校赛部分真题(Java语言C组)

算法笔记_216:第六届蓝桥杯软件类校赛部分真题(Java语言C组)

目录

1 题目一

2 题目二

3 题目三

4 题目四

5 题目五

 

 

 

 前言:以下代码仅供参考,若有错误欢迎指正哦~


1 题目一

二项式的系数规律,我国数学家很早就发现了。

如【图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行的杨辉三角形。请填写划线部分缺少的代码。

注意:只填写划线部分的代码,不要填写任何多余的内容。



public 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 - 1] + a[i - 1][j]

 

 

 

 


2 题目二

10301是个5位的素数。它有个特点,把数字倒过来还是它本身,具有这样特征的素数,我们称之为:回文素数。

10501
10601
11311

这些都是5位的回文素数。

请你计算一下,像这样的5位数的回文素数,一共有多少个?

请填写这个表示个数的整数,注意不要写任何其它多余的内容,比如说明或解释文字,也不要列出所有的回文素数。


答案:93

 

 1 public class Main {
 2     
 3     public boolean judgePrime(int n) {
 4         boolean judge = true;
 5         for(int i = 2;i <= n / 2;i++)
 6             if(n % i == 0) {
 7                 judge = false;
 8                 break;
 9             }
10         return judge;
11     }
12     
13     public boolean judgeReverse(int n) {
14         StringBuffer s = new StringBuffer(""+n);
15         String s1 = "", s2 = "";
16         s1 = s.toString();
17         s2 = s.reverse().toString();
18         if(s1.equals(s2))
19             return true;
20         else
21             return false;
22     }
23     public static void main(String[] args) {
24         Main test = new Main();
25         int count = 0;
26         for(int i = 10000;i < 100000;i++) {
27             if(test.judgePrime(i) && test.judgeReverse(i)) {
28                 count++;
29                 System.out.println(i);
30             }
31         }
32         System.out.println("结果:"+count);
33     }
34 }

 

 

 

 

 


3 题目三

有如下的加法算式。其中每个汉字代表一个数字。
(如存在对齐问题,可参见【图1.png】)

               年
             大年
           过大年
         能过大年
       怎能过大年
     我怎能过大年
+  让我怎能过大年
------------------
   能能能能能能能

请填写“让我怎能过大年” 所代表的整数。
所有数字连在一起,中间不要空格。例如:"3125697"。当然,这个不是正确的答案。

注意:只填写一个整数,不要填写任何多余的内容。


答案:1572836

技术分享

 1 public class Main {
 2     public static boolean[] used = new boolean[10];
 3     
 4     public void dfs(int[] A, int step) {
 5         if(step == 7) {
 6             int[] sum = new int[7];
 7             sum[0] = A[0]*1000000 + A[1]*100000 + A[2]*10000 + 
 8                  A[3]*1000 + A[4]*100 + A[5]*10 + A[6];
 9             sum[1] = sum[0] - A[0]*1000000;
10             sum[2] = sum[1] - A[1]*100000;
11             sum[3] = sum[2] - A[2]*10000;
12             sum[4] = sum[3] - A[3]*1000;
13             sum[5] = sum[4] - A[4]*100;
14             sum[6] = sum[5] - A[5]*10;
15             int judge1 = 0, judge2 = 0;
16             for(int i = 0;i < 7;i++) {
17                 judge1 = judge1 * 10 + A[3];
18                 judge2 = judge2 + sum[i];
19             }
20             if(judge1 == judge2) {
21                 for(int i = 0;i < 7;i++)
22                     System.out.print(A[i]);
23                 System.out.println();
24             }
25             return;
26         } else {
27             for(int i = 0;i <= 9;i++) {
28                 if(step == 0 && i == 0)
29                     continue;
30                 if(!used[i]) {
31                     used[i] = true;
32                     A[step] = i;
33                     dfs(A, step + 1);
34                     used[i] = false;
35                 }
36             }
37         }
38     }
39     
40     public static void main(String[] args) {
41         Main test = new Main();
42         int[] A = new int[7];
43         test.dfs(A, 0);
44     }
45 }

 

 

 

 

 


4 题目四

形如: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 import java.util.Scanner;
 2 
 3 public class Main {
 4     
 5     public static int n;
 6     public static long Lcd_1_30 = 2329089562800L; //1-30的最小公倍数
 7     public static int[] A;
 8     
 9     public void dfs(int step, int nowNum, long result) {
10         if(step == n) {
11             if(result != Lcd_1_30)
12                 return;
13             for(int i = 0;i < n;i++)
14                 System.out.print("1/"+A[i]+" ");
15             System.out.println();
16             return;
17         }
18         if(result > Lcd_1_30)
19             return;
20         for(int i = nowNum + 1;i < 30;i++) {
21             A[step] = i;
22             dfs(step + 1, i, result + Lcd_1_30 / i);
23         }
24     }
25     
26     public static void main(String[] args) {
27         Main test = new Main();
28         Scanner in = new Scanner(System.in);
29         n = in.nextInt();
30         A = new int[n];
31         test.dfs(0, 0, 0);
32     }
33 }

 参考资料:第五届蓝桥杯Java语言C组_单位分数

 

 

 


5 题目五

有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<=10^17,m<=2*10^9。


资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。
 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3 
 4 
 5 public class Main {
 6     public static long n, m;
 7     public static BigInteger MOD;
 8     public static BigInteger zero = BigInteger.ZERO;
 9     public static BigInteger one = BigInteger.ONE;
10     public BigInteger[][] ZERO = {{zero,zero},{zero,zero}};
11     public BigInteger[][] key = {{one, one},{one, zero}};
12     
13     public BigInteger[][] mergeValue(long a) {
14         if(a == 0)
15             return ZERO;
16         if(a == 1)
17             return key;
18         if((a&1) == 0) {
19             BigInteger[][] temp = mergeValue(a>>1);
20             return multiMatrix(temp, temp);
21         } else {
22             BigInteger[][] temp = mergeValue(a>>1);
23             return multiMatrix(multiMatrix(temp, temp), key);
24         }
25     }
26     
27     public BigInteger[][] multiMatrix(BigInteger[][] A, BigInteger[][] B) {
28         BigInteger[][] result = new BigInteger[A.length][B[0].length];
29         for(int i = 0;i < result.length;i++)
30             for(int j = 0;j < result[0].length;j++)
31                 result[i][j] = zero;
32         for(int i = 0;i < A.length;i++)
33             for(int j = 0;j < B[0].length;j++)
34                 for(int k = 0;k < A[0].length;k++) {
35                     result[i][j] = result[i][j].add(A[i][k].multiply(B[k][j]));
36                     result[i][j] = result[i][j].mod(MOD);
37                 }
38         return result;    
39     }
40     
41     public void getResult() {
42         BigInteger result;
43         BigInteger[][] start = {{one, one}};
44         BigInteger[][] temp = multiMatrix(start, mergeValue(n));
45         result = temp[0][0].multiply(temp[0][1]);
46         System.out.println(result.mod(MOD));
47     }
48     
49     public static void main(String[] args) {
50         Main test = new Main();
51         Scanner in = new Scanner(System.in);
52         n = in.nextLong();
53         m = in.nextLong();
54         MOD = new BigInteger(""+m);
55         test.getResult();
56     }
57 }

 参考资料: N阶台阶

 

 

 

算法笔记_216:第六届蓝桥杯软件类校赛部分真题(Java语言C组)