問題注記再帰2(feat繰返しシーケンス、べき乗セット)

20463 ワード

再帰の原理はまだはっきりしていないので、書くたびに混同されます.
最近解いた再帰に関する質問を整理します.

rockPaperScissors


質問する


じゃんけんゲームとは、2人以上が同時に「石はさみ布」と叫び、石はさみ布に手を表す形を伸ばして勝負を決めるゲームです.3皿のハサミ石布ゲームをして、一人で3回の選択をすることができます(例えば:ハサミ、ハサミ、布).3回の選択で関数を作成し、可能なすべての数値を求めることができます.

入力

  • なし

    しゅつりょく

  • の2次元配列(arr[i])を返さなければなりません.
  • arr[i]は、総数の1つ(合計3回の選択)を表す配列である.
  • arr[i]は、1つまたは複数の「rock」、「paper」および「ハサミ」要素を含む配列である.
  • arr[i].長さ324579182

    注意事項

  • は、最終的に、重み付け順序に従ってアレイを返す.
  • の重要度は、「rock」、「paper」、「ハサミ」の順である.
  • は分かりやすく、オリンピックの順位決定方式を参考にすることができます.
  • 金メダル(「rock」)は銀メダル(「paper」)より優先され、銀メダル(「paper」)は銅メダル(「ハサミ」)より優先された.
  • I/O例

    let output = rockPaperScissors();
    
    console.log(output);
    /*
        [
          ["rock", "rock", "rock"],
          ["rock", "rock", "paper"],
          ["rock", "rock", "scissors"],
          ["rock", "paper", "rock"],
          // ...etc ...
        ]
      */

    Advanced


    正の整数ホイールが
  • 石切り布ゲームの数を表す場合は、ホイールで選択可能な任意の状況で数を返す関数を作成します.
  • let output = rockPaperScissors(5);
    
    console.log(output);
    /*
        [
          ["rock", "rock", "rock", "rock", "rock"],
          ["rock", "rock", , "rock", "rock", "paper"],
          ["rock", "rock", , "rock", "rock", "scissors"],
          ["rock", "rock", "rock", "paper", "rock"],
          ["rock", "rock", "rock", "paper", "paper"],
          ["rock", "rock", "rock", "paper", "scissors"],
          ["rock", "rock", "rock", "scissors", "rock"],
          // ...etc ...
        ]
      */

    < CODE >

    //################################< Advanced >##################################
    
    const rockPaperScissors = function (rounds) {
    
      rounds = rounds || 3;
      const rps = ['rock', 'paper', 'scissors'];
    
      const outcomes = [];
      
      // 재귀 -> 배열의 모든 요소의 경우의 수를 훑기 위한 적절한 방법
      let permutate = function (roundsToGo, playedSoFar) {
    
        if (roundsToGo === 0) { // rounds가 0일 경우 outcones 배열에 삽입하고, 재귀에서 빠져나옴(base case)
          outcomes.push(playedSoFar);
          return;
        }
    
        for (let i = 0; i < rps.length; i++) { // rpg 배열 한 번 씩 순회하며 i번째 요소 변수에 담음
          let currentPlay = rps[i];
          
          permutate(roundsToGo - 1, playedSoFar.concat(currentPlay)); //(recursive case)
          /**
           * 처음 실행된 반복문은 rps를 전부 순회해야 끝이 남.
           * 그러나 한 번 반복할 때마다 permutate 함수가 실행되고, rounds의 숫자는 짧아지며, playedSoFar에 요소가 계속 쌓일 것
           * 결국, roundsToGo가 0이 될 때까지 이 반복문은 rps[i]가 0일 것이며, playedSoFar에는 [rock, rock, rock]이 되어 outcones에 Push하고, 종료하게 된다.
           * return이 되었으니, 한 번의 재귀 호출이 끝. 마지막 호출 바로 전으로 돌아가,
           * for문은 i = 1을 가리키게 될 것이고, [rock, rock, paper]을 삽입한 뒤 호출을 하게 됨.
           * roundsToGo가 0이 되어, 해당 배열은 outcomes 배열에 삽입됨.
           * 모든 호출의 반복문이 끝날 때까지 반복하며 outcomes에 경우의 수 요소들이 담기게 된다.
           */
        }
      };
    
      permutate(rounds, []); // 최초 함수 실행(빈 배열과 함께)
    
      return outcomes;
    };
    //################################< Basic >##################################
    
    const rockPaperScissors = function () {
      
     const rps = ['rock','paper','scissors'];
     const rounds = 3;
     const count = 0;
     const outcomes = []; 
      
     const permutate = (count, playedsoFar) => {
       
       if(rounds === count) {
         outcomes.push(playedsoFar)
         return;
       } 
       
       permutate(count+1, playedsoFar.concat(rps[0])
       permutate(count+1, playedsoFar.concat(rps[1])         
       permutate(count+1, playedsoFar.concat(rps[2])    
     }
     
     permutate(count, []);
     
     return outcomes;    
      
    }

    < POINT >


    🔰 || (true를 만나면 바로 실행하는 특성)演算子を使用して、関数のパラメータに特定の値を指定したときに書き込みます.そうしないと、デフォルト値が指定されます.
    function rockPaperScissors (rounds) {
      rounds = rounds || 3
      ...}
    🔰 3つの場合の数字(石ハサミ布)を配列(rpg)に配置し、count変数と結果を配列(結果)に配置することを宣言します.
    🔰 countと進行する配列をパラメータとして受け入れます.
    count==roundsの場合(Advanced:rounds==0)処理中の配列をourcome->base caseにプッシュし、
    またはcount+1(/rounds-1)をrpgの要素の順にconcatごとに返し、->recursive caseに戻ります.
    🔰 concat:pushを使用すると、戻り値はlength、concatは戻り値が配列になります.
    復帰がどのように行われたのか分からないので、直接見てみました.(新しいウィンドウで開くと、クラスとして表示されます)
    中間カットなので初めてからX




    再帰の過程でcountは3-2回繰り返し、最後の3つのインデックス要素は順次循環し、生成された配列がすべて戻るまで、2番目の要素は1回循環し、2番目の要素の再帰呼び出しの下で再帰呼び出しを行い、2番目の要素の次の値を挿入して呼び出す.前のインデックス要素の値を繰り返します(ex> ["paper","rock","sicissor"]->["paper","rock"] -> ["paper"] -> ["paper","paper"]->["paper","paper","rock"] - 밑에서 두번째 캡쳐화면 참고- ) 最後に、作成したアレイが戻った後、["s","s","s"] -> ["s","s"]-> ["s"] -> []の順序で復帰する.
    各インデックスに3種類の選択がある場合の数は,開始順に1種類を選択するごとに3種類の帰属がある場合の数である.
    ->これはソートに関する問題であり、再帰を適用して解決されます.
    順序:n個のリストから一部を選択してリストする(順序別)

    家の飯が恋しい


    質問する


    キム・コディンは数年の海外出張を経て、やっと故郷に帰った.久しぶりに金さんに会った両親は喜んで料理を作ってテーブルの足を折った.感動の再会も一時的で、椅子に座って食事をしていた金コードは、何から食べるべきか考えに陥った.彼は心をこめて準備しているので、できるだけ多くの方法でいろいろな食べ物を食べたいと思っています.
    ご飯が1種類で、料理が多い場合は、ご飯と一緒に食べられる料理の数を並べて戻ってください.

    入力


    パラメータ1:sideDishes
  • Stringタイプの英語のトッピング
  • しゅつりょく

  • Arrayタイプを返さなければなりません.
  • ご飯と一緒に食べられる料理の数は
  • に並ぶ.

    注意事項

  • 料理は英語で書かれています.
  • 料理は重複しません.
  • 料理を食べないことも含まれています.(出力された2 D配列には空の配列が含まれています.)
  • 料理3個以上99個以下.
  • が出力する配列はすべてアルファベット順に並べ替えなければならない.
  • I/O例

    let output = missHouseMeal(["eggroll", "kimchi", "fishSoup"]);
    console.log(output);
    /*
    [ [], 
      [ 'eggroll' ], 
      [ 'eggroll', 'fishSoup' ], 
      [ 'eggroll', 'fishSoup', 'kimchi' ], 
      [ 'eggroll', 'kimchi' ], 
      [ 'fishSoup' ], 
      [ 'fishSoup', 'kimchi' ], 
      [ 'kimchi' ]
    ] 
    */

    < CODE >

    function missHouseMeal(sideDishes) {
    
      // 결과를 담을 배열을 선언
      let result = [];
      // sideDishes를 사전식 순서로 정렬
      sideDishes.sort();
    
      // 모든 조합을 검사하는 재귀 함수
      const sidePowerSet = (idx, sideDish) => {
    
        // 탈출 조건
        if (idx === sideDishes.length) {
          // 만약, idx와 sideDishes의 길이가 같다면(마지막까지 검토한 경우) result에 sideDish를 삽입하고 push
          result.push(sideDish);
          return;
        }
    
        // idx번째 요소가 포함되지 않는 경우
        sidePowerSet(idx + 1, sideDish);
    
        // idx번째 요소가 포함되는 경우
        sidePowerSet(idx + 1, [...sideDish, sideDishes[idx]]);
      };
    
      // 0 번째 인덱스와 빈 배열을 인자로 받는 재귀 함수를 실행
      sidePowerSet(0, []);
    
      // 결과를 사전식 순서로 정렬
      return result.sort();
    }

    < POINT >


    🔰 内部再帰家:主にidxを3に引き上げる役割です.因子はずっと受け入れられている.
    🔰 外部再帰家の仕事:実質的には配列に価値のある役割です.戻ると内部から戻り、下に戻り、戻り値はインデックス値とともに呼び出されます.



    べき乗セット:セットのすべての部分セット
    リスト・メソッドでは、ステップを分割する基準は、一番前の要素(または任意の集合要素)があるかどうかです.
    任意の要素を除いて、集合を小さい単位に縮小します.
    混同された部分:sideDishesの要素を順に参照し、重複しない部分集合を作成して返します.私はやるべきだと思いますが、どうして空の配列からずっと戻ることができますか?
    👉 まずソートを行い、一番下のインデックスと進行中のソートをパラメータとして再帰します.(0,[]から)idx==sideDishes.lengthの場合は条件を返します
    👉 inner/outer再帰宣言、innerにidxをアップロードし、outerに前の要素と新しい要素を含む配列再帰を返します(べき乗セットの概念に基づいて)
    resultの配列要素にアクセスできます.
    1.外部結合要素の配置
    2.内部idxが満たされたときに返される配列(内部からのみ回転し、/outerマージの要素にidxを配置)