《C++课程设计——乘积最大》由会员分享，可在线阅读，更多相关《C++课程设计——乘积最大（25页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告实验内容： 课程设计 相关课程： 信息系统开发语言（二） 学 期： 2011-2012 学年第 2 学期 学时学分： 64 学时 4 学分 专业班级： 学号： 姓名： 指导老师： 提交日期： 2012 年 6 月 23 日 湖南商学院信息系统开发语言（二）课程设计信息系统开发语言课程设计一、课程设计目的C+是实践性很强的课程。课程设计是加强我们实践能力的一个强有力手段,要求我们在完成程序设计的同时能够写出比较规范的设计报告。通过课程设计要达到两个目的，一是检验和巩固专业知识、二是提高综合素质和能力，对于我们基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。课程
2、设计主要是 C+语言程序设计的实现。通过该课程设计，可以将学生课堂上掌握的理论知识与处理数据的业务相结合，以检验我们同学们掌握知识的宽度、深度及对知识的综合运用能力，同时提高和加强自己的计算机应用与软件开发能力,培养自己独立分析问题、解决问题、查阅资料以及自学能力，以适应计算机产业日新月异发展的形势。学习和掌握 C+程序设计方法以及上机调试技巧，为今后学习其它专业课程打好坚实的基础，检测自己在这一学期对 C+的学习及掌握情况。知道自己的不足，及时的弥补。为以后的学习打下一定的基础,也为自己以后如何制定学习计划做一铺垫。二、问题描述题号 8 乘积最大总体需求：编写一个实现将一个的数字串，分成 K
3、+1 个部分，使得这 K+1 个部分的乘积能够为最大。功能需求：设有一个长度为 N 的数字串，要求使用 K 个乘号将它分成 K+1 个部分，找出一种分法，使得这 K+1 个部分的乘积能够为最大。如：有一个数字串：312，当 N=3 时，K=1 时会有以下两种分法：1）312 = 362）312 = 62此时，符合题意的结果是 312 = 62用户界面输入: 湖南商学院信息系统开发语言（二）课程设计1）程序正常运行后，提示用户输入一行共有 2 个自然数N，K（2N40，1K6） 。2）第二行是一个长度为 N 的数字串。 输出:相对于输入，应输出所求得的最大乘积（一个自然数） 。提示与参考输入样例
4、：4 21231输出样例：62三、 问题分析此程序要求实现将长度为 N 的数字串，用 K 个乘号分成 K+1 个部分，使得这K+1 个部分的乘积能够为最大。由题，数字串的顺序固定不变，乘号在不同的位置插入，使得数字乘积发生变化，并取其最大值输出。设 num=3456，n=4，k=3，这表示要将 4 位的十进制整数 3456 分为 3 段。划分方法为：3456=672，3456=810，3456=1020，而第 3 种划分才是最佳划分。本问题属于求最优值的一类问题。假设第 k 个乘号插入的位置为 p，取出由后 n-q 个数字组成的数字串，可能包含任意个（不多于 k 个）乘号。若能求出任意子串包含
5、 k-1 个乘号的最大乘积，则只需穷举第 k 个乘号的插入位置 q，该乘号将数字串分成前后两段，后半段包含 k-1 个乘号，其最大值根据假设已经算出，将它与前半段的值相乘得到第 k 个乘号在位置 q 时的乘积。取所有的第 k 个乘号不同插入方案中的最大乘积即为问题“后 n-q 个数字组成的数字串插入 k-1 个乘号”的解。假设数字字符串为 a a a （2f(q,k-1)左右两边同时乘以 d(q,n-q)得 e(q,k-1)*d(q,n-q)f(q,k-1)*d(q,n-q)=f(n,k)。即 f(n,k)不是一个长度为 N 的数字串加入 K 个乘号的最大乘积与最初的假设相矛盾。所以 f(q,
6、k-1)是前面 q 位字符串加入 k-1 乘号的最大乘积，即此问题具有最优子结构性质。由于子问题是在子串中插入 k-1,k-2, ,1,0 个乘号，因此，把 k 作为阶段变量。状态变量是阶段变量的函数，它会随着阶段变量的改变而变化。阶段数 J ，表示在子串中插入 J 个乘号。最少是长度为 J+1 的子串才能刚好插入这 J 个乘号。这就是 J 阶段的起始状态：在长度为 J+1 的子串中插入 J 个乘号。再思考状态数的上界，有 k-J 个乘号需要插入右子串中，右子串最短刚好容纳 K-J 个乘号的长度为 K-J+1，而整个字串的长度为 n，故左子串最长允许的长度为 n-(k-J+1) = n+J-k
7、-1。总结起来，状态数 I 的取值范围就是 J+1 k，如果这两个条件都满足，则调用函数 Maxproduct(s+i,n-i,k-1)，最后输出最大值，结束算法。开 始2 n 4 0 & & 1 k 6 ？输 入 n 、 k 、n u mn = s t r l e n（ n u m ） ？n k ?M a x p r o d u c t ( s + i , n -i , k - 1 )输 出 ： n u m 中输 入 k 个 乘 号 不能 分 成 k + 1 部 分输 出 ： 请 确保 输 入 的 字符 串 长 度 = n输 出 最 大乘 积结 束输 出 ： 重 新 输 入n 和 k（ 2
8、n 4 0 , 1 k 6 ）N YNNYY湖南商学院信息系统开发语言（二）课程设计五、程序设计方法一：1、程序代码及说明#include #include #include using namespace std; #define BUFFERSIZE 40char numBUFFERSIZE=0;vector result; /将 result 声明为一个元素类型为 string 的向量容器对象vector temp; /将 temp 声明为一个元素类型为 string 的向量容器对象double maxProduct=0; bool getAmaxproduct=false; void
9、maxproduct(char* s, int n,int k) vector:iterator p; /将 p 声明为 string 类型的向量容器迭代器if(k=0) getAmaxproduct=true; temp.push_back(s); /将字符串压入 vectordouble product=1; for (p=temp.begin(); p!=temp.end(); p+) product *= atoi(*p).c_str(); if(product maxProduct) maxProduct = product; result.clear();/将容器 result 清
10、空 result=temp; else 湖南商学院信息系统开发语言（二）课程设计 for(int i=1; ink;coutnum;if(n=2&n=1&k:iterator p=result.begin(); p!=result.end(); p+) cout(const BigDecimal& a) constbool operator=(const BigDecimal& a) constvoid print() const / 从高位开始打印;BigDecimalnum : unsigned char100len : int +BigDecimal()+BigDecimal(s : s
11、tring) + operator*( a : const BigDecimal&) :BigDecimal+ operator( a : const BigDecimal&) const : bool+ operator= (a: const BigDecimal&) const : bool+ print() cons : void湖南商学院信息系统开发语言（二）课程设计2程序代码及说明#include #include #include using namespace std;class BigDecimal / 高精度整数unsigned char num100; / 从低位到高位存放
12、每一位数字，最高支持 100 位，修改此数字可以提高支持精度int len; / 数字的位数public:BigDecimal() / default constructor, 初始化数字为 0len = 1;num0 = 0;BigDecimal(string s) / 由 s 初始化整数len = s.size(); / 读取长度for(int i=s.size()-1;i=0;i-) / 从低位开始读取numlen-i-1 = si-0;while(len0 / 去除高位 0if(len=0) len = 1;BigDecimal operator*(const BigDecimal&
13、a) / 高精度乘法BigDecimal c; / 结果存放变量memset(c.num,0,sizeof(c.num); / 初始化为 0for(int i=0;i0 / 去掉高位 0if(c.len=0) c.len = 1;return c;bool operator a.len)return false;for(int i=len-1;i=0;i-)if(numia.numi)return false;return false;bool operator(const BigDecimal& a) constreturn a=0;i-)cout N K;cout str;if(N=2&N
14、=1&K:iterator p=result.begin(); p!=result.end(); p+) coutnumk; if (num0=0) cout BUFFERSIZE) cout:iterator p=result.begin(); p!=result.end(); p+) coutnk;coutnum;if(n=2&n=1&k:iterator p=result.begin(); p!=result.end(); p+) coutnk;coutnum;if(n !=strlen(num) cout:iterator p=result.begin(); p!=result.end
15、(); p+) coutnk;coutnum;if(n=2&n=1&k:iterator p=result.begin(); p!=result.end(); p+) cout40k6）时的运行结果如下：分别输入 n 和 k，使 n=k，输入不符合题目要求，按照程序设定，应当输出“请重新输入 n 和 k（2N40,1k6）”,程序实际运行结果正确，运行正常。（3）输入一串字符串和两个自然数 n、k（2kn40，1k6） ，当字符串的长度不等于 n 时的运行结果：分别输入 n 和 k，使 n 不等于字符串的长度，输入不符合题目要求，按照程序设定，应当输出“请确保输入的字符串长度=n”,程序实际运行结果正确，运行正常。湖南商学院信息系统开发语言（二）课程设计（4）输入一串字符串和两个自然数 n、k（2n40
