程序的设计艺术与方法

. . .

程序设计艺术与方法

实验一 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<<\插入尾部的随机数为\ for (it1=myV.begin();it1!=myV.end();it1++) {

cout<<(*it1)<

cout<<\ int t=rand();

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

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

cout<<(*it1)<

}

cout<

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

cout<<(*it1)<

cout<

if(myV.empty()) {

cout << \ }

system(\ 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<<\的元素为：\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(\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) { {

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

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<

.. ..