柚子快报激活码778899分享：算法 数塔问题（动态规划法）

http://yzkb.51969.com/

题目

利用动态规划法求解高度为n的数塔，塔中的元素为0-20以内的随机数。

代码

#include

#include

#include

int a = 0;

int* num=&a;

int DataTorwer(int d[100][100], int n){

int i, j, maxAdd[100][100] = { 0 }, path[100][100] = { 0 };

for (j = 0; j < n; j++) //初始子问题

maxAdd[n - 1][j] = d[n - 1][j];

for (i = n - 2; i >= 0; i--) //进行第i层的决策

for (j = 0; j <= i; j++) { //只填写下三角

a++; //基本语句执行次数

if (maxAdd[i + 1][j] > maxAdd[i + 1][j + 1]){

maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j];

path[i][j] = j; //本次决策选择下标j的元素

}

else{

maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j + 1];

path[i][j] = j + 1; //本次决策选择下标j+1的元素

}

}

printf("路径为：%d", d[0][0]); //输出顶层数字

j = path[0][0]; //计算maxAdd[0][0]的选择

for (i = 1; i < n; i++)

{

printf("-->%d", d[i][j]);

j = path[i][j]; //计算maxAdd[i][j]的选择

}

return maxAdd[0][0]; //返回最大数值和

}

int main()

{

int n=0, d[100][100] = { 0 };

printf("问题规模为：");

scanf_s("%d", &n);

srand((int)time(0)); //产生随机数种子

for (int i = 0; i < n; i++) { //给数组元素随机赋值

for (int j = 0; j < i+1; j++) {

d[i][j] = rand() % 20;

printf("%3d ", d[i][j]);

}

printf("\n");

}

printf("\n");

printf("最大数值和是：%d\n", DataTorwer(d, n));

printf("基本语句频度为：%d", *num);

return 0;

}

运行结果

柚子快报激活码778899分享：算法 数塔问题（动态规划法）

http://yzkb.51969.com/

推荐链接

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。