斐波拉契序列几种实现

今天遇到一个面试题：输入n，如果n<=1，f(n)=1，其他(n>1)则f(n)=f(n-1)+f(n-2), 打印f(n)从1到n的值。

public class Fibonacci {

    private int n;
    private StringBuilder sb;
    private String format;

    @Before
    public void init() {
        n = 10;
        sb = new StringBuilder(n);
        format = "f(%s) = ";
    }

直接用递归的方式实现：

/**
     * 递归实现
     */
    @Test
    public void recursion() {
        for (int i = 1; i <= n; i++) {
            sb.delete(0, n);
            sb.append(String.format(format, i));
            sb.append(recursion(i));
            System.out.println(sb.toString());
        }
    }

    private int recursion(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return recursion(n - 1) + recursion(n - 2);
        }
    }

测试结果如下：

面试官说用循环，循环实现：

/**
     * for循环实现
     */
    @Test
    public void fori() {
        if (n <= 1) {
            System.out.println(1);
        }
        int j = 1, k = 1;
        int sum;
        for (int i = 2; i <= n; i++) {
            // f(n)=f(n-1)+f(n-2)
            // 把j作为f(n-1),k作为f(n-2)
            sum = j + k;
            k = j;
            j = sum;

            sb.delete(0, n);
            sb.append(String.format(format, i));
            sb.append(sum);
            System.out.println(sb.toString());
        }
    }

测试结果如下：

他说代码可以更加精简、高效，再次修改：

/**
     * for循环更高效实现
     */
    @Test
    public void forEfficient() {
        if (n <= 1) {
            System.out.println(1);
        }
        int temp = 1;
        int sum = 1;
        for (int i = 2; i <= n; i++) {
            // f(n)=f(n-1)+f(n-2)
            // 此时把sum作为f(n-1),temp作为f(n-2)
            sum = sum + temp;
            // 计算后sum就是f(n)
            // temp = f(n-1) = f(n) - f(n-2)
            temp = sum - temp;

            sb.delete(0, n);
            sb.append(String.format(format, i));
            sb.append(sum);
            System.out.println(sb.toString());
        }
    }

测试结果如下：

后面几面的编程题相关问题：

给一个无序数组，找出第K个大的数

比如23, 5, 7, 2,第2大的数就是7；

快速排序partition函数，比如10个数，找第5大的数，进行降序排列，在一次快排后，返回的下标假如为2就是这个数最终的位置，并且这个左边的所有的数都比它大，右边的所有数都比他小，然后就找3-9的数进行partition……

如果有有序数组相关的问题，应该要想到二分查找，根据数组下标二分！

很多编程题，校招时感觉简单，社招需要想一想才能做出来。