第四周总结

主要过年太放纵，我一定改正 ！！

继续努力呀，小V 同志！

这一周主要学了算法，想为复试做准备，本来以为应该挺快的，但是没想到其实算法挺难理解的，不过学完以后感觉各种理解确实加深了好多，下面整理一下。
（挺简单的，主要为了补上以前的坑，真是少壮不努力，老大徒伤悲）

1. 快速排序
这个算法难点主要是边界值，稍有不慎就会出现死循环或者排序错误，所以理解这个代码确实花了点时间。

 void quick_sort(int q[], int l, int r)
 {
     if(l >= r) return;
     int i = l-1;
     int j = r+1;
     int x = q[(l + 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]);
     }
      
      quick_sort(q, l , j);
      quick_sort(q, j+1, r);
 }

2. 归并排序
就我个人来讲，我觉得这个算法的难点是辅助数组赋回过程和对于递归的理解，因为对递归的不理解所以理解代码会有难度。

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
     int i = l, j = mid+1;
    merge_sort(q, i, mid); merge_sort(q, j, r);
    int k = 0;
    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 = l, j = 0 ; i <= r; i++, j++) q[i] = tmp[j];
}

3. 二分查找
二分查找相对来讲要简单一些，但是有些小技巧，主要体现在 mid 是否进行加一操作
附上一个求三次根号的题目

#include <iostream>
using namespace std;

int main()
{
    double l = -10000, r = 10000;
    double x;
    cin>>x;
    double mid;
    while(r - l >= 1e-7)
    {
        mid = (l + r) / 2;
        if(mid * mid * mid <= x) l = mid;
        else r = mid;
    }
    printf("%.6f", l);
}

4. 01背包
对于一般的数据规划问题要按照下图考虑

TIM图片20200209200438.png

在01背包问题里集合代表所有选择的集合，属性是价值的最大值，状态计算根据题意推导出来

对于01背包问题每一次循环只有两个问题，选择第 i 个和不选择第 i 个，因此
dp[i][j] = max ( dp [ i - 1] [ j ] , dp [ i - 1 ] [ j - v] + w [ i ] );

    for(int i=1; i<=n; i++)
     {
         for(int j=0; j<=m; j++)
           {
               res[i][j] = res[i-1][j];
               if(j >= v[i]) res[i][j] = max(res[i][j], res[i-1][j-v[i]] + w[i]);
           }
     }

优化：
将二维数组转换成一维， 要注意循环时要从大到小，如果不变顺序的话，
res[j-v[i]] + w[i] 的 i 就不是 i - 1 ,就会出错。

    for(int i=1; i<=n; i++)
     {
         for(int j=m; j >= v[i]; j--)
           {
    
                res[j] = max(res[j], res[j-v[i]] + w[i]);
                            
           }
     }

6.ccf大模拟题
这个真的是大头，太难了， 有的时候会很莫名其妙出现一些错误，让人抓狂，但是写了大模拟以后确实有一些提升
ccf 的化学方程式题目：就我个人而言，我觉得这个题目对我的提升很大https://www.jianshu.com/p/efca49969cd3

剩下的题目就不沾了，因为上一个题太经典了哈哈~

继续努力呀，小V 同志！