对于这个题目，看看大家有什么效率更高的算法

下午写了这个算法。跑了下 n=23时， 打印全部结果到控制台花了14秒时间，内存一直在8兆左右。
晚上回家又试着跑了 n=30，把结果输出到文件中，花了554秒，内存变成9兆（可能跟我把BufferedWriter的buffer size 提高到16k有关）。输出的结果文件有2g大。。。

package method;

import java.io.BufferedWriter;
import java.io.CharArrayWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Fibonacci {

	private int n = 0;
	
	private long f0 = 1;
	
	private long f1 = 1;
	
	private long f2 = 2;
	
	private long[] queue = null;
	
	
	public Fibonacci(int n) {
		if(n < 0) {
			throw new IllegalArgumentException("n can not be negative.");
		}
		this.n = n;
		
		queue = new long[n+1];
		
		caculate();
	}
	
	private void caculate(){
		
		// n = 0, 1, 2
		switch(n){
			case 2: queue[2] = f2;
			case 1: queue[1] = f1;
			case 0: queue[0] = f0; return;
			default: break;
		}
		
		// n > 2
		queue[0] = f0;
		queue[1] = f1;
		queue[2] = f2;
		
		
		for (int i = 3; i <= n; i++) {
			queue[i] = queue[i - 1] + queue[i - 2] + queue[i -3];
			System.out.println("Fibonacci("+i+")=" + queue[i]);
		}
	}
	
	public long[] getFibonacciQueue() {
		return queue;
	}
	
	
	public long f(int i) {
		if(i < 0) {
			//throw new IllegalArgumentException("i can not be negative.");
			return 0;
		}
		if(i > n) {
			throw new IllegalArgumentException("i can not be bigger than n.");
		}
		return queue[i];
	}
	
	
	public void printDetail() throws IOException {
		CharArrayWriter caw = new CharArrayWriter(2 * n + 2);
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out), 4096);
		for(long y = 0; y < f(n); y++) {
			for(int x = 0;  x < n; x++) {
				char stepnum = getStepNum(x, y);
				if(stepnum == 0) {
					continue;
				}else {
					if(caw.size() > 0) {
						caw.write(',');
					}
					caw.write(stepnum);
				}
			}
			caw.write("\r\n");
			caw.writeTo(out);
			caw.reset();
		}
		out.flush();
	}
	
	
	
	
	private char getStepNum(int x, long y) {
		if(x == 2 && y == 6) {
			System.out.println("");
		}
		
		int k = 0; int i = 0;
		for (; i < x; i++) {
			
 			if(y >= f(n - k - 1) + f(n - k - 2)) {
				if(n > k + 3) {
	 				y -= f(n - k - 1) + f(n - k - 2);
					k += 3;
				}else {
					break;
				}
			}else if (y >= f(n - k - 1)) {
				if(n > k + 2) {
					y -= f(n - k - 1);
					k += 2;
				}else {
					break;
				}
			}else {
				if(n > k + 1) {
					k += 1;
				}else {
					break;
				}
			}
		}
		
		
	
		if(y < f(n - k - 1)) {
			if(n <= k + 1 && i < x) {
				return 0;
			}
			return '1';
		}else if (y < f(n - k - 1) + f(n - k - 2)) {
			if(n <= k + 2 && i < x) {
				return 0;
			}
			return '2';
		}else {
			if(n <= k + 3 && i < x) {
				return 0;
			}
			return '3';
		}
		
	}
	
	
	

	public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();

		int n = 23;
		Fibonacci fib = new Fibonacci(n);
		System.out.println("[Result]Fibonacci("+n+")=" + fib.f(n));
		fib.printDetail();
		System.out.println("Cost:" + (System.currentTimeMillis() - start) + "ms");
		
	}
}

那你跑这个有没觉得内存耗的好点了？

Ruby 解法:
http://night-stalker.iteye.com/blog/789096

更快哦

你还不睡。。。

唉，郁闷啊，看了之后，竟然一点思路都没有，谁给点

  LZ可以看一下这篇文档，相信会受益匪浅的 小问题大学问呐

不错的算法
我写了个java版

public static void main(String[] args) throws IOException {
		long start = System.currentTimeMillis();
		out_step(35);
		long end = System.currentTimeMillis();
		System.out.println(end-start);
		/*FileInputStream in = new FileInputStream("g:/data.txt");
		System.out.println(in.read());
		in.close();*/
	}
	
	public static void count(Writer writer,StringBuffer s ,int i,int j,int k) throws IOException{
		if(i==0&&j==0&&k==0){
			writer.append(s+"\n");
			return;
		}
		if(i>0){
			count(writer,new StringBuffer(s).append("1"),i-1,j,k);
		}
		if(j>0){
			count(writer,new StringBuffer(s).append("2"),i,j-1,k);
		}
		if(k>0){
			count(writer,new StringBuffer(s).append("3"),i,j,k-1);
		}
	}
	
	public static void out_step(int n) throws FileNotFoundException{
		BufferedWriter out = null;
		try {
			out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("g:/data.txt")),1024*1024);
			for(int i=0;i<=n/3;i++){
				int m = n-3*i;
				for(int j=0;j<=m/2;j++){
					count(out, new StringBuffer(), (m-2*j),j, i);
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				out.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

内存使用一直在6m以下，关键是看硬盘有多大了。。。
测了一下35个台阶，用时2270171ms 半个多小时，生成文件有25g。汗。。。幸亏我硬盘够大

f(x) = f(x-1) + f(x-2) + f(x-3)

是吧，3*3的矩阵，如果求第x项，时间复杂度 O(3log(x))，矩阵乘法要用快速幂

这个问题可以用非递归算法来做。比较了一下，性能比递归算法快很多。具体请看
http://yeaya.iteye.com/admin/blogs/824792

import java.util.ArrayList;

public class Test
{
    static class LongArray
    {
        static final int BLOCK_SIZE = 1000000;
        final ArrayList<long[]> list = new ArrayList<long[]>();
        long[] current = new long[BLOCK_SIZE];
        int index = 0;
        int total = 0;
        void add(long val)
        {
            if(index>=BLOCK_SIZE)
            {
                list.add(current);
                current = new long[BLOCK_SIZE];
                index = 0;
            }
            current[index++] = val;
            total++;
        }
        int size()
        {
            return total;
        }
        long get(int idx)
        {
            int i = idx/BLOCK_SIZE;
            idx %= BLOCK_SIZE;
            if(i<list.size())
                return list.get(i)[idx];
            return current[idx];
        }
    }
    static void calc(LongArray list,long val,int steps,int n)
    {
        val<<=2;
        for(int i=0;i<3;i++)
        {
            val++;
            steps++;
            if(steps == n)
            {
                list.add(val);
                break;
            }
            calc(list,val,steps,n);
        }
    }
    static LongArray calc(int n)
    {
        LongArray ar = new LongArray();
        calc(ar,0,0,n);
        return ar;
    }
    public static void main(String[] args)
    {
        int n = 31; //需要1G JVM内存
        long start = System.currentTimeMillis();
        LongArray list = calc(n);
        long end = System.currentTimeMillis();
        System.out.println("n=" + n);
        System.out.println("count=" + list.size());
        System.out.println("used time " + (end-start) + " ms.");
        System.out.println("memory used " + ((Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory())/1000000L) + "MB");
        /*
        for(int i=0;i<list.size();i++)
        {
            System.out.println(Long.toString(list.get(i),4));
        }*/
    }

}