下载

0下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 低价购买

低价购买.doc

低价购买

faint
2018-09-07 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《低价购买doc》,可适用于工程科技领域

低价购买源程序名   BUYLOW(PAS,C,CPP)可执行文件名BUYLOWEXE输入文件名  BUYLOWIN输出文件名BUYLOWOUT“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者你必须遵循以下的问题建议:“低价购买再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(范围内的正整数)你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买再低价购买”的原则。写一个程序计算最大购买次数。这里是某支股票的价格清单:日期价格最优秀的投资者可以购买最多次股票可行方案中的一种是:日期价格输入第行:N(<=N<=)股票发行天数第行:N个数是每天的股票价格。输出输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这种方案被认为是相同的。样例BUYLOWINBUYLOWOUT问题分析:方法:求最大购买次数显然这是求最长下降序列动态规划很容易解决具体做法是从序列的第一个元素开始依次求出以第i个元素为最后一个元素时的最长下降序列的长度longest(i)边界条件longest()=状态转移方程为:longest(i)=max{longest(j)},其中i>j=,…,i且j同时要满足条件:序列中第j个元素大于第i个元素。但是该问题并非如此简单因为还需要求出最大购买次数的方案数并且方案“看起来”不能重复即购买价格序列是不能一样的。如何解决该问题我们来看一个简单的例子假如股票价格序列为:、、、、则购买方案有两种、、和、、其中、、序列重复了我们在求longest(i)时longest()=longest()=longest()=longest()=那么我们求longest()时到底选用前边的那一组数据呢?显然那一组都可以这就使总方案数不唯一了我们需要记录下来此时的方案数solution()由于股价p()和p()相同所以solution()和solution()只能有一个累加到solution()里所以solution()=solution()solution()由此我们可以推导出:solution(i)=∑solution(j)其中j满足:<j<i且longest(j)=longest(i),且p(j)值不重复。最后把longest(i)中等于最值maxlong的所有方案数相加即为最终的最大方案数。方法:问题的第一部分是要求得到输人数据串中的一个最长下降序列的长度可使用动态规划的方法。具体做法是从序列的最后一个元素开始依次求出以第i个元素为第一个元素时的最长下降序列的长度leni显然lenn=.leni=max(lenj),其中i<n,j=ii…n且j同时要满足条件:序列中第j个元素小于第i个元素。所有的leni中最大的一个即为输人数据中最长下降序列的长度,将它记为maxlen。第二部分比较有难度。由于它紧接着第一问所以一般说来应该充分利用第一个问题的结论对于任意一个最长下降序列。设它的第一个元素的下标为i.第二个元素的下标为i其余元素的下标以此类推则显然有leni=maxlenleni=maxlen,…,现在要求所有不同的最长下降序列的总数,则只要按照数组Ien的值从小到大对整个序列从后向前递推即可。以序列a=()为例len=.en=en=len=Ien=.用ti记录以第i个元素为头一个元素到序列结束为止的最长下降序列的不同方案总数若leni=则ti=本例中由len=en=可知t=t=再由len=Ien=且a=>a=可得t=.由len=.en=且a=>a=和len=,en=且a=>a=可得t=tt=对应{a,a}和{a,a}两个不同的以a起头的最长下降序列.最终由len=.Ien=且a=>a=和len=.en=且a=>a=可得t=tt==所以本例中最长下降序列总数为.分别为{}{}和{}。对于有相同元素的序列来说如序列a=(,,,,)其中有两个相同的元素.前面的推导过程不变.最后一步推导受两个相同元素的影响.不能简单相加由于a=a=对于所有的以a起头的最长下降序列只要将a改为a即可得到同样长度的下降序列.所以t中的统计的序列在t中也统计在内了,当序列中有相同元素时,为避免重复计数从后向前递推时当后面的元素遇到前面的相同元素时则不再向前推。程序中为了方便处理.在整个序列前设置了一个标识元素a=maxIongint,将len置为maxlen。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/3

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利