文档章节

分治算法

jit-hakase
 jit-hakase
发布于 2017/08/31 22:28
字数 825
阅读 14
收藏 3

分治算法

二分查找

问题: 在有序的序列中找数, 找到返回下标, 找不到返回-1. 思路:跟中间数进行比较, 每次序列减半再递归查找.

def part_find(A, n, start_idx):
    if not A:
        return -1

    mid = len(A)//2

    if A[mid] == n:
        return mid+start_idx
    elif A[mid] > n:
        return part_find(A[:mid], n, start_idx)
    elif A[mid] < n:
        return part_find(A[mid+1:], n, start_idx+mid+1)


A = [i for i in range(10)]
idx = part_find(A, 1, 0)
print(idx)

排序

问题: 将无序的序列排成有序.

归并排序

思路: 不断将已有序的子序列合并, 最后得到完全有序的序列.

def merge_sort(A):
    if len(A) <= 1:
        return A
    mid = len(A)//2
    left = merge_sort(A[:mid])
    right = merge_sort(A[mid:])
    
    def merge(left, right):
        T = []
        while left and right:
            T.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
        while left:
            T.append(left.pop(0))
        while right:
            T.append(right.pop(0))
        return T

    return merge(left, right)

    
A = [5, 3, 4, 7, 2, 1, 9, 8, 6, 0]
B = merge_sort(A)
print(B)

快速排序

思路: 将序列分成两部分, 一部分的所有数据都比另外一部分的所有数据小, 然后再按此方法对这两部分数据分别进行这种排序方法.

def quick_sort(A):
    if not A:
        return []
    key = A[0]
    lesser = quick_sort([n for n in A if n < key])
    greater = quick_sort([n for n in A if n > key])
    return lesser + [key] + greater

A = [5, 3, 4, 7, 2, 1, 9, 8, 6, 0]
B = quick_sort(A)
print(B)

排列组合

排列数

问题:求出1~N的所有排列情况 思路: 从序列中分离一个数, 和其他位置交换, 递归未分离的序列直到剩下一个数为止. python code

N = 3
L = [i for i in range(1, N+1)]

def A(cur):
    if cur == len(L)-1:
        print(L)
        return

    for i in range(cur, len(L)):
        L[cur], L[i] = L[i], L[cur]
        A(cur+1)
        L[cur], L[i] = L[i], L[cur]

A(0)

组合数

问题:求出1~N中选取M个的所有组合情况 思路:同排列数, 但不需要交换, 用递减来选出组合数.

N, M = 5, 3
L = [None for i in range(M)]

def C(n, m):
    for i in range(n, m-1, -1):
        L[m-1] = i
        if m > 1:
            C(i-1, m-1)
        else:
            print(L)

C(N, M)

棋盘覆盖

问题: 在一个2^K个方格组成的棋盘中, 有一个方格是特殊方格, 要用三个特殊方格组成的L形状(形状可任意旋转, 数量不限)来覆盖给定棋盘中的所有方格, 不能重叠. 思路: 递归每次分割成4个区域, 确定特殊方块的区域后, 在其余区域放置一个横跨三个区域的L形状.

N, CNT = 4, 0

M = [[0 for j in range(N)] for i in range(N)]

def chess_fill(bx, by, x, y, size):
    if size == 1:
        return

    global CNT
    CNT += 1
    cnt = CNT
    size //= 2
    ex, ey = bx+size, by+size

    # left top area
    if x<ex and y<ey:
        chess_fill(bx, by, x, y, size)
    else:
        M[ex-1][ey-1] = cnt
        chess_fill(bx, by, ex-1, ey-1, size)

    # right top area
    if x>=ex and y<ey:
        chess_fill(ex, by, x, y, size)
    else:
        M[ex][ey-1] = cnt
        chess_fill(ex, by, ex, ey-1, size)

    # left bottom area
    if x<ex and y>=ey:
        chess_fill(bx, ey, x, y, size)
    else:
        M[ex-1][ey] = cnt
        chess_fill(bx, ey, ex-1, ey, size)

    # right bottom area
    if x>=ex and y>=ey:
        chess_fill(ex, ey, x, y, size)
    else:
        M[ex][ey] = cnt
        chess_fill(ex, ey, ex, ey, size)


x, y = 1, 1
chess_fill(0, 0, x, y, N)

for i in range(len(M)):
    for j in range(len(M[i])):
        print(M[i][j], end=' ')
    print()

© 著作权归作者所有

上一篇: 贪心算法
下一篇: Java OOP
jit-hakase
粉丝 3
博文 26
码字总数 30408
作品 0
南京
程序员
私信 提问

暂无文章

IT兄弟连 HTML5教程 HTML5表单 新增的表单属性1

HTML5 Input表单为<form>和<input>标签添加了几个新属性,属性如表1。 1 autocomplete属性 autocomplete属性规定form或input域应该拥有自动完成功能,当用户在自动完成域中开始输入时,浏览器...

老码农的一亩三分地
45分钟前
5
0
OSChina 周五乱弹 —— 葛优理论+1

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @这次装个文艺青年吧 :#今日歌曲推荐# 分享米津玄師的单曲《LOSER》: mv中的舞蹈诡异却又美丽,如此随性怕是难再跳出第二次…… 《LOSER》-...

小小编辑
今天
1K
16
nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
15
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部