实验目的

1.掌握递归与分治策略的基本思想。
2.通过设计求解给定问题的递归算法和分治算法学会使用递归和分治法解决问题的一般技巧。

实验内容

1.二分搜索问题：设a[0:n-1]是已排好序的数组。试改写二分搜索算法，使得当搜索元素x不在数组a中时，返回小于x的最大元素的位置i和大于x的最小元素的位置j；当搜索元素x在数组a中时，返回x在数组中的位置，此时i和j相同。
2.假币识别问题：一个袋子里有n个硬币，其中一枚是假币，假币和真币外观一模一样，仅凭肉眼无法区分，但是已知假币比真币轻一些。试设计识别假币的分治算法。

算法描述

1.二分搜索问题的解题思路或算法思想：

二分搜索问题是运用分治策略来解决，基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较，如果x=a[n/2],则找到x，算法终止，如果x<a[n/2],则只要在数组a的左半部继续搜索x，如果x>[n/2]，则只要在数组a的右半部继续搜索x。
算法步骤：
定义二分查找Binarysearch函数，此函数的参数为数组a，数组长度n，待查找的数字x
先定义first = 0，last = long - 1，此处即是二分查找中的分治策略，从两段开始
设置循环，当first < last，进入循环
判断，如果在数组中可以查到数字x，那么输出此时的位置，i和j的值相等，如果在数组中无法查到数字x，再次判断，如果x大于last位置的值，那么first再次基础+1，反之last = mid，依次循环

2.假币识别问题的解题思路或算法思想：

将这n个硬币分成两等份，然后放到天平的两端，则假币在较轻的那一端；然后将较轻的那一端的硬币再分成2等份，然后再放到天平的两端进行比较，假币还是在较轻的那一段；最后若只剩下两个硬币了，分别放到天平的两端，轻的一段就是假币。最后若剩下3个硬币，从3个硬币中任意拿出来一个，然后将剩下的两个放到天平的两端，如果天平是平的，则说明拿出来的那个硬币就是假币；如果天平不是平的，则轻的那一端是假币。
算法步骤：
首先定义寻找假币的函数，如果只剩下两个银币，那么较轻的那个就是假的
如果是银币的总个数是偶数个，则逐步的一分为二，把查找一堆银币的问题，变成比较两份，左右两份等重，则无假币，如果奇数个银币，则比较除中间银币外的两等份，左右两份等重，则无假币，如果两份等重，中间银币较轻，则中间银币为假币，否则，返回较轻那份中的假币
然后定义再将较轻的一侧中银币等分为两份，重复上述做法。
直到剩下两枚银币，便可用天平直接找出假银币。

程序及运行结果

1.二分搜索问题的程序：
实例：

def Binarysearch(arr, find):
    long = len(arr)
    first = 0
    last = long - 1
    while first < last:
        mid = (last + first) // 2
        if arr[mid] > find:
            last = mid
        elif arr[mid] < find:
            first = mid + 1
        else:
            return mid

if __name__ == '__main__':
print("请输入数组数据：", end="")
arr = list(map(int, input().split(" ")))
arr.sort()  # 排序
print("你输入的数组为：", end="")
print(arr)
long = len(arr)  # 长度
print("请输入您要查找的数字：")
find = int(input())
if find in arr:
x = Binarysearch(arr, find)
print("数字存在数组当中！数组下标为：", x)
else:
print("你要找的数字不在这个列表里！")
if max(arr) < find:
print("没有比你查找数字更大的了！")
print("比查找数字小的最大数组元素下标为", long - 1)
elif min(arr) > find:
print("没有比查找数字还小的了！")
print("比查找数字大的最小数组元素下标为0")
else:
for y in range(0, long):
if arr[y] < find:
y += 1
else:
print("比寻找数字大的下标为", y)
print("比寻找数字小的下标为", y - 1)
break

结果：

2.假币识别问题的程序：
实例：

def find(a, low, high):
    n = high - low
    if n == 2:
        if a[int(low)] < a[int(high) - 1]:
            num = int(low)
            return num
        elif a[int(low)] > a[int(high) - 1]:
            num = int(high) - 1
            return num
    elif n > 2:
        if n % 2 == 0:
            i = n / 2
            a1 = a[int(low):int(i)]
            a2 = a[int(i):int(high)]
            if sum(a1) < sum(a2):
                num = find(a1, low, i)
                return num
            elif sum(a1) > sum(a2):
                num = find(a, i, high)
                return num
        else:
            i = (n - 1) / 2
            a1 = a[int(low):int(i)]
            a2 = a[int(i) + 1:int(high)]
            if sum(a1) < sum(a2):
                num = find(a, low, i)
                return num
            elif sum(a1) > sum(a2):
                num = find(a, i + 1, high)
                return num
            else:
                num = int(i)
                return num
    elif n == 1:
        num = int(low)
        return num


if __name__ == '__main__':
    # print("请输入硬币数据：", end="")
    # a = list(map(int, input().split(" ")))
    # n = len(a)
    # num = find(a, 0, n) + 1
    # print(num)
    a1 = [1, 2]
    n = len(a1)
    num = find(a1, 0, n) + 1
    print('a1:', a1, '的假币在第', num, '个位置')

    a2 = [2, 1]
    n = len(a2)
    num = find(a2, 0, n) + 1
    print('a2:', a2, '的假币在第', num, '个位置')

    a3 = [1, 2, 2]
    n = len(a3)
    num = find(a3, 0, n) + 1
    print('a3:', a3, '的假币在第', num, '个位置')

    a4 = [2, 1, 2]
    n = len(a4)
    num = find(a4, 0, n) + 1
    print('a4:', a4, '的假币在第', num, '个位置')

    a5 = [2, 2, 1]
    n = len(a5)
    num = find(a5, 0, n) + 1
    print('a5:', a5, '的假币在第', num, '个位置')

    a6 = [1, 2, 2, 2]
    n = len(a6)
    num = find(a6, 0, n) + 1
    print('a6:', a6, '的假币在第', num, '个位置')

    a7 = [2, 1, 2, 2]
    n = len(a7)
    num = find(a7, 0, n) + 1
    print('a7:', a7, '的假币在第', num, '个位置')

    a8 = [2, 2, 1, 2]
    n = len(a8)
    num = find(a8, 0, n) + 1
    print('a8:', a8, '的假币在第', num, '个位置')

    a9 = [2, 2, 2, 1]
    n = len(a9)
    num = find(a9, 0, n) + 1
    print('a9:', a9, '的假币在第', num, '个位置')

    a10 = [1, 2, 2, 2, 2]
    n = len(a10)
    num = find(a10, 0, n) + 1
    print('a10:', a10, '的假币在第', num, '个位置')

    a11 = [2, 1, 2, 2, 2]
    n = len(a11)
    num = find(a11, 0, n) + 1
    print('a11:', a11, '的假币在第', num, '个位置')

    a12 = [2, 2, 1, 2, 2]
    n = len(a12)
    num = find(a12, 0, n) + 1
    print('a12:', a12, '的假币在第', num, '个位置')

    a13 = [2, 2, 2, 1, 2]
    n = len(a13)
    num = find(a13, 0, n) + 1
    print('a13:', a13, '的假币在第', num, '个位置')

    a14 = [2, 2, 2, 2, 1]
    n = len(a14)
    num = find(a14, 0, n) + 1
    print('a14:', a14, '的假币在第', num, '个位置')

结果：

总结

实验心得体会：

通过本次实验，我掌握了递归与分治策略的基本思想，加深了对分治法的理解，通过设计求解给定问题的递归算法和分治算法学会使用递归和分治法解决问题的一般技巧。

改进意见：

通过实验我知道了算法 的学习是一个循序渐进的过程，而且需要不断的积累和锻炼，才能够得以提升。
实验成绩： 指导教师： 年 月 日