递归与分治
二分搜索：
//从小到大排好序的数组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];
}
八皇后
