ターゲット番号に到達するために必要な最小操作数をカウントする

Question

現在、JavaScriptの数値配列を取ります（例：[5, 10, 18, 25, 30]）。次に必要な最小操作数を含む配列を返します0から1を追加するか、または2を掛けるだけで、ターゲット番号に変更できます。

例えば、5の数字は、0 + 1 = 1 x 2 = 2 x 2 = 4 + 1 = 5となるため、4を返します。

渡された配列が[5,5,5]の場合、出力配列は[4,4,4]になります。

私はこの問題の潜在的な解決法を見てきましたが、そのうちのいくつかは反復と他の再帰を使用していました。私はここに似たような質問の答えを見つけましたCode Review - Find sequence by adding 5 or multiplying by 3。

唯一の違いは、5を追加するか、2を掛けることです。これは0ではなく1から始まります。私のニーズに合わせてこのソリューションを適応しようとしましたが、何らかの理由でコードがいつもadd 1と決してtimes 2です。したがって、入力5の場合、私は0 + 1 = 1 + 1 = 2 + 1 = 3 + 1 = 4 + 1 = 5と返されますが、明らかに最短の解決策ではありません。

最終的には、入力も配列になるので、配列を返す必要がありますが、パラメータとして単一の整数をとるだけで、上記の答えを適用することにも苦労しています。

この関数に5を渡すと、のため、4という最短解ではなく、5と返されます。

現時点で私が持っているコードは次のとおりです。

function findSequence(goal) { 
    function find(start, history) { 
    if (start == goal) { 
     return history; 
    } 
    if (start > goal) { 
     return null; 
    } 
    return find(start + 1, "(" + history + " + 1)") || 
      find(start * 2, "(" + history + " * 2)"); 
    } 
    return find(0, "0"); 
} 

どのように私はこの作業を行うことができますか？私はこれはおそらく、逆に行うことが容易である2

Answer 1

どのようにこのようなものについて：

function findMoves(target) 
{ 
    arr = []; 
    while (target != 1) 
    { 
     if (target %2 == 0) 
     { 
      target /= 2; 
      arr.unshift(target + " x " + 2); 
      continue; 
     } 
     target -= 1; 
     arr.unshift(target + " + " + 1); 
    } 
    arr.unshift("0 + 1"); 
    return arr; 
} 

res = findMoves(9); 

console.log(
    "TotalMoves: " + res.length + "\n" + 
    "What moves: " + res.join(', ')); 

プリント：

TotalMoves: 5 
What moves: 0 + 1, 1 x 2, 2 x 2, 4 x 2, 8 + 1 

Answer 2

掛ける1またはを追加することにより、目標数に0から取得する最短シーケンスカウントを返す必要があります。あなたの目標から始めて、から1またはを2で割るか、0になるまでで割ります。そのシーケンスを見つけたら、それを逆にして、inverse ops（プラス1、2倍）を使用してターゲットに戻ります。

function getNext(num) { 
 
    if (num === 0) return "end" 
 
    if (num % 2 === 1) return "minus" 
 
    return "div" 
 
} 
 

 
function makeSequence(num, ls) { 
 
    const next = getNext(num); 
 
    if (next === "end") return ls; 
 
    ls.push(next) 
 
    
 
    if (next === "div") return makeSequence(num/2, ls); 
 
    if (next === "minus") return makeSequence(num-1, ls); 
 
} 
 

 
function reverseSequence(sqn) { 
 
    return sqn.reverse().map(x => x === "minus" ? "plus" : "times"); 
 
} 
 

 
var sqn = makeSequence(5, []); 
 
var reversedSqn = reverseSequence(sqn) 
 

 
console.log("Takes", reversedSqn.length, "steps with target of 5"); 
 
console.log("Steps are:", reversedSqn);  
 

 
var bigSqn = makeSequence(200, []); 
 
var bigReversedSqn = reverseSequence(bigSqn); 
 

 
console.log("Takes", bigReversedSqn.length, "steps with target of 200"); 
 
console.log("Steps are:", bigReversedSqn);