藍橋杯基礎（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;
	}
}