首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 急！！！这条整数分解的题目如何做？？？
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cthliao
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    • 揭帖率：
    发表于：2008-08-22 10:57:49 楼主
    将一个正整数n分解成若干个互不相等的正整数的和，使得这些数的乘积最大。

    输入中只有1个数n（其中1 <=n <=1000）。

    输出中也是一个数，是乘积的最大值。

    本来想用动态规划解，F[n]=max{ f[k]*f[n-k],2 <=k <=n/2 }，但是因为要求分解后的数互不相等，那就难办了
    10  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 4
    发表于：2008-08-22 12:02:581楼 得分:0
    可以动态规划，但是要二维。
    f(n,m)表示将n分解成若干个互不相等的正整数的和、且其中最大的分解数不超过m的最优乘积方案
    状态转移方程：
    f(n,m)=max{ k*f(n-k,k-1) | 1 <=k <=m }
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 4
    发表于：2008-08-22 12:04:092楼 得分:0
    最终题目的解就是要知道f(n,n)
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cthliao
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-22 13:58:583楼 得分:0
    问题，问题：按你的做法是O(n^3)的时间复杂度。而且，这样求出的乘积有可能要用到大数运算，更费时间。
    就算只用int运算，当n取最大值时就已经是10亿次O(1)啊，也会引起超时。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 4
    发表于：2008-08-22 18:37:204楼 得分:0
    那就再优化一下，假设有：
    a(1)+a(2)+...+a(k)=n，这里a(1) <a(2) <... <a(k)
    那么显然有如下性质：
    1) a(1)>=2
    证明：假设a(1)=1，那么去掉a(1)，同时令a(k)=a(k)+1
    此时新方案的乘积显然比原来要大，所以假设不可能成立；
    2) a[i+1]-a[i] <=2
    证明：假设有a[i+1]-a[i]>=3
    那么令a'[i]=a[i]+1，a'[i+1]=a[i+1]-1
    用a'[i]和a'[i+1]来替换掉a[i]和a[i+1]
    于是a'[i]+a'[[i+1]=a[i]+a[i+1]，而且
    a'[i]*a'[i+1] = (a[i]+1)*(a[i+1]-1) > a[i]*a[i+1]
    所以假设同样不可能成立。

    有了上述性质(尤其是性质2)之后，再稍微调整一下我们的算法，就会大大降低状态转移方程的复杂度。
    用dp(n,m)来表示将n分解成若干个不相等的自然数、且最大的分解数等于m的最优乘积方案。
    于是根据性质2)，状态转移方程就变得很简单:
    dp(n,m)=max{dp(n-m,m-1)，dp(n-m,m-2)}

    最后遍历dp(n,i)，1 <=i <=n，得到最大值就是题目答案。
    这个复杂度只要O(n^2)就够了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 4
    发表于：2008-08-22 18:38:095楼 得分:0
    dp(n,m)=max{dp(n-m,m-1)，dp(n-m,m-2)}
    ==>
    dp(n,m)=max{m*dp(n-m,m-1)，m*dp(n-m,m-2)}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Keynn
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-22 23:37:006楼 得分:0
    搞那么复杂！
    任意的正整数N，假设将其分解为两个不重复的正整数（X,Y）的和，则其相乘（X*Y）最大：##X=N/2+1和Y=N-X##。
    （暂时还没来得及证明一下是否成立，但是用数学归纳法很好就证明出来了！）
    然后依次用上面的式子##  ##递归X,Y，就可以得到一个二叉树！(形成规则下面阐述！)
    如：
                        20
                  /    \
                  11      9
                /  \    / \
                6  5    7  2
          |    / \  /\ | / \ /\
          |  4  2 3 2 | 4 3 
    （我自己定义的拆分规则：）上面二叉树中两个竖线之间的6，5不拆分！！！！
    1.按照##公式将一个数分解为两个数
    2.当子节点出现重复数字时候，如上面的9本来应该分为5和4，其中5与左边的重复了。此时，我们需要判断“权差”（自己定义的，用于好给大家介绍）的大小，权差的运算规则：两个子节点相乘与他们父节点的差！如上面要判断去左边的5还是右边的5，左边权差为5*6-11=19，右边权差7*3-9=12，所以我们取权差大的子节点留下。右边子节点拆分改为X=N/2+2,Y=N-X.如果拆分子节点再次出现相等的情况，继续比权差……
    3.一直拆到不能拆为止！！
    哈哈哈……是不是感觉在拆房子啊？很好玩吧？
    最后结果拆出来就是6*5*4*3*2=720

    其实看起来挺难的！一个递归，加上几条判断语句和循环语句就搞定了啊！


    等改天再想想方法，自底向上去搜索，就不用递归，浪费电脑时间空间，还浪费感情！

    （以上纯属小弟瞎扯~哈哈，跟着感觉走，没错的！！）
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Keynn
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-22 23:37:397楼 得分:0
    怎么我的二叉树发上去就变形了？555555
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ayalicer
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-23 01:38:298楼 得分:0
    分2种情况
    N <=(2+1001)*1000/2 和 N>(2+1001)*1000/2

    第一种情况:
    N=(2+x)*(x-1)/2+m
    m <=x
    x <=1001

    第二种情况:
    N=(2+1001)*1000/2+1000*n+m
    m <1000
    n为正整数

    2个方程自己解下就OK了

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mathe
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-23 08:43:169楼 得分:0
    不需要动态规划。用数学方法分析一些。直接可以将解构造出来
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tailzhou
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 2
    发表于：2008-08-23 10:15:4610楼 得分:0
    假设分解后按照大小分别为a[1..m]
    那么
    1)1 <a[1] <5;
    2)a[1..m]
      a)要么是一个连续的自然数序列;
      b)要么是两个连续的自然数序列,假设分别为a[1..m'],a[m'+1..m],那么还有a[m'+1] <a[m']+3;

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • lqflyc
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-23 17:06:0811楼 得分:0
    同意ls的观点。
    它肯定是一个连续的自然数外加一个t我们只要把这个t分布到前面连续的自然数上就可以了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • lqflyc
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-23 17:06:3912楼 得分:0
    这样就不需要判重了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mathe
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-23 18:16:0613楼 得分:0
    tail的结论还可以加强。结果根据n不同可以分成四种:
    i)2~m之间所有连续整数之和: n=(2+m)(m-1)/2
    ii)2~m之间除了一个数以外所有整数
    iii)3~m之间所有连续整数
    iv)3~m之间所有连续整数以及m+2
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jiju8484
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-24 13:08:3814楼 得分:0
    引用楼主 cthliao 的帖子:
    将一个正整数n分解成若干个互不相等的正整数的和，使得这些数的乘积最大。

    输入中只有1个数n（其中1 <=n <=1000）。

    输出中也是一个数，是乘积的最大值。

    本来想用动态规划解，F[n]=max{ f[k]*f[n-k],2 <=k <=n/2 }，但是因为要求分解后的数互不相等，那就难办了


    这道题是poj上面的；
    简单说下思想，代码就不给出了；

    正整数n：
    从s=2 3 4 5 6 7 。。。。。m
    使得sum（s)刚刚大于n
    假设：t=sum(s)-n;

    if t=0;return s;
    if t=1; delete 2 and change m to m+1,return s;
    if t>=2;delete t from s,and return s;

    接分
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jiju8484
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-24 13:10:1315楼 得分:0
    分解的思想就是：分解后的序列越长越好，当然不能有1；
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • fvflove
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 2
    发表于：2008-08-25 13:26:4016楼 得分:0
    设定有一个整数是N

    if N mod 3=0 then
      3*3*3....*3
      '(N/3)个3相乘,最大.
    end if

    if n mod 3= 1 then
      3*3*3*3.....*4 
    '(N/3)-1 个3 + 一个4 相乘,最大
    end if

    if n mod 3= 2 then
      3*3*3*3.....*2
    '(N/3) 个3 + 一个2 相乘,最大
    end if
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yazi_love
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-08-25 15:32:1817楼 得分:0
    n>=5 结果只包含2^x*3^y,  找出(2*x+3*y = n)的x最小值.
    int my_sum(int n)
    {
      int k1,k2;
      for( k1 = 1; k1 < n/2 ;k1++)
        if( ((n - 2*k1)%3) == 0 ) {k2 = (n -2*k1)/3 ;break ;}
      return (int)(pow(2.0,k1) * pow(3.0,k2));   
    }
    当
    n = 1  result = 1
    n = 2  result = 1
    n = 3  result = 2
    n = 4  result = 4
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • northwolves
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 2
    发表于：2008-08-30 22:15:3218楼 得分:0
    引用 14 楼 jiju8484 的回复:
    引用楼主 cthliao 的帖子:
    将一个正整数n分解成若干个互不相等的正整数的和，使得这些数的乘积最大。

    输入中只有1个数n（其中1 <=n <=1000）。

    输出中也是一个数，是乘积的最大值。

    本来想用动态规划解，F[n]=max{ f[k]*f[n-k],2 <=k <=n/2 }，但是因为要求分解后的数互不相等，那就难办了


    这道题是poj上面的；
    简单说下思想，代码就不给出了；

    正整数n：
    从s=2 3 4 5 6 7 。。。。。m
    使得sum（s…


    似乎是这样。
    m=int((sqrt(8*n-7)-1)/2)+1  ????
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • northwolves
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 2
    发表于：2008-08-31 08:40:3819楼 得分:0
    引用 13 楼 mathe 的回复:
    tail的结论还可以加强。结果根据n不同可以分成四种:
    i)2~m之间所有连续整数之和: n=(2+m)(m-1)/2
    ii)2~m之间除了一个数以外所有整数
    iii)3~m之间所有连续整数
    iv)3~m之间所有连续整数以及m+2


    iii)是ii)的特殊情况
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • northwolves
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 2
    发表于：2008-08-31 08:48:5220楼 得分:0
    令m=int((sqrt(8*n+1)-1)/2)
      x=n-m*(m+1)/2

    则：

    i) x=m    ---> T=(m+1)!
    ii)x=m-1  ---> T=(m/2+1)* m!
    iii)x <=m-2 ---> T=(m+1)/(m-x) * m!

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • northwolves
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 2
    发表于：2008-08-31 08:54:3421楼 得分:0
    这个难度更大一些：
    http://topic.csdn.net/t/20061016/21/5086754.html
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cymandhxl
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-09-05 15:54:3122楼 得分:0
    递归可能好一点。对一个数开平方后的两个数的乘积是最大的啊。
    既然互不相等。我们有
    1.如果数A的平方根为整数。就A=a*b,其中a=A的平方根-1，b=A的平方根+1
    2.如果偶A的平方根不为整数。a=A的平方根上取整，b=A的平方根下取整
    3.分解后的乘积>原乘积。递归。a,b。否则。返回递归前的状态。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cymandhxl
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-09-05 16:17:1323楼 得分:0
    对于http://topic.csdn.net/t/20061016/21/5086754.html
    仍然从这里入手
    但是。如果A=a+b前提下应该是a,b中至少要有一个为奇数时，并且互相不为公约数时，公倍数最大。
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved