首頁 >Java >java教程 >Java語法實例分析

Java語法實例分析

PHPz
PHPz轉載
2023-05-16 19:28:131050瀏覽

一,質數求解的n種境界

1.1,暴力循環求解

public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 2;i <= 100;i++){//素数从2开始,所以从2开始产生到100的数
            int flg = 1;//假设是素数
            for(int j = 2;j < i;j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数!");
            }
        }
    }
}

1.2,試除前一半數

public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 2;i <= 100;i++){//素数从2开始,所以从2开始产生到100的数
            int flg = 1;//假设是素数
            for(int j = 2;j < i/2;j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数!");
            }
        }
    }
}

可以發現,我們一個數字都是可以拆成兩個數的乘法的,例如16:可以是1 16,2 * 8,4*4,可以看到,前半部的數都是小於其自身的一半的,所以我們只需要檢測這前半部數能否被其自身整除了,因為只要前半部有的話,後半部肯定有一個數與之對應相乘能夠得到自身,所以這就又減少了一半的工作量。 *

1.3,試除小於自身開根號的數

import java.lang.Math;
public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 2;i <= 100;i++){//素数从2开始,所以从2开始产生到100的数
            int flg = 1;//假设是素数
            for(int j = 2;j <= (int)(Math.sqrt(i));j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数!");
            }
        }
    }
}

還是剛才差不多的原理,只不過把範圍又縮小了,因為一個數拆分成兩個數的乘積的形式的話,前面的那個數不只是小於其自身的一半,其實根本上是不可能大於其開平方的值的,就比如16,其實前半部的數不會大於4,因為大於4後可以看到不可能會有某個數能夠與另一個數乘了等於16了,當然2 * 8,8 * 2這只算前面一種就好了

1.4,在奇數中尋找

import java.lang.Math;
public class TestDemo220427 {
    public static void main(String[] args) {
//        这里以求取1~100之间的素数为例
        for(int i = 1;i <= 100;i += 2){//从1开始,产生到100的奇数
            int flg = 1;//假设是素数
            if(i == 1){
                System.out.println((i+1) + "是素数!");//2这里需要单拎出来考虑,比较特殊
                continue;
            }
            for(int j = 2;j <= (int)(Math.sqrt(i));j++){
                if(i%j == 0){
                    flg = 0;
                }
            }
            if(flg == 1){
                System.out.println(i + "是素数!");
            }
        }
    }
}

我們知道,除了2這個特例,所有的偶數不可能是質數,因為最起碼就能夠被2整除,所以在範圍內進行考慮的時候,就只需要檢測奇數就好了,就把外層循環的次數減少了。

其實還有方法可以繼續優化,這裡就不再給大家一一列舉了,如果大家有興趣的話可以去查查,很多博主寫的很詳細深入!

二,閏年問題

public class TestDemo220427 {
    public static boolean isleapYear(int year){
        if((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)){
            return true;
        } else{
            return false;
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入年份:");
        int year = scan.nextInt();
        boolean ret = isleapYear(year);
        if(ret == true){
            System.out.println(year + "是闰年!");
        }else{
            System.out.println(year + "不是闰年!");
        }
    }
}

這裡就只需要知道閏年的判斷標準就可以很好的把題解出來。

三,求最大公約數以及最小公倍數

3.1,求最大公約數

import java.util.Scanner;
public class TestDemo220427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int m = 0;
        while((m = a%b) != 0){//辗转相除法
            a = b;
            b = m;
        }
        System.out.println(b);
    }
}

3.2,求最小公倍數

import java.util.Scanner;
public class TestDemo220427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        for(int i = 1;i > 0;i++){
            if((a*i)%b == 0){
                System.out.println("最小公倍数:" + a*i);
                break;
            }
        }
    }
}

其實還有一個公式,假設最大公約數是m,則最小公倍數是(a*b)/m。

四,自冪數問題

import java.lang.Math;
public class TestDemo220427 {
    public static boolean isNarnum(int num,int count){
        int sum = 0;
        int tmp = num;
        while(tmp != 0){
            sum += Math.pow(tmp%10,count);
            tmp /= 10;
        }
        if(sum == num){
            return true;
        }else{
            return false;
        }
    }
    public static void main(String[] args) {
//        判断一个数是不是自幂数
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数:");
        int num = scan.nextInt();
        int count = 0;
        int tmp = num;
        while(tmp != 0){
            count++;
            tmp /= 10;
        }
        boolean ret = isNarnum(num,count);
        if(ret == true){
            System.out.println(num + "是一个" + count +"位自幂数!");
        }else{
            System.out.println(num + "不是自幂数!");
        }
    }
}

五,統計二進位位元中1的個數

5.1,循環右移位元與1

import java.util.Scanner;
public class TestDemo220427 {
    public static int getOnecount(int num){
        int count = 0;
        while(num != 0){//右移后不为0就继续统计
            if((num& 1) == 1){
                count++;
            }
            num = num >> 1;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数:");
        int num = scan.nextInt();
        int ret =  getOnecount(num);
        System.out.println(num + "的二进制位中1的个数 :" + ret);
    }
}

註:這段程式碼是有bug的,因為對於負數是統計不了的,負數的二進位最高符號位為1,右移補符號位那就是一直在高位補1,那迴圈就死迴圈了。

解:num = num >> 1 ——> 改成num = num >>> 1,用無符號右移,這樣高位只會補0,對於正數負數都適用。

拓展:可能有人會問,既然可以右移,那為啥不能左移?

答案是 : 確實可以左移,但是不推薦,效率太低。

public class TestDemo220427 {
    public static int getOnecount(int num){
        int count = 0;
        for(int i = 0;i < 32;i++){
            if((num & (1 << i)) != 0){
                count++;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数:");
        int num = scan.nextInt();
        int ret =  getOnecount(num);
        System.out.println(num + "的二进制位中1的个数 :" + ret);
    }
}

這時候就不是把這個數去左移了,而是把1左移,然後去與這個數按位與,因為這樣的結果就只有可能是0或非0,非0就表示1左移後的結果的1所在的位置對應的這個數的位置上是1,所以這個時候就統計一下。雖然這個方法也可以解決問題,但是你需要左移32次,因為你無法得知這個數字前面有多少個1,只能對所有的位元進行比較。

5.2,n &(n-1)消除1的原理

import java.util.Scanner;
public class TestDemo220427 {
    public static int getOnecount(int num){
        int count = 0;
        while(num != 0){
            num = num&(num-1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数:");
        int num = scan.nextInt();
        int ret =  getOnecount(num);
        System.out.println(num + "的二进制位中1的个数 :" + ret);
    }

這種方法正數負數都可以用,並且效率很高,每次按位與num-1 一次,就會消掉一個1。

擴充:用這個方法判斷某一個數是不是2的k次方。

import java.util.Scanner;
public class TestDemo220427 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数:");
        int num = scan.nextInt();
        if((num & (num-1)) == 0){
            System.out.println("是2的k次方数!");
        }else{
            System.out.println("不是2的k次方数!");
        }
    }
}

以上是Java語法實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:yisu.com。如有侵權,請聯絡admin@php.cn刪除