1．掌握C++中STL的容器类的使用;

2．掌握C++中STL的算法类的使用.

1．预习ICPC讲义，大致了解STL的相关内容。

2．了解STL中一些类 vector list类的使用方法

3．了解泛型算法的使用

(1) 练习vector 和list 的使用。定义一个空的vector，元素类型为int，生成10 个随机数插入到vector 中，用迭代器遍历vector 并输出其中的元素值。在vector 头部插入一个随机数，用迭代器遍历vector并输出其中的元素值。用泛型算法find 查找某个随机数，如果找到便输出，否则将此数插入vector 尾部。用泛型算法sort 将vector 排序，用迭代器遍历vector 并输出其中的元素值。删除vector 尾部的元素，用迭代器遍历vector 并输出其中的元素值。将vector 清空。定义一个list，并重复上述实验，并注意观察结果。  

(2) 练习泛型算法的使用。定义一个vector，元素类型为int，插入10 个随机数，使用sort 按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find 查找元素。用min 和max 找出容器中的最小元素和最大元素，并输出。

1. 练习vector 和list 的使用：

#include

#include

#include

#include

#include

using namespace std;

vector myV;

bool sortup(int v1,int v2)

{

return v1} 

int main(int argc, char *argv[])

{  

srand(time(NULL)); for (int i=0;i<10;i++)

    myV.push_back(rand());        

sort(myV.begin(),myV.end(),sortup); vector::iterator it1;

    for (it1=myV.begin();it1!=myV.end();it1++)

    {

cout<<(*it1)<    }

cout<   int min=myV[0];    

   for (it1=myV.begin()+1;it1!=myV.end();it1++)

if((*it1)   cout<<"最小元素为" <   int max=myV[0];

   for (it1=myV.begin();it1!=myV.end();it1++)

if((*it1)>max)max=(*it1);

   cout<<"最大元素为" < cout<    int value=rand();

    it1=find(myV.begin(),myV.end(),value);     

    if((*it1)==value)

    cout<<"找到了这个随机数"<    else  

    cout<<"没有找到这个随机数"<     myV.insert(myV.end(),value); 

     cout<<"插入尾部的随机数为"<    for (it1=myV.begin();it1!=myV.end();it1++)

    {

cout<<(*it1)<    }

cout<<"\\n"<    int t=rand();

    myV.insert(myV.begin(),t);

    cout<<"插入头部的随机数为" <    for (it1=myV.begin();it1!=myV.end();it1++)

    {

cout<<(*it1)<    }

cout<    myV.pop_back ();

     for (it1=myV.begin();it1!=myV.end();it1++)

    {

cout<<(*it1)<    }

cout<    myV.clear();

    if(myV.empty())   

    {

cout << "It's empty!" << endl;

    }

    system("PAUSE");  //press any key to continue... 

    return 0;

}

2 练习泛型算法的使用：

#include

#include

using namespace std;

typedef list lin;

int value[]={1,6,7,8,9}; 

void print(lin &l)

{

int i;

lin::iterator lit;

for(lit=l.begin();lit!=l.end();lit++)

cout<<(*lit)<<" ";

cout<}

bool sortsp(int v1,int v2)

   {

return v1>v2;

    }   

int main(){

lin lin2; 

lin2.push_front(3); 

lin2.push_front(4); 

lin2.insert(lin2.begin(),value,value+5);

cout<<"lin2内的元素为：";

print(lin2);

lin2.sort(); 

cout<<"排序后的lin2: ";

print(lin2);

lin2.push_front(10);

cout<<"在list头部插入10之后的结果："; 

print(lin2);

lin2.remove(6);

cout<<"删除一个数后的lin1:"; 

print(lin2); 

system("PAUSE");

return 0;

}

1．掌握宽度优先搜索算法;

2．掌握深度优先搜索算法.

1．预习ICPC讲义中的搜索的内容

2. 了解什么是深度优先搜索和广度优先搜索。

1. 将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。

2.八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。

3. 骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。

4.倒水问题：给定2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出L 升

的水，如果可以，输出步骤，如果不可以，请输出No Solution

2，八皇后问题：

#include

#define N 8

#define NUM 8

int h[N][N],n[N],H[N][N];

int count=0;

void tryit(int,int);

void outputArray(int[][N]);

main()

{

    int x=0,y=0,i,j;

for(i=0;i<=N-1;i++)

    {

        for(j=0;j<=N-1;j++)

            h[i][j]=0;

    }

    tryit(x,y);

    printf("......\\n");

    printf("共有%d种布局.\\n",92);

    return(0);

}

void tryit(int x,int y)

{

    int i,j;

if(count<=NUM)

    {

    if((H[0][0]==1&&H[1][4]==1&&H[2][7]==1&&H[3][5]==1&&H[4][2]==1&&H[5][6]==1&&H[6][1]==1&&H[7][3]==1)&&count!=1)

    {}

    else

    {

        if(x>=0&&x<=N-1&&y>=0&&y<=N-1&&h[x][y]==0)

        {

            for(j=0;j<=7;j++)

            {

                if(h[x][j]==0)

                    h[x][j]=x+1;

                if(h[j][y]==0)

                 h[j][y]=x+1;

                if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&h[x+j][y+j]==0)

                    h[x+j][y+j]=x+1;

                if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&h[x+j][y-j]==0)

                     h[x+j][y-j]=x+1;

                if(x-j>=0&&x-j<=N-1&&y+j>=0&&y+j<=N-1&&h[x-j][y+j]==0)

                        h[x-j][y+j]=x+1;

                if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&h[x-j][y-j]==0)

                    h[x-j][y-j]=x+1;

            }

            h[x][y]=-x-1;

            if(x==7)

            {

                for(i=0;i<=N-1;i++)

                {

                    for(j=0;j<=N-1;j++)

                    {

                        if(h[i][j]<0)

                            H[i][j]=1;

                        else

                            H[i][j]=0;

                    }

                }

             count=count+1;

                if(count<=NUM)

                {

                    printf("------布局%d------\\n",count);

                 outputArray(H);

                }

for(i=0;i<=N-1;i++)

                {

                    for(j=0;j<=N-1;j++)

                    {

                        if(h[i][j]==x||h[i][j]==-x||h[i][j]==-x-1)

                            h[i][j]=0;

                    }

                }

                tryit(x-1,n[x-1]+1);

            }

         else

            {

                n[x]=y;

             tryit(x+1,0);

            }

        }

        else

        {

            if(y>7)

            {

                for(i=0;i<=N-1;i++)

                {

                    for(j=0;j<=N-1;j++)

                    {

                        if(h[i][j]==x||h[i][j]==-x)

                             h[i][j]=0;

                    }

                }

                if(x-1>=0)

                 tryit(x-1,n[x-1]+1);

                else

     tryit(0,0);

            }

            else

                tryit(x,y+1);

        }

    }

    }

}

void outputArray(int h[][N])

{

    int i,j;

for(i=0;i<=N-1;i++)

    {

        for(j=0;j<=N-1;j++)

            printf("%d ",h[i][j]);

        printf("\\n");

    }

}

3. 骑士游历问题：

#include

int board[8][8] = {0}; 

int travel(int x, int y)

 { 

int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; 

int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1}; 

int nexti[8] = {0}; 

int nextj[8] = {0}; 

int exists[8] = {0}; 

int i, j, k, m, l; 

int tmpi, tmpj; 

int count, min, tmp; 

i = x;

j = y; 

board[i][j] = 1; 

for(m = 2; m <= ; m++) {

for(l = 0; l < 8; l++)

exists[l] = 0; 

l = 0;

for(k = 0; k < 8; k++) {

tmpi = i + ktmove1[k]; 

tmpj = j + ktmove2[k]; 

if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)

continue; 

if(board[tmpi][tmpj] == 0) { 

nexti[l] = tmpi; 

nextj[l] = tmpj; 

l++; 

} 

} 

count = l; 

if(count == 0) { 

return 0; 

} 

else if(count == 1) { 

min = 0; 

} 

else { 

for(l = 0; l < count; l++) {

for(k = 0; k < 8; k++) {

tmpi = nexti[l] + ktmove1[k]; 

tmpj = nextj[l] + ktmove2[k]; 

if(tmpi < 0 || tmpj < 0 ||

tmpi > 7 || tmpj > 7) {

continue; 

} 

if(board[tmpi][tmpj] == 0) 

exists[l]++; 

} 

} 

tmp = exists[0]; 

min = 0; 

for(l = 1; l < count; l++) {

if(exists[l] < tmp) {

tmp = exists[l]; 

min = l; 

} 

} 

} 

i = nexti[min]; 

j = nextj[min]; 

board[i][j] = m; 

} 

return 1; 

}

int main()

 { 

int startx, starty; 

int i, j; 

printf("输入起始点："); scanf("%d %d", &startx, &starty); 

if(travel(startx, starty)) { 

printf("游历完成！\\n"); 

} 

else { 

printf("游历失败！\\n"); 

} 

for(i = 0; i < 8; i++) {

for(j = 0; j < 8; j++) {

printf("%2d ", board[i][j]); 

} 

putchar('\\n'); 

} 

return 0; 

} 

1. 理解线段的性质、叉积和有向面积。

2. 掌握寻找凸包的算法。

3. 综合运用计算几何和搜索中的知识求解有关问题。

1．预习ICPC讲义，大致了解计算几何算法的相关内容。

2．了解实现该算法的中一些使用方法。

3．会使用该算法解决实际问题。

1. 将讲义第三章第三节中的凸包代码上机运行并检验结果。

2. 完成讲义第三章的课后习题，上机运行并检验结果。

3. 思考：判线段相交时，如果有个线段的端点在另一条线段上，注意可能与另一条线段上的端点重合，思考这样的情况怎么办。

4. 房间最短路问题：给顶一个内含阻碍墙的房间，求解出一条从起点到终点的最最短路径。房    间的边界固定在x=0,x=10,y=0 和y=10。起点和重点固定在(0,5)和(10,5)。房间里还有0 到18 个墙，每个墙有两个门。输入给定的墙的个数，每个墙的x 位置和两个门的y 坐标区间，输出最短路的长度。下图是个例子：

3.思考：

用跨立方法。线段相交满足且只需满足如下两个条件就可以了：1 两条线段相互跨立；2 一条线段的一个端点在另一条线段上。如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立p3p4 ，则矢量 ( p1 –p3 ) 和( p2 - p1 )位于矢量( p4 – p3 )的两侧，即( p1 –p3） × ( p4- p3 ) * ( p2 – p3 ) × ( p4 –p3 ) < 0。上式可改写成( p1 – p3 ) × ( p4- p3 ) * ( p4 – p3 ) × ( p2 – p3) > 0。当( p1 –p3 ) × ( p4–p3 ) = 0 时，说明( p1 – p3 ) 和 ( p4 – p3 )共线，但是因为已经通过快速排斥试验，所以 p1 一定在线段 p3p4上；同理，( p4 – p3 ) ×(p2 – p3 ) = 0 说明 p2 一定在 p3p4上。所以判断p1p2跨立Q1Q2的依据是：( p1 – p3 ) × ( p4 – p3 ) * ( p4 – p3 ) × ( p2–p3 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( p3 - p1 ) × ( p2 - p1 ) * ( p2 - p1 ) × ( p4 - p1 ) >= 0。代码中函数bool segment_intersect()用于判断p1、p2构成的线段和p3、p4构成的线段是否相交。可以看出共五种情况两线段是相交的，反之就输出“The two are Not intersected!”

4.房间最短路问题：

#include

#include

#include

#include

  using namespace std; 

typedef pair POINT;

  double direction(POINT p,POINT p1,POINT p2){ 

  POINT v1,v2; 

  v1.first=p2.first-p1.first; 

  v1.second=p2.second-p1.first; 

  v2.first=p1.first-p.first; 

  v2.second=p1.second-p.second; 

   return v1.first*v2.second-v1.second*v2.second;} 

  bool on_segment(POINT p,POINT p1,POINT p2){ 

double min_x=p1.first double max_x=p1.first>p2.first?p1.first:p2.first;

double min_y=p1.second double max_y=p1.second>p2.second?p1.second:p2.second;

if(p.first>=min_x&&p.first= min_y&&p.second<=max_y)

  return true; 

  else 

   return false;

}

  POINT startPoint;

   bool sortByPolorAngle(const POINT &p1,const POINT &p2) 

 {

  double d=direction(startPoint,p1,p2); 

if(d<0)return true;

if(d >0)return false;

  if(d==0&&on_segment(startPoint,p1,p2))return true; 

   if(d= =0&&on_segment(p2,startPoint,p1))return true; 

   return false; 

  } 

void find_convex_hull(vector&point)

   { 

   POINT p0=point[0]; 

  int k=0; 

for(int i=0;i  { 

if(point[i].second point[i].second==p0.second&&point[i].first  p0=point[i]; 

  k=i;} 

  } 

  point.erase(point.begin()+k); 

  point.insert(point.begin(),p0); 

vectorconvex_hull;

  do{

  convex_hull.push_back(point[0]); 

  startPoint=point[0]; 

  point.erase(point.begin()); 

  sort(point.begin(),point.end(),sortByPolorAngle);

  if(point[0]==convex_hull[0])break; 

  point.push_back(convex_hull[convex_hull.size()-1]); 

  }while(1); 

for(int j=0;j cout<  }}

  int main(){ 

vector pv;

   double x,y; 

   int i; 

   cout<<"请输入10个点："< for(i=1;i<=10;i++){

cout<<"No."< cin>>x>>y;

pv.push_back(make_pair(x,y));

}

cout< system("Pause"); 

 return 0;

 }

1．理解动态规划的基本思想、动态规划算法的基本步骤 

2．掌握动态规划算法实际步骤

1．动态规划算法的基本要素

2．最长公共子序列

3．矩阵连乘问题

(1) 求两个字符串的最长公共子序列。 

 - 151 - X的一个子序列是相应于X下标序列{1, 2, …, m}的一个子序列，求解两个序列的所有子序列中长度最大的，例如输入：pear, peach输出：pea。

  (2) 给定两个字符串a和b，现将串a通过变换变为串b，可用的操作为，删除串a中的一 个字符；在串a的某个位置插入一个元素；将串a中的某个字母换为另一个字母。对于任意的串a和串b，输出最少多少次能够将串变为串b。 思考：输出变换的步骤。

  (3) 输入一个矩阵，计算所有的子矩阵中和的最大值。  例如，输入 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出为：15  思考：当矩阵很大时，比如100*100的矩阵，你的程序还能够很快的得出结果吗，如果不能，请思考如何用动态规划的思想解决。

源代码如下：

1.求两个字符串的最长公共子序列。

#include

#include

   using namespace std;

      void longest(string s1,string s2)

 {

       int max,tep,i,j;

      int a[100][100];

for(i=0;i for(j=0;j    a[i][j]=0;

for (j=0;j         if (s1[0]==s2[j])

 a[0][j]=1;

for (i=0;i         if (s1[i]==s2[0])

 a[i][0]=1;

              max=a[0][0];

      tep=0;

for(i=1;i for(j=1;j           if(s1[i]==s2[j])

           {

              a[i][j]=a[i-1][j-1]+1;

if(max             {

               max=a[i][j];

              tep=i; 

            }

           }

        if(max==0)

cout<<"没有公共子序列!";

   else

{

cout<<"两个字符串的最长公共子序列为:";

for(i=tep-max+1;i<=tep;i++)

cout< cout<   }

 }

     int main()

 {

      string s1,s2;

cout<<"请输入两个字符串:"< cout<<"一个字符串为:";

cin>>s1;

cout<<"另一个字符串为:";

cin>>s2;

longest(s1,s2); cout<return 0;

 }

 (2) 给定两个字符串a和b，现将串a通过变换变为串b

#include

#include

  using namespace std;

   int min(int x1,int x2, int x3)

  {

if(x2 x1=x2;  

else if(x3 x1=x3;

   return x1;

  }

  void change(string s1,string s2)

  {

     const char * str=s1.c_str();

    const char * tep=s2.c_str();

   int b[100][100];

   b[0][0]=0;

for(int i=1;i<=s1.length();i++)

    b[0][i]=i;

for(int j=1;j<=s2.length();j++)

    b[j][0]=j;

for( i=1;i<=s2.length(); i++)

for(int m=1;m<=s1.length();m++)

   {

   if(tep[i-1]==str[m-1])

 b[i][m]=b[i-1][m-1];

   else

 b[i][m]=1+min(b[i-1][m-1],b[i-1][m],b[i][m-1]);

 }

   cout<<"将a变为b需要"<}

  int main() 

{

  string s1,s2;

   cout <<"输入字符串a:";

cin >>s1;

    cout <<"输入字符串b:";

cin >> s2;

    change(s1,s2);

cout<return 0;

 }