数字三角问题

1、算法设计与分析上 机 实 验 报 告专 业软件工程班 级软件1101学 号04113033学生姓名岳彦利完成日期2013-11-71. 上机题目及实验环境1.1上机题目：数字三角形问题1.2实验环境：CPU：英特尔 第二代酷睿i3-2330M 2.2GHz 双核内存：4G操作系统：windows 7软件平台：ubuntu2. 算法设计与分析小1）根据题意找出最优解的性质，并刻画出其结构特性。 2）.以自底向上的方式计算出最优值。 3）.根据计算最优值时得到的信息，构造最优解。 4）.从倒数第二an-20 开始，将自己与下一行同列的数组相加在和自己与下一行下一列的数相加的结果比较，将大的存放在自

2、己中。 5）.找到最大和之后，又从上往下找到组成这条最大和的路径。3. 核心代码 void maxsum(int (*a)max_num+10,int n)int i,j,max,t;int bn;FILE *fp1;for(i=n-1;i>=1;i-)/从倒数第二层向上求最大和for(j=1;j<=i;j+)if(aij+ai+1j)<(aij+ai+1j+1)aij=(aij+ai+1j+1);elseaij=(aij+ai+1j);if(a21<a22)/由最大和找第二层的路径t=2;max=a22;b1=a11-a22;elset=1;max=a21;b1=a1

3、1-a21;for(i=3;i<=n;i+)从第三层开始找最大和的路径知道第n层if(ait<ait+1)t=t+1;bi-1=max-ait;max=ait;elsebi-1=max-ait;max=ait;bn=ait;printf("路径：n");for(i=1;i<=n;i+)printf("%d ",bi);fp1=fopen("output.txt","wt"); if(fp1=NULL) printf("cannot open!"); exit(0); fprin

4、tf(fp1,"%d",a11);printf("noutput.txt:n");fp1=fopen("output.txt","r"); if(fp1=NULL) printf("cannot open!"); exit(0); / for(i=0;!feof(fp1);i+)/printf("");fscanf(fp1,"%d",&a11);printf("%dn",a11);4. 运行与调试 图一.写程序时遇到的问题 （路

5、径出错） 图二.修改后的正确结果 图三. 另一组数组测试 5. 结果分析和小结如图一，在写路径时最后一个数输出结果过错误，经过调试 ，发现路径循环是到倒数第二行为止的，经过修改输出正确结果如图二。如图二，第一行的数代表行数，从第二行开始想最后一行找一条和最大的路径，如图二。如图三， 另一组测试结果。（2）本次上机实验的收获、心得体会。这次的上机实验，使我对动态规划法有了更进一步的认识，编程的时候也有了更多的思路， 在编程之前一定把思路清晰，这样写的时候就比较轻松了。解决问题的时候，可以将带求解的问题分为若干子问题求解，保存子问题的结果，遇到下一个相同的子问题直接调用就可以了。可以大大节省时间，

6、从而更好的计算出结果，对找路径也有了另一种视野。附录（C/C+源代码）#include<stdio.h>#include<stdlib.h>#include<math.h>#include<time.h>#define max_num 100int amax_num+10max_num+10;void maxsum(int (*a)max_num+10,int n)int i,j,max,t;int bn;FILE *fp1;for(i=n-1;i>=1;i-)/从倒数第二层向上求最大和for(j=1;j<=i;j+)if(aij+a

7、i+1j)<(aij+ai+1j+1)aij=(aij+ai+1j+1);elseaij=(aij+ai+1j);if(a21<a22)/由最大和找第二层的路径t=2;max=a22;b1=a11-a22;elset=1;max=a21;b1=a11-a21;for(i=3;i<=n;i+)从第三层开始找最大和的路径知道第n层if(ait<ait+1)t=t+1;bi-1=max-ait;max=ait;elsebi-1=max-ait;max=ait;bn=ait;printf("路径：n");for(i=1;i<=n;i+)printf(&

8、quot;%d ",bi);fp1=fopen("output.txt","wt"); if(fp1=NULL) printf("cannot open!"); exit(0); fprintf(fp1,"%d",a11);printf("noutput.txt:n");fp1=fopen("output.txt","r"); if(fp1=NULL) printf("cannot open!"); exit(0); / fo

9、r(i=0;!feof(fp1);i+)/printf("");fscanf(fp1,"%d",&a11);printf("%dn",a11);main()int i,j;int n;FILE *fp;printf("input.txt:n");fp=fopen("input.txt","r");if(fp=NULL)printf("cannot open!");exit(0);fscanf(fp,"%d",&n);printf("%dn",n);for(i=1;i<=n;i+)/输出成到三角形式for(j=1;j<=i;j+) f