蓝桥杯 Day2 Java组 排序和排列

蓝桥杯 Day2 Java组 排序和排列

第一题 计算阶乘 n!

输入一个正整数 n，输出 n!的值。n<=1000。

1. 定义一个大数组A[]来存大数，数组的一个元素存大数的一位。例如A[0]存个位，A[1]存十位，A[2]存百位，等等。

2. 那么A[]需要定义成多大？也就是说，1000!有多少位？可以自己估计，不过，可以用 windows 自带的计算器能直接算出来，1000! ≈ 4×10^{2567}。代码中定义一个更大的A[10000]。

3. 模拟乘法计算，处理进位：例如356×8。先计算个位的6×8，得48，其中个位的8等于 48%10=8，进位的4等于48/10=4。见我代码中的10sim 13行，这几行实际上是处理了两个数的乘法，请仔细分析这几行代码。

4. 按3的计算方法，计算n!。第8行的i遍历了1sim n，计算n!。

5. 最后打印是，从最高位开始打印。先找到最高位，即第一个不等于0的数，然后从高位往最低位打印。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int a[] = new int[15000];
        for(int i = 1;i<=10000;i++){
            a[i] = 0;
        }
        int flag = 0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        a[1] = 1;
        for (int i = 1; i <= n; i++) {
            int plus = 0;//最开始进位为0
            for (int j = 1; j <= 10000; j++) {
                a[j] = a[j] * i + plus;
                plus = a[j] / 10;
                a[j] = a[j] % 10;
            }
        }
        for (int i = 10000; i >= 1; i--) {
            if (a[i] != 0) {
                flag = i;
                break;
            }
        }
        for (int i = flag; i >= 1; i--) {
            System.out.print(a[i]);
        }
    }
}

同时，java里有可以处理大数的类

import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        BigInteger bigInteger = new BigInteger("1");
        for(int i = 1;i<=n;i++){
            bigInteger=bigInteger.multiply(new BigInteger(String.valueOf(i)));//参数要改成字符串
        }
        System.out.println(bigInteger);
    }
}

第二题 高精度加法（ps idea格式化代码 CRTL+ALT+L）

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

还是使用BigInteger类来做简单（当然和python还是比不了）

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BigInteger bigInteger1 = new BigInteger(scanner.next());//scanner.next是接受字符串的
        BigInteger bigInteger2 = new BigInteger(scanner.next());
        System.out.println(bigInteger1.add(bigInteger2));
    }
}

对Java 数组的排序通常用 Arrays.Sort()​

第三题  拼数

设有 n 个正整数 a1...an​，请将它们联接成一排，相邻数字首尾相接，使得组成的整数最大。

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++)
            nums[i] = sc.nextInt();
        String[] s = new String[n];
        String ans = "";
        for(int i = 0; i < n; i++)
            s[i] = nums[i] + "";//将数字转换成为字符串
        for(int i = 0; i < n - 1; i++)  //比较
            for(int j = i + 1; j < n; j++)
                if((s[j] + s[i]).compareTo(s[i] + s[j]) < 0) {//比两个字符串（长度相等）的大小
                    String temp = s[j];
                    s[j] = s[i];
                    s[i] = temp;
                }
        for(int i = n - 1; i >= 0; i--)//连字符串
            ans += s[i];
        System.out.println(ans);//输出
    }
}

compareTo  返回的是两字符串之差