您现在的位置是:门户> 算法与数据结构

最简单易懂的10堂算法入门课——程序结构
x0ffer 2018-12-04 424人围观 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 分支结构过长是不好的,可以采用函数表结构的形式,把状态用数字表示出来,以解决这个问题,程序会变得非常简洁美妙。


分享:

文章评论