文章目录
1、 数字三角问题
2、最长公共子序列问题
3、日常购物
4、台阶问题


一、实验目的：

掌握动态规划算法的基本思想及适用条件，掌握动态规划算法的设计步骤和具体实现。

二、实验所用仪器及环境

Windows 7 以上操作系统，PC机，codeblocks环境
三、实验原理：

算法总体思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

动态规划算法设计步骤：

(1)找出最优解的性质，并刻划其结构特征。

(2)递归地定义最优值。

(3)以自底向上的方式计算出最优值。

(4)根据计算最优值时得到的信息，构造最优解。
四、实验内容：
1、 数字三角问题
问题描述：给定一个由n行数字组成的数字三角形，如下图所示

7

3   8

8   1   0

2    7   4   4

4    5   2   6   5
试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

如上图最大值为30=7+3+8+7+5
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[100][100]={0};
int mem[100][100]={0};
int n;
int memd[100][100]={0};
int dp(int p,int q){
    if(mem[p][q]!=0){
        return mem[p][q];
    }
    if(p==n)
    {
        mem[p][q]=a[p][q];
        return mem[p][q];
    }

    if(dp(p+1,q)>=dp(p+1,q+1))
    {
        memd[p][q]=q;
    }else{
    memd[p][q]=q+1;
    }
    mem[p][q]=max(dp(p+1,q),dp(p+1,q+1))+a[p][q];
    return mem[p][q];
}


int main()
{

    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }

    //
    cout<<dp(1,1)<<"=";
    int qt,pt;
    qt=pt=1;
    for(int i=1;i<=n;i++)
    {
        cout<<a[i][pt];
        if(i!=n)
        {
            cout<<"+";
        }
        pt=memd[i][pt];
    }

    return 0;
}
//in
//5
//7
//3 8
//8 1 0
//2 7 4 4
//4 5 2 6 5
//out
//30

2、最长公共子序列问题
问题描述：给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。

输入：

第1行：两个子序列的长度，m n

第2行：第1个子序列的各个元素（序列下标从1开始）

第3行：第2个子序列的各个元素（序列下标从1开始）

输出：

最长公共子序列

实例：

输入：

第1行：

4 5            //m和n的值

第2行

abad        //输入4个字符，下标从1开始

第3行

baade      //输入5个字符，下标从1开始

输出：

Aad
#include<bits/stdc++.h>
using namespace std;
int recdp[1000][1000]= {0};

char str1[1000];
char str2[1000];

int dp(int i,int j)
{
    ///让数组头从开始，dp0，与dp，0都代表空串
    ///base
    if(i==0||j==0)return 0;

    ///rec
    if(recdp[i][j]!=0){return recdp[i][j];}

    ///相同时直接+1
    /// 当这里直接使用图中的0为空字符串时，一定记得，str也是从0开始计算的，所以第五个字符应该是str[4]//
    if(str1[i-1]==str2[j-1]){
        recdp[i][j]=dp(i-1,j-1)+1;
        return recdp[i][j];
    }
    else{
            ///不同时直接选大的（我也不知道谁大，那就比比吧）（可能，要1，可能要2，****可能都不要）
///不需要两个都不要，两个都不要的话，第一次不要1，第二次不要2就行了，而且也不会，因为两个都不要一定是最小的
///*******不同时不要+1
        recdp[i][j]=max(dp(i-1,j),dp(i,j-1));
        return recdp[i][j];
    }
    return 0;
}
int main()
{
    //cout << "Hello world!" << endl;
    cin>>str1;
    cin>>str2;
    cout<<dp(strlen(str1),strlen(str2));
    return 0;


}


///abcde
///ace
///out
//3

3、日常购物
问题描述：小明今天很开心，因为在家买的新房子即将拿到钥匙。新房里面有一间他自己专用的、非常宽敞的房间。让他更高兴的是，他的母亲昨天对他说：“你的房间需要购买什么物品？怎么布置，你说了算，只要他们的价格总和不超过N元钱”。小明今天早上开始预算，但他想买太多的东西，肯定会超过母亲的N元限额。因此，他把对每件物品的渴望程度，分为5等级：用整数1->5表示，第5等表示最想要。他还从互联网上找到了每件商品（所有整数）的价格。他希望在不超过N元（可能等于N元）的情况下，将每件商品的价格与效益度的乘积的总和最大化.

设第j件物品的价格为p[j]，重要度为w[j]，其选中的k件商品，编号依次为j1，j2，……，jk，则所求的总和为：

p[j1]×w[j1]+p[j2]×w[j2]+ …+p[jk]×w[jk]。

请帮小明设计一个符合要求的购物清单。

其中N=2000,K=6

p[1]=200 w[1]=2

p[2]=300 w[2]=2

p[3]=600 w[3]=1

p[4]=400 w[4]=3

p[5]=1000 w[5]=4

p[6]=800 w[6]=5
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int p[10000]={0};
int w[10000]={0};
int mem[10000]={0};

int dp(int n,int k){
    for(int i=0;i<k;i++)
    {
        for(int j=n;j>=p[i];j--)
        {
            mem[j]=max(mem[j],mem[j-p[i]]+p[i]*w[i]);
        }
    }
    return mem[n];
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<k;i++)
    {
        cin>>p[i]>>w[i];
    }
    cout<<dp(n,k);

    return 0;
}
//in
//2000 6
//200 2
//300 2
//600 1
//400 3
//1000 4
//800 5
//out
//8400

4、台阶问题
问题描述：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。

实际情况：给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int mem[1000]={0};
int dp(int n)
{
    if(n==1)
    {
        return 1;
    }
    if(n==2)
    {

        return 2;
    }
    if(mem[n]!=0)
    {
        return mem[n];
    }

    mem[n]=dp(n-1)+dp(n-2);
    return mem[n];
}
int main()
{
    int n;
    cin>>n;
    cout<<dp(n);
    return 0;
}
//in
//12
//233

五、实验结果与分析：

通过运行程序验证程序的正确性，给出程序运行结果，分析程序出现的bug的原因，调试程序过程种出现的错误和解决方法。

多进程实现消费者生产者问题

一，实验目的

1，了解生产者消费者的互斥与同步问题

2，掌握Windows和Linux的进程通信方法

二，实验要求

完成Windows版本和Linux版本。

一个大小为3的缓冲区，初始为空。

2个生产者


	
随机等待一段时间，往缓冲区添加数据，
		
若缓冲区已满，等待消费者取走数据后再添加
		
重复6次
	
3个消费者


	
随机等待一段时间，从缓冲区读取数据
		
若缓冲区为空，等待生产者添加数据后再读取
		
重复4次
	
显示每次添加和读取数据的时间及缓冲区的状态

三，实验环境

Windows版本：Windows 10 64位系统，Dev-cpp编译器

Linux版本：Fedora29版本，gcc环境 vim文本编辑器

四，实验代码结构

1),pv操作伪代码：

array[3]:interger//缓冲区定义,大小为三

int empty=3,full=0;

int mutex=1;

i=0,j=0//缓冲区指针

x，y：item //产品变量

生产者：                                                                                              消费者：

begin：

produce a product to x;

P(empty);

P(mutex);

array[i]=x;

ii=(i+1)%3;

V(full);

V(mutex);

,,,,,, .........,

End

消费者：



end

 

 

2）实验代码分析

Windows版本：

思路分析：Windows创建多进程使用creatprocess()函数调用自己，通过多次创建得到两个生产者进程三个消费者进程，在之中运行相应的生产者函数，消费者函数。在通过传入参数不同，来辨别是第一次主进程还是生产者进程，消费者进程。通过构建共享内存区进行进程间通信。

①多进程创建



 

② 构建共享内存区，再将文件映射到本进程，初始化



③在主创建进程间信号量full empty



分别在生产者消费者进程创建互斥访问量mutex



④同过argv量的不同判断进程归属

 



⑤

运行结果：



全部代码见后

Linux版本：

思路分析：Linux使用fork进行多进程创建，分别在进程中运行消费者函数，生产者函数。建立共享主存区很信号量在进程建进行通信和缓存访问

①，创建进程分别运行消费者和生产者函数



②建立共享主存并进行映射



③创建进程间信号量full，empty和互斥量 mutex，并初始化



 

④实验结果：



五， 实验总结

本次实验获得圆满成功。

本次实验通过分别编写Windows和Linux版本的多进程实现消费者和生产者问题，了解生产者消费者的互斥与同步问题，掌握Windows和Linux的进程通信方法，也同时加强自己对多进程操作的理解。

代码：

WIndows版本：
//实验三生产者消费者 
#include <windows.h>
#include <stdio.h>
#include <time.h>


HANDLE handleOfProcess[5];

struct buf  
{  
	char buffer[3];
	int write;
	int read;
};  

int rand_1()
{
  return rand()%100+1000;
}

char rand_char()
{
	return rand()%26+'A';
}

void StartClone(int nCloneID)
{
	TCHAR szFilename[MAX_PATH];
	GetModuleFileName(NULL,szFilename,MAX_PATH);

	TCHAR szCmdLine[MAX_PATH];
	sprintf(szCmdLine,"\"%s\" %d",szFilename,nCloneID);
	//printf("%s\n",szCmdLine);

	STARTUPINFO si;
	ZeroMemory(reinterpret_cast<void*>(&si),sizeof(si));

	si.cb=sizeof(si);
	PROCESS_INFORMATION pi;

	BOOL bCreateOK=CreateProcess(
		szFilename,
		szCmdLine,
		NULL,
		NULL,
		FALSE,
		CREATE_DEFAULT_ERROR_MODE,
		NULL,
		NULL,
		&si,
		&pi);
	if(bCreateOK)
		handleOfProcess[nCloneID]=pi.hProcess;
	else
	{
		printf("Error in create process!\n");
		exit(0);
	}
}

void pro()//生产者
{
    HANDLE mutex = CreateMutex(NULL,FALSE,"MYMUTEX");  
    HANDLE empty = OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,"MYEMPTY");  
    HANDLE full = OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,"MYFULL");  

    HANDLE hMap = OpenFileMapping(FILE_MAP_ALL_ACCESS,FALSE,"myfilemap");
    LPVOID Data=MapViewOfFile(//文件映射
        hMap,  
        FILE_MAP_ALL_ACCESS,  
        0,  
        0,  
        0);  
    struct buf *pint=reinterpret_cast<struct buf *>(Data);  

    for (int i = 0; i < 6; i++)  
    {  
        WaitForSingleObject(empty, INFINITE);          
        //sleep
        srand((unsigned)time(0));  
        int tim=rand_1();
        Sleep(tim);

        WaitForSingleObject(mutex, INFINITE);  

//code
        pint->buffer[pint->write]=rand_char();
        pint->write=(pint->write+1)%3;
        
       
        ReleaseMutex(mutex);
        ReleaseSemaphore(full,1,NULL);

		SYSTEMTIME syst;
		time_t t=time(0);
		GetSystemTime(&syst);
        char tmpBuf[10];
 		strftime(tmpBuf,10,"%H:%M:%S",localtime(&t));
        printf("生产者%d向缓冲区写入数据:\t%c\t%c\t%c\t@%s.%d\n",
        	(int)GetCurrentProcessId(),pint->buffer[0],pint->buffer[1],
        	pint->buffer[2],tmpBuf,syst.wMilliseconds);
		fflush(stdout);
    }
    UnmapViewOfFile(Data);//解除映射
    Data=NULL;
    CloseHandle(mutex);
    CloseHandle(empty);
    CloseHandle(full);
}

void con()//消费者
{
    HANDLE mutex = CreateMutex(NULL,FALSE,"MYMUTEX");  
   	HANDLE empty = OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,"MYEMPTY");  
    HANDLE full = OpenSemaphore(SEMAPHORE_ALL_ACCESS,FALSE,"MYFULL");  

    HANDLE hMap = OpenFileMapping(FILE_MAP_ALL_ACCESS,FALSE,"myfilemap");
    LPVOID Data=MapViewOfFile(//文件映射
        hMap,  
        FILE_MAP_ALL_ACCESS,  
        0,  
        0,  
        0);  
    struct buf *pint=reinterpret_cast<struct buf *>(Data);  

    for (int i = 0; i < 4; i++)  
    {  
        WaitForSingleObject(full,INFINITE);
        //sleep
        srand((unsigned)time(0));  
        int tim=rand_1();
        Sleep(tim);
       
        WaitForSingleObject(mutex,INFINITE);  

        pint->buffer[pint->read]=' ';
        pint->read=(pint->read+1)%3;
        
        ReleaseMutex(mutex);  
        ReleaseSemaphore(empty,1,NULL); 
//code

        time_t t=time(0);
        char tmpBuf[10];
        SYSTEMTIME syst;
        GetSystemTime(&syst);
 		strftime(tmpBuf,10,"%H:%M:%S",localtime(&t));

        printf("消费者%d从缓冲区读取数据:\t%c\t%c\t%c\t@%s.%d\n",
        	(int)GetCurrentProcessId(),pint->buffer[0],pint->buffer[1],
        	pint->buffer[2],tmpBuf,syst.wMilliseconds);
		 fflush(stdout);
         
    }
    UnmapViewOfFile(Data);//解除映射
    Data=NULL;
    CloseHandle(mutex);
    CloseHandle(empty);
    CloseHandle(full);
}

int main(int argc,char * argv[])
{
	int nCloneID=20;
	if(argc>1)
	{
		sscanf(argv[1],"%d",&nCloneID);
	}

	if(nCloneID<2)//生产者进程
	{
		pro();
	}
	else if(nCloneID<5)//消费者进程
	{
		con();
	}
	else//主进程
	{
        HANDLE hMap=CreateFileMapping(  
            NULL,  
            NULL,  
            PAGE_READWRITE,  
            0,  
            sizeof(struct buf),  
            "myfilemap");  

        if (hMap!=INVALID_HANDLE_VALUE)  
        {  
            LPVOID Data=MapViewOfFile(//文件映射
                hMap,  
                FILE_MAP_ALL_ACCESS,  
                0,  
                0,  
                0);  

            if (Data!=NULL)
            {  
                ZeroMemory(Data,sizeof(struct buf));  
            }  
            struct buf *pnData=reinterpret_cast<struct buf *>(Data);  
            pnData->read=0;  
            pnData->write=0;  
            memset(pnData->buffer,0,sizeof(pnData->buffer));  
            UnmapViewOfFile(Data);//解除映射
            Data=NULL;
        }

        HANDLE empty = CreateSemaphore(NULL,3,3,"MYEMPTY");  
        HANDLE full = CreateSemaphore(NULL,0,3,"MYFULL");  
		for(int i=0;i<5;i++)//创建子进程
			StartClone(i);
        WaitForMultipleObjects(5,handleOfProcess,TRUE,INFINITE);
    CloseHandle(empty);
    CloseHandle(full);
	}
}


Linux版本：

//实验三：生产者消费者                                                                                                                                                                                             
#include<string.h>
#include <sys/time.h>
#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
#include<stdlib.h>
#include<sys/sem.h>
#include<sys/select.h>
#include<sys/wait.h>
#include<sys/ipc.h>
#include<sys/shm.h>
#include<time.h>
#define SEM_ID1 225
#define SEM_ID2 97
#define SEM_ID3 234
#define SHMKEY 75

struct buf{
  char buffer[3];
  int read;
  int write;
};

int rand_1()
{
  return rand()%300;
}

void sleep_ms(int s)
{
    usleep(s*10000);
}

char* cur_time()
{
    time_t timep;
    time(&timep);
    return ctime(&timep);
}
char rand_char()
{
    return rand()%26+'A';
}
void P (int s)//p操作 
{
    struct sembuf sem_op;
    sem_op.sem_num=0;
    sem_op.sem_op=-1;
    sem_op.sem_flg=0;
    semop(s,&sem_op,1);
}
void V(int s)//v操作 
{
    struct sembuf sem_op;
    sem_op.sem_num=0;
    sem_op.sem_op=1;
    sem_op.sem_flg=0;
    semop(s,&sem_op,1);

}
void pro()//生产者
{
    int tim,shmid,i=6;
    int sem_mutex,sem_empty,sem_full;
    void * addr;
    struct buf *pint;
    struct sembuf sem_op;
    struct timeval tv;
    sem_mutex=semget(SEM_ID1,1,0600);
    sem_empty=semget(SEM_ID2,1,0600);
    sem_full=semget(SEM_ID3,1,0600);
    shmid=shmget(SHMKEY,sizeof(struct buf),0777);
    addr=shmat(shmid,0,0);
    while(i--)
    {
        gettimeofday(&tv,NULL);
        srand((unsigned)tv.tv_usec);
        tim=rand_1();
        sleep_ms(tim);  
        //P(empty)
        P(sem_empty);
        //P(mutex)
        P(sem_mutex);

        pint=(struct buf *)addr;

        // pint[semctl(sem_full,0,GETVAL)]=time;
        pint->buffer[pint->write]=rand_char();
        pint->write=(pint->write+1)%3;

        printf("当前生产者进程:%d 写入数据:\t%c\t%c\t%c\t@%lds%ldus\n",
            getpid(),pint->buffer[0],pint->buffer[1],
            pint->buffer[2],tv.tv_sec,tv.tv_usec);


        //V(mutex)
        V(sem_mutex);
        //V(full)
        V(sem_full);                                                                                                                                                                                               
    }
    shmdt(addr);
}
void con()//消费者
{
    int tim,shmid,i=4;                                                                                                                                                                                             
    int sem_mutex,sem_empty,sem_full;
    void * addr;
    struct buf *pint;
    struct sembuf sem_op;
    struct timeval tv;
    sem_mutex=semget(SEM_ID1,1,0600);
    sem_empty=semget(SEM_ID2,1,0600);
    sem_full=semget(SEM_ID3,1,0600);
    shmid=shmget(SHMKEY,sizeof(struct buf),0777);
    addr=shmat(shmid,0,0);
    while(i--)
    {
        gettimeofday(&tv,NULL);
        srand((unsigned)tv.tv_usec);
        tim=rand_1();
        sleep_ms(tim); 
        //P(full)
        P(sem_full);
        //P(mutex)
        P(sem_mutex);

        pint=(struct buf *)addr;

        pint->buffer[pint->read]=' ';
        pint->read=(pint->read+1)%3;

        printf("当前消费者进程:%d 读取数据:\t%c\t%c\t%c\t@%ldst%ldms\n",
            getpid(),pint->buffer[0],pint->buffer[1],
            pint->buffer[2],tv.tv_sec,tv.tv_usec);

        //V(mutex)
        V(sem_mutex);
        //V(empty)
        V(sem_empty);

    }
    shmdt(addr);
}

int main()
{
    int sem_mutex,sem_empty,sem_full,shmid;
    void * addr; 
    union semun {
      int val;
    }empty,full,mutex;

//建立信号量 
    sem_mutex=semget(SEM_ID1,1,IPC_CREAT|0600);
    sem_empty=semget(SEM_ID2,1,IPC_CREAT|0600);
    sem_full=semget(SEM_ID3,1,IPC_CREAT|0600);

    full.val=0;
    empty.val=3;
    mutex.val=1;

    semctl(sem_mutex,0,SETVAL,mutex);
    semctl(sem_empty,0,SETVAL,empty);
    semctl(sem_full,0,SETVAL,full);

//建立共享内存并进行映射 
    shmid=shmget(SHMKEY,sizeof(struct buf),0777|IPC_CREAT);
    if(-1==shmid)
    {
      printf("建立共享内存失败\n");
      exit(0);
    }
    addr=shmat(shmid,0,0);
    memset(addr,0,sizeof(struct buf));

//执行生产者进程 
    for(int i=0;i<2;i++)
        if(fork()==0)
        {
            pro();
            exit(0);
        }
//执行消费者进程 
    for(int i=0;i<3;i++)
        if(fork()==0)
        {
            con();
            exit(0);
        }

    while(-1 != wait(0));
    semctl(sem_mutex,0,IPC_RMID);
    semctl(sem_empty,0,IPC_RMID);                                                                                                                                                                                  
    semctl(sem_full,0,IPC_RMID);
    shmdt(addr);
}


 

数据清洗对数据进行重新审查和校验的过程，目的在于删除重复信息、纠正存在的错误，并提供数据一致性。 

在进行常规的检验数据的时候，根据基本原则，去掉重复数据与冲突数据。将采集到的数据视为均匀分布在设定的特征值数量的情况下，根据得到的数据分布选择适当的插值来补充缺失的特征。对于这样经过快速傅立叶变换后的数据，经过多次实验，最终选择牛段插值法。 

数据降噪  

信息中的噪声数据的变化波动幅度相对于整体数据而言是较小的。并且观察数据分布，经过清洗后的数据经过高斯分布检验呈现出正态分布的趋势，那么在进行降维降噪处理时就可以使用KPCA(kernel principal component analysis)进行处理分析。 

在这个过程中主要进行的操作有: 

计算核矩阵 

中心化核矩阵 

求中心化核矩阵的特征值和特征向量 

按照从从大到小排序选取前n个特征值的特征向量 

将高维数据与核矩阵以及选择出的特征值运算映射到低维空间求得数据的主成分完成降噪降维处理

一、实验目的
1、问题描述
	迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。
2、设计功能要求
迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 
	算法输入：代表迷宫入口的坐标
	算法输出：穿过迷宫的结果。 算法要点：创建迷宫，试探法查找路。
二、算法难点
用栈存储迷宫，模拟走迷宫过程并将其可视化。
三、解决思路及算法
	在迷宫中求出从入口到出口的路径。经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径，就是栈。
假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置"可通"，则纳入"当前路径"，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。
	我们首先定义栈，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述，然后用二维数组存储迷宫，m1代表墙，flag是标志域
迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 
	savefile函数是输入迷宫并将其存储于一个文件，以便日后调用该迷宫。
inread函数是从文件中读入迷宫，并给将文件中的迷宫加上围墙以便于后面的走迷宫。
zumigong函数:首先输入迷宫入口和出口。从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路
利用递归的方式进行求解。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点，。在此过程中，将每一个经过的位置放入栈中，同时要根据判别方向改变行走的方向。
	print1函数将以坐标形式输出迷宫路径并保存到文件中，在此过程中逐次pop出栈顶元素并将横纵坐标分别记录到相应数组中，最后逐次输出。
	print2函数是以形象的矩阵形式输出迷宫路径，算法同print1函数。

四、测试样例




算法时间复杂度与空间复杂度的分析：
    时间复杂度：由于每个点都可能被放入探索路径中探索，因为会将探索过的点置为-1，所以每个点最多一次：O(mn)
空间复杂度：由于该算法中需要用到栈，所以空间复杂度为：O（mn）
五、反思启发
迷宫问题的难点在于记录路径，在走不通的情况下需要返回，若单单这么做则程序会反复试探一条路进入死循环，所以关键在于对于已经试探过的点我们要予以标记，以确保下次不重复探索该条路径，需要用两个栈每一个记录探索的路径，一个记录行走的路径。最后要注意在探索完路径后需要恢复迷宫的初始状态。
六、代码附录
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
	int mg[200];
	int top;
}seqstack;
typedef struct migong
{
	int m1;//存放墙
	int flag;//标志域
}smaze[20][20];
void inista(seqstack &s)
{
	s.top=-1;
}
int empty(seqstack &s)//判栈空
{
	if(s.top==-1)
		return 0;
	else	return 1;
}
void pop(seqstack &s,int &x1)//出栈
{
	if(s.top==-1)
		return	;
	x1=s.mg[s.top];
	s.top--;
}
void push(seqstack &s,int y1,int x1)//入栈
{
	if(s.top==20)
		return ;
	s.top++;
	s.mg[s.top]=y1;
	s.top++;
	s.mg[s.top]=x1;
}
void inread(smaze &maze,int m,int n)
{
    char name[20];
    int i,j;
    printf("输入存放迷宫的文件名\n");
    scanf("%s",name);
    FILE *fp=fopen(name,"rt");
    if(fp==NULL)
    {
        printf("\n打开文件%s失败\n");
        exit(1);
    }
    for(i=1;i<m+1;i++)
    for(j=1;j<n+1;j++)
    {
        fscanf(fp,"%d ",&maze[i][j].m1);
        if(maze[i][j].m1==0)
        maze[i][j].flag=0;
        else
        maze[i][j].flag=1;
    }
    fclose(fp);
    for(i=0;i<=m+1;i++)
    {
        maze[i][0].m1=1;
        maze[i][0].flag=1;//加两堵列墙
        maze[i][n+1].m1=1;
        maze[i][n+1].flag=1;
    }
    for(j=0;j<=n+1;j++)    //加两堵行墙
    {
        maze[0][j].m1=1;
        maze[m+1][j].m1=1;
        maze[0][j].flag=1;
        maze[m+1][j].flag=1;
    }
    for(i=0;i<=m+1;i++)
    {
        for(j=0;j<=n+1;j++)
        {
            if(maze[i][j].m1==1)
            printf("■");
            else
            printf("□");
        }
    printf("\n");
    }
}
void zumigong(seqstack &stack,smaze &maze,int &m,int &n)//走迷宫
{
	int i,j,cout;
	int x1,a,b,y1,x,y,x2,y2;
	printf("输入入口的横纵坐标，空格隔开\n");
	scanf("%d %d",&x,&y);
	printf("输入出口的横纵坐标，空格隔开\n");
	scanf("%d %d",&x2,&y2);
	for(i=0;i<=m+1;i++)
	{
		for(j=0;j<=n+1;j++)
		{
			if(maze[i][j].m1==1)
				printf("■");
			else
				printf("□");
		}
		printf("\n");
	}
	x1=x;
	y1=y;
	if(maze[x1][y1].m1==1)
	{
		printf("此路不通：\n");
		return  ;
	}
	if(maze[x2][y2].m1==1)
	printf("入口为墙。请重新输入\n");
	else
		while(x1!=x2||y1!=y2)
		{
			if(maze[x1][y1+1].m1==0&&maze[x1][y1+1].flag==0)
				cout=0;
			else if(maze[x1+1][y1].m1==0&&maze[x1+1][y1].flag==0)
				cout=1;
			else if(maze[x1-1][y1].m1==0&&maze[x1-1][y1].flag==0)
				cout=2;
			else if(maze[x1][y1-1].m1==0&&maze[x1][y1-1].flag==0)
				cout=3;
			else cout=4;
			switch(cout)
			{
				case 0:
					a=x1;
					b=y1;
					maze[x1][y1].flag=1;
					y1=y1+1;
					push(stack,b,a);//列先入
					break;
				case 1:
					a=x1;
					b=y1;
					maze[x1][y1].flag=1;
					x1=x1+1;
					push(stack,b,a);
					break;
				case 2:
					a=x1;
					b=y1;
					maze[x1][y1].flag=1;
					x1=x1-1;
					push(stack,b,a);
					break;
				case 3:
					a=x1;
					b=y1;
					maze[x1][y1].flag=1;
					y1=y1-1;
					push(stack,b,a);
					break;
				case 4:
					maze[x1][y1].flag=1;
					if(empty(stack)!=0)
					{
						pop(stack,x1);
						pop(stack,y1);
						break;
					}
					else
					{
						printf("此路没有通路：\n");
						return ;
					}
			}
		}
	push(stack,y2,x2);
}
void print1(seqstack stack)
{
    char name[20];
    int s1[20],s2[20],i=0,j=0,n=0;
    while(stack.top!=-1)
    {
        n++;
        pop(stack,s1[i]);
        pop(stack,s2[i]);
        i++;    j++;
    }
	printf("以坐标形式输出迷宫路径\n");
	printf("迷宫路径为:\n");
	for(i=n-1;i>=1;i--)
	printf("<%d,%d> → ",s1[i],s2[i]);
	printf("<%d %d>\n",s1[0],s2[0]);
	printf("请输入要保存路径的文件名\n");
	scanf("%s",name);
	FILE *fp=fopen(name,"wb");
	if(fp==NULL)
    {
        printf("\n打开文件%s失败\n",name);
        exit(1);
    }
    fprintf(fp,"迷宫路径：\n");
    for(i=n-1;i>=0;i--)
    fprintf(fp,"<%d,%d>  ",s1[i],s2[i]);
    fclose(fp);
    printf("已成功保存于%s文件中",name);
}
void print2(seqstack &stack,smaze &maze,int &m,int &n)
{
    int s1[20],s2[20],i=0,j=0,n1,n2;
    while(stack.top!=-1)
    {
        pop(stack,s1[i]);
        pop(stack,s2[j]);
        n1=s1[i];
        n2=s2[j];
        maze[n1][n2].flag=2;
        i++;
        j++;
    }
    printf("以形象的矩阵形式输出迷宫路径 ·表示走过的痕迹 ⊙表示迷宫路径\n");
    printf("如下所示\n");
    for(i=0;i<=m+1;i++)
    {
        for(j=0;j<=n+1;j++)
        {
            if(maze[i][j].m1==1)printf("■");
            if(maze[i][j].m1==0&&maze[i][j].flag==0)
            printf("□");
            if(maze[i][j].m1==0&&maze[i][j].flag==1)
            printf("·");
            if(maze[i][j].m1==0&&maze[i][j].flag==2)
            printf("⊙");
        }
        printf("\n");
    }
}
void savefile(smaze maze,int &m,int &n)
{
    int i,j;
    char name[20];
    printf("输入迷宫：\n");
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
    {
        scanf("%d",&maze[i][j].m1);
        if(maze[i][j].m1==1)
        maze[i][j].flag=1;
        else
        maze[i][j].flag=0;
    }
    for(i=0;i<=m+1;i++)
    {
        maze[i][0].m1=1;
        maze[i][0].flag=1;//加两堵列墙
        maze[i][n+1].m1=1;
        maze[i][n+1].flag=1;
    }
    for(j=0;j<=n+1;j++)    //加两堵行墙
    {
        maze[0][j].flag=1;
        maze[m+1][j].flag=1;
        maze[0][j].m1=1;
        maze[m+1][j].m1=1;
    }
    printf("请输入保存的文件名：\n");
    scanf("%s",name);
    FILE *fp=fopen(name,"wt");
    if(fp==NULL)
    {
        printf("\n打开文件%s失败\n",name);
        exit(1);
    }
    for(i=0;i<=m+1;i++)
    {
        for(j=0;j<=n+1;j++)
        {
            if(maze[i][j].m1==1)
                printf("■");
            else
                printf("□");
        }
        printf("\n");
    }
    fprintf(fp,"迷宫路径：\n");
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        fprintf(fp,"%d ",maze[i][j].m1);
        fputc('\n',fp);
    }
    fclose(fp);
}
int print()
{
    int i;
    printf("输入执行的功能序号\n");
    scanf("%d",&i);
    return i;
}
int main()
{
    seqstack stack;
    inista(stack);
    int m,n,f;
    smaze maze;
    printf("1、从键盘输入迷宫\n");
    printf("2、从文件读出迷宫\n");
    printf("3、走迷宫\n");
    printf("4、以坐标形式输出迷宫路径\n");
    printf("5、以形象的矩阵形式表示路径\n");
    printf("0、退出走迷宫系统\n");
    while(f!=0)
    {
        f=print();
        switch(f)
        {
            case 0:
                printf("您已退出系统期待你的下次访问\n");
                break;
            case 1:
                printf("输入迷宫的行和列:\n");
                scanf("%d %d",&m,&n);
                savefile(maze,m,n);
                break;
            case 2:
                printf("输入迷宫的行和列:\n");
                scanf("%d %d",&m,&n);
                inread(maze,m,n);
                break;
            case 3:
                zumigong(stack,maze,m,n/*,s1,s2*/);
                break;
            case 4:
                print1(stack);
                break;
            case 5:
                print2(stack,maze,m,n);
                break;
            case 6:;
        }
    }
    return 0;
}