Module: 子程序。递归过程和函数


Problem

4/5

迭代第 1 行

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++ 程序将如下所示。
<分区> #include; 使用命名空间标准; void TumbaWords(字符串 A, string &w, int N ) // w - 可变参数(字符串结果) // TumbaWords 程序将字母表作为字符串传递, // 单词 word 和已经设置的字符数(在 – 0 之前)。 { 诠释我; 如果 (N == w.size()) {   // 如果所有字符都已经设置为单词,     // 然后需要输出一个字符串并结束程序 输出 << w<<结束; 返回; } for ( i = 1; i < A.size(); i ++ ) {   // 如果上面的条件为假(也就是说,不是所有的字符都是间隔的,   // 然后在循环中我们遍历字母表中的所有字符并 //交替将字符放在第一个空闲空间 w[N] = A[i]; TumbaWords ( A, w, N+1 ); } } 主要的() { 国际; 字符串词; 国际; 辛>>名词; word.resize(n); // 将字符串增加到 n TumbaWords(“KLMN”,字,0);
注意 w 是一个可变参数(结果字符串)!

Problem

在部落语言“tumba-yumba”的字母表中;四个字母:“K”、“L”、“M”和“N”。您需要显示所有由 n 个字母组成的单词,这些字母可以从该字母表的字母组成。
(c) K.Yu。波利亚科夫