Java经典算法（二)

全栈程序员站长

发布于 2022-09-08 11:23:35

6370

发布于 2022-09-08 11:23:35

大家好，又见面了，我是你们的朋友全栈君。

【程序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;}
        }
    }
}

程序运行结果：

【程序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;
    }
}

程序运行结果：

【程序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次，提高效率。减少循环次数。 程序运行结果：

【程序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);     
        }
    }
}

程序运行结果：

【程序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;}
        }
    }
}

程序运行结果：

【程序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);
        }
    }
}

程序运行结果：

用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费大量时间。 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+"天。");
        }
    }
}

题目：输入某年某月某日，判断这一天是这一年的第几天？ 程序运行结果：

【程序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);
   }
    }
}

程序运行结果：

【程序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);
        }  
    }
}

程序运行结果：

【程序18】

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

概率算法思想

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

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

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

如果均匀的在正方形中撒点，落入阴影部分的概率为π/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;
    }
}

程序运行结果：

路阻且长之Java学习：

API中的重要类（一）： https://blog.csdn.net/Veer_c/article/details/103803248 API中的重要类（二）： https://blog.csdn.net/Veer_c/article/details/103807515 API中的重要类（三）： https://blog.csdn.net/Veer_c/article/details/103808054

Java中的IO流（一）： https://blog.csdn.net/Veer_c/article/details/103833045 Java中的IO流（二）： https://blog.csdn.net/Veer_c/article/details/103833423 Java中的IO流（三）： https://blog.csdn.net/Veer_c/article/details/103833811

Java多线程（一）： https://blog.csdn.net/Veer_c/article/details/103842078 Java多线程（二）： https://blog.csdn.net/Veer_c/article/details/103842263 Java多线程（三）： https://blog.csdn.net/Veer_c/article/details/103842317 Java多线程（四）： 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数据库（二）： https://blog.csdn.net/Veer_c/article/details/103844537 MySQL数据库（三）： https://blog.csdn.net/Veer_c/article/details/103844739

JDBC技术（一）： https://blog.csdn.net/Veer_c/article/details/103845176 JDBC技术（二）： https://blog.csdn.net/Veer_c/article/details/103879890 JDBC技术（三）： https://blog.csdn.net/Veer_c/article/details/103880021 JDBC技术（四）： https://blog.csdn.net/Veer_c/article/details/103882264

HTML的基础框架（一）： https://blog.csdn.net/Veer_c/article/details/103882385 HTML的基础框架（二）： https://blog.csdn.net/Veer_c/article/details/103882684

CSS入门（一） https://blog.csdn.net/Veer_c/article/details/103882856 CSS入门（二）： https://blog.csdn.net/Veer_c/article/details/103883102

JavaScript实用案例与常见问题（一）： https://blog.csdn.net/Veer_c/article/details/103894959 JavaScript实用案例及常见问题（二）： https://blog.csdn.net/Veer_c/article/details/103895166

BOM编程详解： https://blog.csdn.net/Veer_c/article/details/103895433

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/156647.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https