最简单易懂的10堂算法入门课——程序结构

2374人浏览 / 0人评论

先来做个小复习

上一课咱们理解了什么是算法,简单的说算法就是:

“计算机的计算方法”

也知道算法有三个要素——

数学模型输入输出方法算法步骤

算法程序的基本要素

想再仔细看上一课内容的同学,可以在下面的专栏中找到。

什么设计“算法步骤”呢?

就是教计算机一步一步怎么算,也就必须考虑到计算机思考的规律,这个规律其实是人设定的,叫做——

程序结构

程序结构是计算机思维与人脑思维的桥梁

了解程序结构,我们就知道如何把我们人脑的思维,转换为计算机思维了。

那么,计算机怎么思维的呢?

按照现代计算机体系总设计师,冯诺依曼的话——

“CPU每次只能串行执行一条指令。”

多核处理器会在顶层设计并行计算的算法

那些号称支持多线程的操作系统,其实也只是“宏观上并行,微观上串行”。

所以初学算法,可以认为,计算机总是串行地执行指令,一次执行一条。

其实程序结构只有仨

算法是千姿百态,但所有程序只有三种结构——

顺序执行循环执行分支执行

下面依次介绍。

算法一词云

程序结构之一:顺序执行

太简单了,一看字面就知道,就是依照着先后顺序执行指令

这是编程中最基本的结构,只要不在循环中,也不在分支跳转中,那么都默认是顺序执行,简单明确。

结构写出来就长这个样子:

指令1;

指令2;

指令3;

那么执行起来就是:指令1->指令2->指令3,SO EASY。

程序结构之二:循环执行

计算机之所以厉害,有一个重要原因,就是它能重复执行相同的一段指令,把人类从重复地劳动中解脱出来,凡是重复的指令就可以使用“循环执行”的程序结构。

分形图就是同一段代码在循环中变化得到的

最简单的循环结构写出来长这个样:

下面括号内的指令循环执行100次

{

指令1;

}

这样,指令1就循环执行100次,执行完100次后就继续执行接下来的指令。

大括号前面的一句话,称为“循环条件”,就是指明,这个循环的初始条件终止条件

具体地说,上面的结构在运行时,后台会产生一个变量,姑且叫做 i,循环第一次执行时,i=1,每执行一次指令1,i 就自己增加1,即 i 变成 i+1,直到 i=100 时,就是最后一遍执行指令1的时候了。

这里不得不提一句“递归结构”

个别的程序结构书籍文献中,会把“递归结构”单独归为一种程序结构,个人以为不妥,原因很简单——

递归结构都可以写成循环结构的形式

Infinity time with heart shapes

递归,是一种非常重要的解决问题的思路,它最了不起的地方,就是能把复杂问题简化一点点,而且这个简化过程是可以重复的!最终复杂的大问题就变成了容易解决的小问题。

那么什么叫“递归”呢?

举个例子,我要写一个算法来计算 n!(n的阶乘,即 n!=1x2x3x...x(n-1)xn)

这是一个规模比较大的问题,比如当n=10000时,我们不可能用计算器去按,对吧。

好在这个大规模问题有一个明显的规律,就是它可以分解出一个“规模小那么一点的问题”,即——

n!=(n-1)! x n

这就把原来求 n! 的问题,化为了求 (n-1)! 的问题。


好了,直接上程序:(假设n=10000)

m=1;(阶乘储存变量初始化)

变量 i 从1数到10000

{

m=m x i;

}

是的,就这么简洁!

以后再遇到规模为n的问题,就可以想想,它是不是能简化成 n-1 规模的问题,只要找到两者之间的联系,就能解决问题。

这种思维很好理解吧。

递归法计算所需调用资源偏多

程序结构之三:分支结构

计算机程序要想显得很聪明,还必须能够做出判断和选择,这就靠分支结构了。

首先上个简单的例子,我们知道百分制考试中60分是及格,那么问题来了,请设计一个算法,得到小刚(成绩为70分)的成绩状态(是否及格)。

令 A=70; (将小刚的成绩输入进来储存在A中)

如果 A>=60

{

成绩状态=“及格”;

}

否则(即A<60时)

{

成绩状态= “不及格”;

}

很清晰吧,对于条件进行判断,条件为真时,执行某一指令,条件为假时,执行另一指令。这就是分支结构,程序好像被分流成两个分支,要么执行这一条指令,要么就执行另一条指令

聪明的机器人就是依靠一个又一个的分支判断

分支结构进阶——函数表结构

当问题变得复杂以后中,分支结构中的所执行的指令可能会变得很长,而过长的分支结构是不好的,因为这样会大大降低程序的可修改性

函数表结构,简单地说,把各种状态下的动作打包成函数并列成表。

仍然可以拿上面的问题来举例,当然问题复杂时才能体现优越性。

令 A=70; (将小刚的成绩输入进来储存在A中)

令 函数(1) 作用是输出“及格”;

令 函数(2) 作用是输出“不及格”;

如果 A>=60

{

状态值=1;

}

否则

{

状态值=2;

}

执行函数(状态值);

当问题变得复杂以后,程序中有太多的条件判断,或者有太长的执行指令,或许可以试试这种函数表结构的方法,可能会有意想不到的收获哦!

程序结构精华总结


1 基本的程序结构只有三种:顺序/循环/分支。三种结构互相组合/嵌套,就能形成千变万化的各种各校的程序。

2 顺序结构是计算机原理的根本;循环结构是计算机能解决重复劳动问题的原因;分支结构让电脑能够判断/选择,变得聪明起来。

递归是循环的一种,递归可以把规模为n的问题,简化到规模为n-1的问题上,并且可以循环这个过程,最终变成容易解决的问题。

4 分支结构过长是不好的,可以采用函数表结构的形式,把状态用数字表示出来,以解决这个问题,程序会变得非常简洁美妙。


全部评论

晴天下起了小雨
2017-10-01 18:00
很喜欢,果断关注了
wjmyly7336064
2017-10-01 18:00
相当实用,赞美了
橘大佬
2017-10-01 18:00
就是有些细节再到位点就好了…