XDU1139

import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner sc = new Scanner(System.in); while (sc.hasNext()){ int n=sc.nextInt(); int i=1,sum=1; while (n>=sum){ i++; sum=sum+fib(i); } if(n-sum+fib(i)>fib(i-1)) System.out.println(i+" "+(n-sum+fib(i))); else System.out.println((i-1)+" "+fib(i-1)); } } static int fib(int i){ if(i==1||i==2) return 1; else return fib(i-1)+fib(i-2); } } 当OJ判断时，时间超限，关于Fibonacci数列，《编程之美》对它惊醒了各种分析，由于调用方法每次都要从头求解fib(i)的值，故时间复杂度较高；

解决策略1：利用空间弥补时间

        利用数组记录已算Fibonacci数列项

解决策略2：递推

import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { long n = sc.nextLong(); int i = 2, sum = 2; int x = 0, y = 1, z = 1; if (n == 1 || n == 2) System.out.println(1 + " " + 1); while (n >= sum && n > 2) { i++; x = y; y = z; z = x + y; sum = sum + z; } if (n>2){ if (n - sum + z > y) System.out.print(i + " " + (n - sum + z)); else System.out.print((i - 1) + " " + y); } } } } 比起递归，时间复杂度明显减小，但OJ还是时间超限