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

连穷举都看不懂,来求大大们指点一二了😂

  •  
  •   randomize · 2014-11-01 16:40:03 +08:00 via iPad · 3611 次点击
    这是一个创建于 3654 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这是个枚举全排列的程序😂
    能看得懂的:
    这个函数的 else 下面的循环是在每个数字填进去的时候检查此数组前面与其重合的数。

    看不懂的:
    1.在枚举完成、输出第一个排列之后,程序如何工作呢?没有 else 条件可以递归到下一次什么的。
    2.其实我偷偷的把代码打了一遍……可是 a 是个全局数组,输出一次之后就没有什么再次重置的操作么……
    3.检查此次输入与此次前面已经确认的数字里面无重复这个操作我看出来了,可是是如何实现,比如上次输出的排列是 1 2 3 ,这次就应该是 1 3 2 这次如何判断第二位要用 2 而非 3 的?

    程序:
    
    21 条回复    2014-11-02 12:44:16 +08:00
    kmvan
        1
    kmvan  
       2014-11-01 16:51:41 +08:00
    lz用的是啥手机拍的?重心偏绿四周姨妈红了!是华为中兴之类的国产手机吗?
    randomize
        2
    randomize  
    OP
       2014-11-01 16:58:38 +08:00 via iPad
    @kmvan
    iPad mini 1

    😂大牛指点一二?
    kmvan
        3
    kmvan  
       2014-11-01 17:07:57 +08:00
    原来是 apple 的ipad min,我错了,实际上这色彩还原度很不错,肯定是lz书本本来的颜色就是这样的。虽然有点模糊,应该是lz拍的时候手抖了吧。
    randomize
        4
    randomize  
    OP
       2014-11-01 17:23:48 +08:00 via iPad
    @kmvan
    好的……下次注意。

    大大帮忙解答下问题?
    aheadlead
        5
    aheadlead  
       2014-11-01 17:28:10 +08:00   ❤️ 3
    @kmvan 感觉在给肾洗地 虽然我一开始就没觉得偏色..
    aheadlead
        6
    aheadlead  
       2014-11-01 17:28:53 +08:00
    这是个深搜啊...
    llbbzh
        7
    llbbzh  
       2014-11-01 17:31:58 +08:00
    OI的程序建议上机用fprintf一步一步看它的执行过程
    mcwanderer
        8
    mcwanderer  
       2014-11-01 17:34:49 +08:00
    @kmvan 。。。。此贴变成了,讨论LZ拍摄技巧和拍摄设备的帖子了。。。
    gyorou
        9
    gyorou  
       2014-11-01 17:52:30 +08:00   ❤️ 1
    趁lz年轻,我来教一下lz提问的学问。

    一般有问题,第一个想到的应该是去搜索。是在特么的搜索不到,那么再向可能知道的人询问。

    但是,提问之前,要自我反省一下,自己有没有把问题的具体内容描述清楚?

    比如这个问题,lz不提供明确的上下文,就说一个全排序,然后截图一段代码,很多人都不会有时间来特意先揣摩一下这个问题到底是什么,然后再做解答的。

    然后实在是有无聊蛋疼的人。于是我来解释一下。

    首先这个问题的具体要求是:给出一个正整数n,然后输出从1到n的所有可能的排列。(问问题之前,先把问题描述清楚)

    那么利用穷举的方法是ok的。

    首先这个方法用到了递归。不懂递归的自行补习。

    然后看一下这个函数的三个参数,n就是给出的正整数,A指向整数数用来保存中间结果,最后的cur是当前需要决定的数组中的第cur+1( 0<=cur<n)个元素。

    那么问题就很简单了首先进入函数之后,先检查一下,如果当前数组A已经有n个元素,那么就已经形成了一个序列,那么输出结果。

    如果cur还没到达n,那么我们就开始决定地cur+1个元素到底该放入什么数字。因为现在已经安置好了编号0到cur-1的cur的元素,于是第cur的元素不能和前面的这些元素重复,于是我们设置一个ok的flag,然后从1到n中找到一个还没有在A的0到cur-1中出现的数字。找到了这个数字就将其放入数组A中,然后我们完成了从0到cur个元素,将cur+1,然后开始寻找cur+1可以放入的元素。
    randomize
        10
    randomize  
    OP
       2014-11-01 18:02:17 +08:00 via iPad
    @gyorou
    感谢抽出宝贵时间回答问题。

    问题问的不完全,承认,日后注意。但是总觉得有高中数学基础的人还是能够理解全排列的含义的?

    当然,我至少应该多说一句输入指定 n 😂

    另外,大大回答的是我已经看懂的,即「这个函数的 else 下面的循环是在每个数字填进去的时候检查此数组前面与其重合的数。」😂,能不能再看一看下面提出的问题?
    Sharuru
        11
    Sharuru  
       2014-11-01 18:09:16 +08:00
    @randomize
    递归叙述的篇幅往往很长, 很多时候在没有执行到最底层的时候根本不知道自己想当然的初值是否正确. 为了提升效率节约时间, 一开始就应该给出相关的信息.

    @gyorou 回答的很明白, 请仔细品味, 想要明白递归最方便的就是单步执行不断的输出, 如果你做了这样的事, 我想你也不会来问为什么了.
    iptux
        12
    iptux  
       2014-11-01 18:12:50 +08:00
    https://gist.github.com/iptux/021079aed9d280c3c619.js
    bash 版,bash -x XXX.sh 直接看运算过程
    我太无聊了
    zts1993
        13
    zts1993  
       2014-11-01 18:14:59 +08:00
    @kmvan 简直。。。
    gyorou
        14
    gyorou  
       2014-11-01 18:16:25 +08:00
    @randomize 这个要弄清递归的机制。递归会把中间结果保存下来,比如这次,想象一下一棵树,root是起点。 root有三个节点,1,2,3,1下面有2,3两个节点,1下面的2节点下面有节点3,1下面的3节点下面有节点2 这种。因为是递归,所以每次程序的起点不会是root,而是上一次的分歧点。
    lizheming
        15
    lizheming  
       2014-11-01 18:50:15 +08:00
    hx1997
        16
    hx1997  
       2014-11-01 19:07:56 +08:00   ❤️ 1
    竟然看懂了hhh

    我们把这个函数简称为 P(n, A, cur),以全排列 1 2 3 为例。递归过程是这样的:

    P(3, A, 0)
    → P(3, A, 1)
    → → P(3, A, 2)
    → → → P(3, A, 3)

    对吧。那么呢,在执行到 P(3, A, 3) 的时候自然就会打印出第一个排列 1 2 3,打印完成后就回到了 P(3, A, 2) 的 else for 这里,这时会 i++ 变成 4 > n(注意是 P(3, A, 2) 中的 i),于是退出循环,再回到 P(3, A, 1) 的 else for 这里,这时会 i++ 变成 3(注意是 P(3, A, 1) 中的 i),于是 A[1] == 3,接着 P(3, A, 2) 再决定 A[2] == 2,再接着 P(3, A, 3) 打印 1 3 2。

    回到问题上

    1.在枚举完成、输出第一个排列之后,程序如何工作呢?没有 else 条件可以递归到下一次什么的。
    → 见上,利用递归性质以及循环。

    2.其实我偷偷的把代码打了一遍……可是 a 是个全局数组,输出一次之后就没有什么再次重置的操作么……
    → 因为决定完 1 2 3 后会退回到第二个的位置(递归),这时循环将 i++ 变成 3,于是就把第二位的 2 覆盖掉了,不需要重置。

    3.检查此次输入与此次前面已经确认的数字里面无重复这个操作我看出来了,可是是如何实现,比如上次输出的排列是 1 2 3 ,这次就应该是 1 3 2 这次如何判断第二位要用 2 而非 3 的?
    → 见上,利用递归性质以及循环。

    感觉还是没讲明白==
    klion26
        17
    klion26  
       2014-11-01 21:28:30 +08:00
    照着程序,手动执行一次,这样印象深刻。
    randomize
        18
    randomize  
    OP
       2014-11-01 21:47:36 +08:00 via iPad
    @hx1997
    感谢,看懂了,还是年龄相仿的大哥说的明白。

    可是但是看懂之后我觉得自己更加写不出来 DFS /回溯等等之类几乎必用递归的代码了😂
    hx1997
        19
    hx1997  
       2014-11-01 22:44:21 +08:00
    @randomize 多写写类似的代码会形成条件反射的。。。其实我没啥经验别听我的XD
    mikemikemike
        20
    mikemikemike  
       2014-11-02 12:02:45 +08:00
    @kmvan 你这风向变得好快。。。我去。。。
    kmvan
        21
    kmvan  
       2014-11-02 12:44:16 +08:00
    @mikemikemike 你这风向变得好快。。。我去。。。

    要知道这里大多都是果粉,我还不想被打死...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   919 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 20ms · UTC 21:32 · PVG 05:32 · LAX 14:32 · JFK 17:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.