Java经典算法+分析

1：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

• 分析：兔子对数的规律为数列1,1,2,3,5,8,13,21....，即每过3个月兔子的对手是前两个月之和，运用递归的思想即math(x-1)+math(x-2)。好程序如下：

public class Test01 {
    public static void main(String[] args) {
        int i = 0;
        for(i=1;i<=20;i++){
            System.out.println("第"+i+"月的兔子个数为:"+math(i)*2);
        }
    }

    private static int math(int i) {
        if(i==1||i==2){
            return 1;
        }
        return math(i-1)+math(i-2);
    }
}

2：判断101-200之间有多少个素数，并输出所有素数。

• 分析：如果该数能被2整除即不是素数反之即是素数，代码如下：

public class Test02 {
    public static void main(String[] args) {
        int count = 0;
        int j = 2;
        for (int i = 101; i < 201; i++) {
            for(j=2;j<i;j++) {
                if ((i % j) == 0) {
                    break;
                }
            }
            if (j==i) {
                count++;
                System.out.println(i+"这个数为素数");
            }
        }
        System.out.println("101-200之间一共"+count+"个素数");
    }
}

3：打印出所有的 "水仙花数 "，所谓 "水仙花数 "是指一个三位数，其各位数字立方和等于该数本身。 例如：153是一个 "水仙花数，因为153=1的三次方＋5的三次方＋3的三次方。

• 分析：将各位数取出后进行Math.pow(x,3)并求和如果等于原始数即为水仙花数，代码如下：

public class Test3 {
    public static void main(String[] args) {
        for (int i = 100; i <= 999; i++) {
            if (i == math(i)) {
                System.out.println(i + "是一个水仙花数");
            }
        }
    }

    private static int math(int i) {
        int g = i%10;
        int s = i%100/10;
        int b = i/100;
        return (int) (Math.pow(b,3)+Math.pow(s,3)+Math.pow(g, 3));
    }
}

4：将一个正整数分解质因数。例如：输入90,打印出90=233*5。

• 分析：如果该数能被一个小于它的数整除，那么利用递归将商传递下去，直到得到一个只能被该数本身整除的数停止递归。代码如下:

public class Test04 {
    StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个正整数:");
        String n = scan.next();
        System.out.print(n+"=");
        math(Integer.valueOf(n));
    }

    private static void math(int n) {
        for(int i=2;i<n;i++){
            if (n%i==0) {
                System.out.print(i+"*");
                math(n/i);
            }
        }
        System.out.println(n+"");
        System.exit(0);// 不能少了这一句
    }
}

5：利用条件运算符的嵌套来完成此题：学习成绩> =90分的同学用A表示，60-89分之间的用B表示，60分以下的用C表示。

• 分析：条件运算符的格式判断条件?条件成立的结果:条件不成立的结果。代码如下:

public class Test05 {
    public static void main(String[] args) {
        Random random = new Random();
        int n = random.nextInt(101);
        String str = (n<60?"C":(n<90?"B":"A"));
        System.out.println("该学生的成绩是:"+n+",评级为:"+str);
    }
}

6：输入两个正整数m和n，求其最大公约数和最小公倍数。

• 分析：辗转相除法，又称欧几里得算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。这里刚开始的时候使用一种比较笨的方式来求最小公倍数，作为一种思路也发给大家看看啊。代码如下:

public class Test06 {
    public static void main(String[] args) {
        Random random = new Random();
        int a = random.nextInt(300);
        int b = random.nextInt(300);
        int gcd = countGCD(a,b);// 求最大公约数的方法
        //int lcm = countLCM(11,10);// 求最大公倍数的方法
        int lcm = a*b/gcd;// 两个数的乘积等于最大公约数与最小公倍数的乘积
        System.out.println(a+","+b+" 的最大公约数为:"+gcd);
        System.out.println(a+","+b+" 的最小公倍数为:"+lcm);
    }

    private static int countLCM(int a, int b) {
        int t = a>b?a:b;
        while(true){
            if(t%a==0&&t%b==0){
                return t;
            }
            t++;
        }
    }

    private static int countGCD(int a, int b) {
        while(true){
            if((a=a%b)==0){
                return b;
            }
            if((b=b%a)==0){
                return a;
            }
        }
    }
}

7：输入一行字符，分别统计出其\英文字母、汉字的个数。

• 分析：利用正则表达式来进行统计，[\u4e00-\u9fa5]代表匹配汉字的正则表达式。代码如下:

public class Test07 {
    public static void main(String[] args) {
        String m1 = "[a-zA-Z]";// 匹配字母的正则表达式
        String m2 = "[\u4e00-\u9fa5]";// 匹配汉字的正则表达式
        int e = 0;// 统计字母的个数
        int h = 0;// 统计汉字的个数
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一串字符:");
        char[] cArr = scan.nextLine().toCharArray();
        String[] strArr = new String[cArr.length];
        for (int i = 0; i < cArr.length; i++) {
            strArr[i] = String.valueOf(cArr[i]);
        }
        for(String str:strArr){
            if(str.matches(m1)){
                e++;
            }
            if(str.matches(m2)){
                h++;
            }
        }
        System.out.println("输入字母的个数为:"+e);
        System.out.println("输入汉字的个数为:"+h);
    }
}

8：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加有键盘控制。

• 分析：我的思考是用户输入几个数相加，每次循环控制加数2出现的个数。网上的另外一种解法写的更加巧妙，循环内部通过自身不断的乘10加自身来完成每次计算时应出现的加数。具体代码如下:

public class Test08 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入几个数相加:");
        int n = scan.nextInt();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<=i;j++){
                sb.append("2");
            }
            System.out.println(sb.toString());
            sum+=Integer.parseInt(sb.toString());
        }
        System.out.println("和为:"+sum);
    }
}
Other:
private static void other(int n) {
        int sum=0;
        int t=2;
        if(n==0){
            sum = 0;
        }else{
            sum = t;
        }
        for(int i=1;i<n;i++){
            t = t*10+2;
            sum+=t;
        }
        System.out.println("other和为:"+sum);
    }

9：一个数如果恰好等于它的因子之和，这个数就称为 "完数 "。例如6=1＋2＋3.编程，找出1000以内的所有完数。

• 分析：将该数能够整除的数全部相加，如果等于该数本身即是完数。具体代码如下:

public class Test09 {
    public static void main(String[] args) {
        System.out.println("1000以内的所有完数包括:");
        for(int i=1;i<=1000;i++){
            int sum=0;
            for(int j=1;j<i;j++){
                if(i%j==0){
                    sum+=j;
                }
            }
            if(sum==i){
                System.out.print(i+" ");    
            }
        }
    }
}

10：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在 第10次落地时，共经过多少米？第10次反弹多高？

• 分析：除第一次落地以外其他每次落地都要经历上升和下落两段距离。具体代码如下:

public class Test10 {
    public static void main(String[] args) {
        double l = 100;
        double sum = 100;
        for(int i=1;i<2;i++){
            sum+=l;
            l = l/2.0;
        }
        System.out.println("第10次落地时经过了："+sum+" 米");
        System.out.println("第10次反弹 "+l+" 米");
    }
}

11：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

• 分析：组成的三位数各位数都不相等。具体代码如下:

public class Test11 {
    public static void main(String[] args) {
        int n=0;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                for (int k = 1; k <= 4; k++) {
                    if (i!=k&&j!=k&&i!=j) {
                        n++;
                        System.out.println(i*100+j*10+k);
                    }
                }
            }
        }
        System.out.println("一共组成了 "+n+" 个三位数");
    }
}

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

• 分析：这里需要用到一个方法Math.floor(double)，该方法将返回一个无限接近该double值的一个整数。具体代码如下:

public class Test12 {
    public static void main(String[] args) {
        System.out.println("Math.floor():"+Math.floor(101.1));
        long k=0;
        for (k = 1; k < 100000; k++) {
            if (Math.floor(Math.sqrt(k+100))==Math.sqrt(k+100)&&Math.floor(Math.sqrt(k+168))==Math.sqrt(k+168)) {
                System.out.println(k);
            }
        }
    }
}

13：输入某年某月某日，判断这一天是这一年的第几天？

• 分析：看了一下网上的解法，解的不是很巧妙，我这里给大家一个巧妙的解法利用case语句的穿透来实现。具体代码如下:

public class Test13 {
    public static void main(String[] args) {
        int day = 0;
        int month = 0;
        int year = 0;
        int sum = 0;
        System.out.println("请输入年,月,日:");
        Scanner scan = new Scanner(System.in);
        year = scan.nextInt();
        month = scan.nextInt();
        day = scan.nextInt();
        switch(month){
        case 12:
            sum += 30;
        case 11:
            sum += 31;
        case 10:
            sum += 30;
        case 9:
            sum += 31;
        case 8:
            sum += 31;
        case 7:
            sum += 30;
        case 6:
            sum += 31;
        case 5:
            sum += 30;
        case 4:
            sum += 31;
        case 3:
            sum += 28;
        case 2:
            sum += 31;
        case 1:
            sum += day;
        }
        // 判断是否为闰年
        if((year%400==0||(year%4==0&&year%100!=0)) && month>2){
            sum++;
        }
        System.out.println("你输入的日期是"+year+"年的第 "+sum+" 天");
    }
}

14：输入三个整数x,y,z，请把这三个数由小到大输出。

• 分析：注意比较顺序，x与y比，x与z比,最后y与z再比。具体代码如下:

public class Test14 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入三个整数:");
        int x = scan.nextInt();
        int y = scan.nextInt();
        int z = scan.nextInt();
        int t = 0;
        if (x > y) {
            t = x;
            x = y;
            y = t;
        }
        if (x > z) {
            t = x;
            x = z;
            z = t;
        }
        if (y > z) {
            t = y;
            y = z;
            z = t;
        }
        
        System.out.println("这三个数由小到大输出:" + x + " " + y + " " + z);
    }
}

15：输出9*9口诀。

• 分析：这个太基础了吧，注意转义符的用法输出更美观。具体代码如下:

public class Test15 {
    public static void main(String[] args) {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.print(j+"*"+i+"="+(i*j)+"\t");
            }
            System.out.print("\n");
        }
    }
}

16：猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个 第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下 的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。

• 分析：采取逆向思维，从第10天往前推，前一天的桃子数总是后一天桃子的（起始数+1）*2。具体代码如下:

public class Test16 {
    public static void main(String[] args) {
        int n = 1;
        for(int i=9;i>=1;i--){
            n=2*(n+1);
        }
        System.out.println("第一天一共摘了"+n+"个桃子");
    }
}
网上利用递归思想来实现代码如下：
private static int total(int day) {
        if(day==10){
            return 1;
        } else {
            // 当天桃子数总是（后一天桃子数+1）*2
            return (total(day+1)+1)*2;
        }
    }

17：题目：两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。

• 分析：采用穷举法，把所有组合都罗列出来，再按指定条件进行筛选，不知道大家还有没有更简便的方法。具体代码如下:

public class Test17 {
    public static void main(String[] args) {
        String[] A = new String[] { "a", "b", "c" };
        String[] B = new String[] { "x", "y", "z" };
        List<String> list = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    String str = B[i] + B[j] + B[k];
                    if(str.indexOf("x")!=-1 && str.indexOf("y")!=-1 && str.indexOf("z")!=-1){
                        if (str.indexOf("x") != 0 && str.indexOf("x") != 2
                                && str.indexOf("z") != 2) {
                            list.add(str);
                            System.out.println(str);
                            System.out.println(str.indexOf("x"));
                        }
                    }   
                }
            }
        }
        for(String arr:list){
            char[] cArr = arr.toCharArray();
            for(int i=0;i<A.length;i++){
                System.out.println(A[i] + "的对手为: " + cArr[i]);
            }
            System.out.println("-------------------------");
        }
    }
}

18：题目：发现文件夹内部的所有文件名以及文件夹名称（包括子文件夹内部的文件及文件夹）。

• 分析：采用递归算法。具体代码如下:

public class TestFile5 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<File> list = findFiles("E:/test/1");
        
        ArrayList<String> fileName = new ArrayList<>();
        ArrayList<String> dirName = new ArrayList<>();
        
        getName(list, fileName, dirName);
        
        System.out.println("All files name: " + fileName);
        System.out.println("All dirs name: " + dirName);
        
    }

    private static void getName(List<File> list, ArrayList<String> fileName, ArrayList<String> dirName) {
        int n = list.size();
        for(int i=0;i<n;i++) {
            if(list.get(i).isFile()) {
                fileName.add(list.get(i).getName());
            } else {
                getName(findFiles(list.get(i).getAbsolutePath()),fileName,dirName);
                dirName.add(list.get(i).getName());
            }
        }
    }

    private static List<File> findFiles(String path) {
        File fileDir = new File(path);
        
        File[] fileList = fileDir.listFiles();
        List<File> list = Arrays.asList(fileList);
        return list;
    }

}