Module: (C++) 再帰


Problem

11/12

行を繰り返す #1

Theory Click to read/hide

タスク
「トゥンバ・ユンバ」族の言語のアルファベット。 4文字：「K」、「L」、「M」および「N」。このアルファベットの文字から作成できる n 文字で構成されるすべての単語を表示する必要があります。

この問題は通常の総当たり問題ですが、より小さな問題にまとめることができます。
単語を順次文字に置き換えて
いきます。 単語の最初の位置は、アルファベットの 4 文字 (K、L、M、N) のいずれかになります。
最初に文字 K を置きましょう。次に、最初の文字 K を持つすべてのバリアントを取得するには、残りの n - 1 位置にある文字の可能な組み合わせをすべて列挙する必要があります。以下同様です。 (図を参照)。
したがって、問題は長さ n - 1 の 4 つの問題を解くことに帰着します。
 
n 文字を再帰的に繰り返す
w[0]='K'; // 最後の L-1 文字を反復処理します w[0]='L'; // 最後の L-1 文字を反復処理します w[0]='M'; // 最後の L-1 文字を反復処理します w[0]='N'; // 最後の L-1 文字を反復処理します w - 作業単語を格納する文字列。
したがって、再帰が得られました。 再帰手順の形式で問題の解決策を調整できます。 
再帰がいつ終了するかを決定することはまだ残っています。全文字を設定した場合、つまり設定文字数はnとなります。この場合、結果の単語を画面に表示して手順を終了する必要があります
。
C++ プログラムは次のようになります。
#include 名前空間 std を使用します。 void TumbaWords( string A, string &w, int N ) // w - 変更可能なパラメータ (文字列-結果) // TumbaWords プロシージャには、アルファベットが文字列として渡されます。 // 単語 word とすでに設定されている文字数 (先頭は – 0)。 { int i; if (N == w.size()) {   // すべての文字がすでに単語に設定されている場合、    // その後、文字列を出力してプロシージャを終了する必要があります cout << w<<;エンドル; 戻る; } for ( i = 1; i < A.size(); i ++ ) {   // 上記の条件が false の場合 (つまり、すべての文字にスペースが入っていない場合)   // 次に、ループ内でアルファベットのすべての文字を調べ、 // 最初の空きスペースに交互に文字を配置します w[N] = A[i]; TumbaWords ( A, w, N+1 ); } } 主要（） { intn; 文字列; intn; シン>> n; word.resize(n); // 文字列をサイズ n に増加します TumbaWords( "KLMN", word, 0 ); }
注意 w は変更可能なパラメータ (結果文字列) であることに注意してください。

Problem

部族の言語のアルファベットで「トゥンバユンバ」 4文字：「K」、「L」、「M」および「N」。このアルファベットの文字から作成できる n 文字で構成されるすべての単語を表示する必要があります。
(c) K.Yu.ポリアコフ

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <string>
#include <iostream>
using namespace std;

void TumbaWords( string A, string &w, int N )
{                      
}

main()
{
  string word;
  int n;
  cin>>n;
  word.resize(n);
  TumbaWords ( "KLMN", word, 0 );
}

     

Program check result

To check the solution of the problem, you need to register or log in!