#102 记忆化斐波那契函数(Memoization)


  • 0
    administrators

    斐波那契数列指的是类似于以下的数列:

    1, 1, 2, 3, 5, 8, 13, ....
    

    也就是,第 n 个数由数列的前两个相加而来:f(n) = f(n - 1) + f(n -2)

    请你完成 fibonacci 函数,接受 n 作为参数,可以获取数列中第 n 个数,例如:

    fibonacci(1) // => 1
    fibonacci(2) // => 1
    fibonacci(3) // => 2
    ...
    

    测试程序会从按顺序依次获取斐波那契数列中的数,请注意程序不要超时,也不要添加额外的全局变量。

    本题来源:《JavaScript 语言精髓》


  • 0

    
    const fibonacci = ((memory = {}) => n => {
    	if(n < 2) return n
    	if(memory[n-2] === undefined){
    		memory[n-2] = fibonacci(n-2)
    	}
    	if(memory[n-1] === undefined){
    		memory[n-1] = fibonacci(n-1)
    	}
    	return memory[n] = memory[n-1] + memory[n-2]
    })()
    
    

    快在哪里 计算上来说感觉都要算一遍呀,为啥下面都就超时了

    const fibonacci = n =>{
            let [a, b] = [0, 1]
    	while(n--){[a, b] = [b, a + b]}
    	return a
    }
    

  • 3

    ("▔□▔)/!!要怎么说它好呢。
    先用 100ms 打个表,之后爱它怎么玩,就怎么玩。

    const fibonacci = (n) => {
        if (!fibonacci.cache) {
            fibonacci.cache = [];
            for (let i = 1; i <= 1000000; i++) {
                if (i === 1 || i === 2) {
                    fibonacci.cache[i] = 1;
                }
                else if (i > 2) {
                    fibonacci.cache[i] = fibonacci.cache[i - 1] + fibonacci.cache[i - 2];
                }
            }
        }
    
        return fibonacci.cache[n];
    }
    

  • 10

    闭包一行代码搞定,不信试试,哈哈

    const fibonacci=((s)=>(f=(i)=>s[i]||(s[i]=f(i-1)+f(i-2))))([0,1,1])
    

  • 0

    卧槽,好牛逼,能解释下不?


  • 0

    你们这些写法输入 n = 10000 得时候都会溢出 Maximum call stack size exceeded 虽然结果是 Infinity

    怎么过的?


  • 0

    有诈

    const fibonacci = (n) => {
        if (!fibonacci.cache) {
            fibonacci.cache = [];
            for (let i = 1; i <= 1000000; i++) {
                if (i === 1 || i === 2) {
                    fibonacci.cache[i] = 1;
                }
                else if (i > 2) {
                    fibonacci.cache[i] = fibonacci.cache[i - 1] + fibonacci.cache[i - 2];
                }
            }
        }
    
        return fibonacci.cache[n];
    }
    

  • 0

    const fibonacci = (n) => {
      let arr=[1,1];
      
      let index=n-1
      if(index<2){
      	return arr[index]
      }else{
      	return fibonacci(n-1)+fibonacci(n-2)
      }
      
      
    }
    

  • 0

    if(n <= 2){
    return 1;
    }

    		let s1 = 0;
    		let s2 = 1;
    		for (let i = 2; i <= n; i++) {
    			s2 = s1 + s2;
    			s1 = s2 - s1;
    		}
    		return s2;

  • 0

               const fibonacci = (n)=>{
    		if(n <= 2){
    			return 1;
    		}
    
    		let s1 = 0;
    		let s2 = 1;
    		let e = 0;
    		for (let i = 2; i <= n; i++) 
                   {
    			e = s1 + s2;
    			s1 = s2;
    			s2 = e;
    		}
    		return e;
    	};
    

    这答案为什么报超时??


  • 0

    const fibonacci = (n) => {
    var mz_arr=[1,1];
    var i;
    if(n<3){
    return mz_arr[n-1];
    }else if(n>=3){
    for(i=2;i<n;i++){
    mz_arr[mz_arr.length]=mz_arr[i-1]+mz_arr[i-2];
    }
    }
    return mz_arr[n-1];
    }

    这个为什么超时呢?


  • 0

    var a = function (n) {
    if(n<2){
    return 1
    }else{
    return (a(n-1) + a(n-2))
    }

    }


  • 0

    const fibonacci = (n) => {
    return n<=2? 1 : fibonacci(n-1)+fibonacci(n-2)
    }

    你花费了太多的时间。。求解


  • 0

    @忘咲 因为你用的递归呀!递归就是每一次计算都吊在内存里,直到最后算出来


  • 2

    比较了几种算法,t4明显要更快,为什么却通过不了,而t5却过了呢?
    0_1515087539686_upload-e79731d1-06e9-4e9b-9250-88c69601f045
    0_1515087563199_upload-1d7c6bc0-ba76-4e75-be9b-9ae4e4bca4cb
    0_1515087577875_upload-a9362a51-d295-4f3a-a6a0-510e15fbcdd8
    0_1515087588010_upload-6a0f11cc-8455-4ed5-9d8a-276dbd744744
    0_1515087606133_upload-3bfadd72-0f7d-4cfb-a780-a8347d033137


  • 0

    n大一点就会堆栈溢出,程序会死掉。要是要用递归的话用尾递归。不过也超时。。

    const fibonacci = (n) => {
    return (function(a,b,i){
    return i<n?arguments.callee(b,a+b,i+1):a;
    })(1,1,1);

    }


  • 0

    @小菜鸡#102 记忆化斐波那契函数(Memoization) 中说:

    n大一点就会堆栈溢出,程序会死掉。要是要用递归的话用尾递归,不过也超时。。。。
    const fibonacci = (n) => {
    return (function(a,b,i){
    return i<n?arguments.callee(b,a+b,i+1):a;
    })(1,1,1);
    }


  • 0

    怎么了

    const fibonacci = (n) =>{ /* TODO */
      if(n == 0 || n == 1){ return 1;}
      return fibonacci(n-1)+fibonacci(n-2);
    }
    

  • 0

    if(n<=2){
    return 1
    }else{
    let a=[1,1],b=0;
    for(let i=3;i<=n;i++){
    b=a[0]+a[1];
    a[0]=a[1];
    a[1]=b;
    }
    return b;
    }


  • 0

    @aipeidong 厉害厉害,简直大声


登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待