一道简单但具有dfs(深度优先搜索)思想模型的题目
本文最后更新于 244 天前,其中的信息可能已经有所发展或是发生改变。

一.题目描述

输入一个数n,输出1~n的全排列。

 

二.解题思路

我们可以先把问题形象化,举个例子,我们有1,2,3个箱子和号数为 1,2,3的三张扑克,放到箱子有几种放法?第一步就是先将1号扑克放到1号箱子里,然后把2号扑克放到2号箱子里。

以此类推,直到当我们到第四个箱子面前(好像没有第四个箱子(/ω\)),因为我们不需要第四个箱子,所以此时已经完成了一次排列。

那么接下来,我们回到第3号箱子(递归),把扑克收回,此时扑克3号在我们手中(标记),再次回到第2号箱子这里,将2号扑克收回,此时2号扑克在我们手中,我们继续遍历放置,再将3号扑克放到2号箱子里,然后走到了3号箱子,把2号扑克放到3号箱子里,此时又完成了一次排列组合。按照这个步骤模拟,就会得出排列。

123
132
213
231
312
321

那么此时程序应该怎么实现呢?

#include<stdio.h>

int box[10],joker[10],n;

void dfs(int step) //step表示现在站在第几个盒子面前
{
    int i;
    if (step == n+1) //如果站在第n+1个盒子面前,则表示前n个盒子已经放好了扑克牌
    {
        //输出一种排列(1~n号盒子中的扑克牌序号)
        for ( i = 1; i <=n; i++)
        {
            printf("%d",box[i]);
        }
        printf("\n");   

        return; //返回之前的一步(最近一次调用dfs函数的地方)
    }
    //此时站在第step个盒子面前,应该放哪张牌呢?
    //按照1,2,3....n的顺序一一尝试
    for ( int j = 1; j <=n; j++)
    {
        //判断扑克牌i是否还在手上
        if (joker[j] == 0) //book[i]等于0表示i号扑克牌在手上
        {
            //开始尝试使用扑克牌i
            box[step] = j; //将i号扑克牌放入到第step个盒子中
            joker[j] = 1; //将Book[i]设为1,表示i号扑克牌已经不再手上
            //第step个盒子已经放好扑克牌,接下来需要走到下一个盒子面前
            dfs(step+1); //这里通过函数的递归调用来实现(自己调用自己)
            joker[j] = 0; //这是非常重要的一步,一将要将刚刚尝试的扑克牌收回,才能进行下一次尝试
        }        
    }
    return;
}
int main()
{
    scanf("%d",&n); //输入的时候323注意n为1~9之间的整数
    dfs(1); //首先站在1号小盒子3面前
    getchar(); getchar();
    return 0;
}

 

这个简单的例子(恶心了我两天),核心代码很短,但是却饱含了深度优先搜索(Depth First Search)DFS的基本模型,理解DFS的关键在于:“当下该如何做”,至于“下一步应该怎么做”则与“当下应该怎么做”一样的,比如我们这里写的dfs函数主要功能是解决当你在第step个盒子的时候你该怎么办。通常的方法是把每一种可能都去尝试一遍(for循环),当这一步成功解决后进入下一步(step+1)。

即:

//判断边界

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

{

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

}

每一种尝试就是一种“扩展”,每次站在一个盒子面前的时候,都有n(n表示全排列的n)种扩展方法,但并不是每种扩展都能成功。

 

到这里这题就结束了,简单的题目描述,饱含了一种算法模型,希望早点能吸收消化。。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇