小数を作成(dfs)

10761 ワード
algorithm テキストリンク

これは,配列から3個の数を抽出し,さらに1個の値が「小数」である場合の問題である.
for乙を3回使ってこそ解決できるが、なかなか良い方法ではない.だからdfsで解決しました.
function isPrime(num){
    for(let i = 2; i <= Math.sqrt(num); i++){
        if(num % i === 0){
            return false
        }
    }
    return true
}

function solution(nums) {
    var answer = [];
    
    const dfs = (nums, cnt, arr = []) => {
        if(cnt === 3) return answer.push(arr.reduce((a, c) => a + c));
        for(let i = 0; i < nums.length; i++){
            arr.push(nums[i]);
            dfs(nums.slice(i+1), cnt + 1, arr);
            arr.pop()
        }

    }
    dfs(nums, 0);
    return answer.filter(v => isPrime(v)).length;
}
まず、平行移動小数の部分をisPrime関数として個別に定義します.
Nの約数はsqrt(N)の範囲内に無条件に存在する.そこで使用しましたMath.sqrt小数を求める部分が完成し、配列から3つ抽出する部分が設計されています.
dfsという関数を作成しました.3つの因子を受け取る.
  • dfs関数動作
  • dfs(nums, 0);nums配列と0を加えます.説明のためnumsで試してみる[1, 2, 3, 4]
  • forゲートから見始めます.i=0でarrにnums[i]を押す.再びdfs関数に入り、これから[2, 3, 4]から抽出するのでnums.slice(i+1)を最初の因子に入れます.次いでカウントのためにcntを1個増やしarrアレイに直接加えた.
  • 現在dfsに入ります.cntは1でifゲートには入りません.ドアに入り、i=0から再開します.ただし、ここの並びは[2, 3, 4]であることを覚えておいてください.cntは3の前にdfs関数にも入ります.
  • 上記手順を繰り返すとarr[1, 2, 3]を押すとcntは3になってifゲートに入る.reduceで1+2+3の結果値6を返し、答えに押します.この値を戻り値として与えたのでdfsを終了する.
    dfsを脱出した後、for文のi=0の状態になるはずです.あとarrには[1, 2, 3]、numsは[3, 4]現在arr.pop()を行い、arrに[1, 2],i=1を残す.[3, 4]nums[i]に相当する4をarrに押し込む.
    • dfsは上記のように動作しています.この文章を理解していない場合は、繰り返し読んで、そのままノートに動作を書くことができます.
    現在、解答列には[1, 2, 3, 4]から3つの合計を抽出した値があるはずです.answer.filter(v => isPrime(v))小数点を探し、長さで最終的に返します.
    function solution(nums) {
    var answer = []
    
    const dfs = (nums, cnt, sum) => {
        if(cnt === 3){
            answer.push(sum)      
        } else{
            for(let i = 0; i < nums.length; i++){
                dfs(nums.slice(i+1), cnt+1, sum+nums[i])
            }
        }
    }
    dfs(nums, 0, 0)
    answer = answer.filter(num=>isPrime(num))
    
    return answer.length;
}
    考えてみれば、cnt === 3条件が満たされていれば、reduce関数が呼び出されている.コードをより効率的に設計するために、上記の変更を行いました.
    日常運行メンテナンス(三)
    Redmine(四)-redmineのアップグレード