java算法基础范例

题目1：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 
　　　　1.程序分析： 兔子的规律为数列1,1,2,3,5,8,13,21....

分析：我分析发现其实头两个数不变，然后后面的数字等于前面两个数字相加，这是就这个题目直接可以看出的规律

//那么就存在一个解法pre2+pre1=pre;pre2=pre1;pre1=pre;
//通过不断计算前面的数据 产生新的数据
import java.util.Scanner;

public class Test3A {
    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        int count=scanner.nextInt();
        int pre=count;
        int now=count;
        System.out.printf("%d %d ",pre,now);
        for(int i=3;i<20;i++){
            int temp=count;
            count=count+pre;
            pre=temp;
            System.out.printf("%d ",count);
        }
    }
}

 或者一般性的算法，根据面向对象的思想，认为这是一个兔子类 ，有总数和新兔子数，然后不断的用 当前兔子数目=上个月兔子总数+新生兔子数；新生兔子数=上上月兔子数

import java.util.ArrayList;
import java.util.Scanner;

public class Test3B {
    static class hare{
        int count;
        int newhare;
    }
    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        int n=scanner.nextInt();
        fun(n);
    }
    private static void fun(int n) {
        ArrayList<hare> arrayList =new ArrayList<hare>();
        hare h0=new hare();
        h0.count=n;
        h0.newhare=0;
        hare h1=new hare();
        h1.count=n;
        h1.newhare=0;
        arrayList.add(h0);
        arrayList.add(h1);
        for(int i=2;i<20;i++){
            hare h=new hare();
            h.newhare=arrayList.get(i-2).count;
            h.count=arrayList.get(i-1).count+h.newhare;
            arrayList.add(h);
        }
        for(int i=0;i<20;i++){
            System.out.printf("%d ",arrayList.get(i).count);
        }
    }

}

 题目2：打印出所有的"水仙花数"，所谓"水仙花数"是指一个三位数，其各位数字立方和等于该数本身。例如： 
        153是一个"水仙花数"，因为153=1的三次方＋5的三次方＋3的三次方。 
        1.程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位

//很常见的水仙花数
public class Test4A {

    public static void main(String[] args) {
        for (int i = 100; i <= 999; i++) {
            int[] A = new int[3];
            A = test(i);
            check(A, i);
        }
    }

    private static void check(int[] a, int i2) {
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            int num = a[i];
            sum = testA(num) + sum;
        }
        if (i2 == sum) {
            System.out.println(i2);
        }
    }

    private static int testA(int num) {
        int temp = 1;
        for (int i = 0; i < 3; i++) {
            temp = num * temp;
        }
        return temp;
    }

    private static int[] test(int i) {
        int[] A = new int[3];
        int j = 0;
        int temp = 0;
        for (;;) {
            if (i >= 10) {
                temp = i % 10;
                i = i / 10;
                A[j++] = temp;
            } else {
                A[j] = i;
                break;
            }
        }
        return A;
    }
}

 题目3：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*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 Test6A {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        comput(n);
    }

    private static void comput(int n) {
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            if (n % i == 0) {
                temp = i;
                n = n / i;
                break;
            }
        }
        if (temp!=0&&n > 1) {
            System.out.printf("%d*", temp);
        } else {
            System.out.printf("%d", temp);
        }
        if (n != 1) {
            comput(n);
        }
        return;
    }

}

 改进了一下 可以少算几次 提高一下效率

public class Test6A {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        comput(n,2);
    }

    private static void comput(int n, int j) {
        int temp = 0;
        for (int i = j; i <= n; i++) {
            if (n % i == 0) {
                temp = i;
                n = n / i;
                j=i;
                break;
            }
        }
        if (temp!=0&&n > 1) {
            System.out.printf("%d*", temp);
        } else {
            System.out.printf("%d", temp);
        }
        if (n != 1) {
            comput(n,j);
        }
        return;
    }

}

 题目3：输入两个正整数m和n，求其最大公约数和最小公倍数。 
　　　　1.程序分析：利用辗除法。

import java.util.Scanner;

public class Test8 {

    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        int a=scanner.nextInt();
        int b=scanner.nextInt();
        int first=a;
        int second=b;
        int temp=0;
        if(a<b){
            temp=a;
            a=b;
            b=temp;
        }
        while(b!=0){
            temp=a%b;
            a=b;
            b=temp;
        }
        System.out.println("最大公约数："+a);
        System.out.println("最大公倍数："+first*second/a);
    }

}

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

import java.util.Scanner;

public class Test9 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        char[] arr = string.toCharArray();
        int abcCount = 0;
        int spaceCount = 0;
        int numberCount = 0;
        int otherCount = 0;
        for (int i = 0; i < arr.length; i++) {
            if (Character.isLetter(arr[i])) {
                abcCount++;
            } else if (Character.isDigit(arr[i])) {
                numberCount++;
            } else if (Character.isWhitespace(arr[i])) {
                spaceCount++;
            } else {
                otherCount++;
            }
        }
        System.out.println("字母数：" + abcCount);
        System.out.println("空格数：" + spaceCount);
        System.out.println("数字数：" + numberCount);
        System.out.println("其他数：" + otherCount);
    }

}

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

　　　　1.程序分析：关键是计算出每一项的值。

import java.util.Scanner;

public class Test10 {

    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        int s=scanner.nextInt();
        int temp=0;
        for(int i=1;i<10;i++){
            int number=ManyNumber(i,0,1,0);
            if(s==number){
                System.out.println(i);
                break;
            }
        }
        
        
    }
    //当前这个数 ,上一次的数据 ,当前是第几个下标
    private static int ManyNumber(int i, int sum, int index,int nownumber) {
        
        nownumber=i*Ten(index)+nownumber;
        sum=sum+nownumber;
        if(index==5){
            return sum;
        }
        return ManyNumber(i, sum, index+1,nownumber);
        
    }
    private static int Ten(int index) {
        int temp=1;
        for(int i=1;i<index;i++){
            temp=temp*10;
        }
        if(index==1){
            return 1;
        }
        return temp;
    }

}

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

import java.util.ArrayList;

public class Test11 {

    public static void main(String[] args) {
        for(int i=1;i<100;i++){
            ArrayList<Integer> arrayList=factor(i);
            if(i==sum(arrayList)){
                System.out.println(i);
            }
        }
    }

    private static int sum(ArrayList<Integer> arrayList) {
        int temp=0;
        for(int i=0;i<arrayList.size();i++){
            temp=temp+arrayList.get(i);
        }
        return temp;
    }

    private static ArrayList<Integer> factor(int i) {
        ArrayList<Integer> arrayList= new ArrayList<Integer>();
        for (int j = 1; j < i; j++) {
            if (i % j == 0 && i != j) {
                arrayList.add(j);
            }
        }
        return arrayList;
    }

}

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

分析：一次的路径=下落高度+反弹高度

public class Test12 {

    public static void main(String[] args) {
        int count = 0;
        double height = 100;
        double line = 0;
        for (int i = 0; i <= 100; i++) {
            count++;
            line = height + height / 2 + line;
            height = height / 2;
            if (count == 10) {
                System.out.println("经过的线路长度：" + line);
                System.out.println(height);
                break;
            }
        }

    }

}

 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 
　　　　1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。

我首先弄出了全部的可重排列,然后使用去重的方式进行数组减员

import java.util.Stack;

//1，2,3,4能够组成多少个无重复的三位数
//说白了就是4个数 能够组成多少种三位数
//可以有重复 
public class Test13 {
    private static int count=0;
    private static Stack<Integer> stack =new Stack<Integer>();
    public static void main(String[] args) {
        int[] A={1,2,3,4};
        int k=3;
        group(A,k);
        System.out.println(count);
    }
    private static void group(int[] a, int k) {
        if(k==1){
            for(int i=0;i<a.length;i++){
                stack.add(a[i]);
                System.out.println(stack.toString());
                count++;
                stack.remove((Object)a[i]);
            }
        }else if(k>1){
            for(int i=0;i<a.length;i++){
                stack.add(a[i]);
                group(a, k-1);
                stack.remove((Object)a[i]);
            }
        }else{
            return;
        }
    }

}

public class Test13A {
    private static int count=0;
    private static Stack<Integer> stack =new Stack<Integer>();
    public static void main(String[] args) {
        int[] A={1,2,3,4};
        int k=3;
        group(A,k);
        System.out.println(count);
    }
    private static void group(int[] a, int k) {
        if(k==1){
            for(int i=0;i<a.length;i++){
                stack.add(a[i]);
                System.out.println(stack.toString());
                count++;
                stack.remove((Object)a[i]);
            }
        }else if(k>1){
            for(int i=0;i<a.length;i++){
                stack.add(a[i]);
                group(removeElement(a), k-1);
                stack.remove((Object)a[i]);
            }
        }else{
            return;
        }
    }
    private static int[] removeElement(int[] a) {
        Stack<Integer> temp=new Stack<Integer>();
        for(int i=0;i<a.length;i++){
            if(!stack.contains(a[i])){
                temp.add(a[i]);
            }
        }
        int[] B=new int[temp.size()];
        for(int i=0;i<temp.size();i++){
            B[i]=temp.get(i);
        }
        return B;
    }

}

 这个地方弄的是组合哟 我最苦恼的是在递归调用过程中下标移动这是一个坎 越过了 就好了

import java.util.Stack;

//这个地方是弄的是组合
//重点注意传入值为i哟
public class Test13B {
    private static int count = 0;
    private static Stack<Integer> stack = new Stack<Integer>();

    public static void main(String[] args) {
        int[] A = { 1, 2, 3, 4 };
        int k = 3;
        group(A, 0, k);
        System.out.println(count);
    }

    private static void group(int[] a, int index, int k) {
        if (k==1) {
            for (int i = index; i < a.length; i++) {
                stack.add(a[i]);
                System.out.println(stack.toString());
                count++;
                stack.remove((Object) a[i]);
            }
        } else if (k>1) {
            for (int i = index; i < a.length; i++) {
                stack.add(a[i]);
                group(a, i+1,k-1);
                stack.remove((Object) a[i]);
            }
        } else {
            return;
        }
    }

}