c++200971030102-11

系别 学号 课程名称 实验名称 计算机 计算机科学与技术（师范类） 姓 名 陈建峰 200971030102 课程类型 程序设计Ⅱ 专业基础 专业 09计师1班 实验日期 2010-11-25 学时数 4 班级 实验11 利用动态规划法编程解决求最优解问题(二) 一．实验目的 ❖ 深入理解和体会动态规划法编程解决问题的思想和基本概念。 ❖ 总结采用动态规划法设计算法的基本步骤和程序框架。 二．实验报告要求 (1)实验报告中按以上题号分别给出各程序规范的源程序清单，题目可略； (2)程序中的所有变量要加注释说明功能，主要语句也要加必要的注释； (3)每个程序之后，要如实记录程序的运行结果； (4)对实验中的难点和重点问题要进行总结。 三．实验内容与步骤 ❖ 理解并调试运行教材143页-144页插入乘号问题参考程序； 解：/*在一个数字串中插入若干个乘号使积最大*/ #include #include #define N 50 void main() { FILE *fp; /*fp为指向FILE结构的指针变量*/ char b[N]; int n,i,j,k,u,r,t[N],c[N][N]; long f[N][N],d; if((fp=fopen(\"input.txt\ /*以读写方式打开或建立一个文本文件input.txt*/ { printf(\"不能打开这个文件：\\n\"); exit(1); /*退出程序*/ } printf(\"请输入整数：\"); fprintf(fp,\"请输入整数：\\n\"); scanf(\"%s\ fprintf(fp,\"%s\\n\ for(n=0,i=0;b[i]!='\\0';i++) n++; printf(\"请输入插入的乘号个数r:\");

1

1125 fprintf(fp,\"请输入插入的乘号个数r:\\n\"); scanf(\"%d\ fprintf(fp,\"%d\\n\ rewind(fp); /*把文件fp的内部位置指针移向文件首*/ fclose(fp); /*关闭文件*/ if((fp=fopen(\"output.txt\ /*以读写方式打开或建立一个文本文件output.txt*/ { printf(\"不能打开这个文件：\\n\"); exit(1); /*退出程序*/ } printf(\"在整数%s中插入%d个乘号，使积最大：\\n\ fprintf(fp,\"在整数%s中插入%d个乘号，使积最大：\\n\ for(d=0,j=1;j<=n;j++) { d=d*10+b[j-1]-48; /*把b数组的一个字符转化位数值*/ f[j][0]=d; /*f[j][0]赋初值*/ } for(k=1;k<=r;k++) for(i=k+1;i<=n;i++) for(j=k;j=1;k--) t[k]=c[t[k+1]][k]; /*逆推出第k个乘号的位置t[k]*/ t[0]=0; t[r+1]=n; for(k=1;k<=r+1;k++) { for(u=t[k-1]+1;u<=t[k];u++) { printf(\"%c\ fprintf(fp,\"%c\ /*输出最优解*/ } if(k2

1125 printf(\"*\"); fprintf(fp,\"*\"); } } printf(\"=%d\\n\ /*输出最优值*/ fprintf(fp,\"=%d\\n\ rewind(fp); /*把文件output.txt的内部位置指针移向文件首*/ fclose(fp); /*关闭文件*/ } 程序运行结果为： ❖ 尝试编程求解教材167页第5题。

3

1125解：/*在一个数字串中插入若干个加号使和最小*/ #include #include #define N 50 void main() { FILE *fp; /*fp为指向FILE结构的指针变量*/ char b[N]; int n,i,j,k,u,r,t[N],c[N][N]; long f[N][N],d,min; if((fp=fopen(\"input.txt\ /*以读写方式打开或建立一个文本文件input.txt*/ { printf(\"不能打开这个文件：\\n\"); exit(1); /*退出程序*/ } printf(\"请输入整数：\"); fprintf(fp,\"请输入整数：\\n\"); scanf(\"%s\ fprintf(fp,\"%s\\n\ for(n=0,i=0;b[i]!='\\0';i++) n++; printf(\"请输入插入的加号个数r:\"); fprintf(fp,\"请输入插入的加号个数r:\\n\"); scanf(\"%d\ fprintf(fp,\"%d\\n\ rewind(fp); /*把文件fp的内部位置指针移向文件首*/ fclose(fp); /*关闭文件*/ if((fp=fopen(\"output.txt\ /*以读写方式打开或建立一个文本文件output.txt*/ { printf(\"不能打开这个文件：\\n\"); exit(1); /*退出程序*/ } printf(\"在整数%s中插入%d个加号，使和最小：\\n\ fprintf(fp,\"在整数%s中插入%d个加号，使和最小：\\n\ for(d=0,j=1;j<=n;j++) { d=d*10+b[j-1]-48; /*把b数组的一个字符转化位数值*/ f[j][0]=d; /*f[j][0]赋初值*/ } for(k=1;k<=r;k++) for(i=k+1;i<=n;i++) for(min=9999999,j=k;j4

1125 { for(d=0,u=j+1;u<=i;u++) d=d*10+b[u-1]-48; if(min>f[j][k-1]*d) /*逆推求取f[i][k]*/ { min=f[j][k-1]*d; c[i][k]=j; } f[i][k]=min; } t[r]=c[n][r]; for(k=r-1;k>=1;k--) t[k]=c[t[k+1]][k]; /*逆推出第k个加号的位置t[k]*/ t[0]=0; t[r+1]=n; for(k=1;k<=r+1;k++) { for(u=t[k-1]+1;u<=t[k];u++) { printf(\"%c\ fprintf(fp,\"%c\ /*输出最优解*/ } if(k1125 四．实验总结： 通过本次试验使我掌握了以下几个发面的知识： (1) 进一步熟悉VC++集成开发环境新建源程序、编译、运行、调试源程序的基本操作流程和方法； (2) 掌握动态规划法的解题要点； (3) 学会利用动态规划法编程解决问题。 成绩 批阅老师 批阅日期 6