数据结构与算法分析实验报告

实验报告

学院：电信学院

班级：计算机06

学号：xxx

姓名：xxx

小组成员：xxx

2011年12月20日

实验四 八皇后问题

1、问题描述

    设在初始状态下，在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行有8个选择的位置，但在任一时刻棋盘的合法布局都必须满足3个条件（1）任意两个棋子得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。

2、基本要求

     编写求解并输出此问题的一个合法布局的程序。

3、实现提示

    在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向列方向正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j列布放旗子。

解：编写程序如下：

#include

#define NUM 8 

int a[NUM+1];

int main()

{

int i,k,flag,not_finish=1,count=0;

i=1; 

a[1]=1; 

printf("The possible configuration of 8 queens are: \\n");

while(not_finish)

{

while(not_finish&&i<=NUM)

{

for(flag=1,k=1;

flag&&kif(a[k]==a[i])

flag=0;

for(k=1;flag&&kif((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))

 flag=0;

if(!flag) 

{

if(a[i]==a[i-1]) 

{

i--;

if(i>1&&a[i]==NUM)

a[i]=1; 

else if(i==1&&a[i]==NUM)

not_finish=0; 

else a[i]++; 

}

else if(a[i]==NUM)

 a[i]=1;

else a[i]++; 

}

else if(++i<=NUM)

if(a[i-1]==NUM) 

a[i]=1;

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

}

if(not_finish)

{

++count;

printf((count-1)%3?" [%2d]: ":" [%2d]: ",count);

for(k=1;k<=NUM;k++)

printf(" %d",a[k]);

if(a[NUM-1]a[NUM-1]++; 

else a[NUM-1]=1;

i=NUM-1; 

}

}

}

运行结果如下：

算法分析：

S1：创建一个一维数组a[n]，用n表示棋子所在的行标，a[n]值表示棋子所在的列标；

S2：给第一行第一列（即a[1]）赋初值，表明有一个棋子在该处；

S3：用flag作为是否处理过的标记，判断是否有多个皇后在同一行，判断是否有多个皇后在同一对角线。

时间复杂度为：O（n2）

空间复杂度为：O（0）

实验五 约瑟夫环问题仿真

1、问题描述

设编号为1,2，…，n（n>0）个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起报数，报到m时停止报数，报 m的人出列，将他的密码作为新的m值，从在他顺时针方向上的下一个人起重新自1报数；如此下去，直到所有人全部出列为止。

2、基本要求

设计一个程序模拟此过程，给出出列人的编号序列。

3、实现提示

    可考虑不带头指针的单链表结构。

4、测试数据

     N=7，其个人的密码依次为：3,1,7,2,4,8,4.

    初始报数上限值m=20。

解：编写程序如下：

#include

class Node

{

public:

    int number,data;

    Node *next;

    Node(int a,int b)

    {

        number=a;

        data=b;

        next=0;

    }

};

class Circle

{

public:

    Node *Head,*Tail;

    Circle()

    {

        Head=Tail=0;

    }

    void add(Node *p)

    {

        if(Head==0)

        {

            Head=Tail=p;

        }

        else

        {

         Tail->next=p;

            Tail=p;

         Tail->next=Head;

        }

    }

    int search(int a)

    {

        Node *p,*q;

        int d;

        p=Head;

     if(p==p->next)

        {

         cout<number<            return 0;

        }

     for(int i=1;i        {

            q=p;

         p=p->next;

        }

     cout<number<     d=p->data;

        if(i==1)

        {

            q=p;

         p=p->next;

         q->data=p->data;

         q->number=p->number;

         Head=q;q->next=p->next;

            delete p;

            return d;

        }

     Head=q->next=p->next;

        delete p;

        return d;

    }

    int out(int a)

    {

        while(a=search(a));

        return 1;

    }

};

int main()

{

    Circle a;

    int amount,d;

    Node *p;

cout<<"请输入人数"< cin>>amount;

cout<<"请依次输入其密码"< for(int i=0;i    {

     cin>>d;

        p=new Node(i+1,d);

        a.add(p);

    }

cout<<"请输入起始数"< cin>>d;

cout<<"************"<    a.out(d);

    return 1;

}

运行结果如下：

算法分析：

S1：创建一个链表，表头指向表尾，形成一个环；

S2：从头结点即尾结点的下一个结点，开始报数，若所报的数小于d，i++，直至所报的数等于d，将报d的结点的number输出，并将其从链表中删掉；

S3：继续s2，直至将链表中所有结点输出；

S4：此时链表为空，程序结束。

时间复杂度为：O((a-1)*d)

空间复杂度为：O（2）