frog.cpp

青蛙跳河

//***********************************************************************
//*程序名：  frog.cpp                                                   *
//*作者：    侯俊飞、谭祖                                               *
//*编制时间：2008.6.3                                                   *
//*主要功能：计算青蛙过河问题                                           *
//*问题描述：一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，*
//*          面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容  *
//*          得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青 *
//*          蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在  *
//*          左岸的石柱L上，当然是一个落一个，小的落在大的上面。不允许  *
//*          大的在小的上面。在小溪中有s个石柱，有y片荷叶，规定溪中的柱 *
//*          子上允许一只青蛙落脚，如有多只同样要求一个落一个，大的在下 *
//*          ，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。 *
//*          对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一 *
//*          个落一个，小的在上，大的在下。当青蛙从左岸的L上跳走后就不  *
//*          允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中 *
//*          石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有s根石柱 *
//*          和y片荷叶的情况下，最多能跳过多少只青蛙？中石柱跳至右岸R上 *
//*          的青蛙也不允许再离开。问在已知溪中有s根石柱和y片荷叶的情况 *
//*          下，最多能跳过多少只青蛙？                                 *
//*          程序以0号柱表示R柱，ss+1表示L柱                            *
//***********************************************************************
#include<iostream.h>
#include<iomanip.h>
#include<fstream.h>
#include<stdlib.h>
class frog
{
public:
	int ss;//石柱数
	int yy;//荷叶数
	int nn;//可通过的最大青蛙数
	int *y;//存储荷叶上青蛙编号
	int **s;//存储石柱上的青蛙编号
	ofstream outs;
	frog();
	~frog();
	int t;//递归次数
	void wait();//数据过大时等待
	int jump(int t,int z);//计算可通过青蛙的数目
	void input();//输入
	void output();//输出数目
	void jmp(int l,int m,int r,int n);
	//显示整个过程.n只青蛙从l号石柱跳到r号石柱,并借助个水中的m个石柱
};
void frog::wait()
{
	int i=t;
	system("cls");
	cout<<"                青蛙过河"<<endl;
	cout<<"请输入石柱数:"<<ss<<endl;
	cout<<"请输入荷叶数:"<<yy<<endl;
	cout<<endl;
	if(i!=0)
	{
	    i=i%45;
	    if(i<20)
             i=3;
	    else if(i<35)
		     i=6;
	    else
		     i=9;
	    cout<<"    数据较大请等待";	
	    for(i;i>0;i--)
		     cout<<'.';
	    cout<<endl;
	}
};
int frog::jump(int t,int z)
//jump(t,z)=2*jump(t-1,z)
//jump(0,z)=z+1
{
	int k=0;
	if(t==0)
		k=z+1;
	else
		k=2*jump(t-1,z);
	return(k);
};
void frog::jmp(int l,int m,int r,int n)
//递归模拟整个过程
{
	int j=1;
	if(m==0)
	{
		int i=nn;
		while(s[l][i]==0)
			i--;
	    j=1;		
		for(int x=n;x>1;x--)
		{
			y[j]=s[l][i];
			s[l][i]=0;
			outs<<setw(6)<<y[j]<<" 号青蛙从";
			outs<<setw(2)<<l<<"柱跳到荷叶"<<setw(2)<<j<<endl;
			i--;
			j++;
		}
		j=nn;
		while(s[r][j]==0)
		{
			if(j==1)
				break;
			j--;
		}
		if(j!=1)
			j++;
		s[r][j]=s[l][i];
		outs<<setw(6)<<s[l][i]<<" 号青蛙从";
		outs<<setw(2)<<l<<"柱跳到柱"<<setw(4)<<r<<endl;
		s[l][i]=0;
		for(i=n-1;i>0;i--)
		{
			s[r][++j]=y[i];
			outs<<setw(6)<<y[i]<<" 号青蛙从";
			outs<<setw(2)<<i<<"荷叶跳到柱"<<setw(2)<<r<<endl;
		}
	}
	else
	{
		j=l-1;
		while(s[j][1]!=0||j==r)
			j--;
		jmp(l,m-1,j,n/2);
		jmp(l,m-1,r,n/2);
		jmp(j,m-1,r,n/2);
		wait();
		t++;
	}
};
frog::frog()
{
	ss=0;
	yy=0;
	nn=0;
	t=1;
	cout<<"                青蛙过河"<<endl;
	outs.open("青蛙过河.txt");
	if(!outs)
	{
		cout<<"青蛙过河.txt不能打开！frog"<<endl;
		return;
	}
    outs<<"                青蛙过河"<<endl;
	input();
	outs<<"石柱数："<<setw(2)<<ss<<endl;
	outs<<"荷叶数："<<setw(2)<<yy<<endl;
	output();
	y=new int[yy+1];//动态分配数组空间         
	s=new int*[ss+2];
	for(int w=0;w<ss+2;w++)
		s[w]=new int[nn+1];
    for(int g=0;g<ss+2;g++)//初始化2维数组
		for(w=0;w<=nn;w++)
			s[g][w]=0;
	for(w=1;w<=nn;w++)
		s[ss+1][w]=nn-w+1;
	outs<<endl;
	outs<<"过河过程为:"<<endl;
	outs<<endl;
};
frog::~frog()
{
	for(int g=0;g<ss+2;g++)//释放数组空间
		delete []s[g];
	delete s;
	delete y;
};
void frog::input()
{
	cout<<"请输入石柱数:";
	cin>>ss;
	cout<<"请输入荷叶数:";
	cin>>yy;
	nn=jump(ss,yy);
};
void frog::output()
{
	outs<<endl;
	outs<<"       可通过的青蛙数目为："<<nn<<endl;
	outs<<endl;
};
void main()
{
    frog f;
	int ss=f.ss;
	int n=f.nn;
	f.jmp(ss+1,ss,0,n);
	f.outs.close();
	f.t=0;
	f.wait();
	cout<<"请打开文件“青蛙过河.txt”查看结果。"<<endl<<endl;
	cout<<"     感谢使用！热忱为你服务！"<<endl<<endl;
}