数塔路径 算法
从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。
这道题如果用枚举法，在数塔层数稍大的情况下则需要列举出的路径条数将是一个非常庞大的数目。
如果用贪心法又往往得不到最优解。
在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决
于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的
道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层
时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层
递进，最后得到最大值。
实际求解时应掌握其编程的一般规律，通常需要哪几个关键数组来存储变化过程这一点非常重要。
数塔问题的样例程序如下：
数为64！
给你一个代码，这个代码可以实现最多31个盘子的移动，
再多就超过数组存储上限了。
#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.txt中有以下内容，其中第一行表示三角行的行数。
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
请编一程序，计算从顶至底某处的一条路径，使该路径经过的数字总和最大，要求每一步只能沿左斜线或右斜线向下走。(最长路径问题)
分析:该题相当于路径的求权问题.分析题意可知,对于三角形中任何一个不在最底行的结点M[i][j],它的下一步有且只有两条路径:M[i+1][j]与M[i+1][j+1].用一个数组last[]保存目前已经走过的权重最大的路径,用max保存其权值,用数组path[]保存当前刚走过的路径.这样,只需从左至右用递归的方法遍历该三角形,最终的last[]即为所求的路径.
下面的程序已经编译通过了，格式有点乱，自己改改啰。
#include <stdio.h>
#include <stdlib.h>
int b[2]={0,1},m;
int path[100],max=0,a[100][100],last[100];
void go1(int i,int j)
{int y,k,l;
path[i]=a[i][j];
for (k=0;k<2;k++)
{y=j+b[k];
if (i<m-1)
go1(i+1,y);
else
{int s=0;
for(l=0;l<m;l++)
s+=path[l];
if(s>max)
{max=s;
for(l=0;l<m;l++)
last[l]=path[l];
}
}
}
}
int main()
{FILE *fp;
int i,j;
system("cls");
fp=fopen("2.txt","r");/*假定文件位置在当前目录下*/
if(fp==NULL)
{printf("不能打开2.txt文件!");
exit(1);
}
fscanf(fp,"%d",&m);
for(i=0;i<m;i++)
for(j=0;j<=i;j++)
fscanf(fp,"%d",&a[i][j]);
go1(0,0);
for(i=0;i<m;i++)
printf("%3d ",last[i]);
printf("\nmax=%d\n",max);
system("pause");
return 0;
}
国语都说不好，真同情你。
