Javascript - 再帰呼び出しの代わりに

Question

私はこの問題を抱えています。 時刻tに基づいて数値xを計算する必要があります。xはM（t）で表されます。 我々有する以下

• M（0）= 1
• M（1）= 1
• M（2）= 2
• M（2T）= M（T）+ M（ T + 1）+ T（Tのために> 1）
• M（2T + 1）= M（T - 1）+ M（T）+ 1（すなわち有するT> = 1）

用私がこれを実装するのを忘れていた最初のことは、再帰を使用することであると言われています

function CalculateForTime(t) { 
    if (t == 0 || t == 1) { 
     return 1; 
    } 
    else if (t == 2) { 
     return 2; 
    } 
    else if (t % 2 == 0) { 
     t = t/2; 
     return CalculateForTime(t) + CalculateForTime(t + 1) + t; 
    } 
    else { 
     t = (t - 1)/2; 
     return CalculateForTime(t - 1) + CalculateForTime(t) + 1; 
    } 
} 

これは、例えば、多数tに1^20

を実行しているときしかし、それは私が末尾呼び出しの再帰に探したり、反復的なアプローチに再帰的なアプローチを代入しようとしたが、実際にそれを理解できなかった破る作品でる。

テール再帰または繰り返しが次に進む方法であれば、私はこれを変換する際に助けが必要です。そうでなければ、私はこれをより最適化するためのさまざまな方法を公開しています。

ありがとう、 オマール。

Answer 1

...再計算する必要がtheresの値なし。

function calculateForTime(t) { 
 
    var k = t; 
 
    if (k in lookup) { 
 
     return lookup[k]; 
 
    } 
 
    if (t == 0 || t == 1) { 
 
     return lookup[k] = 1; 
 
    } 
 
    if (t == 2) { 
 
     return lookup[k] = 2; 
 
    } 
 
    if (t % 2 == 0) { 
 
     t = t/2; 
 
     return lookup[k] = calculateForTime(t) + calculateForTime(t + 1) + t; 
 
    } 
 
    t = (t - 1)/2; 
 
    return lookup[k] = calculateForTime(t - 1) + calculateForTime(t) + 1; 
 
} 
 

 
var lookup = {}; 
 
console.log(calculateForTime(1e10));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

あなたは、配列に値を格納することができ、その配列のために、それは穴を生成するので、あなたは、ハッシュテーブルを使用することができ

var times=[1,1,2]; 
 
function CalculateForTime(t) { 
 
    t = Math.floor(t/2); 
 
     return times[t]||(times[t]=CalculateForTime(t) + CalculateForTime(t + 1) + t); 
 
} 
 

 
console.log(
 
CalculateForTime(100), 
 
CalculateForTime(1000), 
 
CalculateForTime(10000), 
 
); 
 
console.log(times.slice(0,100));

Answer 3

あなたは何度も何度も同じ値を再計算を避けるためにメモ化を使用することができます。 https://addyosmani.com/blog/faster-javascript-memoization/

これは、アルゴリズムを値のキャッシュから分離することを除いて、他の人が提案したものと同じです。

function memoize(func){ 
    var cache = {}; 
    return function(arg){ 
     if(arg in cache) { 
      return cache[arg]; 
     } else { 
      return cache[arg] = func(arg); 
     } 
    } 
    } 

    // Overwrite with a function that remember previous results 
    CalculateForTime = memoize(CalculateForTime); 

恩赦タイプミスは、次のように行った後、電話