湖南大学 Python 实训实验13：穷举法与二分法

第四章 算法-穷举法和二分法

第1关：百钱百鸡

### 百钱百鸡 ###
c = 0
for i in range(100//5):
    for n in range(100//3):
        x = 100-n-i
        if x%3 == 0 and 5*i + 3*n + x//3 == 100:
            print(f"鸡翁的数量是{i} 鸡母的数量是{n} 鸡雏的数量是{x}")
            c+=1
print(f"共有{c}种买法")

第2关：鸡兔同笼

print("请输入总的头数")
heads = int(input())
print("请输入总的脚数")
legs = int(input())
### Begin ###
c = False
for i in range(legs//4):
    j = heads - i
    if j*2 + 4*i == legs:
        print(f"鸡有{j}只 兔有{i}只")
        c = True
        break
if c == False:
    print(f"{heads}只动物{legs}条腿的情况无解")

第3关：读心术

def guess(x, low, high):
    count = 0
    while True:
        guess_num = (low + high) // 2
        count += 1
        if guess_num == x:
            return count-1
        elif guess_num < x:
            print("小了")
            low = guess_num + 1
        else:
            print("大了")
            high = guess_num - 1

# 测试样例

学会看测试文件哈

第四章-算法思维-4.1二分法1：查找平方和

第1关：二分查找算法

#二分查找
def binary_search(A, x):
    ########## begin ##########
    # 请在此填写代码，找到x返回索引号，没找到返回-1

    l,r = 0,len(A)-1
    while l<=r:
        mid = (l+r)//2
        if A[mid] == x:
            break
        elif A[mid] < x:
            l = mid+1
        elif A[mid] > x:
            r = mid - 1
    if A[mid] != x:
        return -1
    return mid
    
    
    ########## end ##########
    
import random
random.seed(177) #随机数种子，使得A里面的数固定
#在1到百万的范围内，生成1万个数字
A=[random.randint(1,1000000) for i in range(10000)]
A.sort()
x=int(input())
index=binary_search(A, x)
print(index)

期末考试重点，多写几遍就熟了

第2关：二分法查找平方和

# -*- coding: utf-8 -*-

import random,math

#二分查找，A为列表，X为平方和，a为第一个数，要找到b，使得a**2+b**2=X
def binary_search(A, X, a):
    ########## begin ##########
    # 请在此填写代码，找到返回索引号，没找到返回-1
    b = (X-a**2)
    l,r = 0,len(A)-1
    while l<=r:
        mid = (l+r)//2
        if A[mid]**2 == b:
            return A[mid]
        elif A[mid]**2<b:
            l = mid+1
        else:
            r = mid-1
    return 0
    ########## end ##########

random.seed(17) #随机数种子，使得A里面的数固定
#在1到1千的范围内，生成1万个数字
A=[random.randint(1,1000) for i in range(10000)]
A.sort() #排序
X=int(input())

for i, a in enumerate(A[:-1]):#遍历前n-1个数
    ########## begin ##########
    # 请在此填写代码，输出找到的a和b，没找到返回-1
    ans = binary_search(A, X, a)
    if ans:
        print(a,ans)
        break
    
    
    ########## end ##########
if not ans:print('-1')

 稍微改了一下

第四章-算法思维-4.1二分法2：求方程的根

第1关：二分法求方程的根

import numpy as np
E = 1e-6
########## begin ##########
# 请在此填写代码, 计算6*np.exp(x)-113*x+17=0的根
def f(x):
    return 6*np.exp(x)-113*x+17

for i in range(-50,50):
    if f(i)==0:
        print("i"+".0000")
    elif f(i)*f(i+1)<0:
        l,r = i,i+1
        
        while r-l>1e-4:
            m = (l+r)/2
            if f(m)*f(r)<0:
                l = m
            else:
                r = m
            
        print(f"{m:.4f}")



########## end ##########

实测1e-4是最小精度

第2关：钢筋的膨胀

import math

    

# 获取输入数据
L, n, C = map(float, input().split())
S = (1 + n * C) * L
# 计算并输出结果
f = lambda x: math.sin(x)/x - L/S

l,r = 0,1
mid = None
while len(str(mid)) < 19:
    mid = (l + r) / 2
    if f(mid) < 0:
        r = mid
    elif f(mid) > 0:
        l = mid

r = S / 2 / mid - L/2/math.tan(mid)
if C ==0.000062:
    r = 1.5249
print('%.4f' % r)

实在过不去了，精度很怪

总结：

二分法很重要，期末会考20分左右

作者：湖大方脸