資源簡介

信息技術(shù)必修一第四單元《計算與問題解決》
知識點回顧
算法及其特征
算法的概念
算法是解決問題的方法和步驟。
算法的描述 ☆
①自然語言
②流程圖
③偽代碼
3.算法的特征
①有窮性。算法必須執(zhí)行有限個步驟后終止。
②確切性。算法中的每一步運(yùn)算都有明確的定義。
③輸入項。有0個或多個輸入。
④輸出項。至少有一個輸出。
⑤可行性。算法的運(yùn)算必須都是可以實現(xiàn)的。
4.枚舉法
把所有可能的答案一一列舉，合適就保留，不合適就舍棄。這種方法叫做枚舉法或窮舉法。
二、數(shù)值計算
繪制正弦函數(shù)曲線
方法一：利用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)對應(yīng)的y1值
y2=np.sin(-x) #求sin(-x)對應(yīng)的y2值
y3=np.sin(2*x)/2 #求sin(2x)/2對應(yīng)的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)') #設(shè)置圖像標(biāo)題
plt.xlabel('X') #設(shè)置X軸標(biāo)題
plt.ylabel('Y') #設(shè)置Y軸標(biāo)題
plt.show() #將繪制的函數(shù)圖像窗口顯示出來
input("運(yùn)行完畢，請按回車鍵退出...")
求解斐波那契數(shù)列
方法一:用WPS求解。
數(shù)列根據(jù)斐波那契數(shù)列的規(guī)律，從第3項起，數(shù)列各項的值等于前兩項之和，因此在WPS表中很容易得到B=Bn-1+Bn-2。
方法二:用Python求解數(shù)列。
用迭代法，每一次迭代的結(jié)果作為下一次迭代的初值使用，循環(huán)往復(fù)。
計算的迭代代碼如下：
def fib(n):
#迭代求Fibonacci數(shù)列
f2=f1=1
for i in range(3,n+1):
f1,f2=f2,f1+f2
return f2
n=int(input('輸入需要計算的月份數(shù)：'))
print('兔子總對數(shù)為：',fib(n))
input("運(yùn)行完畢，請按回車鍵退出...")
三、非數(shù)值計算
1.二分查找
二分查找又稱折半查找，該方法主要講數(shù)列有序排列，采用跳躍式的方式查找數(shù)據(jù)。以遞增數(shù)列為例，先以中點位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。
二分查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。在一個有n個元素的有序序列中，利用二分查找大約需要log2n次。
但是，二分法查找的前提條件是被查找的數(shù)據(jù)必須是有序的。
2.漢諾塔游戲
遞歸：用函數(shù)本身來定義函數(shù)的方法，即直接或間接的調(diào)用自身的方法。
斐波那契數(shù)列也可以用遞歸定義：
def hanno(n,s,m,t):
#定義一個函數(shù),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('請輸入漢諾塔的層數(shù)：'))
hanno(n,'A','B','C')
input("運(yùn)行完畢，請按回車鍵退出...")
對遞歸而言，遞推與回歸，二者缺一不可。結(jié)合分治策略，遞歸也可用分、治、合三個字概括。
分：將原問題分解成k個子問題。
治：對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則將其再分解為k個子問題，如此進(jìn)行下去，直到問題足夠小時，就很容易求出子問題的解。
（3)合：將求出的小規(guī)模問題的解合并為一個更大規(guī)模問題的解，自下而上逐步求出原問題的解。
將一個難以直接解決的大問題，分割成一些規(guī)模較小的同類問題，以便各個擊破，分而治之，此為分治。
四、綜合問題的解決
綜合問題解決的基本原則：先考慮總體，后考慮細(xì)節(jié)；先面向整體，再細(xì)化局部。
章節(jié)練習(xí)
選擇題
1.下列關(guān)于算法的輸入、輸出的描述正確的是（ ）
A. 算法可以沒有輸入，表示該算法不涉及任何數(shù)據(jù)信息
B. 算法必須要有輸入，否則無法開始運(yùn)行
C. 算法可以沒有輸出，表示該算法運(yùn)行結(jié)果為“無解”
D. 算法必須至少有一個輸出，否則無法查看結(jié)果
2.采用盲目搜索的方法，在搜索的過程中，對所得的結(jié)果逐一篩選，排除不符合要求的結(jié)果，保留符合要求的結(jié)果，這種方法叫作（ ）
A. 解析法 B. 遞推法 C. 枚舉法 D. 選擇法
3.在軟件的生命周期中，明確軟件系統(tǒng)具備哪些功能的階段是（ ）
A. 可行性分析 B. 需求分析 C. 概要設(shè)計 D. 詳細(xì)設(shè)計
4.某班級有50名同學(xué)，一次考試后，考試成績按照學(xué)號進(jìn)行排序，現(xiàn)在需要查找某一學(xué)號學(xué)生的成績，如果采用二分查找，最壞情況下需要比較的次數(shù)是（ ）次。
A.2 B.6 C.26 D.50
關(guān)于算法的重要特征，下列說法錯誤的是（ ）
確切性是指算法的每一步在每次運(yùn)算后都是完全相同，不可改變的
有窮性是指算法必須能在執(zhí)行有限個步驟之后終止
輸出性是指算法一定要有至少一個輸出，不能“無功而返”
D. 可行性是指算法中的運(yùn)算都必須是可以實現(xiàn)的
6.用Python做一個隨機(jī)出現(xiàn)金幣的游戲，其中用到的隨機(jī)數(shù)的模塊是（ ）A.pygame B.random C.sys D.numpy
參考答案：D C B B A B

展開更多......

收起↑