资源简介

信息技术必修一第四单元《计算与问题解决》
知识点回顾
算法及其特征
算法的概念
算法是解决问题的方法和步骤。
算法的描述 ☆
①自然语言
②流程图
③伪代码
3.算法的特征
①有穷性。算法必须执行有限个步骤后终止。
②确切性。算法中的每一步运算都有明确的定义。
③输入项。有0个或多个输入。
④输出项。至少有一个输出。
⑤可行性。算法的运算必须都是可以实现的。
4.枚举法
把所有可能的答案一一列举，合适就保留，不合适就舍弃。这种方法叫做枚举法或穷举法。
二、数值计算
绘制正弦函数曲线
方法一：利用WPS绘制。
方法二：利用Python绘制。
代码如下：
import numpy as np #加载numpy模块并取名为np
import matplotlib.pyplot as plt #加载matplotlib.pyplot并取名为plt
x=np.arange(0,2*np.pi,0.01) #x在0到2π之间，每隔0.01取一个点
y1=np.sin(x) #求sin(x)对应的y1值
y2=np.sin(-x) #求sin(-x)对应的y2值
y3=np.sin(2*x)/2 #求sin(2x)/2对应的y3值
plt.plot(x,y1) #绘制sin(x)图像
plt.plot(x,y2) #绘制sin(-x)图像
plt.plot(x,y3) #绘制sin(2*x)/2图像
plt.title('sin(x)') #设置图像标题
plt.xlabel('X') #设置X轴标题
plt.ylabel('Y') #设置Y轴标题
plt.show() #将绘制的函数图像窗口显示出来
input("运行完毕，请按回车键退出...")
求解斐波那契数列
方法一:用WPS求解。
数列根据斐波那契数列的规律，从第3项起，数列各项的值等于前两项之和，因此在WPS表中很容易得到B=Bn-1+Bn-2。
方法二:用Python求解数列。
用迭代法，每一次迭代的结果作为下一次迭代的初值使用，循环往复。
计算的迭代代码如下：
def fib(n):
#迭代求Fibonacci数列
f2=f1=1
for i in range(3,n+1):
f1,f2=f2,f1+f2
return f2
n=int(input('输入需要计算的月份数：'))
print('兔子总对数为：',fib(n))
input("运行完毕，请按回车键退出...")
三、非数值计算
1.二分查找
二分查找又称折半查找，该方法主要讲数列有序排列，采用跳跃式的方式查找数据。以递增数列为例，先以中点位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。
二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。在一个有n个元素的有序序列中，利用二分查找大约需要log2n次。
但是，二分法查找的前提条件是被查找的数据必须是有序的。
2.汉诺塔游戏
递归：用函数本身来定义函数的方法，即直接或间接的调用自身的方法。
斐波那契数列也可以用递归定义：
def hanno(n,s,m,t):
#定义一个函数,n层塔，将盘子从s借助m移动到t
if n==1:
print(s,'-->',t) #将一个盘子从s移动到t
else:
hanno(n-1,s,t,m) #将前n-1个盘子从s移动到m上
print(s,'-->',t) #将最底下的最后一个盘子从s移动到t上
hanno(n-1,m,s,t) #将m上的n-1个盘子移动到t上
#主程序
n=int(input('请输入汉诺塔的层数：'))
hanno(n,'A','B','C')
input("运行完毕，请按回车键退出...")
对递归而言，递推与回归，二者缺一不可。结合分治策略，递归也可用分、治、合三个字概括。
分：将原问题分解成k个子问题。
治：对这k个子问题分别求解。如果子问题的规模仍然不够小，则将其再分解为k个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。
（3)合：将求出的小规模问题的解合并为一个更大规模问题的解，自下而上逐步求出原问题的解。
将一个难以直接解决的大问题，分割成一些规模较小的同类问题，以便各个击破，分而治之，此为分治。
四、综合问题的解决
综合问题解决的基本原则：先考虑总体，后考虑细节；先面向整体，再细化局部。
章节练习
选择题
1.下列关于算法的输入、输出的描述正确的是（ ）
A. 算法可以没有输入，表示该算法不涉及任何数据信息
B. 算法必须要有输入，否则无法开始运行
C. 算法可以没有输出，表示该算法运行结果为“无解”
D. 算法必须至少有一个输出，否则无法查看结果
2.采用盲目搜索的方法，在搜索的过程中，对所得的结果逐一筛选，排除不符合要求的结果，保留符合要求的结果，这种方法叫作（ ）
A. 解析法 B. 递推法 C. 枚举法 D. 选择法
3.在软件的生命周期中，明确软件系统具备哪些功能的阶段是（ ）
A. 可行性分析 B. 需求分析 C. 概要设计 D. 详细设计
4.某班级有50名同学，一次考试后，考试成绩按照学号进行排序，现在需要查找某一学号学生的成绩，如果采用二分查找，最坏情况下需要比较的次数是（ ）次。
A.2 B.6 C.26 D.50
关于算法的重要特征，下列说法错误的是（ ）
确切性是指算法的每一步在每次运算后都是完全相同，不可改变的
有穷性是指算法必须能在执行有限个步骤之后终止
输出性是指算法一定要有至少一个输出，不能“无功而返”
D. 可行性是指算法中的运算都必须是可以实现的
6.用Python做一个随机出现金币的游戏，其中用到的随机数的模块是（ ）A.pygame B.random C.sys D.numpy
参考答案：D C B B A B

展开更多......

收起↑