六盘山-班主任管理经验

数字棋盘
在n*n的数字棋盘中，每个方格有一个数字成本C[i][j] ,求从最后一行开始到
第一行的最短路径（所有路过的成本方格和最小），假定每次只能允许向右对角，左对角，垂直移动。
算法的递推式：
Q[i][j]＝
C[n][j] i＝n；
+∞j<1或j>n；
Min{Q[i+1][j-1]、Q[i+1][j]、Q[i+1][j+1]}+C[i][j] other。
其中Q[i][j]表示从最后一行开始走到[i][j]位置的最小成本。
算法分析：
矩阵链相乘的时间复杂度是O(n2)，算法所需要的工作空间取决于所需要的< br>三角数组的大小，也就是其空间复杂度是O(n2)。
算法问题：
在C++环境中如何实现二维数组的形参带入函数中计算。
算法实现：
#include
#include
#include
#include
#include
int q[100][100];
1 3

int p[100][100];
int c[100][100];
void Printpath(int i,int j,int n){int k;
int po=n-1;
printf(
printf(
if(i==po){k=j+p[i][j];
printf(
int m;
int n;
int m1;
printf(请输入数字棋盘的行列数:

scanf(
cout << 请输入数字棋盘矩阵:
n
for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin >> c[i][j];}}
for(int d=1;d<=n;d++)
q[n][d]=c[n][d];
for(int i2=1;i2<=n;i2++){q[i2][0]=999;
q[i2][n+1]=999;}for(int i1=n-1;i1>=1;i1--){for(int j1=1;j1<=n;j1++){if(q[i 1+1][j1-
1] 2 3

p[i1][j1]=-1; }}else
{else { m1=q[i1+1][j1+1]; p[i1][j1]=1; }
if(q[i1+1][j1]{ m1=q[i1+1][j1+1]; p[i1][j1]=1;}}q[i1][j1]=m1+c[i1][j1];}}
m=q[1][1];
k=1;
for(int j=2;j<=n;j++){if(q[1][j]k=j;}}
printf(该数字棋盘从最上行到最下行的的路径是：
n
Printpath(1,k,n);
cout <<该数字棋盘的最小路径值为:

3 3