62,074
社区成员
发帖
与我相关
我的任务
分享准备去长期潜伏，最后和大家探讨一下几个经典的回朔算法
前些天看到了有人发布有关算法的贴子，说来惭愧，本人几乎忘记了如何做回溯了，花了很长时间，不段在草稿纸上模拟，上天不负有心人，最终还是做出了以前做过的几个经典案例，与大家分享一下。
下载地址
下载地址
/// <summary>
/// 获取数列
/// </summary>
protected void getNumList()
{
int[] ary = new int[] { 0, 1, 2, 2 };
ary.CopyTo(ary, 0);
int s = 3;
string num = "1234";
char[] ary_num = num.ToCharArray();
int n = ary_num.Length - 1;
int cout = 0;
string txt = string.Empty;
while (s >= 0)
{
loop: if (ary[s] >= n)
{
ary[s] = -1;
s = s - 1;
}
else
{
ary[s] = ary[s] + 1;
for (int i = s - 1; i >= 0; i--)
{
if (ary[s] == ary[i])
{
goto loop;
}
}
if (s == 3 && !txt.Contains(string.Format("{0}{1}{2}{3}", ary_num[ary[0]], ary_num[ary[1]], ary_num[ary[2]], ary_num[ary[3]])))
{
cout++;
txt = txt + "," + string.Format("{0}{1}{2}{3}", ary_num[ary[0]], ary_num[ary[1]], ary_num[ary[2]], ary_num[ary[3]]);
Response.Write(string.Format("{0}{1}{2}{3}<br/>", ary_num[ary[0]], ary_num[ary[1]], ary_num[ary[2]], ary_num[ary[3]]));
}
if (s < 3)
{
s = s + 1;
}
}
}
Response.Write(string.Format("{1}总数为：{0} 个数列", cout, num));
}
/// <summary>
/// 走迷宫
/// </summary>
protected void findPath()
{
//初使化地图
int[,] ary_map = new int[8, 12]
{
{ 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1 },
{ 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1 },
{ 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 },
{ 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0 },
{ 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
{ 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0 }
};
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 12; j++)
{
Response.Write(ary_map[i, j]);
}
Response.Write("<br/>");
}
//开始询址
int s = 0;//记录第几步
int[] st = new int[8 * 12];//记录每步的方向y - 1(上),x + 1(左),y - 1(下),x - 1(右)
int x = 0;//第几步的x
int y = 0;//第几步的y
while (s >= 0)
{
//判断方向
switch (st[s])
{
case 0:
y = y - 1;//向上走
break;
case 1:
x = x + 1;//向左走
break;
case 2:
y = y + 1;//向下走
break;
case 3:
x = x - 1;//向右走
break;
}
//如果碰壁就往回走
if (st[s] > 4 || x < 0 || y < 0 || x >= 12 || y >= 8 || ary_map[y, x] == 1 || ary_map[y, x] == -1)
{
Loop://判断方向，回退到上一步
switch (st[s])
{
case 0:
y = y + 1;
break;
case 1:
x = x - 1;
break;
case 2:
y = y - 1;
break;
case 3:
x = x + 1;
break;
}
//换一个方向
st[s] = st[s] + 1;
//所有方向都走不通就返回上一步
if (st[s] > 3)
{
st[s] = 0;
s = s - 1;
if (s > 0)
goto Loop;
}
}
else
{
//将走过的路径设为-1
ary_map[y, x] = -1;
//下一步
s = s + 1;
if (x == 11 && y == 7)
{
break;
}
}
}
//询址结束
//输出路径
x = 0;
y = 0;
string txt=string.Empty;
for (int i = 0; i < s; i++)
{
switch (st[i])
{
case 0:
y = y - 1;
break;
case 1:
x = x + 1;
break;
case 2:
y = y + 1;
break;
case 3:
x = x - 1;
break;
}
if (st[i] <= 0)
{
break;
}
else
{
txt = (txt == "" ? "" : txt + ",") + string.Format("(x:{0},y:{1})", x, y);
}
}
Response.Write(string.Format("<p>路径为:(x:0,y:0),{0}</p>", txt));
}
...全文
请发表友善的回复…
发表回复
lw_881020 2012-04-16
- 打赏
- 举报
这个神马？
SK_Aqi 2011-07-20
- 打赏
- 举报
mark研究
牧心 2011-07-11
- 打赏
- 举报
厉害 mark
SolarJupiter 2011-07-07
- 打赏
- 举报
mark 仔细学习~
netaass123 2011-07-07
- 打赏
- 举报
顶。。。。。
南瓜 2011-07-07
- 打赏
- 举报
标记 学习
sergeant39225 2011-07-04
- 打赏
- 举报
楼主很强，学习一下，没看懂
yiyi6477 2011-07-04
- 打赏
- 举报
学习了 强
baoganghan 2011-07-04
- 打赏
- 举报
好东东，收藏了
Vincent_Hddddd 2011-07-04
- 打赏
- 举报
还没学过这个。
byshome 2011-07-04
- 打赏
- 举报
看到goto人就烦了，
mingl11 2011-07-04
- 打赏
- 举报
一般不用算法的飘过啊~~~
jpjiang4648 2011-07-04
- 打赏
- 举报
学习了
_为了部落 2011-07-04
- 打赏
- 举报
回溯的话用堆栈比较好处理吧。
Xiaoloveliuforever 2011-07-04
- 打赏
- 举报
楼主犀利
hg2980986 2011-07-03
- 打赏
- 举报
学习学习，多多指教
chuzhaowei 2011-07-02
- 打赏
- 举报
mark了慢慢看了
Angeleschen 2011-07-02
- 打赏
- 举报
学习了
shenyanm 2011-07-02
- 打赏
- 举报
需要耐心阅读分析
allen5200 2011-07-02
- 打赏
- 举报
这个要顶
加载更多回复（110）
