矩阵连乘问题《算法分析与设计》(2)

printf (\请输入矩阵的个数（小于100）:\scanf (\

for (int i=0;i<=2*n-1;i++)//各矩阵的阶数的输入先存入数组q中接受检验 { }

for (i=1;i<=2*n-2;i++)//矩阵连乘条件的检验 { }

for (int j=1;j<=n-1;j++) { } if (flag!=0) {

p[0]=q[0]; p[n]=q[2*n-1];

matrixChain (p,m,s); printf (\式子如下:\\n\traceback(1,n,s); printf (\

printf (\最小数乘次数为%d\\n\

p[j]=q[2*j]; { }

flag=0; break; if (i%2==0) { } else { }

printf (\列************:\printf (\printf (\请输入A%d的行:\

scanf (\

if (i%2!=0&&q[i]!=q[i+1])

} else { } }

printf (\这%d个矩阵不能连乘!\\n\

- 5 -

实验结果：

一、输入正确的情况：

二、输入有误的情况：

- 6 -

六、编程体会

经过了几天的连续研究，终于小有收获，也渐渐理解了动态规划的基本思想，动态规划算法与分治法类似，其基本思想也是将待解问题分解成若干个子问题，先求解子问题，，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在分治法求解时，有些子问题被重复计算了多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。具体的动态规划算法是多种多样的，但它们具有相同的填表格式。

动态规划算法适用于解最优化问题。通常可以按以下步骤设计动态规划算法： （1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优值；

（3）以自底向上的方式计算出最优值；

（4）根据计算最优值时得到的信息，构造最优解。

虽然已经了解了动态规划算法的基本思想，而且也参考了书上的算法，但是实际的情况却并不是那么顺利，我按照书上编写程序之后，发现有很多逻辑错误，应该是编写环境不同，所以出现了一系列的问题，最后经过自己的多番研究发现了许多c语言有许多默认的规则：就拿数组来讲，在计算数组m和数组s时，虽然我们不用到下标为零的元素，所以我一开始定义用长度为N*N的m数组和s数组来分别存储矩阵的最小数乘次数和其对应的断开位置，但经过多次调试之后，发现总是在求m[*][N]和s[*][N]时就会出错，后来才知道c语言的默认规则：不管我们用不用数组的零下标元素，下标为零的元素都默认在该数组中，因此，必须把m和s数组的行列长度都必须加一才行， 经过这次程序设计之后，我懂得了一个道理，做程序设计，不仅要弄透解决这个问题的基本思想和算法，而且要注意编程过程中的一些细节性问题，例如一些特定编程环境的默认规则，而且还要要求我的逻辑思路一定要清晰，不然的话，很难发现自己先前所犯下的逻辑错误，这样就很容易造成事倍功半，效率低下。以上就是我这次的程序设计编程体会。

七、成绩评定

根据学习态度，任务完成质量（应用程序的难易程度、界面的友好性、程序的正确程度）和实验报告质量进行打分，满分100分。 项 目 成 员 学习态度 姓名、学号 组 长： 成员一： 成员二： 成员三： - 7 -

（25%） 任务完成质量 （50%） 实验报告质量 （25%） 合计

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库矩阵连乘问题《算法分析与设计》(2)在线全文阅读。