计算机解决问题的过程

　　分析问题、设计算法、编写程序、调试运行、检测结果

计算机解决问题的流程-grcp.png

活动：贴春联

运行以下代码，对比用计算机贴春联和生活中贴春联的差异

Python程序运行调试方法参见：IDLE的使用方法 | 信息技术学习

import turtle
#右边春联
turtle.penup()
turtle.goto(100,150)
turtle.pendown()
turtle.color('red','red')
turtle.begin_fill()
turtle.forward(50)
turtle.right(90)
turtle.forward(400)
turtle.right(90)
turtle.forward(50)
turtle.right(90)
turtle.forward(400)
turtle.end_fill()
#左边春联
turtle.right(90)
turtle.penup()
turtle.goto(-150,150)
turtle.pendown()
turtle.begin_fill()
turtle.forward(50)
turtle.right(90)
turtle.forward(400)
turtle.right(90)
turtle.forward(50)
turtle.right(90)
turtle.forward(400)
turtle.end_fill()
#上边春联
turtle.begin_fill()
turtle.right(90)
turtle.penup()
turtle.goto(-100,200)
turtle.pendown()
turtle.forward(200)
turtle.left(90)
turtle.forward(50)
turtle.left(90)
turtle.forward(200)
turtle.left(90)
turtle.forward(50)
turtle.end_fill()
#写上联
turtle.penup()
turtle.goto(125,-210)
turtle.pendown()
turtle.color('black')
turtle.write('龙\n年\n书\n声\n琅\n琅\n起',align='center',font=('隶书',35))
#写下联
turtle.penup()
turtle.goto(-125,-210)
turtle.pendown()
turtle.color('black')
turtle.write('春\n日\n学\n子\n步\n步\n高',align='center',font=('隶书',35))
#写横批
turtle.penup()
turtle.goto(0,200)
turtle.pendown()
turtle.color('black')
turtle.write('学业有成',align='center',font=('隶书',35))
turtle.done()

运行成功后，请尝试修改代码，改成你自己的春联

算法

概念

　　算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。

编程界的“Pascal之父”Nicklaus Wirth有一句人尽皆知的名言：“算法+数据结构=程序”。（Algorithm+Data Structures=Programs），可见算法对程序的重要性。

发展历程

　　在我国古代，算法被称为“演算法”，关于算法的起源最早可以追溯到我国古代公元前1世纪的《周髀算经》，是算经的十书之一，原名《周髀》，主要阐述古代中国的盖天说和四分历法。在唐朝的时候，此书被定为国子监算科的教材之一，并改名为《周髀算经》。《周髀算经》中记载了勾股定理、开平方问题、等差级数等问题，其中用到了相当复杂的分数算法和开平方算法等。在随后的发展中，出现了割圆术、秦九昭算法和剩余定理等一些经典算法。

　　在西方，算法（algorithm）一词最早来源于9世纪波斯数学家花拉子米（花拉子米是代数与算术的创立人，被誉为“代数之父”，所著《代数学》一书，最早给出了一次和二次方程的一般解法），花拉子米的拉丁文译名是“Algoritmi”，英文对“算法”原译为“algorism”，意思是花拉子米的运算法则，指的是用阿拉伯数字进行算术运算的过程，在18世纪演变为“algorithm”。

数学家花拉子米

自然语言描述算法

　　所谓自然语言，就是日常生活中的语言。它可以是汉语、英语、日语等，一般用于描述一些简单的问题、步骤，可以使算法通俗、简单易懂。下面通过具体实例来介绍自然语言。例如，任意输入三个数，求这三个数中的最大数。

第一步：定义四个变量，分别为x、y、z以及max。第二步：输入大小不同的三个数，分别赋给x、y、z。

第三步：判断x是否大于y，如果大于，则将x的值赋给max，否则将y的值赋给max。

第四步：判断max是否大于z，如果大于，则执行步骤五，否则将z的值赋给max。

第五步：将max的值输出。

　　自然语言最大的优点就是容易理解，适用于比较简单的问题。对于比较复杂的问题或者在描述包括分支或循环的算法时一般会很冗长，所以不建议用自然语言描述、表示算法，避免出现二义性。

流程图描述算法

用图表示的算法就是流程图。流程图是用一些图框来表示各种类型的操作，在框内写出各个步骤，然后用带箭头的线把它们连接起来，以表示执行的先后顺序。用图形表示算法，直观形象，易于理解。

流程图符号

处理框（矩形框），表示一般的处理功能。

判断框（菱形框），表示对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后的操作。它有一个入口，二个出口。输入输出框（平行四边形框）。

起止框（圆弧形框），表示流程开始或结束。

连接点（圆圈），用于将画在不同地方的流程线连接起来。用连接点，可以避免流程

线的交叉或过长，使流程图清晰。

流程线（指向线），表示流程的路径和方向。

程序的三大基本结构

任务：绘制鸡兔同笼问题的流程图

运行鸡兔同笼代码，体会用程序和其他方法的区别

a = int(input("请输入鸡和兔的总数\n"))
b = int(input("请输入鸡和兔的脚数\n"))

# 计算鸡的数量
x = (4 * a - b) / 2

# 检查 x 是否为整数，且 x 和 y 是否非负
if x.is_integer() and x >= 0 and a - x >= 0:
    y = a - x
    print("鸡有{}只，兔有{}只".format(int(x), int(y)))
else:
    print("{}只动物{}条腿的情况无解".format(a, b))

请打开桌面的draw.io程序或网页版的图表工具，对照程序代码绘制出流程图，保存成文件后提交给老师。

image-kuen.png 或者 image-ceey.png

拓展阅读

世界上第一个算法

　　公元前300年，“几何之父”欧几里得提出了人类史上第一个算法——欧几里得算法，又称辗转相除法，是求最大公约数的一种方法。它的具体做法是: 用较大数除以较小数，再用出现的余数(第余数)去除除数，再用出现的余数(第二余数)去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

辗转相除法举例:

求10，25的最大公约数:

25/10=2……5

10/5=2……0

所以10，25的最大公约数为5

世界上第一个算法程序

　　'If I should see you，after long year.How should I greet, with tears, with silence. '这是英国著名诗人拜伦的诗句，而世界上第一位程序员阿达·洛芙莱斯（Ada Lovelace），就是这位著名诗人的女儿，她编写了世界上第一个算法程序。1842年，Ada为巴贝奇分析机编写求解伯努利方程的程序，写作了第一份“程序设计流程图”，被珍视为“第一位给计算机写程序的人”。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。

Ada Lovelace-wbyp.jpg

Ada Lovelace

算法的评定

　　算法的复杂性是算法效率的度量，在评价算法性能时，复杂性是一个重要的依据。算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂性越高:所需要的资源越少，表明该算法的复杂性越低。计算机的资源，最重要的是运算所需的时间和存储程序和数据所需的空间资源，算法的复杂性有时间复杂性和空间复杂性之分。

1.时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=Ο(f(n))。因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。常见的时间复杂度量级有：常数阶O(1)、对数阶O(logN)、线性阶O(n)、线性对数阶O(nlogN)、平方阶O(n²)、立方阶O(n³)、K次方阶O(n^k)、指数阶(2^n)。

2.空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

空间复杂度记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。空间复杂度比较常用的有：O(1)、O(n)、O(n²)。

N-S流程图

　　在使用过程中，人们发现流程线不一定是必需的，随着结构化程序设计方法（structured programming, SP）的出现，1973年美国学者Ike Nassi和Ben Shneiderman提出了一种新的流程图形式，这种流程图完全去掉了流程线，算法的每一步都用一个矩形框来描述，把一个个矩形框按执行的次序连接起来就是一个完整的算法描述。这种流程图同两位学者名字的第一个字母来命名，称为N-S流程图。

1.顺序结构的N-S流程图，如图3.3所示。

2.选择结构的N-S流程图，如图3.4所示。

例如，输入一个数，判断该数是否是偶数，并给出相应提示。此程序的选择结构的N-S流程图如图3.5所示。

3.循环结构。

当型循环的N-S流程图，如图3.6所示。

例如，程序求1~100之间（包括1和100）所有整数之和的当型循环的N-S流程图如图3.7所示。

直到型循环的N-S流程图，如图3.8所示。

例如，程序求1~100之间（包括1和100）所有整数之和的直到型循环的N-S流程图如图3.9所示