六十、备战蓝桥杯 - Java算法 （基础练习二）

蓝桥杯：全国软件和信息技术专业人才大赛 [1] 是由工业和信息化部人才交流中心举办的全国性IT学科赛事。共有北京大学、清华大学、上海交通大学等全国1200余所高校参赛，累计参赛人数超过40万人。 [2]

2020年，蓝桥杯大赛被列入中国高等教育学会发布的“全国普通高校学科竞赛排行榜”，是高校教育教学改革和创新人才培养的重要竞赛项目。 [3]

背景：第十三届蓝桥杯Java组省赛备战

练习题官网：蓝桥杯练习系统

练习目录

答题要求

题目说明

说明：要答题，请点击页面上方的“提交此题”按钮，页面将跳转到提交代码的页面，选择好你的编译语言，将你的编写好的代码粘贴到代码框中，再点击“提交答案”即可。

你的答案提交给系统后系统会自动对你的代码进行判分，并跳转到结果的列表里面，你可以直接从列表中看到你提交的代码的状态，一般几秒钟后就可以看到判分的结果。

本题作为第一题，在提示中已经分别给了C++和Java的代码，你可以直接把这个代码拷贝过去作为自己的代码提交。

请特别注意，Java的主类名必须是Main。

题目一

数列特征

给出n个数，找出这n个数的最大值，最小值，和。

第一行为整数n，表示数的个数。

第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。

输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        while (input.hasNext()) {
            int math = input.nextInt();
            int num = 0;
            int number[] = new int[math];
            for (int i = 0; i < math; i++) {
                number[i] = input.nextInt();
                num += number[i];
            }
            Arrays.sort(number);
            System.out.println(number[math - 1]);
            System.out.println(number[0]);
            System.out.println(num);
            System.exit(0);
        }
    }
}

题目二

字母图形

利用字母可以组成一些美丽的图形，下面给出了一个例子：

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。

输出n行，每个m个字符，为你的图形。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char zifu = (char) (Math.abs(i - j) + 'A');
                System.out.print(zifu);
            }
            System.out.println();
        }
    }
}

题目三

01字串

对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

输出32行，按从小到大的顺序每行一个长度为5的01串。

public class Main {
    public static void main(String[] args) {

        for(int a = 0; a < 2; a++) {
            for(int b = 0; b < 2; b++) {
                for(int c = 0; c < 2; c++) {
                    for(int d = 0; d < 2; d++) {
                        for(int e = 0; e < 2; e++) {
                            System.out.println(""+a+b+c+d+e);
                        }
                    }
                }
            }
        }
    }
}

题目四

闰年判断

给定一个年份，判断这一年是不是闰年。

当以下情况之一满足时，这一年是闰年：

1. 年份是4的倍数而不是100的倍数；

2. 年份是400的倍数。

其他的年份都不是闰年。

输入包含一个整数y，表示当前的年份。

输出一行，如果给定的年份是闰年，则输出yes，否则输出no。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int num = input.nextInt();
        if (num % 4 == 0 && num % 100 != 0 || num % 400 == 0) {
            System.out.println("yes");
        } else {
            System.out.println("no");
        }
    }
}

题目五

Fibonacci数列

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入包含一个整数n。

输出一行，包含一个整数，表示Fn除以10007的余数。

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int num = input.nextInt();
        int remainder = 0;
        int number[] = new int[num + 1];
        for (int i = 3; i <= num; i++) {
            number[0] = 0;
            number[1] = 1;
            number[2] = 1;
            number[i] = number[i - 1] + number[i - 2];
            remainder = number[i] % 10007;
        }
        System.out.println(remainder);
    }
}

题目六

圆的面积

给定圆的半径r，求圆的面积。

输入包含一个整数r，表示圆的半径。

输出一行，包含一个实数，四舍五入保留小数点后7位，表示圆的面积。

说明：在本题中，输入是一个整数，但是输出是一个实数。

对于实数输出的问题，请一定看清楚实数输出的要求，比如本题中要求保留小数点后7位，则你的程序必须严格的输出7位小数，输出过多或者过少的小数位数都是不行的，都会被认为错误。

实数输出的问题如果没有特别说明，舍入都是按四舍五入进行。

提示：本题对精度要求较高，请注意π的值应该取较精确的值。你可以使用常量来表示π，比如PI=3.14159265358979323，也可以使用数学公式来求π，比如PI=atan(1.0)*4。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int r = input.nextInt();
        double area = Math.PI*r*r*10000000;

        System.out.println((double)Math.round(area)/10000000);
        
        
    }
}

题目七

序列求和

求1+2+3+...+n的值。

输入包括一个整数n。

输出一行，包括一个整数，表示1+2+3+...+n的值。

说明：有一些试题会给出多组样例输入输出以帮助你更好的做题。

一般在提交之前所有这些样例都需要测试通过才行，但这不代表这几组样例数据都正确了你的程序就是完全正确的，潜在的错误可能仍然导致你的得分较低。

说明：请注意这里的数据规模。

本题直接的想法是直接使用一个循环来累加，然而，当数据规模很大时，这种“暴力”的方法往往会导致超时。此时你需要想想其他方法。你可以试一试，如果使用1000000000作为你的程序的输入，你的程序是不是能在规定的上面规定的时限内运行出来。

本题另一个要值得注意的地方是答案的大小不在你的语言默认的整型(int)范围内，如果使用整型来保存结果，会导致结果错误。

如果你使用C++或C语言而且准备使用printf输出结果，则你的格式字符串应该写成%I64d以输出long long类型的整数。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int math = input.nextInt();
        long sum = 0;
        for (long i = 0; i <= math; i++) {
            sum += i;
        }
        System.out.println(sum);
    }
}

VIP题目

题目八

阶乘计算

输入一个正整数n，输出n!的值。
其中n!=123…**n。

算法描述：n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

输入包含一个正整数n，n<=1000。

输出n!的准确值。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int number = input.nextInt();
        BigInteger bg = new BigInteger("1");

        for (int i = 1; i <= number; i++) {

            String n = String.valueOf(i);

            bg = (new BigInteger(n)).multiply(bg);
        }
        System.out.println(bg);
    }
}

题目九

高精度加法

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。
　　定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。
　　计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。
　　最后将C输出即可。

输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。

输出一行，表示*a *+ b的值。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String a = input.next();
        String b = input.next();
        int[] arr = new int[100];
        int[] brr = new int[100];
        int[] crr = new int[101];
        int r = 0;
        int count = 0;
        for (int i = a.length() - 1; i >= 0; i--) {
            arr[count++] = Integer.parseInt(a.substring(i, i + 1));
        }
        count = 0;
        for (int i = b.length() - 1; i >= 0; i--) {
            brr[count++] = Integer.parseInt(b.substring(i, i + 1));
        }
        for (int i = 0; i < 100; i++) {
            if ((crr[i] = (arr[i] + brr[i]) % 10 + r) == 10) {
                crr[i] = 0;
                r = 1;
                continue;
            }
            crr[i] = (arr[i] + brr[i]) % 10 + r;
            if (arr[i] + brr[i] > 10) {
                r = 1;
            } else {
                r = 0;
            }
        }
        int x = valid(crr);
        for (int i = x; i >= 0; i--) {
            System.out.print(crr[i]);
        }
    }

    public static int valid(int crr[]) {
        int tmp = 0;
        for (int i = 100; i >= 0; i--) {
            if (crr[i] != 0) {
                return i;
            }
        }
        return 100;
    }
}

题目十

Huffuman树

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

　　例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入的第一行包含一个正整数n（n<=100）。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。

输出用这些数构造Huffman树的总费用。

import java.util.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int a = input.nextInt();
            list.add(a);
        }

        boolean flag = true;
        int sum = 0;
        while (flag) {
            if (list.size() < 2) {
                System.out.println(sum);
                flag = false;
            } else {
                int cc[] = new int[list.size()];
                for (int i = 0; i < cc.length; i++) {
                    cc[i] = list.get(i);
                }
                Arrays.sort(cc);
                int b = cc[0];
                int c = cc[1];
                list.remove(Integer.valueOf(b));
                list.remove(Integer.valueOf(c));
                int d = b + c;
                sum += d;
                list.add(d);

            }
        }
    }
}

每周算法练习

备战蓝桥杯 - Java算法 （基础练习一）https://blog.csdn.net/m0_54925305/article/details/122367512

每日一悟：

你的现在很可能会是别人羡慕的明天

                                                                                                                      ** --托马斯**