java-笔试-编程题，关联 面试

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//这是一个菲波拉契数列问题
public class Fibonacci {
    public static void main(String[] args) {
        System.out.println("第1个月的兔子对数:    1");
        System.out.println("第2个月的兔子对数:    1");
        int f1 = 1, f2 = 1, f, M = 24;
        for (int i = 3; i <= M; i++) {
            f = f2;
            f2 = f1 + f2;
            f1 = f;
            System.out.println("第" + i + "个月的兔子对数: " + f2);
        }
    }
}

二分查找

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class BinarySearchRecursive {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 4, 6, 8, 9 };
        int key = 4;
        int result = recursionBinarySearch(arr, key, 0, arr.length-1);
        
        System.out.println("searching " + key + " index is :" + result);
    }
    
    public static int recursionBinarySearch(int[] data, int key, int low, int high) {
        if( key < data[low] || key > data[high] || low > high) {
            return -1;
        }
        
        int middle = (low + high) / 2;
        if( key < data[middle] ) {
            return recursionBinarySearch(data, key, low, middle - 1);
        }
        if( key > data[middle] ) {
            return recursionBinarySearch(data, key, middle + 1, high);
        }
        return middle;
    }

}

不使用递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class BinarySearchNoRecursion {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }
    
    public static int commonBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;
        
        if( key < arr[low] || key > arr[high] || low > high ) {
            return -1;
        }
        
        while(low <= high) {
            middle = (low + high) / 2;
            if( arr[middle] > key ) {
                high = middle - 1;
            } else if ( arr[middle] < key ) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        
        return -1;
    }
}

素数

判断素数的方法：用一个数分别去除2到这个数开方（Math.sqrt），如果能被整除， 则表明此数不是素数，反之是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 判断101-200之间有多少个素数，并输出所有素数。
 */
public class PrimeNumber {
    public static void main(String[] args) {
        int count = 0;
        for(int i=101; i<200; i+=2) {
            boolean b = false;
            for(int j=2; j<Math.sqrt(i); j++) {
                if(i % j == 0) {
                    b = false;
                    break;
                } else {
                    b = true;
                }
            }
            if(b) {
                count ++;
                System.out.println("发现素数：" + i);
            }
        }
        System.out.println("素数的个数是： " + count);
    }
}

水仙花数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class NarcissisticNumber {

    public static void main(String[] args) {
        int b1, b2, b3;
        for(int i=101; i<1000; i++) {
            b1 = i / 100;
            b2 = i % 100 / 10;
            b3 = i % 10;
            if( b1*b1*b1 + b2*b2*b2 + b3*b3*b3 == i ) {
                System.out.println("发现水仙花数： " + i);
            }
        }
    }
}

分解质因数 integer factorization

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class IntegerFactorize {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.print("请输入一个正整数： ");
        int n = s.nextInt();
        int k = 2;
        
        System.out.print(n + " = ");
        while( k <= n ) {
            if( k == n ) {
                System.out.println(n);
                break;
            } else if( n % k == 0 ) {
                System.out.print(k + " * ");
                n = n / k;
            } else {
                k++;
            }
        }
    }
}

最大公约数和最小公倍数

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

在循环中，只要除数不等于0，用较大数除以较小的数，将小的一个数作为下一轮循环的大数，取得的余数作为下一轮循环的较小的数，如此循环直到较小的数的值为0，返回较大的数，此数即为最大公约数，最小公倍数为两数之积除以最大公约数。

  • 最大公约数： 最大公因数、Greatest Common Divisor(GCD)、Highest Common Factor(HCF)。
    a，b的最大公约数记为（a，b）
    • 质因数分解法
      例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。
    • 短除法
    • 辗转相除法
    • 更相减损法
  • 最小公倍数： Least Common Multiple
    两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class CommonFactor {

    public static void main(String[] args) {
        int a,b,m;
        Scanner s = new Scanner(System.in);
        System.out.print("键入一个整数： ");
        a = s.nextInt();
        System.out.print("再键入一个整数： ");
        b = s.nextInt();
        deff cd = new deff();
        m = cd.deff(a,b);
        int n = a * b / m;
        System.out.println(a + ", " + b + " 的最大公约数： " + m);
        System.out.println(a + ", " + b + " 的最小公倍数： " + n);
    }
}

class deff {
    public int deff(int x, int y) {
        int t;
        if(x < y) {
            t = x;
            x = y;
            y = t;
        }
        
        while(y != 0) {
            if( x == y ) {
                return x;
            } else {
                int k = x % y;
                x = y;
                y = k;
            }
        }
        
        return x;
    }
}

完数

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class PerfectNumbers {

    public static void main(String[] args) {
        // 找出1000以内的所有完数。 
        System.out.println("1到1000的完数有： ");
        for(int i=1; i<1000; i++) {
            int t = 0;
            for(int j=1; j<=i/2; j++) {
                if( i % j == 0 ) {
                    t = t + j;
                }
            }
            if( t == i ) {
                System.out.print(i + " ");
            }
        }
    }
}

执行结果：

1到1000的完数有：
6 28 496

交换两个变量值

前提：

1
2
int a = 3;
int b = 4;

几种解法：

1
2
3
int temp = a;
a = b;
b = temp;

1
2
3
a = a + b;//a = 3 + 4 = 7
b = a - b;//b = 7 - 4 = 3
a = a - b;//a = 7 - 3 = 4

1
2
3
4
5
6
7
8
a = a ^ b;  // a = 4 ^ 3, b = 3;
b = a ^ b;  // a = 4 ^ 3, b = 4 ^ 3 ^ 3 = 4
a = a ^ b;  // a = 4 ^ 3 ^ 4 = 3, b = 4;
//用到的知识：
//a ^ a = 0;
//a ^ 0 = a;
//a ^ b = b ^ a;
//a ^ b ^ b = a;

1
2
3
a = (a + b) - (b = a);
//用到的知识点:
//赋值运算符在连续赋值的时候会使用初始值代替中间变量

1
a = (a ^ b) ^ (b = a);