分治思想延伸：数学归纳法、递归、归并排序、MapReduce - 跟黄申老师学数学(python实现)02

引言：

数学归纳法(Mathematical Induction)、递归、归并排序(merge sort)、MapReduce，这些方法或技术都基于一个重要的数学思想—— 分而治之(Divide and Conquer) ，简称分治，就是将一个复杂的问题，分解成两个或多个规模相同/相似的子问题（更简单一点或更接近目标一点），然后分别对这些子问题进一步细分，直到最后子问题变得非常简单。

下面通过代码对分治思想的这些实际应用进行一一展示。

数学归纳法

• 定义：

  • 做出合理假设
  • 证明基本情况，比如n=1时，是否成立
  • 假设n=k-1成立，再证明n=k也成立(k为任意大于1的整数)

• 特点：

  • 数学归纳法，已经归纳总结出规律，只要我们能够证明其正确，就没必要再逐步进行计算，以节省时间和资源。

用程序证明数学归纳法

需求：用代码证明数学归纳法，证明第k格的麦子总数是2**k-1

# params: k：第几格，result：当前格子的数量和总数
# return: 放到第k格时，是否成立

class Result:
    def __init__(self,wheet_num = 0,wheet_total_num = 0):
        self.wheet_num = wheet_num
        self.wheet_total_num = wheet_total_num
    def __str__(self):
        return str(self.wheet_num)+"__"+str(self.wheet_total_num)

def prove(k,result):
    if k == 1:
#         if math.pow(2,k) - 1 == 1:
        if 2 ** k - 1 == 1:
            result.wheet_num = 1
            result.wheet_total_num = 1
            return True
        else:
            return False
    else:
        if_previous_true = prove(k-1,result)
        if if_previous_true:
            result.wheet_num *= 2
            result.wheet_total_num += result.wheet_num
            if result.wheet_total_num == 2 ** k - 1:
                print result
                return True
        print result
        return False

print(prove(64,Result()))        
复制代码

注意：如果使用math.pow(2,k)，因为精度的问题，k=54以后的数字是不准的。而2**k的格式则可以。待深入研究。。。

数学归纳法和递归

如果用编程来证明数学归纳法，会发现这个过程就是递归调用。

• 数学归纳法的思路：
  • 看初始状态，n=1时，是否成立
  • 如果n=k-1成立，那判断n=k时是否成立
• 将数学归纳法稍作转变，就是递归的一般思路：
  • 假设n=k-1时，问题已经解决（或者已经求得解），那么只要求解n=k的时候，问题如何解决（或者求解是多少）
  • 初始状态（n=1时），问题如何解决（或者解是多少）

递归的特点

递归，本质是用“ 分而治之 ”的思想，将复杂的问题，每次都解决一点点，并将剩下的问题转化成更简单的问题等待下次求解，如此反复，直到初始状态。这中间每次嵌套都会让函数体生成自己的局部变量，来保存大量的中间变量，省去我们复杂的操作。总之，递归的两大优点：

• “ 分而治之 ”，本质思想和数学归纳法相似：把复杂问题化解为两部分：
  • 一个简单的当前步骤 ：可能是一次运算，一个选择、一次操作
  • 另一个更简单一点的问题：通过 嵌套调用
• 计算机调用嵌套函数，会保存大量中间状态和变量值，大大简化编程操作

递归例子一：限定总和，求所有可能的加加方式

需求：假设有四种面额的钱币，1 元、2 元、5 元和 10 元，而一共给我10 元，那您可以奖赏我 1 张 10 元，或者10 张 1 元，或者 5 张 1 元外加 1 张 5 元等等，如果考虑每次奖赏的金额和先后顺序，那么最终一共有多少种不同的奖赏方式？

• 法一 ：

# 限定总和，求所有可能的加加方式
# params: left_total 目前总共还剩多少，current_result 当前的结果
rewards = [1,2,5,10]
current_result = []
def find(left_total,current_result):
    if left_total == 0:
        print(current_result)
        return
    elif left_total < 0:
        return
    else:
        for i in rewards:
            new_result = current_result[:]
            new_result.append(i) # 解决目前一点点问题
            find(left_total - i, new_result) # 剩下的问题，留给之后嵌套调用来解决
print(find(10,[]))
复制代码

• 法二：

# 限定总和，求所有可能的加加方式
# params: current_total 目前总数是多少，current_result 当前的结果
rewards = [1,2,5,10]
total = 10
current_result = []
def find(current_total,current_result):
    if current_total == total:
        print(current_result)
        return
    elif current_total > total:
        return
    else:
        for reward in rewards:
            new_result = current_result[:]
            new_result.append(reward)
            get(current_total + reward, new_result)
print(find(0,[]))
复制代码

递归例子二：

一个整数可以被分解为多个整数的乘积，例如，6 可以分解为2x3。请使用递归编程的方法，为给定的整数 n，找到所有可能的分解（1 在解中最多只能出现 1 次）。例如，输入 8，输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2...

n = 8
def find(current_product,current_result):
    if current_product == n :
        print(current_result)
        return
    elif current_product > n :
        return
    else:
        for i in range(1, n+1):
            if i != 1 or 1 not in current_result:
                new_result = current_result[:]
                new_result.append(i)
                find(current_product * i,new_result)

find(1,[])
复制代码

归并排序

直接上代码

需求：使用归并排序（递归调用），对数字列表进行排序。

# 归并排序
# 每一步操作：是将list分成两个子children_list，将children_list的 排序 交给下一步，
#   这一步专注于将返回的排好序的children_list进行合并。

def merge(front_list,back_list):
    """
    对已经排好序的两个列表，进行排序
    """
    new_list = []
    if not front_list:
        return back_list
    if not back_list:
        return front_list

    while True:
        if len(front_list)==0:
            new_list.extend(back_list)
            break
        if len(back_list)==0:
            new_list.extend(front_list)
            break
        
        if front_list[0] <= back_list[0]:
            new_list.append(front_list.pop(0))
        else:
            new_list.append(back_list.pop(0))

    return new_list

        

def merge_sort(list):
    if not list or len(list)==1:
        return list
    print(len(list))
    front_list = list[:len(list)/2]
    back_list = list[len(list)/2:]
    front_list = merge_sort(front_list)
    back_list = merge_sort(back_list)
    return merge(front_list,back_list)
    
list = [1,3,0]
# list = [5,6,1,0,3,8,1,6,9,-2,7,2]
list = merge_sort(list)
print(list)

复制代码