V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
taogen
V2EX  ›  程序员

递归里面有 for 循环,感觉大脑维度不够用。请问大佬们,要怎么理解才好?

  •  
  •   taogen ·
    tagnja · 2019-11-01 17:11:54 +08:00 · 1838 次点击
    这是一个创建于 1610 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如:字符串的排列

    输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

    void Permutation(char* pStr)
    {
        if(pStr == nullptr)
            return;
    
        Permutation(pStr, pStr);
    }
    
    void Permutation(char* pStr, char* pBegin)
    {
        if(*pBegin == '\0')
        {
            printf("%s\n", pStr);
        }
        else
        {
            for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
            {
                char temp = *pCh;
                *pCh = *pBegin;
                *pBegin = temp;
    
                Permutation(pStr, pBegin + 1);
    
                temp = *pCh;
                *pCh = *pBegin;
                *pBegin = temp;
            }
        }
    }
    
    6 条回复    2019-11-01 19:30:40 +08:00
    yesterdaysun
        1
    yesterdaysun  
       2019-11-01 17:23:18 +08:00   ❤️ 1
    abc 的全排列={a,b,c}开头+其他字符的全排列={a+bc 的全排列, b+ac 的全排列, c+ab 的全排列}

    里面再继续递归, 终结条件就是递归到尾, 然后打印

    for 里面 前面是遍历当前递归字符串的字符, 并分别替换到头部, 中间就是递归除了头部以外的部分, 后面是把开始的替换再换回来, 还原并进行下一步
    taogen
        2
    taogen  
    OP
       2019-11-01 17:32:29 +08:00 via iPhone
    @yesterdaysun 感谢大佬
    dany813
        3
    dany813  
       2019-11-01 18:00:53 +08:00
    有点懵逼
    crclz
        4
    crclz  
       2019-11-01 18:02:22 +08:00   ❤️ 1
    用树来理解。
    打印 xx 排列本质上是对树的 dfs、bfs。用理解 dfs、bfs 的思路来理解排列,会很容易。假如不知道,请务必先学习 dfs、bfs。

    假设第一步选定的是字母 a,那么接下来就是一个 dfs 过程:
    这一层的 a 节点到树的下一层的节点,就只剩下去往 b c d e f...的边了。通往下一层的 a 的边已经不可用。
    总结起来,下一层能选择的字母就是:之前未选择过的字母,也就是没出现在路径上的字母。
    如果所有字母都用完了,那么意味着生成了一个排列。输出这个排列就是输出 dfs 的路径。
    ungrown
        5
    ungrown  
       2019-11-01 18:23:31 +08:00 via Android
    脑袋不够用就要依靠外部存储器啊
    咳咳
    草稿纸,请
    EminemW
        6
    EminemW  
       2019-11-01 19:30:40 +08:00 via iPhone   ❤️ 1
    其实这类全排列问题,或者说回朔算法的写法都差不多的。你多做几道就发现用一个模版就能解决
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2873 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 11:28 · PVG 19:28 · LAX 04:28 · JFK 07:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.