蓝桥杯基础（java)

文章目录

• • 高精度问题可以使用BigInteger和数组。
  • • 高精度阶乘计算
    • 高精度加法
    • 字符串对比
    • 分解质因数

高精度问题可以使用BigInteger和数组。

高精度阶乘计算

问题描述

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

　　其中n!=123*…*n。

算法描述

　　n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。

　　将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。

　　首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

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

public class Factory {

	public static void main(String[] args) {
		
				Scanner sc=new Scanner(System.in);
		        int n=sc.nextInt();
		        BigInteger bi=new BigInteger("1");
		        for(int i=2;i<=n;i++){
		            bi=bi.multiply(new BigInteger("i"));
		        }
		        System.out.println(bi);
           

高精度加法

输入两个整数a和b，输出这两个整数的和。

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

public class AddBigNums {

	public static void main(String[] args) {
		Scanner scn=new Scanner(System.in);
		BigInteger a=new BigInteger(scn.next());
		BigInteger b=new BigInteger(scn.next());
		System.out.println(a.add(b));			
	}
}
           

字符串对比

给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：

　　1：两个字符串长度不等。比如 Beijing 和 Hebei

　　2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing

　　3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing

　　4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing

　　编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。

import java.util.Scanner;

public class StringCompare {

	public static void main(String[] args) {
		Scanner scn=new Scanner(System.in);
		String a=scn.next();
		String b=scn.next();
		if(a.length()!=b.length())
			System.out.println(1);
		else
		{
			if(a.equals(b))
				System.out.println(2);
			else if(a.equalsIgnoreCase(b))
				System.out.println(3);
			else
				System.out.println(4);
		}
	}
}
           

分解质因数

求出区间[a,b]中所有整数的质因数分解。

输入格式

　　输入两个整数a，b。

输出格式

　　每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)

　　

　先筛出所有素数，然后再分解

数据规模和约定

　　2<=a<=b<=10000

思路：

质因数：首先是质数，然后才是因数。每个数都有唯一的质因数分解。

1.如何求质数：

• 比较容易想到的是定义法，求某个数是否是质数，则在比他小的数里面找，如果有超过两个因数，则不是质数。

x=int(input('please input a number:'))
counter=0
for i in range(1,x+1):
    if x%i==0:
        counter+=1

if counter>2:
    print('%d is not a prime'%x)
else:
    print('%d is a prime'%x)
           

上述的方法利用的是素数的定义，如果一个数只有自身和1两个因子，则说明这个数是素数。这种方法的缺点是遍历了所有数，会增加时间浪费，接下来我们使用优化的方法。

假如一个数 a 不是素数，那它一定可以写成 a=m*n，m不是1，n不是a。

这两个数必然一个小于√a，一个大于√a。

因为如果两个都小于，那么两个数的乘积是小于a的

两个都大于同理。

from math import sqrt
x=int(input('please input a number:'))
counter=0
end=int(sqrt(x))
for i in range(2,end+1):
    if x%i==0:
        counter+=1
if counter>=1 or x==1:
    print('%d is not a prime'%x)
else:
    print('%d is a prime'%x)
           

但是我们将利用上述优化过的方法来测试依然会超时。

所以关于求素数我们还要继续优化。

public static boolean isPrime(int n) {
		if (n == 2 || n == 3)
			return true;
		if (n % 6 != 1 && n % 6 != 5)
			return false;
		for (int i = 5; i <= Math.floor(Math.sqrt(n)); i += 6)//Math.floor返回小于或等于给定数的最大整数
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
		return true;
	}
           

2.求完质数后分解因子。首先要将找到的质因子打印出来，但是因为8=222,所以我们不能只求出一个质数因子后便直接继续寻找下一个质数因子。如果我们找出2，再让8直接找质数因子，我们找不到。那么就会打印 8=2*。所以找到一个质因子后，便将哪这个数除以质因子获得的数去找质因子。比如上述例子我们拿4去寻找质因子，找到2；再拿2去找……

代码如下：

import java.util.Scanner;

public class PrimeFactor {

	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int m = scn.nextInt();
		int n = scn.nextInt();

		for (int i = m; i <= n; i++) {
			int temp = i;
			String s = temp + "=";

			for (int j = 2; j <= temp; j++) {
				if (isPrime(j)) {//
					while (temp % j == 0) {
						s = s + j + "*";
						temp = temp / j;//
					}
				}
			}
			System.out.println(s.substring(0, s.length() - 1));
		}
	}

	public static boolean isPrime(int n) {
		if (n == 2 || n == 3)
			return true;
		if (n % 6 != 1 && n % 6 != 5)
			return false;
		for (int i = 5; i <= Math.floor(Math.sqrt(n)); i += 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
		return true;
	}
}