计算机导论第三次作业

10205102406 edited 1 年,10 月前

1、(10 points)《计算机导论》1.5.4,完成求圆周率-蒙特卡洛法的Python程序,试验不同的times值。试试看109次方。

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))

avatar

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()

avatar

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

avatar

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)

avatar

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)

avatar

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)

avatar

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)))

avatar

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)))

avatar

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)

avatar

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)

avatar

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)])

avatar

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)]))

avatar

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])

avatar

13、(10 points)沙老师希望你能自行学习,希望你能自行阅读编程导论的第二章和计算机导论的第二章。能看多少算多少。

a)你学了一些什么?成果和收获是什么?你能总结一下吗?

b)在学习方面,有什么值得高兴的地方?你觉得哪个算法比较有趣?

c)你认为你所欠缺的是什么?以及下一步的学习计划是什么?

d)假如你给自己评分,1-10分,10分为最高分,6分算及格,你给自己评几分?

最后,这次作业比较多,要恭喜你学习了好多,相信自己,相信老师,你会越来越棒的!

制作者:姜博远
仅供参考

Past Versions

Comments

wty24601

tql,这就是dalao吗