递归解决遍历问题

小鱼儿 2024-04-20 10:43 60阅读 0赞

# 递归解决遍历问题 #

### 觉得有用的话,欢迎一起讨论相互学习~[Follow Me][] ###

> 参考文献  
> 《算法竞赛宝典》--张新华

# 算法流程 #

![949241-20190626193153799-1269276020.jpg][]

//递归解决枚举问题
    //
    // Created by cloud on 2019/5/4.
    //
    //全排列算法-深搜字典序
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    using namespace std;
    
    int a[10000], Count, DNAsequences_length, DNABase_types;
    
    void print() {
        for (int k = 1; k < DNAsequences_length + 1; k++)
            cout << a[k];
        cout << "\n";
        Count++;
    }
    
    void dfs(int i) {
        if (i > DNAsequences_length)//递归结束，打印结果,递归的深度即为DNAsequences_length
            print();
        else
            for (int k = 1; k <= DNABase_types; k++) {
                a[i] = k-1;//赋值 a[1]=0,
                dfs(i + 1);
                //这个for循环一直很奇妙因为我不知道这个for循环什么时候才能停止下来
    //            cout<<k<<endl;
    
          /*    //1.发现DNA长度达到DNAsequences_length后才会输出k,认为是dfs函数达到条件后才退出
                //2.在Test3length.txt中的结果显示
                //k=1 a[1]=1
                //dfs(2)
                //k=1 a[2]=1
                //dfs(3)
                //k=1 a[3]=1
                //dfs(4)
                //调用print函数，依次输出a[1],a[2],a[3]
                // 111--根据下一步输出是112推断程序发生了a[3]=2这种改变，即k=2,i=3
                //此时程序退回到dfs(3),执行输出k=1,并将k+1
                //因此a[3]=2,执行dfs(4)在执行print()函数
                // 112
                //程序又退回到dfs(3),执行输出k=2,并将k+1
                //因此a[3]=3,执行dfs(4)在执行print()函数
                // 113
                //程序又退回到dfs(3),执行输出k=3,并将k+1,
                //因此a[3]=4,执行dfs(4)在执行print()函数
                //114
                //程序又退回到dfs(3),执行输出k=4,并将k+1=5,已经不满足for循环的条件了
                //则程序退回到dfs(2),k=1时，输出k,并将k+1=2
                //a[2]=2
                //程序进入dfs(3)，k=1,a[3]=1,程序进入dfs(4),输出121,退出dfs(4),进入dfs(3),输出k=1
                //k=k+1,a[3]=2,程序进入dfs(4),输出122,退出dfs(4),进入dfs(3),输出k=2
                //...*/
    
            }
        // i的值在函数调用内会不断的增加直到超越DNAsequences_length即最终终止此函数的条件是i=DNAsequences_length+1
    
    }
    
    int main() {
    
    
        freopen("V0in.txt", "r", stdin); //输入重定向，输入数据将从V0in.txt文件中读取
        freopen("V0out.txt", "w", stdout); //输出重定向，输出数据将保存在V0in.txt文件中
        cin >> DNAsequences_length; // DNAsequences_length是指需要全排序使用的元素个数
        cin >> DNABase_types;//表示生成序列的长度
        dfs(1);
        cout << Count << endl;
        // Count是一个全局变量，用于统计一共生成的序列数
        fclose(stdin);//关闭文件
        fclose(stdout);//关闭文件
        return 0;
    }

# 结果 #

*  **V1in.txt**  
    ![949241-20190626193602198-810504416.png][]

![949241-20190626194433838-1986447074.png][]

--------------------

![949241-20190626194520308-1439074970.png][]

--------------------

转载于:https://www.cnblogs.com/cloud-ken/p/11093485.html

[Follow Me]: https://github.com/Asurada2015
[949241-20190626193153799-1269276020.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/78f8a992c4224657be29c1e43d553516.jpg
[949241-20190626193602198-810504416.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c121bbff3c344e7c9c2a1cdf7f3d3ddd.png
[949241-20190626194433838-1986447074.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8c3a91bcac244ed984a4f96709f615a2.png
[949241-20190626194520308-1439074970.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2b2bb70c85ae41d69e007bde39192ef1.png