第一周 數(shù)據(jù)儲存與運算
題目1
問題重述
1.有一個包含有100個元素的數(shù)組，該100個元素從數(shù)組的第0位置連續(xù)存放，請計算完成下面每個功能所需要的步驟數(shù)：
- 搜索一個不在該數(shù)組中的數(shù)；
- 在數(shù)組的頭部插入一個新元素；
- 在數(shù)據(jù)的尾部插入一個新元素；
- 刪除數(shù)組頭部元素；
- 刪除數(shù)組尾部元素。
解
(1)
搜索一個不在該數(shù)組中的數(shù)
需要100步，需要遍歷數(shù)組內(nèi)每一個元素與搜索值進(jìn)行比對
(2)
在數(shù)組的頭部插入一個新元素
需要101步，由于數(shù)組連續(xù)存儲，需要將100個元素分別向后移動一個儲存單元，再將該元素放在空出的第一位中
(3)
在數(shù)據(jù)的尾部插入一個新元素
需要1步，由于數(shù)組連續(xù)存儲，直接在數(shù)組末節(jié)點后插入新元素即可
(4)
刪除數(shù)組頭部元素
需要100步，先將頭元素刪除，再將后續(xù)的99個元素分別向前移動一個儲存單元
(5)
刪除數(shù)組尾部元素
需要1步，直接刪除尾部元素即可
題目2
問題重述
2.計算機(jī)內(nèi)存的資源是非常有限的，在處理有些問題時，并不是需要把所有的數(shù)據(jù)都保存在存儲器中才能完成。假如輸入的數(shù)據(jù)數(shù)量是N，可以想象N比較大，請判斷下面的任務(wù)，有哪些任務(wù)需要保存輸入的所有數(shù)據(jù)？有哪些任務(wù)只需要使用固定數(shù)量的變量和固定大小的數(shù)組（和N無關(guān)）？
（注：回答問題時請不要只給出結(jié)論，如果有可能，可以用偽代碼或流程圖或真實代碼的方式給出具體的解決方案）
- 輸出最大和最小的數(shù)；
- 輸出所有數(shù)的中位數(shù)；
- 輸出第k小的數(shù)，k小于100；
- 輸出所有數(shù)的平方和；
- 輸出N個數(shù)的平均值；
- 輸出大于平均值的數(shù)的百分比；
- 將N個數(shù)據(jù)按照升序輸出。
解
(1)
輸出最大和最小的數(shù)
?使用固定數(shù)量的變量即可，通過將第一個數(shù)指定為最大和最小值，再分別和列表中其他數(shù)對比
def max_and_min(list):
max=list[0]
min=list[0]
for i in (0,len(list)-1):
if list[i] > max:
max = list[i]
if list[i] < min:
min = list[i]
return max,min
list_test=[1,3,7,0,14]
print("(最大值,最小值):",max_and_min(list_test))
(2)
輸出所有數(shù)的中位數(shù)
?需要保存輸入的所有數(shù)據(jù)，先通過冒泡排序?qū)⒘斜碚蚺帕校蟾鶕?jù)索引值取出中位數(shù)
def bubblesort(list):
for i in range(len(list)):
for j in range(0, len(list)-i-1):
if list[j] > list[j+1] :
temp=list[j]
list[j]= list[j+1]
list[j+1]=temp
def mid(list):
bubblesort(list)
if len(list)%2==1:
return list[int(len(list)/2)]
else:
return (list[int(len(list)/2-1)]+list[int(len(list)/2)])/2.0
list_test=[1,3,7,0,14]
print(mid(list_test))
(3)
輸出第k小的數(shù)，k小于100
方法一
?需要保存輸入的所有數(shù)據(jù)，先通過冒泡排序?qū)⒘斜碚蚺帕?，之后取出?00個數(shù)
def bubblesort(list):
for i in range(len(list)):
for j in range(0, len(list)-i-1):
if list[j] > list[j+1] :
temp=list[j]
list[j]= list[j+1]
list[j+1]=temp
list_test=[1,3,7,0,14]
bubblesort(list_test)
print(list_test[99])
方法二
?使用固定數(shù)量的變量即可，創(chuàng)建一個大小為k的順序列表，將列表N中前k個輸入作為初始值，之后分別對比每個元素，如果比k中任意元素小，則替換插入，否則則略過，最終輸出列表k的末尾值
def bubblesort(list):
for i in range(len(list)):
for j in range(0, len(list)-i-1):
if list[j] > list[j+1] :
temp=list[j]
list[j]= list[j+1]
list[j+1]=temp
def select(list,k):
list1=list[0:k]
bubblesort(list1)
for i in range(k,len(list)):
if list[i]< list1[k-1]:
list1[k-1]=list[i]
bubblesort(list1)
return list1[k-1]
list_test=[15,66,22,15,23,29,54,80,58,34,60,97,81,40,19,3,28,67,18,16,54,73,29,20,36,5,60,23,14,67,16,27,62,28,17,86,37,83,50,3,18,29,88,3,24,12,89,7,82,16,0,95,8,88,38,66,25,98,29,97]
print(select(list_test,13))
(4)
輸出所有數(shù)的平方和
?使用固定數(shù)量的變量即可，通過將每一個數(shù)平方后加在和變量上，可得平方和
def Quadratic_Sum(list):
qsum=0
for i in range(len(list)):
qsum=qsum+list[i]*list[i]
return qsum
list_test=[1,3,7,0,14]
print(Quadratic_Sum(list_test))
(5)
輸出N個數(shù)的平均值
?使用固定數(shù)量的變量即可，通過計算N個數(shù)的和之后將其除以N即可
def Average(list):
sum=0
for i in range(len(list)):
sum=sum+list[i]
return sum/len(list)
list_test=[1,3,7,0,14,4]
print(Average(list_test))
(6)
輸出大于平均值的數(shù)的百分比
?使用固定數(shù)量的變量即可,算出平均數(shù)后，遍歷列表，統(tǒng)計大于平均值元素的個數(shù)，之后通過格式化輸出為百分比
def Percentage(list):
sum=0
count=0
for i in range(len(list)):
sum=sum+list[i]
average=sum/len(list)
for i in range(len(list)):
if list[i]> average:
count=count+1
return count/len(list)
list_test=[1,3,7,0,14,4]
print('percent: {:.2%}'.format(Percentage(list_test)))
(7)
將N個數(shù)據(jù)按照升序輸出
?需要保存輸入的所有數(shù)據(jù)，通過冒泡排序?qū)⒘斜磉M(jìn)行排序
def bubblesort(list):
for i in range(len(list)):
for j in range(0, len(list)-i-1):
if list[j] > list[j+1] :
temp=list[j]
list[j]= list[j+1]
list[j+1]=temp
list_test=[1,3,7,0,14]
bubblesort(list_test)
print(list_test)
吳博成 2021.03.08 update
|
