Module: 子程序。递归


Problem

11/12

遍历行

Theory Click to read/hide

任务
在部落语言“Tumba-Yumba”的字母表中；四个字母：“K”、“L”、“M”和“N”。您需要显示所有由 n 个字母组成的单词，这些单词可以从这个字母表的字母组成。

这个问题是一个普通的蛮力问题，可以简化为一个更小的问题。
我们将依次用字母替换单词。
单词的第一个位置可以是字母表中的 4 个字母之一（K、L、M、N）。
让我们把字母K放在第一位。然后，为了得到第一个字母为K的所有变体，您需要枚举剩余n - 1位置的所有可能的字母组合 等等。 （见图）
这样，问题就简化为解决四个长度为n - 1的问题。
 
递归遍历 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 程序将字母表作为字符串传递， // 单词word和已经设置的字符数（开头–0） static void TumbaWords（字符串 A，引用字符串 w，int N） { if (N == w.Length) // w.Length - 字符串中的字符数 {   // 如果所有字符都已经设置为单词，       // 然后需要输出一个字符串并结束程序 控制台.WriteLine(w); 返回; } for ( int i = 0; i < w.Length; i ++ ) // 如果上面的条件为假（即不是所有的字符都是间隔的， {     // 如果上面的条件为假（即不是所有的字符都是间隔的，    // 然后在循环中我们遍历字母表中的所有字符并   //交替将字符放在第一个空闲空间 w += A[i]; TumbaWords(A, ref w, N+1); w = w.Remove(w.Length - 1); // 然后删除最后添加的字符，   // 用相同的前缀创建一个新词 } } 静态无效主要（） { int n = Convert.ToInt32(Console.ReadLine()); 字串=“”； TumbaWords(“KLMN”，参考字，0); }
注意 w 是一个可变参数（结果字符串）！

Problem

在部落语言“tumba-yumba”的字母表中；四个字母：“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!