算法设计与分析

第一章 绪论

第一章重点的内容是递归问题和一些简单的算法题。

n!问题

示例Python代码：

1
2
3
4
5
6
7
8
def fac(num):
    if num == 0 or num == 1:
        return 1
    else:
        return fac(num)*fac(num-1)
if __name__ == "__main__":
    ret = fac(5)
    print(ret)

自写C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;

int fac(num)
{
    if(num==1||num==0)
        return 1;
    else
        return fac(num)*fac(num-1);
}
int main(){
    int n;
    cin<<n;
    int res = fac(n);
    cout>>res;
    return 0;
}

全排列问题

示例Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def all_permutation(array,start):
    if start == len(array):
        print(array)
        return
    for i in range(start,len(array)):
        array[start],array[i] = array[i],array[start]
        all_permutation(array,start+1)
        array[start],array[i] = array[i],array[start]
        
if _name_ == '_main_':
    array=['a','c','b']
    all_permutation(array,0)

自写c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<vector>
using namespace std;
void swap(int&a,int&b)
{
    int t=a;
    a=b;
    b=t;
}
void all_permutations(std::vector<int>& array, int start) {  
    if (start == array.size()) {  
        for (int num : array) {  
            std::cout << num << " ";  
        }  
        std::cout << std::endl;  
        return;  
    }  
  
    for (int i = start; i < array.size(); ++i) {  
        swap(array[start], array[i]);  
        all_permutations(array, start + 1);  
        swap(array[start], array[i]); // 恢复原数组  
    }  
}  
  
int main() {  
    vector<int> array = {1, 2, 3};  
    all_permutations(array, 0);  
    return 0;  
}

斐波那契数列

示例Python代码

1
2
3
4
5
def Fibonacci(n):
    assert n >= 0, "n > 0"
    if n <= 1:
        return n
    return Fibonacci(n-1) + Fibonacci(n-2)

自写c++代码

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int Fibonacci(num){
    if(num>0){
        if(num==1)
            return 1;
        else
            return Fibonacci(num-1) + Fibonacci(num-2);
    }
}

汉诺塔问题

1
2
3
4
5
6
7
def hanoi(n,a,b,c):#n为圆盘数，a代表初始位圆柱，b代表过渡位圆柱，c代表目标位圆柱
    if n==1:
        print(a,'-->',c)
    else:
        hanoi(n-1,a,c,b)#将a柱的n-1个圆盘借助c柱移动到b柱
        print(a,'-->',c) #将a柱剩下的1个圆盘移动到c柱
        hanoi(n-1,b,a,c) #将b柱的n-1个圆盘借助a柱移动到c柱

杨辉三角问题

1
2
3
4
5
6
7
8
9
10
11
def yang(i,j):
    if j==0 or j==i:
        return 1
    else:
        return yang(i-1,j)+yang(i-1,j-1)

def print_yang_triangle(n):
    for i in range(n):
        for j in range(i + 1):
            print(yang(i, j), end=" ")
        print()

N个连续自然数的连加和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#依次累加求和
#算法1：
def sum1(a,n):
    sum11 = 0
    for i in range(a,a+n):
        sum11 = sum11 + i
    return sum11
#算法2：
def sum2(a1,n):
    summ=a1
    start=a1+1
    end=a1+n-1
    for i in range(start,end+1):
        summ=summ+i
    return summ
#利用等差数列求和公式
def sum3(a1,n):
    end=a1+n-1
    return (a1+end)*n//2
if __name__ == "__main__":
    print ("sum1=",sum1(1,10))
    print("sum2=",sum2(1,11))
    print("sum3=",sum3(1,10))

调度问题

有n个客户带来n项任务，每项加工时间已知，设为ti(i=1,2,…,n)。从0时刻开始，陆续安排到一台机器上加工。每个任务的完成时间是从0时刻到该任务加工完成的时间。为了使尽可能多的客户满意，我们希望找到总等待时间最少的调度方案，即：总完成时间最短。

1
2
3
4
5
6
7
8
9
10
11
# 将n项任务的加工时间由小到大排序得到的次序为最优调度次序
def schedule(a):
    a.sort(key=lambda item:item[1])
    return a
if __name__=="__main__":
    a=[[1,23],[2,3],[3,20],[4,18],[5,2]]
    res = schedule(a)
    length = len(res) 
    print("调度次序为：")
    for i in res:  
        print(i[0])

参考C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>

bool compareSecond(const pair<string, int>& a, const pair<string, int>& b) {
    return a.second < b.second;
}

vector<pair<string, int>> schedule(vector<pair<string, int>>& a) {
    sort(a.begin(), a.end(), compareSecond);
    return a;
}

int main() {
    vector<pair<string, int>> events = { {"活动1", 5}, {"活动2", 3}, {"活动3", 8}, {"活动4", 1} };
    vector<pair<string, int>> sortedEvents = schedule(events);

    for (const auto& event : sortedEvents) {
        cout << event.first << ": " << event.second << endl;
    }
    
    return 0;
}

最大值问题

1
2
3
4
5
6
7
def arrayMax(a):
    n=len(a)
    max1=a[0]
    for i in range(1,n):
        if (a[i]>max1):
            max1=a[i]
    return max1

在序列A中查找元素K

1
2
3
4
5
6
def find(a,K):
   n = len(a)
   for i in range(n):
       if(a[i]==K):
           break
   return i

检查序列A和B是否存在公共元素

1
2
3
4
5
6
7
8
def check_common(a_list,b_list):
    n_a = len(a_list)
    n_b = len(b_list)
    for i in range(n_a):
        for j in range(n_b):
            if a_list[i] == b_list[j]:
                return True
    return False

第二章 贪心算法

贪心算法本质就是从眼前某一个初始解出发，在每一阶段都做出当前最优的决策，即贪心策略，逐步逼近给定的目标，尽可能快地求得更好的解。贪心算法可以理解为以逐步的局部最优，达到最终的全局最优的方法。

活动安排问题

1
2
3
4
5
6
7
8
9
10
11
void GreedySelector(int n, Type s[],type f[],bool A[]){
    A[1] = true;
    int j = 1;
    for(int i = 2;i <= n;i++){
        if(s[i]>=f[j]){
            A[i]=true;
            j=i;
        }
        else A[i]=false;
    }
}

最优装载问题

1
2
3
4
5
6
7
8
9
void Loading(int x[],Type w[],Type c,int n){
    for(int i=1;i<=n;i++){
        x[i]=0;
    }
    for(int i=1;i<=n&&w[i]<=c;i++){
        x[i]=1;
        c-=w[i];
    }
}

单源最短路径问题

dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#线性时间找最小
def dijkstra(start_point, graph):
    n = len(graph)
    # 初始化各项数据，把dist[start]初始化为0，其他为无穷大
    dist = [99999999 for _ in range(n)]#路径长度
    pre = [-1 for _ in range(n)]#前驱pre
    s = [False for _ in range(n)]#集合S
    dist[start_point]=0
    for i in range(n):
        minLength = 99999999
        minVertex = -1
        for j in range(n):
            if not s[j] and dist[j] < minLength:
                minLength = dist[j]
                minVertex = j
        s[minVertex] = True

        # 从这个顶点出发，遍历与它相邻的顶点的边，计算特殊路径长度，更新dist和pre
        for edge in graph[minVertex]:
            if not s[edge[0]] and minLength + edge[1] < dist[edge[0]]:
                dist[edge[0]] = minLength + edge[1]
                pre[edge[0]] = minVertex
        for e in graph:
            print(e)
    return dist, pre
if __name__ == "__main__":
    data = [
    [1, 0, 8],
    [1, 2, 5],
    [1, 3, 10],
    [1, 6, 9],
    [2, 0, 1],
    [0, 6, 2],
    [3, 6, 5],
    [3, 4, 8],
    [0, 5, 4],
    [5, 6, 7],
    [5, 3, 8],
    [5, 4, 5]]#边集合（顶点，顶点，边权）
    n = 7#图的顶点数n
    graph = [[] for _ in range(n)]#图的邻接表
    #根据输入的图构建图的邻接表
    for edge in data:
        graph[edge[0]].append([edge[1], edge[2]])
        graph[edge[1]].append([edge[0], edge[2]])
    dist,pre = dijkstra(1,graph)
    print("dist=\n",dist)
    print("pre=\n",pre)

哈夫曼编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
'''
    huffman编码
'''
import copy

class Node:
    def __init__(self, name, weight):
        self.name = name #节点名
        self.weight = weight #节点权重
        self.left = None #节点左孩子
        self.right = None #节点右孩子
        self.father = None # 节点父节点
    #判断是否是左孩子
    def is_left_child(self):
        return self.father.left == self

#创建最初的叶子节点
def create_prim_nodes(data_set, labels):
    if(len(data_set) != len(labels)):
        raise Exception('数据和标签不匹配!')
    nodes = []
    for i in range(len(labels)):
        nodes.append( Node(labels[i],data_set[i]) )
    return nodes


# 创建huffman树
def create_HF_tree(nodes):
    #此处注意，copy()属于浅拷贝，只拷贝最外层元素，内层嵌套元素则通过引用，而不是独立分配内存
    tree_nodes = nodes.copy() 
    #tree_nodes.sort(key=lambda node: node.weight)#升序排列
    while len(tree_nodes) > 1: #只剩根节点时，退出循环
        tree_nodes.sort(key=lambda node: node.weight)#升序排列
        new_left = tree_nodes.pop(0)
        new_right = tree_nodes.pop(0)
        new_node = Node(None, (new_left.weight + new_right.weight))
        new_node.left = new_left
        new_node.right = new_right
        new_left.father = new_right.father = new_node             
        tree_nodes.append(new_node)
    tree_nodes[0].father = None #根节点父亲为None
    return tree_nodes[0] #返回根节点

#获取huffman编码
def get_huffman_code(root, nodes):
    codes = {}
    for node in nodes:
        code=''
        name = node.name
        while node.father != None:
            if node.is_left_child():
                code = '0' + code
            else:
                code = '1' + code
            node = node.father
        codes[name] = code
    return codes


if __name__ == '__main__':
   # labels =  ['A','B','C','D','E','F','G','H','I','J','K','L','M','N']
    labeks = ['a','b','c','d','e','f']
   # data_set = [10,4,2,5,3,4,2,6,4,4,3,7,9,6]
    data_set = [9,12,6,3,5,15]
    nodes = create_prim_nodes(data_set,labels)#创建初始叶子节点  
    root = create_HF_tree(nodes)#创建huffman树
    codes = get_huffman_code(root, nodes)#获取huffman编码
    #打印huffman码
    for key in codes.keys():
        print(key,': ',codes[key])

最小生成树

Prim算法

每次循环选择一个合适的顶点

时间复杂度 O（n^2）

Kruskal算法

每次循环选择一条合适的边

时间复杂度 O（nlogn）

第三章 分治算法

大整数乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#通用的两个大整数乘法分治算法
#能够处理两个整数位数不等情况
#能够处理整数位数不能整除的情况（计算之前通过将位数补充到2^n位实现，如整数12345，6789，则会调整为00012345，00006789
from math import log2,ceil
#将给定的整数高位补0，补充够2^n位

def add_zero(str1,real_len,max_len):
    add_zero_len = max_len - real_len
    return "0" * add_zero_len + str1

def kara(n1,n2):
    if n1 < 10 or n2 < 10:
        return n1 * n2
    n1_str = str(n1)
    n2_str = str(n2)
    n1_len = len(n1_str)
    n2_len = len(n2_str)
    real_len = max(n1_len,n2_len)
    max_len = 2 ** ceil(log2(real_len))
    mid_len = max_len >> 1
    n1_add_zero = add_zero(n1_str,real_len,max_len)
    n2_add_zero = add_zero(n2_str,real_len,max_len)
    a1 = int(n1_add_zero[:mid_len])
    a2 = int(n1_add_zero[mid_len:])
    b1 = int(n2_add_zero[:mid_len])
    b2 = int(n2_add_zero[mid_len:])
    u = kara(a1,b1)
    v = kara(a1-a2,b2-b1)
    w = kara(a2,b2)
    return u * 10 ** max_len +(u + v + w) * 10 ** mid_len + w
if __name__ == "__main__":
    n1 = 1234
    n2 = 5678
    res = kara(n1,n2)
    print(res)

求最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def n_min(a_list,low,high):
    if low >=high:
        return a_list[low]
    mid = (low + high)//2
    left_min = n_min(a_list,low,mid)
    right_min = n_min(a_list,mid+1,high)
    if left_min < right_min:
        return left_min
    else:
        return right_min
if __name__ == "__main__":
    a_list = [8]
    res = n_min(a_list,0,0)
    print(res)

棋盘覆盖问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def chess(tr,tc,pr,pc,size):#tr,tc：棋盘左上角的位置，即棋盘位置。pr,pc:特殊方格的位置，size为棋盘大小。
    global mark
    global table
    if size==1:
        return
    mark = mark + 1
    count = mark
    half=size//2
    if pr<tr+half and pc<tc+half:
        chess(tr,tc,pr,pc,half)
    else:
        table[tr+half-1][tc+half-1]=count
        chess(tr,tc,tr+half-1,tc+half-1,half)
    if pr<tr+half and pc>=tc+half:
        chess(tr,tc+half,pr,pc,half)
    else:
        table[tr+half-1][tc+half]=count
        chess(tr,tc+half,tr+half-1,tc+half,half)
    if pr>=tr+half and pc<tc+half:
        chess(tr+half,tc,pr,pc,half)
    else:
        table[tr+half][tc+half-1]=count
        chess(tr+half,tc,tr+half,tc+half-1,half)
    if pr>=tr+half and pc>=tc+half:
        chess(tr+half,tc+half,pr,pc,half)
    else:
        table[tr+half][tc+half]=count
        chess(tr+half,tc+half,tr+half,tc+half,half)
       
if __name__ == "__main__":
    mark = 0
    n=4
    table=[[-1 for x in range(n)] for y in range(n)]
    count = chess(0,0,1,1,n)
    for i in range(n):
        for j in range(n):
            print(table[i][j],end='	')
        print('')
    print(mark)

幂乘问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def power(a,n):
    if a == 1:
        return 1
    if a == 0:
        return 0
    if n == 1:
        return a
    if n % 2 == 0:
        b = power(a,n//2)
        return b*b
    else:
        b = power(a,(n-1)//2)
        return b * b * a
if __name__ == "__main__":
    a = 5
    n = 6
    k = power(a,n)
    print(k)

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int N = 100010;
int a[N];

int binary_search(int left,int right,int num){
    if(left>right)
        return -1;
    int mid = (1eft+right)/2;
    if(num<a[mid]){
        return binary_search(left,mid-1,num);
    }else if(num>a[mid]){
        return binary_search(mid+1,right,num);
    }
    else{
        return mid;
    }
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int num;
    cin>>num;
    sort(a,a+n);
    int mid = binary_search(0,n-1,num);
    cout << "list[" << mid << "]=" << a[mid] << endl;
}

选第二大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def find_max(a_list,left,right):
    global dic
    if left>=right:
        return a_list[left]
    mid=(left+right)//2
    left_max=find_max(a_list,left,mid)
    right_max=find_max(a_list,mid+1,right)
    if left_max>right_max:
        dic[left_max].append(right_max)
        return left_max
    else:
        dic[right_max].append(left_max)
        return right_max
    
def find_second(n_max):
    second_max=n_max[n]
    for i in range(1,n):
        if n_max[i]>second_max:
            second_max = n_max[i]
    return second_max

if __name__ == "__main__":
    a_list = [6,12,3,7,2,18,90,87,54,23]
    n = len(a_list)
    dic = {}
    for i in range(n):
        dic.update([(a_list[i],[])])
                   
    first_max = find_max(a_list,0,n-1)
    second_max = find_second(dic[first_max])
    print(dic)
    print(second_max)
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 100010;
int n;

struct List {
	int val;
	vector<int> out;
}MyList[N];

int find_index(int val) {
	for (int i = 0; i < n; i++) {
		if (MyList[i].val == val) {
			return i;
		}
	}
	return -1;
}

int find_max(int left, int right) {
	if (left >= right) {
		return MyList[left].val;
	}
	int mid = (left + right) / 2;
	int left_max = find_max(left, mid);
	int right_max = find_max(mid + 1, right);
	if (left_max > right_max) {
		int index = find_index(left_max);
		MyList[index].out.push_back(right_max);
		return left_max;
	}
	else {
		int index = find_index(right_max);
		MyList[index].out.push_back(left_max);
		return right_max;
	}
}

int find_second(List list) {
	int len = list.out.size();
	int second_max = list.out[0];
	for (int i = 1; i < len; i++) {
		if (list.out[i] > second_max) {
			second_max = list.out[i];
		}
	}
	return second_max;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		MyList[i].val = x;
	}
	int first_max = find_max(0, n - 1);
	int second_max = 0;
	int t = 0;
	for (int i = 0; i < n; i++) {
		if (MyList[i].val == first_max) {
			t = i;
			second_max = find_second(MyList[i]);
			break;
		}
	}
	cout << "最大值淘汰的元素：";
	for (int i = 0; i < MyList[t].out.size(); i++) {
		cout << MyList[t].out[i] << " ";
	}
	cout << endl;
	cout << "第二大元素：" << second_max;
	return 0;
}

循环赛日程表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#非递归算法
def round_robin_calendar(k):#整数k：比赛人数为2^k。
    n = 2**k
    import numpy as np
    a = np.zeros((n,n))
    a[0][0] = a[1][1] = 1
    a[1][0] = a[0][1] = 2
    for i in range(1,k):
        half = 2 ** i
        # 左下角的子表中项为左上角子表对应项加2**i
        for row in range(half):
            for col in range(half):
                a[row+half][col]=a[row][col]+half

        # 右上角的子表等于左下角子表
        for row in range(half):
            for col in range(half):
                a[row][col+half]=a[row+half][col]

        # 右下角的子表等于左上角的子表
        for row in range(half):
            for col in range(half):
                a[row+half][col+half]=a[row][col]
    return a

if __name__ =="__main__":
    a = round_robin_calendar(4)
    print(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int n;
const int N = 1000;
int arr[N][N];

void arrange(int p,int q,int n) {
	if (n > 1) {
		arrange(p, q, n / 2);
		arrange(p, q + n / 2, n / 2);
	}
	for (int i = p + n / 2; i < p + n; i++) {
		for (int j = q; j< q + n / 2; j++) {
			arr[i][j] = arr[i - n / 2][j + n / 2];
		}
	}
	for (int i = p + n / 2; i < p + n; i++) {
		for (int j = q + n / 2; j < q + n; j++) {
			arr[i][j] = arr[i - n / 2][j - n / 2];
		}
	}
}

int main()
{
	cin >> n;
	memset(arr, 0, sizeof arr);
	for (int i = 0; i < n; i++) {
		arr[0][i] = i + 1;
	}
	arrange(0, 0, n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
suing namespace std;
const int N = 1010;
int q[N];

void merge_sort(int q[],int l,int r){
    if(l>=r) return;
    int mid = (l+r)>>1;
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k = 0;
    int i=1,j=mid+1,tmp[N];
    while(i<=mid&&j<=r){
        if(q[i]<q[j]){
            tmp[k++]=q[i++];
        }
        else{
            tmp[k++]=q[j++];
        }
    }
    while(i<=mid){
        tmp[k++]=q[i++];
    }
    while(j<=r){
        tmp[k++]=q[j++];
    }
    for(i=1;j=0;i<=r;i++,j++){
        q[i]=tmp[j];
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>

using namespace std;

int n;
const int N = 1010;
int q[N];

void quick_sort(int l, int r) {
	if (l >= r) return;
	int i = l - 1, j = r + 1, x = q[(l + r) / 2];
	while (i < j) {
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(l, j);
	quick_sort( j + 1, r);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> q[i];
	}
	quick_sort( 0, n - 1);
	for (int i = 0; i < n; i++) {
		cout << q[i] << " ";
	}
	return 0;
}

找第K小问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>

using namespace std;

const int N = 1010;
int n,k;
int q[N];

int quickFind(int l,int r,int k){
    if(l >= r) return q[l];
    int x = q[(l + r) / 2],i = l - 1 , j = r + 1;
    while(i < j){
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }
    int s = j - l + 1;
    if(s >= k) return quickFind(l,j,k);
    else return quickFind(j+1,r,k-s);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 0 ; i < n ; i++)
    scanf("%d",&q[i]);
    
    printf("%d",quickFind(0,n-1,k));
    return 0;
}

第四章 动态规划

常用场景：

  • 主要用于求解以实践划分阶段的动态过程的优化问题
  • 动态规划算法用于求解具有某种最优性质的问题

动态规划基本思想

  • 经分解得到的各个子问题往往不是相互独立的

  • 在求解过程中，将已解决的子问题的最优值进行保存，在需要时可以轻松取出

动态规划基本要素

  • 最优子结构性质

  • 子问题重叠性质

  • 自底向上的求解方法

矩阵连乘问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include <string> 

using namespace std;

const int N = 1000;
int m[N][N]; // 记录最优值
int s[N][N]; // 记录最优决策
vector<string> res;

void matrix_chain(vector<int> p,int n) {
	for (int i = 0; i < n + 1; i++) {
		m[i][i] = 0;
		s[i][i] = 0;
	}
	for (int r = 2; r < n + 1; r++) {
		for (int i = 1; i < n - r + 2; i++) {
			int j = i + r - 1;
			m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;
			for (int k = i + 1; k < j; k++) {
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (t < m[i][j]) {
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void trace_back(int i, int j, int s[][1000]) {
	if (i == j) {
		int t = i;
		res.push_back("A" + to_string(t));
	}else {
		res.push_back("(");
		trace_back(i,s[i][j],s);
		trace_back(s[i][j] + 1, j, s);
		res.push_back(")");
	}
}

int main()
{
	vector<vector<int>> arr = { {3,2},{2,5},{5,10},{10,2},{2,3} };
	int n = arr.size();
	vector<int> p;
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			p.push_back(arr[0][0]);
			p.push_back(arr[0][1]);
		}
		else {
			p.push_back(arr[i][1]);
		}
	}
	matrix_chain(p, n);
	trace_back(1, n, s);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i];
	}
	return 0;
}

凸多边形最优三角划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
#include<string>

using namespace std;

vector<vector<int>> weights = { {0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1} ,{4,3,4,2,1,0} };
const int N = 1000;
int m[N][N], s[N][N];
vector<string> res;
int get_weight(int i, int j, int k,int n) {
	if (k < n) {
		return weights[i][j] + weights[j][k] + weights[k][i];
	}
}

void convex_polygon_optimal(int n) {
	memset(m, 0, sizeof m);
	memset(s, 0, sizeof s);
	for (int i = 0; i < n; i++) {
		m[i][i] = 0;
		s[i][i] = 0;
	}
	for (int r = 2; r < n; r++) {
		for (int i = 1; i < n - r + 1; i++) {
			int j = (i + r - 1) % n;
			m[i][j] = m[(i + 1) % n][j] + get_weight(i - 1, i, j, n);
			s[i][j] = i;
			for (int k = i + 1; k < j; k++) {
				int t = m[i][k] + m[(k + 1) % n][j] + get_weight(i - 1, k, j, n);
				if (t < m[i][j]) {
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void trace_back(int i, int j) {
	if (i == j) {
		return;
	}
	else {
		trace_back(i, s[i][j]);
		trace_back(s[i][j] + 1, j);
		res.insert(res.begin(), "v" + to_string((i - 1)) + ",v" + to_string(j) + ",v" + to_string(s[i][j]));
	}
}
int main()
{
	int n = weights.size();
	convex_polygon_optimal(n);
	trace_back(1,5);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << "    ";
	}
	return 0;
}

最长公共子序列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<vector>
using namespace std;

const int N = 1010;

vector<char> a = { 'z','x','y','x','y','z' };
vector<char> b = { 'x','y','y','z','x' };
int c[N][N],s[N][N];
vector<char> res;

void LCS(int n,int m) {
	a.insert(a.begin(), '0');
	b.insert(b.begin(), '0');
	for (int i = 0; i < n + 1; i++) {
		for (int j = 0; j < m + 1; j++) {
			if (i == 0 || j == 0) {
				c[i][j] = 0;
			}
			else if (a[i] == b[j]) {
				c[i][j] = (c[i - 1][j - 1] + 1);
				s[i][j] = 0;
			}
			else if (c[i - 1][j] >= c[i][j - 1]) {
				c[i][j] = c[i - 1][j];
				s[i][j] = 1;
			}
			else {
				c[i][j] = c[i][j - 1];
				s[i][j] = -1;
			}
		}
	}
}

int printLCS(int i,int j) {
	if (i == 0 || j == 0) {
		return 0;
	}
	if (s[i][j] == 0) {
		printLCS(i - 1, j - 1);
		res.push_back(a[i]);
	}
	else if (s[i][j] == 1) {
		printLCS(i - 1, j);
	}
	else {
		printLCS(i, j - 1);
	}
}

int main()
{
	int n = a.size(), m = b.size();
	LCS(n, m);
	printLCS(n, m);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << " ";
	}
	return 0;
}

加工顺序问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> a = { 3,8,10,12,6,9,15 };
vector<int> b = { 7,2,6,18,3,10,4 };
vector<int> x;
struct Jobtype {
	int key, id, N1;
};


bool compare(const Jobtype& a, const Jobtype& b) {
	if (a.N1 != b.N1) {
		return a.N1 > b.N1; 
	}
	return a.key < b.key;
}


void flow_shop(int n) {
	vector<Jobtype> job;
	for (int i = 0; i < n; i++) {
		x.push_back(0);
	}
	for (int i = 0; i < n; i++) {
		int key = min(a[i], b[i]);
		int N1 = a[i] < b[i];
		job.push_back({ key,i,N1 });
	}
	sort(job.begin(),job.end(), compare);
	x.resize(n);
	int j = 0, k = n - 1;
	for (int i = 0; i < n; i++) {
		if (job[i].N1) {
			x[j++] = job[i].id;
		}
		else {
			x[k--] = job[i].id;
		}
	}
}

int main()
{
	int n = a.size();
	flow_shop(n);
	cout << "最佳加工次序为：" << endl;
	for (int i = 0; i < n; i++) {
		cout << x[i] + 1 << " ";
	}
}

0-1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 1010;

vector<int> v = { 0,2,2,6,5,4 };
vector<int> w = { 0,3,6,5,4,6 };
int dp[N][N];
bool choice[N][N]; 
bool st[N];
int main() {
    int m;
    int n = w.size();
    cin >> m;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i][j] < dp[i - 1][j - v[i]] + w[i]) {
                dp[i][j] = dp[i - 1][j - v[i]] + w[i];
                choice[i][j] = true;  
            }
        }
    }

    cout << "最优值为：" << dp[n - 1][m] << endl;

    vector<int> items;
    int capacity = m;
    for (int i = n - 1; i > 0; i--) {
        if (choice[i][capacity]) {
            st[i] = true;
            capacity -= v[i];   
        }
    }
    cout << "背包中所装的物品为：";
    for (int i = 1; i < n; i++) {
        if (st[i]) {
            cout << 1 << " ";
        }
        else {
            cout << 0 << " ";
        }
    }
    return 0;
}

第五章 深度优先搜索

N皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u){
    if(u == n){
        for(int i = 0 ; i < n ; i++)puts(g[i]);
        puts("");
        return;
    }
    for(int i = 0 ; i < n ; i ++){
        if(!col[i] && !dg[u+i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            dfs(u+1);
            col[i] = dg[u+i] = udg[n-u+i] = false;
            g[u][i] = '.';
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j ++){
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}

0-1背包问题——子集树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 1010;

vector<vector<int>> goods = { {0,2,6},{1,2,3},{2,6,5},{3,5,4},{4,4,6} };
int bestp = 0; // 当前最优值
int cw = 0; // 当前重量
int cp = 0; // 当前价值
int n = 5; // 问题规模
int c = 10; // 背包容量
int x[N],bestx[N];
bool compare(vector<int>& a, vector<int>& b) {
	return a[2] / a[1] > b[2] / b[1];
}

int bound(int i) {
	int Wleft = c - cw;
	int b = cp;
	while (i <= n && goods[i][1] <= Wleft) {
		Wleft -= goods[i][1];
		b += goods[i][2];
		i += 1;
	}
	if (i <= n) {
		b += goods[i][2] / goods[i][1] * Wleft;
	}
	return b;
}

void backtrack(int t) {
	if (t >= n) {
		if (bestp < cp) {
			bestp = cp;
			memcpy(bestx, x, sizeof x);
		}
	}
	else {
		if (cw + goods[t][1] <= c) {
			x[goods[t][0]] = 1;
			cw += goods[t][1];
			cp += goods[t][2];
			backtrack(t + 1);
			cw -= goods[t][1];
			cp -= goods[t][2];
		}
		if (bound(t) > bestp) {
			x[goods[t][0]] = 0;
			backtrack(t + 1);
		}
	}
}
int main()
{
	sort(goods.begin(), goods.end(), compare);
	backtrack(0);
	cout << bestp << endl;
	for (int i = 0; i < n; i++) {
		cout << bestx[i] << " ";
	}
}

最大团问题——子集树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<vector>

using namespace std;

const int N = 1010;

vector<vector<int>> a = { {0,1,1,0,0},{1,0,1,1,1},{1,1,0,1,1},{0,1,1,0,1},{0,1,1,1,0} };
int bestx[N],x[N];
int bestn = 0 ,cn = 0;
int n;

int place(int t) {
	bool ok = true;
	for (int j = 0; j < t; j++) {
		if (x[j] && a[t][j] == 0) {
			ok = false;
			break;
		}
	}
	return ok;
}

void backtrack(int t) {
	if (t > n) {
		memcpy(bestx, x, sizeof x);
		bestn = cn;
		return;
	}
	if (place(t - 1)) {
		x[t - 1] = 1;
		cn += 1;
		backtrack(t + 1);
		cn -= 1;
	}
	if (cn + n - t > bestn) {
		x[t - 1] = 0;
		backtrack(t + 1);
	}
}

int main() {
	n = a.size();
	for (int i = 0; i < n; i++) {
		x[i] = i;
	}
	backtrack(1);
	cout << bestn << endl;
	for (int i = 0; i < n; i++) {
		cout << x[i] << " ";
	}
}

批处理作业调度问题——排列树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 1010;
vector<vector<int>> M = { {0,0,0},{0,2,1},{0,3,1},{0,2,3} };
int f = 0, f1 = 0;
int n;

int f2[N], x[N];
int bestf = INT_MAX;
int bestx[N];

void backtrack(int t) {
	if (t >= n) {
		std::copy(x, x + n, bestx);
		bestf = f;
	}
	else {
		for (int j = t; j < n; j++) {
			f1 += M[x[j]][1];
			int k = t - 1;
			f2[t] = max(f2[k], f1) + M[x[j]][2];
			f += f2[t];
			if (f < bestf) {
				swap(x[t], x[j]);
				backtrack(t + 1);
				swap(x[t], x[j]);
			}
			f1 -= M[x[j]][1];
			f -= f2[t];
		}
	}
}

int main()
{
	n = M.size();
	for (int i = 0; i < n; i++) {
		f2[i] = i;
		x[i] = i;
	}
	backtrack(1);
	cout << bestf << endl;
	for (int i = 0; i < n; i++) {
		cout << bestx[i] << " ";
	}
}

旅行商问题——排列树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int NoEdge = INT_MAX, N = 1010;

vector<vector<int>> a = { {0,0,0,0,0,0},{0,NoEdge,10,NoEdge,4,12},{0,10,NoEdge,15,8,5},{0,NoEdge,15,NoEdge,7,30},{0,4,8,7,NoEdge,6},{0,12,5,30,6,NoEdge} };
int n;
int x[N], bestx[N];
int bestc = NoEdge;
int cc = 0;

void backtrack(int t) {
	int g_n = n - 1;
	if (t == g_n) {
		if (a[x[g_n - 1]][x[g_n]] != NoEdge && a[x[g_n]][1] != NoEdge && (cc + a[x[g_n - 1]][x[g_n]]) + a[x[g_n]][1] < bestc || bestc == NoEdge) {
			std::copy(x, x + n, bestx);
			bestc = cc + a[x[g_n - 1]][x[g_n]] + a[x[g_n]][1];
		}
	}
	else {
		for (int j = t; j < n; j++) {
			if (a[x[t - 1]][x[j]] != NoEdge && (cc + a[x[t - 1]][x[t]]) < bestc || bestc == NoEdge) {
				swap(x[t], x[j]);
				cc += a[x[t - 1]][x[t]];
				backtrack(t + 1);
				cc -= a[x[t - 1]][x[t]];
				swap(x[t], x[j]);
			}
		}
	}
}

int main()
{
	n = a.size();
	for (int i = 0; i < n; i++) {
		x[i] = i;
	}
	backtrack(2);
	cout << bestc << endl;
	for (int i = 0; i < n; i++) {
		cout << bestx[i] << " ";
	}
	return 0;
}

图的m着色问题——满m叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<vector>

using namespace std;

const int N = 1010;

vector<vector<int>> a = { {0,0,0,0,0,0},{0,0,1,1,0,0},{0,1,0,1,1,1},{0,1,1,0,1,0},{0,0,1,1,0,1},{0,0,1,0,1,0 } };
int n;
int m = 3;
int sum1 = 0;
int x[N];
vector<vector<int>> colors;

bool Ok(int k) {
	for (int j = 1; j < k; j++) {
		if ((a[k][j] == 1) && (x[j] == x[k])) {
			return false;
		}
	}
	return true;
}

void backtrack(int t) {
	if (t > n) {
		sum1 += 1;
		vector<int> temp;
		for (int i = 0; i < n + 1; i++) {
			temp.push_back(x[i]);
		}
		colors.push_back(temp);
	}
	else {
		for (int i = 1; i < m + 1; i++) {
			x[t] = i;
			if (Ok(t)) {
				backtrack(t + 1);
			}
		}
	}
}

int main()
{
	n = a.size() - 1;
	backtrack(1);
	for (int i = 0; i < colors.size(); i++) {
		for (int j = 0; j < colors[i].size(); j++) {
			cout << colors[i][j] << "，";
		}
		cout << endl;
	}
}

最小质量机器设计问题——满m叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1010;
int COST = 7, n = 3, cw = 0, cc = 0, Total_cost = 0, m = 3, bestw = INT_MAX;
vector<vector<int>> w = { {0,0,0,0},{0,1,2,3},{0,3,2,1},{0,2,3,2} };
vector<vector<int>> c = { {0,0,0,0},{0,1,2,3},{0,5,4,2},{0,3,1,2} };
int bestx[N], x[N];

void backtrack(int t) {
	if (t > n) {
		Total_cost = cc;
		bestw = cw;
		std::copy(x, x + n + 1, bestx);
		return;
	}
	for (int j = 1; j < m + 1; j++) {
		x[t] = j;
		if (cc + c[t][j] <= COST && cw + w[t][j] < bestw) {
			cc += c[t][j];
			cw += w[t][j];
			backtrack(t + 1);
			cc -= c[t][j];
			cw -= w[t][j];
		}
	}
}

int main()
{
	backtrack(1);
	for (int i = 0; i < n + 1; i++) {
		cout << bestx[i] << " ";
	}
	cout << endl;
	cout << bestw << endl;
	cout << Total_cost << endl;
	return 0;
}