Java经典算法（二)

清疚 2023-02-11 04:38 17阅读 0赞

## 【程序10】 ##

**题目**：将一个正整数分解质因数。例如：输入90,打印出90=233\*5。  
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：  
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。  
(2)如果n != k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行第一步。  
(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。

**解题代码：**

import java.util.Scanner;
    public class Test10 { 
        public static void main(String[] args) { 
            Scanner read=new Scanner(System.in);
            while(read.hasNext()){ 
            int n=read.nextInt();
            fenjiezhiyinshu(n);
            }
        }
        public static void fenjiezhiyinshu(int n ){ 
            for(int k=2;k<=n;k++){ 
                if(n==k) { 
                    System.out.println("质因数包括："+k);
                break;}
                else if (n%k==0) { 
                    System.out.println("质因数包括："+k);
                    n=n/k;}
            }
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70]

## 【程序11】 ##

**题目**：输入两个正整数m和n，求其最大公约数和最小公倍数。  
**分析**：在循环中，只要除数不等于0，用较大数除以较小的数，将小的一个数作为下一轮循环的大数，取得的余数作为下一轮循环的较小的数，如此循环直到较小的数的值为0，返回较大的数，此数即为最大公约数，最小公倍数为两数之积除以最大公约数。

**解题代码：**

import java.util.*;
    public class Test11{ 
        public static void main(String[] args) { 
            Scanner read =new Scanner(System.in);
            while(read.hasNext()){ 
            int a=read.nextInt(),b=read.nextInt();
            int  Maxyueshu= gongyinshu(a, b);
            System.out.println("您好：您输入的数字"+a+"和"+b+"的最小公因数为："+Maxyueshu);
            System.out.println("您好：您输入的数字"+a+"和"+b+"的最大公倍数为："+a*b/Maxyueshu);
            }
        }
        public static int gongyinshu(int a,int b) { 
            if(a<b) { 
                b+=a;
                a=b-a;
                b=b-a;
            }
            while(b!=0) { 
                if(a==b)
                    return a;
                int x=b;
                b=a%b;
                a=x;
            }
            return a;
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 1]

## 【程序12】 ##

**题目**：一个数如果恰好等于它的因子之和，这个数就称为 "完数 "。例如6=1＋2＋3， 找出N以内的所有完数。  
**解题代码：**

import java.util.*;
    public class Test12{ 
    public static void main(String[] args){ 
        Scanner read=new Scanner(System.in);
        while(read.hasNext()){ 
            int N=read.nextInt();
         for(int i=1;i<=N;i++){ 
             int s=0;
             for(int j=1;j<=i/2;j++){ //此处循环i/2次，提高效率。
                if(i % j==0){ 
                    s=s+j;
                    if(s==i)
                    System.out.print(i+" ");    
                }
             }
         }
         System.out.println("\n上行数据为"+N+"以内所有的完数");
        }
     }
    }

总结：第二个for循环，即代码第九行，循环i/2次，提高效率。减少循环次数。  
**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 2]

【程序13】

**题目**：输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。  
**解题代码：**

import java.util.*;
    public class Test13{ 
        public static void main(String[] args) { 
            Scanner read=new Scanner(System.in);
            while(read.hasNext()){ 
            int zimucount=0;
            int spacecount=0;
            int numcount=0;
            int othercount=0;
            String S=read.nextLine();
            for(char c:S.toCharArray()) { 
                if(Character.isLetter(c)) { 
                    zimucount++;
                }else if(Character.isDigit(c)) { 
                    numcount++;
                }else if(Character.isSpaceChar(c)){ 
                    spacecount++;
                }else { 
                    othercount++;
                }
            }
            System.out.println("您好：您输入的字符串："+S+"中\n英文字母个数为："+zimucount+"\n空格数为"
            +spacecount+"\n阿拉伯数字个数为"+numcount+"\n其它字符个数为："+othercount);     
            }
        }
    }

**程序运行结果：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 3]

## 【程序14】 ##

**题目**：一个整数，它加上100后是一个完全平方数，加上168又是一个完全平方数，请问该数是多少？

**程序分析**：先将该数加上100后再开方，再将该数加上268后再开方，如果开方后的结果满足条件，即是结果。**因为不知到循环次数，故for循环判断语句恒为真，找到即跳出循环，时间最优，因为某数最小加100，所以循环变量i的初始值应为-100。**

**解题代码：**

public class Test14 { 
    public static void main(String[] args) { 
        for(int i=-100;true;i++) { 
        if(Math.sqrt(i+100)%1==0&&Math.sqrt(i+168)%1==0) { 
        System.out.println(i);
        break;}
            }
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 4]

## 【程序15】 ##

**题目**：查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。  
**1.暴力匹配算法**  
**解题代码：**

import java.util.*;
    public class Test15{ 
        public static void main(String[] args){ 
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){ 
                String s1 = in.nextLine();
                String s2 = in.nextLine();
                String max = s1.length() >= s2.length()?s1:s2;
                String min = s1.length() >= s2.length()?s2:s1;
                int l = 0;
                String s ="";
                for(int i=0;i<max.length();i++){ 
                    for(int j=i+1;j<=min.length();j++){ 
                        if(max.contains(min.substring(i,j)) && j-i>l){ 
                            l=j-i;
                            s=min.substring(i,j);
                        }
                    }
                }
                System.out.println("您好：你所输入的字符串："+s1+"与字符串"+s2+"中最先出现的最长公共子串为：\n"+s);
            }
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 5]  
**用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费大量时间。**  
**1.KMP算法**  
***未完待续……***

## 【程序16】 ##

**解题代码：**

import java.util.*;
    public class Test16 { 
        public static void main (String[]args){ 
            int [] yuetianshu={ 0,0,31,59,90,120,151,181,212,243,273,304,334};
            Scanner read= new Scanner(System.in);
            System.out.println("请输入年,月,日");  
            while(read.hasNext()){ 
                int year=read.nextInt(),month=read.nextInt(),day=read.nextInt(),sum=0;
                sum=yuetianshu[month]+day; /*再加上某天的天数*/ 
                if((year%400==0||(year%4==0&&year%100!=0))&& month>2)/*判断是不是闰年*/ 
                sum++;
            System.out.println("您好：您所输入的"+year+"年"+month+"月"+day+"日是当年的第"+sum+"天。");
            }
        }
    }

**题目**：输入某年某月某日，判断这一天是这一年的第几天？  
**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 6]

## 【程序17】 ##

**题目**：求1+2!+3!+…+N!的和。  
**解题代码：**

import java.util.*;
    public class Test17{ 
    public static void main(String[] args) { 
        Scanner read=new Scanner(System.in);
        while(read.hasNext()){ 
            int N=read.nextInt();
            long sum=0,ver=1;
            for(int i=1;i<=N;i++) { 
            ver=ver*i;
            sum+=ver;
            }
        System.out.println("1~"+N+"的阶乘和为："+sum);
       }
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 7]

## 【程序17】 ##

**题目**：输入一个int型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。  
**解题代码**：直接暴力解决。

import java.util.*;
    public class Test18{ 
        public static void main(String[] args){ 
            Scanner in=new Scanner(System.in);
            while(in.hasNext()){ 
                String str=in.next();
                String a=str.substring(str.length()-1);
                for(int i=str.length()-2;i>=0;i--){ 
                        if(!a.contains(str.substring(i,i+1)))
                             a+=str.substring(i,i+1);
                }
                System.out.println(a);
            }  
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 8]

## 【程序18】 ##

**题目**：经典实例蒙特卡罗π。

## **概率算法思想** ##

**基本算法思想**：  
概率算法执行的基本过程如下：  
(1)将问题转化为相应的几何图形S, S 的面积是容易计算的，问题的结果往往对应几何图形中某一部分S1 的面积。  
(2)然后，向几何图形中随机撒点。  
(3)统计几何图形S 和 S1 中的点数。根 据 S 的面积和S1 面积的关系以及各图形中的点数来计算得到结果。  
(4) 判断上述结果是否在需要的精度之内，如果未达到精度则执行步骤(2)。如果达到精度,则输出近似结果。

**概率算法大致分为如下4 种形式：**  
**• 数值概率算法。  
• 蒙特卡罗 （MonteCarlo)算法。  
• 拉斯维加斯 （Las Vegas)算法。  
• 舍伍德 （Sherwood)算法。**

**题目：经典实例蒙特卡罗π**  
![蒙特卡罗算法解析图][2020052210070489.png]  
如果均匀的在正方形中撒点，落入阴影部分的概率为π/4  
根据概率统计的规律，只要点足够多就可以得到非常近似的结果

**解题代码**：

import java.util.*;
    public class Test18Pi{ 
    public static void main(String[] args) { 
        Scanner read=new Scanner(System.in);
        while(read.hasNext()){ 
            long n=read.nextLong();
            System.out.println("根据您的输入计算获得PI的近似值为："+getPI(n));}}
    public static double getPI(long n){ 
    	double x,y;
    	int sum = 0;
    	for(int i = 0;i<n*n;i++){ 
    		x = Math.random();
    		y = Math.random();
    		if(x*x+y*y<=1){ 
    			sum++;
    		}
    	}
    	return sum*4.0/n/n;
        }
    }

**程序运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 9]

## 路阻且长之Java学习： ##

**[API中的重要类（一）：][API]  
https://blog.csdn.net/Veer\_c/article/details/103803248  
[API中的重要类（二）：][API 1]  
https://blog.csdn.net/Veer\_c/article/details/103807515  
[API中的重要类（三）：][API 2]  
https://blog.csdn.net/Veer\_c/article/details/103808054**

**[Java中的IO流（一）：][Java_IO]  
https://blog.csdn.net/Veer\_c/article/details/103833045  
[Java中的IO流（二）：][Java_IO 1]  
https://blog.csdn.net/Veer\_c/article/details/103833423  
[Java中的IO流（三）：][Java_IO 2]  
https://blog.csdn.net/Veer\_c/article/details/103833811**

**[Java多线程（一）：][Java]  
https://blog.csdn.net/Veer\_c/article/details/103842078  
[Java多线程（二）：][Java 1]  
https://blog.csdn.net/Veer\_c/article/details/103842263  
[Java多线程（三）：][Java 2]  
https://blog.csdn.net/Veer\_c/article/details/103842317  
[Java多线程（四）：][Java 3]  
https://blog.csdn.net/Veer\_c/article/details/103842602**

**[网络编程上（UDP）：][UDP]  
https://blog.csdn.net/Veer\_c/article/details/103843591  
[网络编程下（TCP）：][TCP]  
https://blog.csdn.net/Veer\_c/article/details/103843825**

**[MySQL数据库（一）：][MySQL]  
https://blog.csdn.net/Veer\_c/article/details/103844059  
[MySQL数据库（二）：][MySQL 1]  
https://blog.csdn.net/Veer\_c/article/details/103844537  
[MySQL数据库（三）：][MySQL 2]  
https://blog.csdn.net/Veer\_c/article/details/103844739**

**[JDBC技术（一）：][JDBC]  
https://blog.csdn.net/Veer\_c/article/details/103845176  
[JDBC技术（二）：][JDBC 1]  
https://blog.csdn.net/Veer\_c/article/details/103879890  
[JDBC技术（三）：][JDBC 2]  
https://blog.csdn.net/Veer\_c/article/details/103880021  
[JDBC技术（四）：][JDBC 3]  
https://blog.csdn.net/Veer\_c/article/details/103882264**

**[HTML的基础框架（一）：][HTML]  
https://blog.csdn.net/Veer\_c/article/details/103882385  
[HTML的基础框架（二）：][HTML 1]  
https://blog.csdn.net/Veer\_c/article/details/103882684**

**[CSS入门（一）][CSS]  
https://blog.csdn.net/Veer\_c/article/details/103882856**  
**[CSS入门（二）：][CSS 1]  
https://blog.csdn.net/Veer\_c/article/details/103883102**

**[JavaScript实用案例与常见问题（一）：][JavaScript]  
https://blog.csdn.net/Veer\_c/article/details/103894959  
[JavaScript实用案例及常见问题（二）：][JavaScript 1]  
https://blog.csdn.net/Veer\_c/article/details/103895166**

**[BOM编程详解：][BOM]  
https://blog.csdn.net/Veer\_c/article/details/103895433**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521181756112.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521184210975.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200521213913239.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020052121434751.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200521195233994.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200521214642466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200522073450720.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200521220604186.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200521221756572.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[2020052210070489.png]: https://img-blog.csdnimg.cn/2020052210070489.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200522102436516.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZlZXJfYw==,size_16,color_FFFFFF,t_70
[API]: https://blog.csdn.net/Veer_c/article/details/103803248
[API 1]: https://blog.csdn.net/Veer_c/article/details/103807515
[API 2]: https://blog.csdn.net/Veer_c/article/details/103808054
[Java_IO]: https://blog.csdn.net/Veer_c/article/details/103833045
[Java_IO 1]: https://blog.csdn.net/Veer_c/article/details/103833423
[Java_IO 2]: https://blog.csdn.net/Veer_c/article/details/103833811
[Java]: https://blog.csdn.net/Veer_c/article/details/103842078
[Java 1]: https://blog.csdn.net/Veer_c/article/details/103842263
[Java 2]: https://blog.csdn.net/Veer_c/article/details/103842317
[Java 3]: https://blog.csdn.net/Veer_c/article/details/103842602
[UDP]: https://blog.csdn.net/Veer_c/article/details/103843591
[TCP]: https://blog.csdn.net/Veer_c/article/details/103843825
[MySQL]: https://blog.csdn.net/Veer_c/article/details/103844059
[MySQL 1]: https://blog.csdn.net/Veer_c/article/details/103844537
[MySQL 2]: https://blog.csdn.net/Veer_c/article/details/103844739
[JDBC]: https://blog.csdn.net/Veer_c/article/details/103845176
[JDBC 1]: https://blog.csdn.net/Veer_c/article/details/103879890
[JDBC 2]: https://blog.csdn.net/Veer_c/article/details/103880021
[JDBC 3]: https://blog.csdn.net/Veer_c/article/details/103882264
[HTML]: https://blog.csdn.net/Veer_c/article/details/103882385
[HTML 1]: https://blog.csdn.net/Veer_c/article/details/103882684
[CSS]: https://blog.csdn.net/Veer_c/article/details/103882856
[CSS 1]: https://blog.csdn.net/Veer_c/article/details/103883102
[JavaScript]: https://blog.csdn.net/Veer_c/article/details/103894959
[JavaScript 1]: https://blog.csdn.net/Veer_c/article/details/103895166
[BOM]: https://blog.csdn.net/Veer_c/article/details/103895433