Module: サブルーチン。再帰


Problem

11/12

行を反復処理する

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# プログラムは次のようになります。
// w - 変更可能なパラメータ (文字列-結果) // TumbaWords プロシージャには、アルファベットが文字列として渡されます。 //単語単語と文字数が設定済み(先頭–0) static void TumbaWords( string A, ref string w, int N ) { if (N == w.Length) // w.Length - 文字列の文字数 {   // すべての文字がすでに単語に設定されている場合、      // その後、文字列を出力してプロシージャを終了する必要があります Console.WriteLine(w); 戻る; } for ( int i = 0; i < w.Length; i ++ ) // 上記の条件が false の場合 (つまり、すべての文字が空白になっているわけではなく、 {     // 上記の条件が false の場合 (つまり、すべての文字にスペースが入っていない場合、    // 次に、ループ内でアルファベットのすべての文字を調べ、   // 最初の空きスペースに交互に文字を配置します w += A[i]; TumbaWords(A, ref w, N+1); w = w.Remove(w.長さ - 1); // 最後に追加された文字を削除し、   // 同じプレフィックスを持つ新しい単語を作成する } } 静的 void Main() { int n = Convert.ToInt32(Console.ReadLine()); 文字列の単語 = ""; TumbaWords("KLMN", ref 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#
1 
using System;
2 
class Program
3 
{
4 
    static void TumbaWords(string A, ref string w, int N)
5 
    {
6 
        if (N == w.Length)
7 
        {
8
9
10
11
12 
        for (int i = 0; i < A.Length; i++)
13 
        {
14 
            w += A[i];
15
16 
            w = w.Remove(w.Length - 1);
17 
        }
18 
    }
19 
    static void Main()
20 
    {
21 
        int n = Convert.ToInt32(Console.ReadLine());
22 
        string word = "";
23
24 
    }
25 
}

     

Program check result

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