1.ROSE矩阵
实现：
使用算法2
分析： 每半圈元素值的增长规律变换一次
设增量为t，每半圈变换一次t <— -t .
设矩阵边长为i，每半圈的元素个数是2*(i-1)个，hc为记数变量，则1≤hc<=2i-1，前1/4圈是1≤hc<=i-1，后1/4是i≤hc<=2i-2，若hc%i==0，则前1/4圈结果为0，后1/4结果为1，可表示为：index <— hc/i, hc <— hc+1。
计算模型：
设s[1]为矩阵行下标，s[0]为矩阵列下标。s数组下标为index。
t为下标增量，初值为-1，矩阵元素k∈[1,n*n].
1.index<- hc/i+1
2.hc<- hc+1
3.hc∈[1,2*i-1]
4.s[index]<-s[index]+t
5.a[s[1],s[0]]<- k , k<- k+1
6.当hc>2*i-1,i<- i-1 ,t<- -t
代码：
void rose(int n)
{
int s[2];
int a[n][n];
int k=1,i=n,t=1;
s[0]=-1,s[1]=0;
while(k<=n*n)
{
for(int hc=1;hc<=2*i-1;++hc)
{
int index=hc/(i+1);
s[index]+=t;
a[s[1]][s[0]]=k;
++k;
}
i--;
t=-t;
}
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
cout<<a[i][j]<<"\t";
}
cout<<endl;
}
}
2.迷宫
最优路径？
可以使用栈或队列完成。
定义：
int M
[
10
]
[
10
]
[10][10]
[10][10]={
1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,1,
1,0,1,1,1,1,0,1,0,1,
1,0,0,0,0,1,0,1,0,1,
1,0,1,0,0,0,0,1,0,1,
1,0,1,0,1,1,0,1,0,1,
1,0,1,0,0,0,0,1,1,1,
1,0,1,0,0,1,0,0,0,1,
1,0,1,1,1,1,1,1,0,1,
1,1,1,1,1,1,1,1,1,1,} ;
//状态定义 ：
// M
[
x
]
[
y
]
[x][y]
[x][y]为0:通路 ，为1：墙 ， 为2：死路 ， 为3：已走过
int fx[]={-1,1,0,0};
int fy[]={0,0,-1,1};
typedef struct p
{
int x,y;
struct p* next;
}point;
1）.若使用栈：
主要代码：
void bfs()
{
stack<point*>s;
point *head=new point,*p;
int x=1,y=1;
head->x=x;
head->y=y;
head->next=NULL;
M[x][y]=3;
s.push(head);
int flag=0;
while(!s.empty() )
{
p=s.top();
s.pop();
//cout<<"front:"<<p->x<<" "<<p->y<<endl;
for(int i=0;i<4;++i)
{
y=p->y+fy[i];
x=p->x+fx[i];
if(M[x][y]==0)
{
//cout<<x<<" "<<y<<endl;
M[x][y]=3;
point * newp=new point;
newp->x=x;
newp->y=y;
newp->next=p;
s.push(newp);
if(x==8 && y==8)
{
flag=1;
break;
}
}
}
if(flag)break;
}
p=s.top();
while(p)
{
cout<<"("<<p->x<<","<<p->y<<")"<<" ";
p=p->next;
}
}
具体实现：
使用栈可以完成查找，但因其后入先出的特性，在程序实现中，优先对左上方的节点进行查找，针对此迷宫而言会产生一些不必要的路径。
所以若想最短时间得到最优路径可以使用队列。
2).队列实现：队列由于其先入先出的特点，每次都对右下方的点进行率先遍历，故更容易找到最优路径。
使用链表存储。
主要代码实现：
void bfs()
{
m[x][y]=3;
p=new po;
p->x=x;
p->y=y;
p->pre=NULL;
q.push(p);
while(!q.empty() )
{
po * p1=q.front();
q.pop();
for(int i=0;i<4;i++)
{
po* pnew=new po;
pnew->pre=NULL;
pnew->x =p1->x + fx[i];
pnew->y = p1->y+ fy[i];
if(m[pnew->x][pnew->y] ==0 )
{
m[pnew->x][pnew->y]=3;
pnew->pre=p1;
q.push(pnew);
}
if(pnew->x==8 && pnew->y==8)
return;
}
}
}
实现：
使用队列来实现，其时间为使用栈实现的一半左右。
3.三壶问题
BFS思想 穷举+回溯.
代码实现：
逐步模拟三个壶的倒水状态
typedef struct node
{
int x,y,z;
struct node * pre;
}node;
queue<node*>q;
node *p2;
node *p3;
set<int> cha;
bool is(node *p)
{
if(p->x==4||p->y==4||p->z==4)
return true;
else return false;
}
void out(node *p)
{
cout<<"("<<p->x<<","<<p->y<<","<<p->z<<")"<<endl;
}
void BFS()
{
node *p=new node;
p->x=8;p->y=0;p->z=0;
p->pre=NULL;
q.push(p);
while(!q.empty())
{
node *p1=q.front();
if(is(p1)) return;
int x=p1->x;
int y=p1->y;
int z=p1->z;
q.pop();
if(cha.find(x*100+y*10+z)!=cha.end()) //没有任何一组状态使用此公式得到的计算结果是相同的，故用此来判别状态是否已被遍历
continue;
else cha.insert(x*100+y*10+z);
if(x>0&&y<5)
{
p3=new node;
if(x+y>5)
{
p3->x=x+y-5;
p3->y=5;
}
else
{
p3->x=0;
p3->y=x+y;
}
p3->z=z;
p3->pre=p1;
q.push(p3);
if(is(p3)) return;
}
if(x>0&&z<3)
{
p3=new node;
if(x+z>3)
{
p3->x=x+z-3;
p3->z=3;
}
else
{
p3->x=0;
p3->z=x+z;
}
p3->y=y;
p3->pre=p1;
q.push(p3);
if(is(p3)) return;
}
if(y>0)
{
p3=new node;
p3->x=x+y;
p3->y=0;
p3->z=z;
p3->pre=p1;
q.push(p3);
if(is(p3)) return;
}
if(z>0)
{
p3=new node;
p3->x=x+z;
p3->z=0;
p3->y=y;
p3->pre=p1;
q.push(p3);
if(is(p3)) return;
}
if(y>0&&z<3)
{
p3=new node;
if(y+z>3)
{
p3->y=y+z-3;
p3->z=3;
}
else
{
p3->y=0;
p3->z=y+z;
}
p3->x=x;
p3->pre=p1;
q.push(p3);
if(is(p3)) return;
}
if(z>0&&y<5)
{
p3=new node;
if(y+z>5)
{
p3->z=y+z-5;
p3->y=5;
}
else
{
p3->z=0;
p3->y=y+z;
}
p3->x=x;
p3->pre=p1;
q.push(p3);
if(is(p3)) return;
}
}
}
4.蛮力匹配
有A B两个字符串 ，长度为n和m
则其最差情况下：首先让A从第一个字符与B的各个字符进行比较，耗时m，A中共n个字符
耗时：O((n-m-1)*m)
5.相当于全排列，则共需 T(n)=O( (n-1)! )时间
6.经计算：15！=1307674368000
16！=20922789888000
18！=6402373705728000
19！=121645100408832000
1小时 运算：3.6* 1 0 13 10^{13} 1013次 16个城市
24小时 运算8.64* 1 0 14 10^{14} 1014次 17个城市
1年运算3.1536* 1 0 17 10^{17} 1017次 19个城市
100年运算3.1536* 1 0 19 10^{19} 1019次 20个城市
- BFS时间复杂度分析
使用邻接表完成
对于 G 令 vexnum=n 即节点数量为n 对于邻接表：共e条边
则其所需时间共分为两部分，n个节点需要O(n)的复杂度，
而邻接表需O(e)的复杂度~ 总时间复杂度为O(n+e).
8.背包问题
1）时间复杂度
单纯通过穷举法，则：对于n个物品，会有 2 n − 1 2^{n-1} 2n−1种解 时间复杂度为 O ( 2 n ) O(2^{n}) O(2n)
2）改进
动规
int main()
{
int N, V;
cin >> N >> V;
vector<int> v(N + 1), w(N + 1), f(V + 1);
for(int i = 1; i <= N; ++i)
cin >> v[i] >> w[i];
for(int i = 1; i <= N; ++i)
for(int j = V; j >= v[i]; --j)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << *max_element(f.begin(), f.end());
return 0;
}
时间复杂度： O ( N ∗ V ) O(N*V) O(N∗V)
贪心
对物品的： 价值/物品体积 进行排序，逐个判断其体积是否能被装下
int G()
{
float temp=0;
float result=0;
float c1=8;
for(int i=0;i<4;i++)
{
for(i=0;i<4;i++)
{
if(temp<sortBest[i])
temp=sortBest[i];
}
//cout<<"max(sortBest)="<<temp<<endl;
for(i=0;i<4;i++)
{
if (temp==sortBest[i])
sortBest[i]=0;
if (w[i]<=c1)
result=result+v[i];
c1=c1-w[i];
}
}
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
