实验目的

1. 掌握贪心法解决问题的一般步骤。
2. 通过设计与实现贪心算法求解给定问题，学会使用贪心法解决实际问题。

实验内容

1. 均分纸牌问题：有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
2. 线段覆盖问题：在一维空间中存在N条线段，每条线段的起始坐标与终止坐标已知，要求求出这些线段一共覆盖了多大的长度。

算法描述

均分纸牌问题的解题思路或算法思想：

1.首先求得每堆牌的期望值，也就是总牌数与牌堆数的比值，或称为平均值，记作cardAverage。
2.从第一堆开始比较，如果当前堆的牌数cardCount小于平均值cardAverage，那么可以取当前堆的下一堆中的牌进行“补齐”，也就是说当前堆欠缺的数量为（cardAverage-cardCount），则需要从下一堆中取得（cardAverage-cardCount）张牌进行“补给”
3.有的时候可能会出现下一堆牌中数量还不足以补给的情况，比如：一共有30张牌，第一堆1张，第二堆3张，第三堆26张。第一堆明显需要（10-1=9）张，但是第二堆只有3张，如果进行强行补给，那么第二堆只会剩余（3-9=-6）张，虽不符合事实，但是告知计算机之后并不影响我们的正常计算，也就是此时第二堆需要（10-（-6）=16）张，只需从第三堆中转移过来即可。
4.同样，有的时候会出现前面一堆中的牌数多于后面的一堆中的牌数，这个时候要用到的解法和前面的补给的办法恰好相反，只是将多余的补充出去到下一堆即可，不再赘述。

算法步骤：

从第一堆牌开始处理，如果第一堆牌整好是avg那么就放在一边不管了。如果第一堆牌不是avg，那么就要把第二堆牌（合法的移动只有从2移到1，这也是这个算法的精髓之处）移动几张到第一堆，恰好使第一堆等于avg，从而只考虑第二堆开始到第N堆为止这些堆如何搞的子问题。然后依次递归下去。

线段覆盖问题的解题思路或算法思想：

将线段按照起始点的非降序排列

算法步骤：

首先定义两个数组a,b分别存储起始坐标和终止坐标，并按照起始坐标排好序，定义一个Max变量存储覆盖长度。然后用for循环对终止坐标进行比较，如果b[i]大于b[j]，则对覆盖长度进行累加，直到最后为止，所得的Max就是最大覆盖长度。

程序及运行结果

1.均分纸牌问题的程序：

def zhipai(n):
    sum1 = 0
    count = 0
    # a = [1] * 100
    a = [9, 8, 17, 6]
    for i in range(0, n):
        # a[i] = int(input())
        sum1 = sum1 + a[i]
        # print(sum1)
    average = int(sum1 / n)
    # print(average)
    for i in range(0, n):
        a[i] -= average
        # print(a[i])
    for i in range(0, n):
        if a[i] != 0:
            a[i + 1] = a[i + 1] + a[i]
            count = count + 1
            a[i] = 0
            # print(count)
    print(count)

if __name__ == '__main__':
# n = int(input())
n = 4
zhipai(n)

实例：

结果：

1. 线段覆盖问题的程序：

def xianduan(a, b):
    max1 = b[0] - a[0]
    j = 0
    for i in range(1, 10):
        if a[i] >= b[i]:
            max1 += (b[i] - a[i])
            j = i
        else:
            if b[i] <= b[j]:
                continue
            else:
                max1 += b[i] - b[j]
                j = i
    print('最大长度为', max1)


if __name__ == '__main__':
    a = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    b = [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
    xianduan(a, b)

实例：

结果：

总结

实验心得体会：

通过这节实验课，我更深入了动态规划算法，以前只是从书本上只看教材上的理论和实例，但是通过真正的实际应用才可以把理论付诸于实验，才能让脑海里所学会的算法更加应用于生活

改进意见：

实验成绩： 指导教师： 年 月 日