计算思维课程思考
信安1502刘嘉欣
摘要：信息技术的快速发展不仅改变着人们的日常行为方式，也转变着人们的认知结 构和思维特征。计算机渗入到人类生活的各个领域，影响和改变着人们的生活，人类如今要做的是让计算机成为帮助自己的工具，而不是沦为计算机的奴隶，这其中计算思维显得尤为重要，让学生学会像计算机科学家一样思考，不断培养学生的计算思维，这便是计算思维课程的目的。
关键词：课程回顾，思维方式的思考，建议，子集求和问题
一. 回顾
程序，作为计算机的核心部分，决定了计算机的功能及作用，使计算机能够按照人类的指令完成一系列的处理任务，它是一个详细的逐步执行的指令序列，没有程序，再华丽精致的计算机也只是一堆废铁。不同的程序完成不同的处理任务，而程序设计则是让程序智能地完成预设的处理任务的基础。
随着科技的日益进步，计算机已经占据了人类生活的各个层面，不少人为之奴役。而程序设计的本质则颠覆了这种奴役，它让人们成为计算机的主人，让计算机实现你想做的事，但这并非轻而易举的，它极具挑战性，需要调动大脑深处的各种思维模式，其中最重要的便是计算思维。
计算思维是涵盖了计算机科学领域中所采用的最广泛的心理工具，是对问题解决、系统设计、人类行为理解的综合能力反映。发展学生计算思维就是要‘像计算机科学家’那去思考信息化问题，当然这问题绝不只是应用于计算机科学领域，它适合信息技术所渗透的每一个角落。
计算思维课程便引导我们培养分析问题和解决问题的能力，引导我们培养和训练计算思维，像计算机科学家一样去思考，课程介绍的各种思维方法给我们扩展了狭隘的思维广度，学会去探索去发现新的思维深度。
（一）. 穷举法 穷举法是一种针对于密码的破译方法。这种方法很像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。
（二）递归法
递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n ）的求解推到比原问题简单一些的问题（规模小于n ）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib 中，当n 为1和0的情况。
（三）分治法
分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解。
（四）回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i 列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：
a[] a[i]=0表示第i 行上还没有皇后；
b[] b[i]=0表示第i 列反斜线/上没有皇后；
c[] c[i]=0表示第i 列正斜线\上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号相同；同一正斜线\上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m 列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m 列，col[m]行的位置设定有皇后的标志；当从第m 列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。
（五）贪心法
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
二．逆向思维
逆向思维作为一种新型的思考问题的思维模式，是信息安全专业所必需拥有的良好的思维习惯和思维方式。
逆向思维也叫求异思维，它是对司空见惯的似乎已成定论的事物或观点反过来思考的一种思维方式。敢于“反其道而思之”，让思维向对立面的方向发展，从问题的相反面深入地进行探索，树立新思想，创立新形象。尤其在如今的社会背景下，当人们的思维模式逐渐僵化，习惯于朝着固定的思维方向思考问题时，你偏要另辟蹊径；当大家一股脑儿的想要从正面将问题逐个击破却在问题开始的地方徘徊不前时，你偏要从反向推理，以问题的结果为开始，从求解回到已知条件，看似是标新立异，哗众取宠，却往往能让事情简单化，从而找到更快更有效的解决问题的办法，在不损失一兵一卒的情况下，使自己的利益最大化，或是在不经意间找寻到更为绝佳的反击的办法或是强劲的回击的力量。
当今的社会局势下，尤其是作为国家或企业负责信息安全有关的人员，若只是一昧的防守，那终将被社会所淘汰，现在的企业所需的，不是兵来将挡水来土掩的看似牢不可破实质找出一条裂缝就能推倒一面墙的防护，真正的防守在于进攻，你要敢于从入侵者的角度去思考，去找寻系
统的漏洞，去发现和维护，从而做到真正意义上的安全防护。
逆向思维决定了你与大多数人走在了不一样的路上，不代表你是和社会不在同一个空间维度，相反你的思维维度会更加立体，更加直观，更难找出破绽，能够逆向思维的人必定是思维缜密，思考问题深入的人，这样的人才又怎会被埋没，这样的人才定会在如今的社会上褶褶生辉。
三． 对课程的建议
对于大部分新生而言，计算机专业的知识是极其浅薄的甚至可以说是零基础的，所以我认为在培养计算思维的同时，课堂上可以适量的灌输一些基础知识，并且在教学方面可以将具体的思维方式与案例结合起来，并让学生自己动身实践，毕竟实践出真知，再多再深奥的道理也比不过自己动手一试，教学与实践结合才能让学生有更大的提升空间。
四．子集求和问题
给定正数w i (1≤i ≤n) 和m ，要求寻找w i 的所有子集，它们的和为m 。例如，如果n=4、（w 1,w 2,w 3,w 4）=（11，13，24，7）且m=31，那么想得到的子集为（11，13，7）和（24，
7）。与其通过和为m 的w i 来表示解向量，不如先为w i 指定索引，然后利用索引来表示解向量。一般来说，所有的解都表示为k 元祖（x 1,x 2, …,x k ）(1≤k ≤n) 的形式，不同的解对应着不同大小的元祖。显示约束要求x i ∈{j|j为整数，1≤j ≤n }。隐式约束要求任何两个w i 都不相同，且对应的w i 的和为m 。由于期望避免生成同一子集的多个实例，所以必须增加一个隐式约束xj
子集求和问题还有另外一种表示方法：每一个解子集都用一个n 元（x1,x2, …,xn ）, xi ∈{0，1}(1≤i ≤n) 来表示。如果没有选中wi ，那么xi=0；如果选中wi ，那么xi=1。
动态结构图
静态结构图
控制抽象：
void Backtrack(int t) {
if (t > n) Output(x);
else {
for (int i = f(n,t); i
x[t] = h(i);
if (Constraint(t) && Bound(t))
Backtrack(t+1);
}
}
}
t 表示递归深度
for 循环中f(n,t)和g(n,t)分别表示在当前扩展节点处未搜索过的子数的起始编号和终止编号。
h(i)表示在当前扩展节点处x[t]的第i 个可选值。Constraint(t)和Bound(t)表示在当前扩展节点处的约束方程和接线函数。
计算思维课程思考
信安1502刘嘉欣
摘要：信息技术的快速发展不仅改变着人们的日常行为方式，也转变着人们的认知结 构和思维特征。计算机渗入到人类生活的各个领域，影响和改变着人们的生活，人类如今要做的是让计算机成为帮助自己的工具，而不是沦为计算机的奴隶，这其中计算思维显得尤为重要，让学生学会像计算机科学家一样思考，不断培养学生的计算思维，这便是计算思维课程的目的。
关键词：课程回顾，思维方式的思考，建议，子集求和问题
一. 回顾
程序，作为计算机的核心部分，决定了计算机的功能及作用，使计算机能够按照人类的指令完成一系列的处理任务，它是一个详细的逐步执行的指令序列，没有程序，再华丽精致的计算机也只是一堆废铁。不同的程序完成不同的处理任务，而程序设计则是让程序智能地完成预设的处理任务的基础。
随着科技的日益进步，计算机已经占据了人类生活的各个层面，不少人为之奴役。而程序设计的本质则颠覆了这种奴役，它让人们成为计算机的主人，让计算机实现你想做的事，但这并非轻而易举的，它极具挑战性，需要调动大脑深处的各种思维模式，其中最重要的便是计算思维。
计算思维是涵盖了计算机科学领域中所采用的最广泛的心理工具，是对问题解决、系统设计、人类行为理解的综合能力反映。发展学生计算思维就是要‘像计算机科学家’那去思考信息化问题，当然这问题绝不只是应用于计算机科学领域，它适合信息技术所渗透的每一个角落。
计算思维课程便引导我们培养分析问题和解决问题的能力，引导我们培养和训练计算思维，像计算机科学家一样去思考，课程介绍的各种思维方法给我们扩展了狭隘的思维广度，学会去探索去发现新的思维深度。
（一）. 穷举法 穷举法是一种针对于密码的破译方法。这种方法很像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合，也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算，也就是说用我们破解任何一个密码也都只是一个时间问题。
（二）递归法
递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n ）的求解推到比原问题简单一些的问题（规模小于n ）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib 中，当n 为1和0的情况。
（三）分治法
分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解。
（四）回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i 列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：
a[] a[i]=0表示第i 行上还没有皇后；
b[] b[i]=0表示第i 列反斜线/上没有皇后；
c[] c[i]=0表示第i 列正斜线\上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号相同；同一正斜线\上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m 列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m 列，col[m]行的位置设定有皇后的标志；当从第m 列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。
（五）贪心法
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
二．逆向思维
逆向思维作为一种新型的思考问题的思维模式，是信息安全专业所必需拥有的良好的思维习惯和思维方式。
逆向思维也叫求异思维，它是对司空见惯的似乎已成定论的事物或观点反过来思考的一种思维方式。敢于“反其道而思之”，让思维向对立面的方向发展，从问题的相反面深入地进行探索，树立新思想，创立新形象。尤其在如今的社会背景下，当人们的思维模式逐渐僵化，习惯于朝着固定的思维方向思考问题时，你偏要另辟蹊径；当大家一股脑儿的想要从正面将问题逐个击破却在问题开始的地方徘徊不前时，你偏要从反向推理，以问题的结果为开始，从求解回到已知条件，看似是标新立异，哗众取宠，却往往能让事情简单化，从而找到更快更有效的解决问题的办法，在不损失一兵一卒的情况下，使自己的利益最大化，或是在不经意间找寻到更为绝佳的反击的办法或是强劲的回击的力量。
当今的社会局势下，尤其是作为国家或企业负责信息安全有关的人员，若只是一昧的防守，那终将被社会所淘汰，现在的企业所需的，不是兵来将挡水来土掩的看似牢不可破实质找出一条裂缝就能推倒一面墙的防护，真正的防守在于进攻，你要敢于从入侵者的角度去思考，去找寻系
统的漏洞，去发现和维护，从而做到真正意义上的安全防护。
逆向思维决定了你与大多数人走在了不一样的路上，不代表你是和社会不在同一个空间维度，相反你的思维维度会更加立体，更加直观，更难找出破绽，能够逆向思维的人必定是思维缜密，思考问题深入的人，这样的人才又怎会被埋没，这样的人才定会在如今的社会上褶褶生辉。
三． 对课程的建议
对于大部分新生而言，计算机专业的知识是极其浅薄的甚至可以说是零基础的，所以我认为在培养计算思维的同时，课堂上可以适量的灌输一些基础知识，并且在教学方面可以将具体的思维方式与案例结合起来，并让学生自己动身实践，毕竟实践出真知，再多再深奥的道理也比不过自己动手一试，教学与实践结合才能让学生有更大的提升空间。
四．子集求和问题
给定正数w i (1≤i ≤n) 和m ，要求寻找w i 的所有子集，它们的和为m 。例如，如果n=4、（w 1,w 2,w 3,w 4）=（11，13，24，7）且m=31，那么想得到的子集为（11，13，7）和（24，
7）。与其通过和为m 的w i 来表示解向量，不如先为w i 指定索引，然后利用索引来表示解向量。一般来说，所有的解都表示为k 元祖（x 1,x 2, …,x k ）(1≤k ≤n) 的形式，不同的解对应着不同大小的元祖。显示约束要求x i ∈{j|j为整数，1≤j ≤n }。隐式约束要求任何两个w i 都不相同，且对应的w i 的和为m 。由于期望避免生成同一子集的多个实例，所以必须增加一个隐式约束xj
子集求和问题还有另外一种表示方法：每一个解子集都用一个n 元（x1,x2, …,xn ）, xi ∈{0，1}(1≤i ≤n) 来表示。如果没有选中wi ，那么xi=0；如果选中wi ，那么xi=1。
动态结构图
静态结构图
控制抽象：
void Backtrack(int t) {
if (t > n) Output(x);
else {
for (int i = f(n,t); i
x[t] = h(i);
if (Constraint(t) && Bound(t))
Backtrack(t+1);
}
}
}
t 表示递归深度
for 循环中f(n,t)和g(n,t)分别表示在当前扩展节点处未搜索过的子数的起始编号和终止编号。
h(i)表示在当前扩展节点处x[t]的第i 个可选值。Constraint(t)和Bound(t)表示在当前扩展节点处的约束方程和接线函数。