啊哈！算法—DFS—放扑克

小鱼儿 2022-08-21 12:55 212阅读 0赞

将n张扑克放在n个盒子中，有哪些全排列。

思路：

利用深度优先搜索。

深度优先搜索关键在于解决“当下该如何做”。至于“下一步该如何做”则和“当下该怎么做”是一样的。

void dfs(int step)

\{

判断边界

尝试每一种可能 for(i=1;i<=n;i++)

\{

继续下一步 dfs(step+1);

\}

返回

\}

#include <iostream>
    using namespace std;
    int a[10],book[10],n;  //全局变量未赋值前均默认为0
    void dfs(int step)    //step表示站在第几个盒子面前
    {
        int i;
        if(step==n+1)     //如果站在第n+1个盒子面前表示前n个盒子已放好
        {
            for(i=1;i<=n;i++)  //输出一种全排列
                cout<<a[i]<<" ";
            cout<<endl;
            return;        //递归出口，返回
        }
        //盒子里放哪张牌，按照1,2,3...的顺序一一尝试
        for(i=1;i<=n;i++)
        {
            //判断扑克牌是否在手上
            if(book[i]==0)   //表示在手上
            {
                a[step]=i;   //将i放在第step个盒子中
                book[i]=1;    //表示i扑克牌已不在手上
                //接下来需走到下一个盒子面前
                dfs(step+1);
                book[i]=0;   //将刚才放完的扑克牌一一收回，再进行下一次尝试
            }
        }
        return;
    }
    int main()
    {
        cin>>n;    //输入为1~9之间的整数
        dfs(1);    //首先站在1号盒子面前
        return 0;
    }

运行结果：  
![Center][]

[Center]: /images/20220724/231c00ae1d424aa689f7db76a29c004a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关【啊哈！算法】文章目录

[《啊哈！算法》读书笔记][Link 1] [《啊哈！算法》学习心得][Link 2] -------------------- <table> <thea

系统管理员/ 2022年10月22日 07:54/ 0 赞/ 224 阅读

相关啊哈！算法—深度优先搜索DFS—解救小哈

小哈去玩迷宫，结果迷路了，小哼去救小哈。迷宫由n行m列的单元格组成（n和m都小于等于50），每个单元格要么是空地，要么是障碍物。问题：帮小哼找到一条从迷宫的起点通往小哈所在

拼搏现实的明天。/ 2022年08月21日 13:57/ 0 赞/ 202 阅读

相关啊哈！算法—DFS—坑爹的奥数2

下面等式：？？？+？？？=？？？，将数字1~9分别填入9个？中，每个数字只能使用一次使得等式成立。例如：173+286=459 和 286+173=459 是同一个组合

悠悠/ 2022年08月21日 12:55/ 0 赞/ 187 阅读

相关啊哈！算法—DFS—放扑克

将n张扑克放在n个盒子中，有哪些全排列。思路：利用深度优先搜索。深度优先搜索关键在于解决“当下该如何做”。至于“下一步该如何做”则和“当下该怎么做”是一样的。 v

小鱼儿/ 2022年08月21日 12:55/ 0 赞/ 213 阅读

相关啊哈！算法—火柴棍等式

现手中有m(m<=24)个火柴棍，希望拼出A+B=C等式。等式中的A、B、C均为火柴棍拼出来的整数（若该数非0，则最高位不能为0）。注意： 1、加号与等号各自需要2根火

小灰灰/ 2022年08月21日 12:47/ 0 赞/ 226 阅读

相关啊哈算法（8）——更多精彩的算法

1、图的最小生成树（Kruskal算法）对于一个给定的图，找出其最小生成树，用最少的边让n个顶点的图连通，很显然若要让n个顶点的图连通，最少要n-1条边，最小生成树还需要

逃离我推掉我的手/ 2022年05月15日 06:48/ 0 赞/ 268 阅读

相关啊哈算法（7）——神奇的树

1、堆（完全二叉堆）建堆的方法：（自上而下的向上调整）每一次插入一个新节点，并且对其进行向上调整，实现如下： /建立最小堆，方法一/ in

冷不防/ 2022年05月15日 06:42/ 0 赞/ 246 阅读

相关啊哈算法（6）——最短路径

最短路径问题：对于一个给定的的图求出任意两点之间的最短路径？可以通过DFS或者BFS求出两个点之间的最短的路径，在本节介绍其他的算法来求出两个点之间的最短路径。

柔光的暖阳◎/ 2022年05月15日 05:44/ 0 赞/ 225 阅读

相关啊哈算法（4）—万能的搜索

深度优先搜索DFS 深度优先搜索的关键在于解决“当下该如何做”。至于下一步怎么做与当下该如何做是一样的。深度优先搜索的基本模型： void dfs(int ste

痛定思痛。/ 2022年05月15日 01:27/ 0 赞/ 284 阅读

相关编程珠玑 ~~ 啊哈! 算法

2. 啊哈，算法 A.给定一个包含32位整数的顺序文件，它至多包含40亿个这样的整数，并且整数的次序是随机的，请查找一个此文件中不存在的32位整数(至少必有一个遗漏，为什么？

谁践踏了优雅/ 2022年01月10日 01:21/ 0 赞/ 319 阅读