再多就超过数组存储上限了。
#include
<iostream>慧世野
using
namespace
std
//圆盘的个数最多为64
const
int
MAX
=
64
//用来表示每根柱子的信息
struct
st{
int
s[MAX]
//柱子上的圆盘存储情况
int
top
//栈顶，用来最上面的圆盘
char
name
//柱子的名字，可以是A，B，C中的一个
int
Top()//取栈顶元素
{
return
s[top]
}
int
Pop()//出栈
{
return
s[top--]
}
void
Push(int
x)//入栈
{
s[++top]
=
x
}
}
long
Pow(int
x,
int
y)
//计算x^y
void
Creat(st
ta[],
int
n)
//给结构数组设置初值
void
Hannuota(st
ta[],
long
max)
//移动汉诺塔的主要函数
int
main(void)
{
int
n
cin
>>
n
//输入圆盘的个数
st
ta[3]
//三根柱子的信息用结构数组存储
Creat(ta,
n)
//给结返嫌构数组设置初值
long
max
=
Pow(2,
n)
-
1//动的次数应等于2^n
-
1
Hannuota(ta,
max)//移动汉诺塔的主要函数
system("pause")
return
0
}
void
Creat(st
ta[],
int
n)
{
int
i
ta[0].name
=
'A'
ta[0].top
=
n-1
//把所有的圆盘按从大到小的顺序放在柱子A上
for
(i=0
i<n
i++)
ta[0].s[i]
=
n
-
i
//柱子B，C上开始没有没有圆盘
ta[1].top
=
ta[2].top
=
0
for
(i=0
i<n
i++)
ta[1].s[i]
=
ta[2].s[i]
=
0
//若n为偶数，按顺时针方向依次摆放
A
B
C
if
(n%2
==
0)
{
ta[1].name
=
'B'
ta[2].name
=
'C'
}
else
//若n为奇数，按顺时针方向依次摆放
A
C
B
{
ta[1].name
=
'C'
ta[2].name
=
'B'
}
}
long
Pow(int
x,
int
y)
{
long
sum
=
1
for
(int
i=0
i<y
i++)
sum
*=
x
return
sum
}
void
Hannuota(st
ta[],
long
max)
{
int
k
=
0
//累计移动的次数
int
i
=
0
int
ch
while
(k
<
max)
{
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch
=
ta[i%3].Pop()
ta[(i+1)%3].Push(ch)
cout
<<
++k
<<
":
"
<<
"Move
disk
"
<<
ch
<<
"
from
"
<<
ta[i%3].name
<<
"
to
"
<<
ta[(i+1)%3].name
<<
endl
i++
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
if
(k
<
max)
{
//把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
if
(ta[(i+1)%3].Top()
==
0
||
ta[(i-1)%3].Top()
>
0
&&
ta[(i+1)%3].Top()
>
ta[(i-1)%3].Top())
{
ch
=
ta[(i-1)%3].Pop()
ta[(i+1)%3].Push(ch)
cout
<<
++k
<<
":
"
<<
"Move
disk
"
<<
ch
<<
"
from
"
<<
ta[(i-1)%3].name
<<
"
to
"
<<
ta[(i+1)%3].name
<<
endl
}
else
{
ch
=
ta[(i+1)%3].Pop()
ta[(i-1)%3].Push(ch)
cout
<<
++k
<<
":
"
<<
"Move
disk
"
<<
ch
<<
"
from
"
<前喊<
ta[(i+1)%3].name
<<
"
to
"
<<
ta[(i-1)%3].name
<<
endl
}
}
}
}
从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。这道题如果用枚举法，在数塔层数稍大的情况下则需要列举出的路段差径条数将是一个非常庞大的数目。
如果用贪心法又往往得不到最优解。
在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决
于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的
道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到运燃明倒数第二层
时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从旁告底层开始，层层
递进，最后得到最大值。
实际求解时应掌握其编程的一般规律，通常需要哪几个关键数组来存储变化过程这一点非常重要。
数塔问题的样例程序如下：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）