qingwaguohe.cpp

在河上有一座独木桥

/*在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
*/

/*青蛙过河问题*/

#include <iostream>
#include <vector>
using namespace std;

vector<int> stone;
int BridgeLong;
int MinJump,MaxJump;
int StoneNum;
int MinStoneNUM = -1;

/*读入数据*/
void Read()
{
	BridgeLong = 10;
	MinJump = 2;
	MaxJump = 3;
	StoneNum = 5;

	stone.push_back(2);
	stone.push_back(3);
	stone.push_back(5);
	stone.push_back(6);
	stone.push_back(7);

	return;
}
/*递归遍历所有过河方式，取得最小的数目*/
int through(int NowLength, int NowNum)
{
	int lengthBK,numBK;
	int iLp;
	int jLp;

	lengthBK = NowLength;
	numBK = NowNum;

	if(NowLength >= BridgeLong)
	{
		/*到达河对岸，如果踩到石子数比以前的小，则替换之*/
		if(MinStoneNUM == -1 || NowNum < MinStoneNUM)
		{
			MinStoneNUM = NowNum;
		}
		return 1;
	}

	for(iLp = MinJump; iLp <= MaxJump; iLp++)
	{
		NowLength = lengthBK;
		NowNum = numBK;
		
		NowLength += iLp;
		for(jLp = 0; jLp < StoneNum; jLp++)
		{
			if(stone[jLp] == NowLength)
			{
				/*踩到石子*/
				NowNum++;
				break;
			}
		}
		through(NowLength,NowNum);
	}
	return 1;
}

void main()
{
	int iLp,jLp,NowNum;
	Read();
	for(iLp = MinJump; iLp <= MaxJump; iLp++)
	{
		NowNum = 0;
		for(jLp = 0; jLp < StoneNum; jLp++)
		{
			if(stone[jLp] == iLp)
			{
				NowNum++;
				break;
			}
		}
		through(iLp,NowNum);
	}
	cout<<"踩到的最小石子数："<<MinStoneNUM<<endl;
	return;
}