计算机导论第三次作业 (Past)
10205102406 edited 3 年，6 月前
This is a past version of blog 计算机导论第三次作业
1、（10 points）《计算机导论》1.5.4，完成求圆周率-蒙特卡洛法的Python程序，试验不同的times值。试试看10的9次方。
from random import random
def pi(times):
count = 0
for i in range(times):
x = random()
y = random()
d2 = x**2+y**2
if d2 <= 1:
count += 1
return (4*count)/times
times = 10**9
print("Pi=%.8f" %pi(times))
2、(15 points) 《计算机导论》练习题 1.5.3, 1.5.4, 1.5.5, 1.5.6, 1.5.7
略
3、（10 points）请写一个Python程序，利用双层循环完成以下的输出：
****
-***
–**
—***
----**
-----*
------
第一行打印出6个“*”，第二行打印出一个“*-”和5个“*”，依此类推，到第7行时打印出6个“-”。必须要用双层循环，在内层会有两个循环。*
for i in range(7):
for j in range(i):
print('-',end='')
for j in range(6-i):
print('*',end='')
print()
4、（10 points）《编程导论》练习题2.1.2 和 2.1.3。
x = 0
y = 2
dx = 0.5
dy = 7.378*0.5
while x<=5:
print(x, y)
x+=dx
y+=dy
5、（10 points）（A）完成《编程导论》2.1.2节的第二种方法和第三种方法的Python程序。（B）请问当L=[1,2,3,4,5,6,7,8] 和 L=[8,7,6,5,4,3,2,1] 时这二种方法所需要的比较次数各是多少？
L1 = [1,2,3,4,5,6,7,8]
L2 = [8,7,6,5,4,3,2,1]
def Find1(L):
Min = L[0]
Max = L[0]
count = 0
for i in L:
if Min < i:
count += 1
Min = i
elif Max > i:
count += 2
Max = i
else:
count += 2
print("The min is:", Min)
print("The max is:", Max)
print("共比较%d次"%count)
print("方法二")
print("当L=[1,2,3,4,5,6,7,8]时")
Find1(L1)
print("当L=[8,7,6,5,4,3,2,1]时")
Find1(L2)
L1 = [1,2,3,4,5,6,7,8]
L2 = [8,7,6,5,4,3,2,1]
def Find2(L):
Min = L[0]
Max = L[0]
start = 1
count = 0
if len(L) % 2 == 0:
count += 1
if L[1]>L[0]:
Max = L[1]
else:
Min = L[1]
start = 2
for i in range(start, len(L)-1, 2):
if L[i]>L[i+1]:
count += 3
if L[i]>Max:
Max = L[i]
if L[i+1]<Min:
Min = L[i+1]
else:
count += 3
if L[i+1]>Max:
Max = L[i+1]
if L[i]<Min:
Min = L[i]
print("The min is:", Min)
print("The max is:", Max)
print("共比较%d次"%count)
print("方法三")
print("当L=[1,2,3,4,5,6,7,8]时")
Find2(L1)
print("当L=[8,7,6,5,4,3,2,1]时")
Find2(L2)
6、（10 points）《编程导论》练习题2.1.4，假设x=1, y=1, 找出是否有数列元素是11的倍数也是13的倍数，打印出此数。（请注意沙老师出题时也不知道有没有这个数！所以沙老师也很好奇你的答案。）
x=1
y=1
while y%11 != 0 or y%13 != 0:
x, y = y, x+y
print(y)
7、（10 points）《编程导论》练习题2.5.1，（A）完成及试验书中二分法的Python程序，（B）请解释为什么二分查找的前提是所搜寻的列表为排好序的列表？假设列表长度为100000，请问用二分查找法最多找几次能知道答案？（C）你能用递归函数的方式来完成此二分查找吗？
def binary_sreach(L, a, Min, Max):
if Max == Min:
return -1
Mid = (Min+Max)//2
if L[Mid] > a:
return binary_sreach(L, a, Min, Mid-1)
elif L[Mid] < a:
return binary_sreach(L, a, Mid+1, Max)
else:
return Mid
L = [1,2,3,4,5,6,7,8]
a = 5
print(binary_sreach(L,a,0,len(L)))
def binary_sreach(L, a, Min, Max):
if Max == Min:
return -1
Mid = (Min+Max)//2
if L[Mid] > a:
return binary_sreach(L, a, Min, Mid-1)
elif L[Mid] < a:
return binary_sreach(L, a, Mid+1, Max)
else:
return Mid
L = [1,2,3,4,5,6,7,8]
a = 5
print(binary_sreach(L,a,0,len(L)))
8、（10 points）完成《编程导论》练习题2.5.1 测时间部分，再次假设寻找的值都不在列表内，试验k的不同值，2倍，4倍，8倍，看看执行时间的增长速度？
import time
def binary_sreach(L, a):
Min = 0
Max = len(L)-1
Mid = (Min+Max)//2
while Max-Min > 1:
if L[Mid] > a:
Max = Mid
elif L[Mid] < a:
Min = Mid
else:
return Mid
Mid = (Min + Max) // 2
if L[Max] == a:
return Max
elif L[Min] == a:
return Min
else:
return -1
for j in range(8):
k = 2 ** (j+10)
L = [x for x in range(k)]
start = time.clock()
for i in range(k):
if binary_sreach(L,k+1)>=0:
continue
elapsed = time.clock()-start
print("binary_sreach耗时:",elapsed)
start = time.clock()
for i in range(k):
if k+1 in L:
continue
elapsed = time.clock()-start
print("in耗时:",elapsed)
9、（10 points）《编程导论》2.5.1 节的排序算法，（A）完成选择排序和插入排序的python程序。（B）假设输入的列表是反向的，从大到小：例如N=10000;L=[i for i in range(N, 0,-1)]，请分析这两种排序算法所需要的“比较”次数。哪个算法比较快？
def selection_sort(L):
count = 0
for i in range(len(L)-1):
min = i
for j in range(i+1, len(L)):
count+=1
if L[j]<L[min]:
min = j
L[i], L[min] = L[min], L[i]
print("选择排序共比较%d次"%count)
return L
def insertion_sort(L):
count = 0
for i in range(1, len(L)):
for j in range(i):
while L[j] > L[i]:
count+=1
L[i], L[i-1] = L[i-1], L[i]
i -= 1
count += 2
if j==i:
break
print("插入排序共比较%d次" % count)
return L
N = 10000
L = [i for i in range(N, 0, -1)]
selection_sort(L)
insertion_sort(L)
10、（10 points）《编程导论》练习题2.5.2
L = [12,11,3,11,6,11,12,3,11]
D = {}
for i in L:
if i not in D.keys():
D[i] = 0
D[i] += 1
print([x for x in map(lambda x: [x, D[x]], D)])
11、（10 points）《编程导论》练习题2.5.3。对于出现次数相同的元素的顺序是按照其值从小到大排序。
def selection_sort(L):
count = 0
for i in range(len(L)-1):
min = i
for j in range(i+1, len(L)):
count+=1
if L[j][1]<L[min][1] or (L[j][1] == L[min][1] and L[j][0] < L[min][0]):
min = j
L[i], L[min] = L[min], L[i]
return L
L = [12,11,3,11,6,11,12,3,11]
D = {}
for i in L:
if i not in D.keys():
D[i] = 0
D[i] += 1
print(selection_sort([x for x in map(lambda x: [x, D[x]], D)]))
12、（15 points）这题可以两人合作，写下合作同学的名字及学号。请同学们把你的代码拷贝到word报告中，并将程序的运行结果截图粘贴到代码下方。
改写扑克牌游戏，我要你模拟不同情况下庄家的胜率。（A）按照原来的规则，庄家是等所有玩家结束后，他才开始玩牌，假设我们改变规则，庄家不是最后一个翻牌，而是先翻牌，他的胜率会降低吗？请你模拟多次比赛，最好让程序自动模拟玩家和庄家（不是手动输入），计算庄家得胜率。（B）假设庄家不是用17作为继续拿牌的标准，而是用16,18,19？其得胜率会有什么改变？这题是不是很有趣。其实这就是科研的探索。你还能想到其他什么不同的规则来测试呢？
import random
def shuffle(L):
for i in range(len(L)):
j = random.randint(0,len(L)-1)
L[i], L[j] = L[j], L[i]
def deal(L, k):
W = L[0:2]
Z = L[2:4]
i = 4
while point(Z)<k:
Z.append(L[i])
i += 1
while point(W)<k:
W.append(L[i])
i += 1
return [W, Z]
def point(L):
sum = 0
num1 = 0
for i in L:
if i == 1:
num1 += 1
sum += i
max = 0
while num1>0:
if sum + 10 < 21:
sum += 10
num1 -= 1
else:
break
return sum
def main(k):
L = 4*[1,2,3,4,5,6,7,8,9,10,10,10,10]
shuffle(L)
W, Z = deal(L,k)
if point(W)>21:
return -1
elif point(Z)>21 or point(Z) < point(W):
return 1
elif point(Z) == point(W):
return 0
else:
return -1
K = 50000
for k in [16,17,18,19]:
res = {1: 0, 0: 0, -1: 0}
for i in range(K):
res[main(k)]+=1
print("当先后手均采取点数未到%d即取牌的策略时"%k)
print("在%d场中"%K)
print("先手胜%d场"%res[-1])
print("后手胜%d场"%res[1])
print("平局%d场"%res[0])
13、（10 points）沙老师希望你能自行学习，希望你能自行阅读编程导论的第二章和计算机导论的第二章。能看多少算多少。
（a）你学了一些什么？成果和收获是什么？你能总结一下吗？
（b）在学习方面，有什么值得高兴的地方？你觉得哪个算法比较有趣？
（c）你认为你所欠缺的是什么？以及下一步的学习计划是什么？
（d）假如你给自己评分，1-10分，10分为最高分，6分算及格，你给自己评几分？
最后，这次作业比较多，要恭喜你学习了好多，相信自己，相信老师，你会越来越棒的！
略
制作者：姜博远