| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3013 人关注过本帖
标题:设有一个长度为N的数字串,要求使用K个乘号将它分成K+1个部分,找出一种分法 ...
只看楼主 加入收藏
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
结帖率:100%
收藏
已结贴  问题点数:30 回复次数:7 
设有一个长度为N的数字串,要求使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
在我的印象中,如果二个数之和为定值,那么在这二个数相等的情况下之积为最大,如5+5=10,则25为最大积,这二个数越向中间趋,之积就越大。
对于此题,我觉得K取一个*时才有最大积,(因为一个数不可能还有他本身的二个数相乘还大于他 如9999》99*99)而且这二个数要尽可能的接近才对,1111999最大积为(1111*999),  1111111(111*1111), 9999999 (9999*999)   1234567(1234*567)

不知是否正确,欢迎讨论。
搜索更多相关主题的帖子: 而且 印象 
2012-10-22 00:08
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:15 
按照你上面的思路, 应该是对的
2012-10-22 08:54
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:0 
感觉因这个和是不定的值,还有一重要的条件,就是“*”应该是最大的数之前(第一个数是不参与比较),9234567(923456*7)
如果同时有多个最大数字,原则上应该是尽可能向中趋向,如12456*888 ,如果第一个很小而第二个数又是最大,则*有可能在第二大数之前(171234*62)。
归纳如下,如果把“*”放在每个最大数,或放在每个次大数之前比较,应该可以找到最大之积。

www.qunxingw.wang
2012-10-22 20:56
qunxingw
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:贵宾
威 望:24
帖 子:1676
专家分:7295
注 册:2011-6-30
收藏
得分:0 
要求使用K个乘号将它分成K+1个部分,是不是也可能是大数字前优先放入*呢?

www.qunxingw.wang
2012-10-22 21:55
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
一个数No = {No(x)No(y)...No(n)}    x,y,n 分别表示数据的长度   总长度为L, L = x+y+...+n

No(原) = No(x)*10^(L-x) + No(y)*10^(L-x-y) +...+No(n)

新的数据值应该为No(新) = No(x)*No(y)*...*No(n)  

可知  No(x)*10^(L-x) > No(x)*No(y)*...*No(n)   
则可以得出=》K的值越小 相对而言数据被拆解的越大 No(x)*No(y)*...No(n)值越大
则No(新)越接近No(原)的值    -------------》最好是k为0

如果k的范围在[1, +oo),
No(原) = No(x)*10^y + No(y)    已知 L = x + y, (x, y >= 1)
No(新) = No(x) * No(y)
---------------------------------------现在只需要证明|x-y|的值越小No(新)的值越小
先证明一个方向的
已知, x < L - x, x' = x + 1, x' < L - x'
则有No(x')*No(L-x') = [No(x)*10+z]*[No(L-x)-z*10^(L-x-1)] =                                    ------------------ z 为个位数
N(x)*10*No(L-x) + z*No(L-x) - No(x)*z*10^(L-x) - z^2*10^(L-x-1)





[ 本帖最后由 寒风中的细雨 于 2012-10-23 09:46 编辑 ]
2012-10-23 09:42
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
回复 5楼 寒风中的细雨
最后一段的证明不行
2012-10-23 09:55
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:15 
以前有人问过,你可以参考一下:
https://bbs.bccn.net/thread-372126-1-1.html

这是个技术帖,里面确实有可行的办法。我认为是完美解决这个问题了,就是没代码。
楼主正好练练自己实现,实现好了帖出来,正好大家学习。

[ 本帖最后由 pangding 于 2012-10-23 23:30 编辑 ]
2012-10-23 23:28
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
Ding~  可以写写
2012-10-24 09:39
快速回复:设有一个长度为N的数字串,要求使用K个乘号将它分成K+1个部分,找出一 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.042536 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved