第三章 算法基础

3-1　体验计算机解决题的过程

3.1.1　人工解决问题的过程

-　首先要分析问题的需求情况、已知条件和需要解决的问题。 -　整理解决问题需要的各类数据。 -　从已知条件和已经获取的数据中推理出可能的最佳方案。 -　当问题的复杂度过高或数据量过于庞大的时候，人工无法获取最优解。 -　当得到自认为的最优解后，无法快速的进行科学验证。

3.1.2　计算机解决问题的过程

-　首先要分析问题的需求情况、已知条件和需要解决的问题。 -　设计算法 -　编写程序 -　调试运行程序

学生实践

• 安装python编程环境的方法。【视频】

• 访问python 官网，找到下载windows操作系统下，python环境的安装程序位置。

• 在桌面上运行“命令提示符”，运行python命令行模式。观察python环境窗口，了解python当前版本。

• 初次使用python编程环境:掌握下列编程环境的启动方法，窗口界面，主要菜单，编写代码的方式。

• python idle

• thonny

• jupyter notebook

• 编写“Hello world!”程序。 参考代码： print("Hello world!")

解释：print()是python输出函数，将括号中的表达式计算后输出。括号中可以是数值、字符串或表达式。

• 求算式的值的整数部分： $$ 9988×2333÷567 $$ 主要参考代码：int(9988*2333/567) 结果：41097

​ 解释：int(x)是取x整数部分的数学函数。

• 体验计算机求解最佳路线问题

打开“计算机”，找到“share”网络共享盘“Z:”，在“Z:\share\resource\3”中，找到“程序3-1.py”，使用python编辑工具打开。

说明：

此代码引用了xlrd和xlwt两个EXCEL操作库，因此，如果计算机中的python没有安装这两个库时，需要先安装。步骤如下：

• 打开命令提示符窗口
• 输入：pip install xlrd 后回车，等候安装完毕。
• 输入：pip insall xlwt后回车，等候安装完毕。

import xlrd
ms=[]
ra=[]
rb=[]
for k in range(1,4):
    data = xlrd.open_workbook("./data/B"+str(k)+".xlsx")
    table_1 = data.sheet_by_name("Sheet1")
    table_2 = data.sheet_by_name("Sheet2")
    rs1 = table_1.nrows
    rs2 = table_2.nrows
    m= 99
    for i in range(1,rs1):
        t14 = table_1.cell(i,4).value
        t12 = t14-table_1.cell(i,2).value
        for j in range(1,rs2):
            t22 = table_2.cell(j,2).value
            if t22-t14>=1/24 :
                m1=t12+(t22-t14)+(table_2.cell(j,4).value-t22)
                if m>m1:
                    m=m1
                    r1=i
                    r2=j
    ms.append(m)
    ra.append(r1)
    rb.append(r2)
ms0=min(ms)
ms1=ms.index(ms0)
print("从A地出发经B",ms1+1,"到达B地，最少耗时为：",ms0*24,"小时。具体行程请查看文件zjxc.XLS。")
data = xlrd.open_workbook("./data/B"+str(ms1+1)+".xlsx")
table_1 = data.sheet_by_name("Sheet1")
table_2 = data.sheet_by_name("Sheet2")


import xlwt
wbk = xlwt.Workbook()
sheet = wbk.add_sheet('sheet 1')
for l in range (5):
    sheet.write(0,l, table_1.cell(0,l).value)
    sheet.write(1,l, table_1.cell(ra[ms1],l).value)
    sheet.write(2,l, table_2.cell(rb[ms1],l).value)
wbk.save('./data/zjxc.xls')

3.2 算法及其描述

3.2.1　算法

1.算法

算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，算法就是用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。

2.算法的五个特征

1. 有穷性　

一个算法在执行有穷步之后必须结束，即一个算法所包含的计算步骤是 有限的。

1. 确定性　

算法执行的每一个步骤必须有确切的定义，不能出现模棱两可的情况。

1. 数据输入　

一个算法必须有零个或多个数据输人，以确定运算对象的初始情况。

1. 数据输出　

一个算法有一个或多个数据输出，以反映对输人数据加工后的结 果，没有输出的算法是毫无意义的。

1. 可行性　

算法中执行的任何计算步骤都可以被分解为基本的可执行的操作步 骤，即每个计算步骤都可以在有限时间内完成。

3.2.2　算法的描述【视频】

1、描述算法的常用方法

1. 用自然语言描述算法

2. 用流程图描述算法

x是用程序框图来描述算法的一种表示方法。使用流程图描述算法， 可使算法的流程描述得清晰、简洁。

1. 用伪代码描述算法

用伪代码描述算法就是用介于自然语言和计算机语言之间的文字和符号来描述算法。它不用图形符号，书写方便，格式紧凑，易于理解，便于向计算机程序设计语言过渡。

### 学生实践

任务：绘制计算机分发校服的流程图。学生站在计算机前，如果是男生，就发裤子，如果是女生，发裙子。

访问http://iodraw.com, 在线绘制。

2、三种基本控制结构【视频】

这三种基本控制结构的主要作用是：

1. 顺序结构表示程序中的各步操作按出现的先后顺序执行。
2. 选择结构表示程序的处理步骤出现了分支，需要根据某一特定的条件选择其中 的一个分支执行。选择结构有单选择、双选择和多选择三种。
3. 循环结构表示程序反复执行某个或某些操作，直到判断条件为假(或为真)时 才可终止循环。

学生实践

任务：在上面分发一个同学校服的流程图基础上，绘制计算机分发全班校服的流程图。

要求：绘制好流程图后，点击页面上的“文件”菜单，“保存”命令，就可以下载当前的流程图。再将流程图文件通过屏幕上方的极域学生端提交文件功能，提交给教师。

3.3 计算机程序与程序设计语言

3.3.1 计算机程序

• 计算机程序

​ 就是指计算机可以识别运行的指令集合。

• 计算机程序工作原理【视频】

​ 计算机主要包括运算器、控制器、存储器、输入设备和输出设备五大基本部件。

​ 计算机内部采用二进制形式表示和存储指令或数据，把解决问题的程序和需要加工处 理的原始数据事先转换成二进制数，并存入存储器中。计算机的工作过程实际上是周而复始地获取指令、执行指令的过程。

3.3.2 计算机程序设计语言【视频】

计算机程序设计语言的发展，经历了从机器语言、汇编语言到高级语言的发展历程。

• 机器语言

计算机只能识别“0”和“1”组成的二进制数，因此，二进制是计算机语言的基础。

早期的程序设计语言是由 “0”和“1”所表示的二进制代码指令组表示的。

• 汇编语言

人们使用了一种类似英文缩略词且带有助记性符号的语言，来替代一个特定的指令二进制串，每条指令都和一条机器指令相对应，只是指令码和操作数都采用符号形式，这种程序设计语言就被称为汇编语言，即第二代计算机语言。

汇编语言程序需要经过翻译程序转换成机器语言后，才能被计算机执行。

• 高级语言

高级语言接近于数学语言和人的自然语言，并且不再过度地依赖某种特定的机器或环境。

第一种髙级语言是Fortran语言，它主要用于科学和工程计算。 用高级语言编写的程序也不能直接被计算机所识别和执行，必须经过编译程序或解释程序将其翻译成机器语言。 高级语言发展也经历了从早期语言到结构化程序设计语言、从面向过程到非过程化程序设计语言的过程。

高级语言的程序代码不能直接被执行，需要经过编译程序编译成机器语言，或通过解释程序逐条解释成机器语言后才能运行。

C和C++都是编译型语言，Python是解释型语言。

3.3.3 学生实践

1.根据下面的自然语言描述，绘制“辗转相除法“的流程图。

2、在Thonny编辑器中输入下面的代码，（注释部分省略），并调试运行，获取正确结果。