《数字三角形-数字塔-C语言实现》由会员分享，可在线阅读，更多相关《数字三角形-数字塔-C语言实现（2页珍藏版）》请在金锄头文库上搜索。
1、/*数字塔-数字三角形问题-动态规划算法练习功能：给定一个由N行数字组成的数字三角形，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大，以及路径。作者：猪来投胎时间：2012-7-10*/#include#define N 4int main()int ANN,BNN=0,CNN=0,DN;/B存放数据，C存放状态，D存放路径int i,j;int M,k;/输入数据for(i = 0;iN;i+)for(j = 0;j=i;j+)scanf(%d,&Aij);/数字塔数据处理B00=A00;C00=0;for(i = 1;iN;i+)Bi0 = Bi-10+Ai0;Ci0 = 1
2、;for(i = 1;iN;i+)Bii = Bi-1i-1+Aii;Cii = 0;for(i = 2;iN;i+)for(j = 1;jBi-1j)Bij = Bi-1j-1+Aij;Cij =0;else Bij = Bi-1j+Aij;Cij = 1;/输出 数据表 和 状态表printf(B表的结果:n);for(i = 0;iN;i+)for(j = 0;j=i;j+)printf(%dt,Bij);printf(n);printf(C表的结果:n);for(i = 0;iN;i+)for(j = 0;j=i;j+)printf(%dt,Cij);printf(n);/找出最大值 M = BN-10;for(j = 1;jM)M = BN-1j; k = j;printf(最大的数是:%d,下标是%d,%dn,M,N-1,k);/根据状态表C，找路径DN-1 = AN-1k; for(i=N-1;i0;)if(Cik=0) i-;Di = Ai-k;/对角线else i-;Di = Aik; /打印路径printf(D的结果:n);for(i = 0;iN;i+)printf(%dt,Di);return 0;
