0x1 前言

算法课他lie了，本身想系统的整理一下，但是最近要学的东西实在有点多，就先贴上代码，之后进行系统整理，方便复习使用。

0x2 全排列的实现

C++实现方法：

#include <iostream>
#include <string>
using namespace std;
void swap(char* A, char* B)
{
    char* C = A;
    A = B;
    B = C;
}
void perm(string A,int start,int end) {//产生A[start:end]的全排列
    if (start == end)//当首尾一致时，说明此时产生了一种排列方法
        cout << A<<" ";//递归停止条件
    else
    {
        for (int i = start; i < end; i++) //分治条件，以每个字符为第一位开始一次递归
        {
            swap(A[start], A[i]);//保持长度不发生改变，进行交换，使每一位都可以在第一位
            perm(A, start + 1, end);//弹出第一位
            swap(A[start], A[i]);//还原原数组
        }
    }
}
int main() {//主函数采用输入一个字符串的形式
    int m;//提供字符串的长度
    string A;//输入字符串
    cin >>m>> A;
    perm(A,0,m);//递归函数
    system("pause");
    return 0;
}

python实现方法：

def fun1(s=''):
    if len(s) <= 1:
        return [s]
    else:
        sl = []
        for i in range(len(s)):
            for j in fun1(s[0:i] + s[i + 1:]):
                sl.append(s[i] + j)
        return sl


if __name__=="__main__":
    n = str(input())
    a = fun1(n[:-1])
    H=0
    b=list(set(a))
    b.sort()
    for i in b:
        print(i,end=" ")

0x3 汉诺塔

C++实现

#include <iostream>
using namespace std;
void move(char a, char b)
{
    cout << "将" << a << "移动至" << b<<endl;
}
void hanoi(int n, char a, char b, char c)//n代表a柱子上有几个盘子，b代表目标盘子，c代表辅助盘子
{
    if (n > 0)//整个流程分为三步
    {
        hanoi(n - 1, a, c, b);//将除了最大的盘子，其余的都移动到辅助盘子上
        move(a, b);//将最大的盘子移动到目标轴上
        hanoi(n - 1, c, b, a);//将其余的盘子，作为一次新的输入，重新继续移动
    }
    return ;
}
int main() {
    cout << "输入汉诺塔层数:";
    int Y;
    cin >> Y;
    hanoi(Y, 'A', 'B', 'C');
    system("pause");
    return 0;
}

0x6 猴子吃桃子推导

0x5 大数乘法两种推导

0x7 9.14 课后思考题

思考题目描述：一学期结束了，我们所有专业课的总成绩被老师统计出来了，我们需要猜数（132--1154）之间进行猜数，设计最高效的算法。
这里先记录一下，明天下午进行实验。

二分查找

二分查找一定是本题的第一直观想法，这玩意比顺序查找要快，时间复杂度在最坏情况下也只有O(log2n)。具体原理和复杂度推导就不再说了。
python实现代码：

import datetime
def insert_value_search(array, left, right, val):
    #array=sorted(array)
    if left > right or val < array[0] or array[right-1] < val: # 注意后半部分的判断条件
        return -1#表示没有找到
    mid_index = left + (right - left) * (val - array[left]) // (array[right] - array[left])
    mid_val = array[mid_index]
    if mid_val < val:
        return insert_value_search(array, mid_index + 1, right, val)
    elif val < mid_val:
        return insert_value_search(array, left, mid_index - 1, val)
    else:
        return mid_index

if __name__ == '__main__':
    exam = [i for i in range(132,1155)]
    #print(exam)
    time=[]
    for i in range(132,1155):
        start = datetime.datetime.now()
        binary_search(exam,i)
        end = datetime.datetime.now()
        time.append(end-start)
    print(max(time)) #0:00:00.004314 最长搜索用时

插值查找

这个算是二分查找的以这种改进方法，使用key值，对1/2进行动态优化，对于均匀顺序的数组效率一定比二分法要高。
主要原理就是优化二分法的查找公式：
二分法：mid=(low+high)/2, 即mid=low+1/2*(high-low);
插值查找：mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
举个例子：

当然这是对于你不知道你要找的具体数值的情况下使用的方法，感觉设置key很玄乎。但是当我们需要查找一个具体的数字时，我们就可以令key==find，此时插值查找就会自动适应，不需要我们进行玄幻的估计。一下代码是在已知find的时候进行讨论的。

import datetime
def insert_value_search(array, left, right, val):
    #array=sorted(array)
    if left > right or val < array[0] or array[right-1] < val: # 注意后半部分的判断条件
        return -1#表示没有找到
    mid_index = left + (right - left) * (val - array[left]) // (array[right] - array[left])
    mid_val = array[mid_index]
    if mid_val < val:
        return insert_value_search(array, mid_index + 1, right, val)
    elif val < mid_val:
        return insert_value_search(array, left, mid_index - 1, val)
    else:
        return mid_index

if __name__ == '__main__':
    exam = [i for i in range(132,1155)]
    #print(exam)
    time=[]
    for i in range(132,1155):
        start = datetime.datetime.now()
        insert_value_search(exam,0, 1022, i)
        end = datetime.datetime.now()
        time.append(end-start)
    print(max(time)) #0:00:00.001007 最长搜索用时

当数组分布均匀的时候，时间复杂度为：O(log2(log2n)) （为啥不给出证明。emmmm我查了很多资料，不太会算，先留坑之后想起来再填）

斐波那契查找

斐波那契查找：使用黄金分割进行查找（实用优化算法课跳车前的最后遗产），是不是更加玄学了起来，这个算法本质上也是切割算法的一种，只不过他不像二分法一样和傻子一样进行分割，也不是像插值一样进行进行动态分割，而是使用了一种美丽的分割，使用黄金分割点进行划分。emmmmm有点玄乎，但是确实可能也许有用。基本分割原理如下：
将一个长度为F(n)数组看做前后两半，前面一半长度是F(n-1)，后面一半的长度是F(n-1)。

讲人话就是将数列按个数划分，尽可能的使前后比值接近0.618。（要是我没理解错的话应该是这样）

import datetime
import copy
def fibonacci_search(ord_data, target_value):
    """
    Args:
        ord_data: ordered data
        target_value: value that be searched
        max_size: max size of fibonacci number
    """
    # 0：首选深度复制数据
    D = copy.deepcopy(ord_data)
    
    # 1：构建斐波那契数列
    F = [0, 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597]

    # 2：计算数据长度对应斐波那契数列元素
    index = 0
    while(F[index]<len(D)):
        index += 1

    # 3：对数据进行填充
    for i in range(len(D), F[index]):
        D.append(D[len(D)-1])
   
    # 4：对区间不断分割
    left = 0
    right = F[index]
    while left <= right and index>0:
        # 计算分割位置，左区间长度为F(n-2)，右区间长度为F(n-1)
        # -1是因为下标从0开始，即D[0]到D[20]对应21个元素
        mid = left + F[index-1] - 1
           
        # 判断中间值和目标值的关系
        if D[mid] == target_value:
            # 此时搜索到的目标值是填充的值
            if mid > len(ord_data):
                return len(ord_data)-1
            else:
                return mid
                
        elif D[mid] < target_value:
            left = mid + 1
            index = index - 2

        elif D[mid] > target_value:
            right = mid - 1
            index = index - 1

    return None

if __name__ == '__main__':
    exam = [i for i in range(132,1155)]
    #print(exam)
    time=[]
    for i in range(132,1155):
        start = datetime.datetime.now()
        fibonacci_search(exam, i)
        end = datetime.datetime.now()
        time.append(end-start)
    print(max(time)) #0:00:00.007022 最长搜索用时

代码是嫖的，看起来感觉不是很快。

哈希查找

哈希查找 构建属于自己的哈希函数（有待商确）
哈哈哈哈哈，自己挖坑自己跳，不会！没看明白是咋实现的，之后有机会再补吧！

总结：从理论复杂度来看，插值查找应该是最优解，但是还是带有一定的主管色彩，但是要是将这个问题抽象成一个查找问题的话，均匀，连续，那最优解一定是插值。也不知道老韩想要那种算法，搞得神神密密的。要是明天出现重大偏差，本人不负责，等听完在进行修正吧。

0x8 线性时间选择算法手动模拟例子

有一说一，我觉得这个地方有点难，需要手动模拟一遍熟悉一下：


动手来一遍，基本就明白了。

0x9 动态规划算法

矩阵连乘问题

基础的动态规划问题，通过枚举的方法选择出每次的最优解。具体例子：

最长公子序问题

注意，答案不唯一。并且对于所有的行列一定是单调递增的。
老韩规定：相等优先选上方（此时会产生一个个固定的序列）

凸多边形最优切割

图像压缩

这是个单值DP

01背包问题

方法1：

注意最优解一定是个向量
方法2：

最优布线问题

流水线问题

排序要满足两种条件：

1. 在M1上加工时间<在M2上加工时间，并且按照在M1上加工时间由小到大（递增）排序
2. 在M1上加工时间>=在M2上加工时间，并且按照在M2上加工时间由大到小（递减）排序
   否则出来的代价可能是对的，但是顺序是和bp算法出来的不太一样。

0xA 10.14 测试

复习复习把流水线给漏掉了，mmp。完全忘记自己还学过一个这样的小玩意。
01背包问题断点法效率会稍微的高一点，完全忘记还有一个这样的方法。
最后就是01背包的最优解一定是个向量，记住是个向量。
（01背包于流水现会补在上方bp处）

0xB 贪心法则

本章不会涉及到很多计算，主要是涉及到三个步骤：

• 贪心策略
• 贪心步骤
• 时间复杂度
  后续会重点讨论这几项，贪心策略尤为重要，如何书写明确的贪心策略成为了本章的关键。

活动安排问题

• 贪心策略：尽可能的选择结束早的课程先加入集合，为后续课程的选择留下更大的余地
• 贪心步骤：首先将所有课程的结束时间由早到晚进行排序，之后尽可能将结束早的课程加入选择集合为后续课程留下更多的时间，然后在集合中个课程相容的前提下筛选结束早的课程继续加入集合直至时间用尽或是没有相容课程相容时，完成算法。
• 时间复杂度：一次排序O（nlogn），一次筛选O（n），最终复杂度为O（nlogn）。

背包问题

此处的背包问题不是bp处的01背包问题，这里的背包问题是可以进行拆卸的（就是可以取小数个，不一定必须要取整数个）

• 贪心策略：Vi/Wi的比值大者可优先被选入
• 贪心步骤：先进行一次遍历，计算出每个物品的价值于重量的比值，对比值进行降序排列，依次将物品选入背包，直至选满或物品没有剩余为止。
• 时间复杂度：两次遍历O（N），一次排序O（NlogN），最终复杂度为O（nlogn）。

最优装载问题

不管每个集装箱的价值，只记录装载的集装箱数量：

• 贪心策略：重量轻的优先装
• 贪心步骤：对集装箱重量进行升序排列，依次将物品选入，直至选满或物品没有剩余为止。
• 时间复杂度：一次排序O（nlogn），一次筛选O（n），最终复杂度为O（nlogn）。

哈夫曼树

• 贪心策略：用的次数多的字符编码短，次数少的字符编码长
• 贪心步骤：按照字符频率进行降序排列，存入队列Q。从Q中选择最小的两个，作为两个节点，相加后的值再次加入队列。重复直至完成。
• 时间复杂度：排序O（nlogn），筛选O（n），最终复杂度为O（nlogn）。
  例题：

最短路径

在一个无向图中，从一个原点出发，到各各节点的最短路径。

最小生成树

生成一颗代价最小的树将所有的节点相连。

0xC 时间复杂

本身这里应该紧跟的是深搜和广搜，但是由于上周打比赛很忙，这里的笔记没有及时进行整理。现在进入了复习阶段，就直接跳回第一章了。
算法具有下面五个特征：

• 输入（input）：算法有零个或多个输入量
• 输出（output）：算法至少产生一个输出量
• 确定性（definiteness）：算法的每一条指令都有确切的定义，没有二义性
• 可行性（effectiveness）：算法的每一条指令必须足够基本，他们可以通过已经实现的基本运算执行有限次来实现
• 有穷性（finiteness）：算法必须总能在执行有限步之后终止

算法时间复杂性

渐进分析

当N足够大的时候，相加的几个时间直留最小的。

大O表示法

舍弃常数生成时间复杂性。
常见的阶排序：

双计算机运行效率问题

渐进复杂性例题

0xd 分治法时间复杂性推导

分治法，就是把一个大的复杂的问题分为a(a>1)个形式相同的子问题，这些子问题的规模为n/b，如果分解或者合并的复杂度为f(n)，那么总的时间复杂度可以表示为：

分治法时间复杂度的运算例题：

二分搜索

#include <bits/stdc++.h>
using namespace std;
int A[]={160,173,187,173,61,20,85,116,128,131,55,95,120,184,3,161,128,180,90,189,70,99,76,186,68,190,52,110,6,155};
int erfen(int input,int start,int end,int sum){
    if(start=end-1){
        cout<<"NOT"<<endl;
        return 0;
    }
    int mid=(start+end)/2;
    if(A[mid]>input)
        end=mid;
    else if(A[mid]<input)
        start=mid;
    else{
        cout<<"find"<<endl;
        return sum;
    }
    sum++;
    cout<<A[mid]<<" "; 
    erfen(input,start,end,sum); 
    //return 0;
}
int main(){
    int input;
    cout<<"input your data:"<<endl;
    sort(A,A+30);
        for(int i=0;i<30;i++)
    {
        cout<<A[i]<<" "; 
    }
    cout<<endl;
    while(cin>>input){
        int B=erfen(input,0,30,0);    
        if(B==0){
            //cout<<"no found"<<endl;
        }
        else{
            cout<<"time："<<B<<endl;
        }
    }
    return 0;
} 

这个地方跳过整理的太乱了！！！

0xE 分支限界法

分支限界法分为两种出队模式分别是：

• 队列式
• 优先队列式

队列式

队列式很简单，顾名思义就是先进先出的搜索模式，并且在搜索的途中加入限界剪枝和约束剪枝简化搜索。注意：当儿子是叶节点时将不会被加入队列。这种方法很简单，不在手操，附PPT。

优先队列式

优先队列式则是加入了每次选择的权值。

0xE 第五章 深度优先搜索

不撞南墙不回头的算法。注意：这里的树与哈夫曼的树是相反的，哈夫曼树是左零右一，而这里是左一右零。
两种剪枝方式分别是：

• 限界剪枝：超过要求。如背包问题的背包装满。
• 约束剪枝：已经无法达到最高低要求。如背包问题剩余的物品重量之和已经无法达到最低要求。
  呈现方式：在需要剪枝处使用一个叉号，并标明剪枝方式即可。

两种树的结构：

• 子集树：所有东西选择性带走。如0-1背包
• 排列树：所有东西一个也不少的带走。如流水调度问题。

DFS+01背包代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn = 30;
int n,v,MAXValue;//物品个数，背包容量
int w[maxn] = {0},c[maxn] = {0}; //每件物品的重量为w[i],价值为c[i]

void DFS(int index, int sumW, int sumC) {
    if(index == n) { //完成对 n个 物品的选择---递归边界
        MAXValue = max(MAXValue,sumC);//更新最大价值MAXValue
        return ;
    }
    if(sumW + w[index] <= v)//“选择”当前物品 ,不超过背包最大容量时//约束剪枝 
        DFS(index+1,sumW + w[index],sumC + c[index]);
    int sum1=0;
    for(int i=index+1;i<=n;i++)
        sum1+=c[i];//剩余没有遍历的节点重量总和
    if((sum1+sumC)>=MAXValue)//限界剪枝 
        DFS(index+1,sumW,sumC);//“不选择”当前物品
}
int main() {
    cin>>n>>v;
    for(int i = 0; i < n; ++i)
        cin>>w[i];
    for(int i = 0; i < n; ++i)
        cin>>c[i];
    DFS(0,0,0);//初始时为第 0件物品、当前总重量和总价值 均为0
    cout<<MAXValue;
    return 0;
}