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

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

  •  
  •   taogen · 36 天前 · 1279 次点击
    这是一个创建于 36 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如:字符串的排列

    输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串 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
        1
    yesterdaysun   36 天前   ♥ 1
    abc 的全排列={a,b,c}开头+其他字符的全排列={a+bc 的全排列, b+ac 的全排列, c+ab 的全排列}

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

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

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