《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