算法代码

递归与分治

二分搜索：

//从小到大排好序的数组list[low:high]中查找x
int binarySearch(int *list,int low,int high,int x)
{
    int left=low;
    int right=high;
    while(left<=right)
    {
        int minddle(left+right)/2;
        if(list[middle]==x)return middle;
        if(list[middle]<x)
            left=middle+1;
        else
            right=middle-1;
    }
    return -1;
}

---

归并排序：

//将a[low,mid]和a[mid+1，high]归并
void merge(int* a,int low,int mid,int high)
{
    int i=low;
    int j=mid+1;
    for(int k=low;k<=high;k++)
    {
        aux[k]=a[k];
    }
    for(int k=low;k<=high;k++)
    {
        if(i>mid)
            a[k]=aux[j++];
        else if(j>high)
            a[k]=aux[i++];
        else if(aux[i]<aux[j])
            a[k]=aux[i++];
        else
            a[k]=aux[j++];
    }
}

void mergeSort(int *list,int low,int high)
{
    if(high<=low)return ;
    int mid=(low+high)/2;
    mergeSort(list,low,mid);
    mergeSort(list,mid+1,high);
    merge(list,low,mid,high);
}

---

快速排序：

void quickSort(int* list,int low,int high)
{
    if(low<high)
    {
        int q=partition(list,low,high);
        quickSort(list,low,q-1);
        quickSort(list,q+1,high);
    }
}
int partition(int* list,int low,int high)
{
    int i=low;
    int j=high+1;
    int x=a[low];
    while(true)
    {
        while(list[++i]<x&&i<r);
        while(list[--j]>x);
        if(i>=j)break;
        swap(list[i],list[j]);
    }   
    swap(list[low],list[j]);
    return j;
}

---

循环赛日程表：

void fun(int n){
    if (n==2){
        mp[1][1]=mp[2][2]=1;
        mp[1][2]=mp[2][1]=2;
        return ;
    }
    if (n>2) fun(n/2);
    int k=n/2;
    //进行复制
    for (int i=1;i<=k;i++)
        for (int j=1;j<=k;j++){
            mp[i+k][j+k]=mp[i][j];
            mp[i+k][j]=mp[i][j]+k;
            mp[i][j+k]=mp[i][j]+k;
        }
    return ;
}

---

动态规划

矩阵连乘：

//m[i][j]代表Ai...Aj最小乘法运算次数
//s[i][j]记录Ai...Aj中间加括号的位置
int memoizedMatrixChain(int n)
{
    for(int i=1;i<n;i++)
    {
        for(int j=i;j<=n;j++)
            m[i][j]=0;
    }
    return lookUpChain(1,n);
}
int lookUpChain(int i,int j)
{
    if(m[i][j]>0)
        return m[i][j];
    if(i==j)
        return 0;
    int u = lookUpChain(i+1,j) + p[i-1]*p[i]*p[j];
    s[i][j]=i;
    for(int k=i+1;k<j;k++)
    {
        int t=lookUpChain(i,k)+lookUpChain(k+1,j)+p[i-1]*p[k]*p[j];
        if(t<u)
        {
            u=t;
            s[i][j]=k;
        }
    }
    m[i][j]=u;
    return u;
}

---

最长公共子序列

#include <iostream>
#include <cstring>
using namespace std;
char sz1[1000];
char sz2[1000];
//maxLen[i][j]表示sz1左边i个字符形成的子串，与sz2左边j个字符形成的子串的
//最长公共子序列长度，i，j从0开始算。
int maxLen[1000][1000];
int main()
{
    while(cin>>sz1>>sz2)
    {
        int length1=strlen(sz1);
        int length2=strlen(sz2);
        int nTmp;
        int i,j;
        for(i=0;i<=length1;i++)
            maxLen[i][0]=0;
        for(j=0;j<=length2;j++)
            maxLen[0][j]=0;
        for(i=1;i<=length1;i++)
        {
            for(j=1;j<=length2;j++)
            {
                if(sz1[i-1]==sz2[j-1])
                    maxLen[i][j]=maxLen[i-1][j-1]+1;
                else
                {
                    maxLen[i][j]=max(maxLen[i-1][j],maxLen[i][j-1]);
                }
            }
        }
        cout<<maxLen[length1][length2]<<endl;
    }
    return 0;
}

---

贪心算法

活动安排：

struct action
{
    int begin;
    int end;
}a[1000];
int n;//活动总数
int sum=0;//能参加的活动的数量
void search()
{
    sort(a);//按照结束时间排序
        sum=1;
    int temp=a[0].end;
    for(int i=1;i<n;i++)
    {
        if(a[i].begin>=temp)
        {
            sum++;
            temp=a[i].end;
        }
    }
}

---

搬桌子:

#include <iostream>
using namespace std;

struct 
{
    int start;
    int end;
}a[100];
bool used[100];
int main()
{
    sort(a,n);//按照start将a数组排序
    int min=0;
    int num=0;
    while(num<n)
    {
        int temp=0;
        for(int i=0;i<n;i++)
        {
            if(!used[i]&&a[i].start>=temp)
            {
                temp=a[i].end;
                used[i]=true;
                num++;
            }
        }
        min++;
    }
}

---

回溯算法

最大装载

//r代表剩余集装箱的重量和
void backtrack(int i)
{
    if(i>n)
    {
        if(cw>bestw)
            bestw=cw;
        return ;
    }
    r-=w[i];
    if(cw+w[i]<c)
    {
        cw+=w[i];
        backtrack(i+1);
        cw-=w[i];
    }
    if(cw+r>bestw)
    {
        backtrack(i+1);
    }
    r+=w[i];
}

---

八皇后