Erlo

通过一个小算法,谈谈学习如何编写程序

时间:2019-03-15 19:01   阅读:16次   来源:博客园页面报错

点赞 打赏

×打赏

支付宝

微信

给定一个数字列表,返回其所有可能的排列

输入:[1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

假定各个数字不相同

给出核心代码

   private void dfs(int[] nums,

                     boolean[] visited,
                     List<Integer> permutation,
                     List<List<Integer>> results) {
        if (nums.length == permutation.size()) {
            results.add(new ArrayList<Integer>(permutation));
            return;
        }
       
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
           
            permutation.add(nums[i]);
            visited[i] = true;
            dfs(nums, visited, permutation, results);
            visited[i] = false;
            permutation.remove(permutation.size() - 1);
        }
    }

考虑int[] nums={1,2,3,4}情况

——————————————————————————————————————————————

可以看下面各个量的变化情况,当看不懂算法的时候,可以用这种方法,自己一步一步模拟程序做了什么,就能明白代码的含义了

在这个小例子中,visted【】数组存放的是,1234是否在permutation中的状态,

对于1234这四个数,visited【0】=false,就代表1没在permutation中

1234会不断添加到permutation中,并且当4个数字都进入p中时,会得到一个结果;

——————————————————————————————————————————————

在模拟的过程中,我们明白各个变量发生了什么,所代表的意义

然后对于比较有代表性的几个位置,看看程序发生了什么

——————————————————————————————————————————————

1     观察程序回到dfs(tttf,1230)时

v2 变成f

p   变成1200

循环进入f3

而此时4不在p中

4进入p中

然后重新调用

dfs(ttft,1240)

可以预见,下一个进入result的就是1243

————————————————————————————————

2    继续观察程序运行到dfs(tttt,1432)

首先会将1432add进入result

然后回到dfs的位置

dfs(tttf,1430)的f1循环中,

继续运行

v1变成f  p变成143 此时v是 tftt然后

f2 t

f3 t

此时 dfs(tttf,1430)运行结束 A8位置

给出A8之前的三行

f2 f

p143

v2 t tftt

然后我们继续模拟程序

v2 f tfft

p14

f3 t

说明某个dfs已经完成了全部循环,这个dfs的位置应该是最近的一个没有被标号的dfs

因为有标号的,说明都被执行完了

goto A9

我们回到了 dfs(tfft,1400)A9

f3 f

p14

v3 t tfft

继续模拟程序

v3 f

p1

此时 dfs(tfft,1400)所在的循环也结束了

goto A10

说明dfs(tfff,1000) A10也执行结束了

观察dfs(tfff,1000) A10上面的三行代码

f0 f

p1

v0 f

继续进行

v0 f ffff

p0000

f1 f

p2

v1 t

dfs(ftff,2000)

——————————————————————————————————————————————————————————————

通过这两处 我们完全可以明白这些代码的意义了

对于任何一位上的某个数字a,在它进入p之后,对于这一位来讲,没进入p而比a更靠后的数字,会添加进p

而对于当添加一个元素进入后,它的下一位会从重新又从头去寻找v[i] t,也就是没有进入p的数字

而对于填入某个位置数字后的dfs执行完成了,如果后一位的数字都比前一位的数字在原数组更靠前,那么就会出现

每退掉一位,回到前一个dfs,而将要退掉这个位置的数字,而之前的数字,在原数组的位置都比这个数字靠前,所以之后的循环不会再有数字进入

如果是1432,那么会变成2000

如果是4321,那么会变成dfs(fttt,4000)结束,整个程序结束

——————————————————————————————————————————————————————————————

 

而学习其他代码的过程也类似

看懂了代码以后,尝试用自然程序做了什么说出来,如果能说明白发生了什么事,也就说明看懂了

然后再把自己想要完成的事梳理一下,拆解成一步一步要做的事,再用代码使其重新实现

学习代码的过程:

  模拟程序代码逐条运行 ——》尽量提炼出代码块的作用 ——》用自然语言 说明算法做了什么

而编写代码的过程:

  分析问题——》提出完成算法的各个步骤 ——》逐条编写代码完成各个步骤 ——》调试,带入测试数据

 

下面给出模拟程序运行时,各个变量的变化情况

dfs(ffff,0000)  //dfs(nums,ffff,,)为了方便 只写最频繁变化的两个参数

f0 f       //f(0) 为了方便写成 f0 v[0]是f

p1        //permutation={1} 为了方便写成 p1

v0 t     tfff      //v[0]改成0 visited变成 tfff

dfs(tfff,1000) A10

f0 t   

f1 f

p12

v1 t 

dfs(ttff,1200) A3

f0 t

f1 t

f2 f

p123

v2 t

dfs(tttf,1230) A1

f0 t

f1 t

f2 t

f3 f

p1234

v3 t

dfs(tttt,1234)

result 1234 //这里的dfs直接结束了 能找到

v3 f tttf

p123

goto A1 这里其实是方法A的 for循环结束了 返回A所在位置,继续下一行

v2 f ttff

p12

f3 f

p124

v3 t

dfs(ttft,1240) A2

f0 t

f1 t

f2 f

p1243

v2 t

dfs(tttt,1243)

result  1243

v2 f ttft

p124

f3 t

goto A2

v3 f ttff

p12

goto A3

v1 f tfff

p1 

f2 f

p13

v2 t tftf

dfs(tftf,1300) A6

f0 t

f1 f

p132

v1 t

dfs(tttf,1320) A4

f0 t

f1 t

f2 t

f3 f

p1324

v3 t tttt

dfs(tttt,1324)

result 1324

v3 f tttf

p132 

goto A4

v1 f tftf

p13

f2 t

f3 f

p134

v3 t tftt

dfs(tftt,1340) A5

f0 t

f1 f

p1342

v1 t tttt

dfs(tttt,1342)

result 1342

v1 f tftt

p134

f2 t

f3 t

goto A5

v3 f tftf

p13

goto A6

v2 f tfff

p1

f3 f

p14

v3 t tfft

dfs(tfft,1400)A9

f0 t

f1 f

p142

v1 t ttft

dfs(ttft,1420) A7

f0 t

f1 t

f2 f

p1423

v2 t tttt

dfs(tttt,1423)

result 1423

v2 f ttft

p142 

f3 t

goto A7

v1 f tfft

p14

f2 f

p143

v2 t tftt

dfs(tftt,1430) A8

f0 t

f1 f

p1432

v1 t

dfs(tttt,1432)

return 1432

v1 f tftt

p143

f2 t

f3 t

goto A8

v2 f tfft

p14

f3 t

goto A9

v3 f tfff

p1

goto A10

v0 f ffff

p000

f1 f

p2

v1 ftff

dfs(ftff,2000)

我们可以预见 下一个就是2134

我们已经完全可以预见程序将要完成什么了

也就是此时此刻,我们看懂了这段代码的含义

 

下一篇:基于SSH+shiro+solr的家庭记账系统

评论留言

还没有评论留言,赶紧来抢楼吧~~

Erlo大厅()

* 这里是“吐槽厅”,所有人可看,只保留当天信息。

  • Erlo.vip2019-03-19 12:42:06Hello、欢迎使用吐槽厅,这里是个吐槽的地方。
  • 首页 笔记分享 案例展示 ERLO 搜索
    鼠标试试
    返回顶部