程序的设计艺术与方法

程序设计艺术与方法

实验一 STL 的熟悉与使用

1．实验目的（1）掌握 C++中 STL 的容器类的使用。（2）掌握C++中 STL 的算法类的使用。

2．试验设备硬件环境：PC 计算机软件环境：操作系统：Windows 2000 / Windows XP / Linux 语言环境：Dev cpp / gnu c++

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

- 149

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

源代码：

#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<<"插入尾部的随机数为"<

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");

return 0;

}

运行截图：

2 练习泛型算法的使用：

源代码：

#include

#include

//#inclued

using namespace std;

typedef list lin;

int value[]={1,2,3,4,5};

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. 实验目的 (1) 掌握宽度优先搜索算法。 (2) 掌握深度优先搜索算法。

2. 试验设备硬件环境：PC 计算机软件环境：操作系统：Windows 2000 / Windows XP / Linux 语言环境：Dev cpp / gnu c++

3. 试验容 (1) 将书上的走迷宫代码上机运行并检验结果，并注意体会搜索的思想。 (2) 八皇后问题：在一个国际象棋棋盘上放八个皇后，使得任何两个皇后之间不相互攻击，求出所有的布棋方法。上机运行并检验结果。思考：将

此题推广到 N 皇后的情况，检验在 N 比较大的情况下，比方说 N=16 的时候，你的程序能否快速的求出结果，如果不能，思考有什么方法能够优化算法。 (3) 骑士游历问题：在国际棋盘上使一个骑士遍历所有的格子一遍且仅一遍，对于任意给定的顶点，输出一条符合上述要求的路径。 (4) 倒水问题：给定 2 个没有刻度容器，对于任意给定的容积，求出如何只用两个瓶装出 L 升的水，如果可以，输出步骤，如果不可以，请输出 No Solution。

（2）八皇后问题

源代码：

#include

using namespace std;

#include

int sum = 0;

int upperlimit = 1;

void compare(int row,int ld,int rd)

{

if(row!=upperlimit)

{

int pos=upperlimit&~(row|ld|rd);

while(pos!=0)

{

int p=pos&-pos;pos-=p;

compare(row+p,(ld+p)<<1,(rd+p)>>1);

}

}

else{sum++;

}

}

int main()

{

int n;

cout<<"请输入皇后的个数:";

cin>>n;

upperlimit = (upperlimit<

compare(0,0,0);

cout<<"问题的解如下:"<

return 0;

}

运行截图：

（4）倒水问题

源代码：

4.倒水问题：

#include"stdio.h"

int main()

{

int ca,cb,cc,x,y;

while(scanf("%d%d%d",&ca,&cb,&cc)!=EOF) {

if(cb==cc)

{ printf("fill B\n");

}

else if(ca==cc)

{

printf("fill A\n");

printf("pour A B\n");

}

else

{

x=y=0;

if(ca

{

while(1)

{ if(y==0)