新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 算法理论与分析 』 → 挑战自我, ACM试题系列(1) ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 13507 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 挑战自我, ACM试题系列(1) 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     tangdragon 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：7
      积分：106
      门派：XML.ORG.CN
      注册：2005/5/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给tangdragon发送一个短消息 把tangdragon加入好友 查看tangdragon的个人资料 搜索tangdragon在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看tangdragon的博客楼主
    发贴心情 挑战自我, ACM试题系列(1)

    最近在研究ACM/ICPC的试题, 遇到了不少难题, 将陆续发布一个系列, 望各位不吝赐教!

    1.给定一个正整数n, 则在n所有的分解式中, 求因子乘积最大的一个分解及此乘积.

    PS: 这是我的翻译, 不太清楚. 举例说, n = 8时, 则8有如下分解式：8 = 8, 8 = 7 + 1 , 8 = 4 + 4 , 8 = 3 + 3 + 2, 8 = 2 + 2 + 2 + 2 直至 8 = 8个1的和，等等
    那么，在这些分解式中，３*３*２ = 18最大，这就是所要求的结果．　对于n = 12,则应该是3*3*3*3 = 81.
    我原来打算递归使用二分法，直至遇到因子 1 就停止，后来发现是错误的．例如，按照这个方法，8 = 2 + 2 + 2 + 2　将是程序求出的分解式，而2*2*2*2 = 16 < 18．
    当然有一个比较差的办法，就是先把 n 的所有分解式都求出(重复的除外，如 5 = 3 + 2 和　5 = 2 + 3叫做重复)，然后再比较各分解式的值．

    期待优秀的算法！　谢谢！


       收藏   分享  
    顶(1)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/6 21:17:00
     
     tangdragon 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：7
      积分：106
      门派：XML.ORG.CN
      注册：2005/5/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给tangdragon发送一个短消息 把tangdragon加入好友 查看tangdragon的个人资料 搜索tangdragon在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看tangdragon的博客第2楼
    发贴心情 
    还有一个我不愿意采用的算法, 就是使用高数的知识：
    任意n可以分解成X1,X2,....Xk,其中k<=n,Xi属于整数。
    假设n分成p份，则X1＋X2＋....＋Xp ＝ n ，问题即为求X1*X2*....*Xp的最大值。
    利用拉格朗日乘数法，可得此式在X1=X2=X3=...=Xp时取极大值．
    使用此法解决这个问题不很简洁, 因为X1=X2=X3=...=Xp只是最优条件, 为了保证它们都是整数， 有时需要在几种情况下权衡比较。
    我在期待精练的算法．　大家不要藏私啊！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/7 0:57:00
     
     bloud 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：4
      积分：75
      门派：XML.ORG.CN
      注册：2005/4/28

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给bloud发送一个短消息 把bloud加入好友 查看bloud的个人资料 搜索bloud在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看bloud的博客第3楼
    发贴心情 
    好像是尽量分解成 3+3+3。。。
    如果 n=3k,  3^k
    n=3K+1  3^(k-1)  * 4
    n=3k+2  3^k * 2

    不知道对不对

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/7 8:38:00
     
     tangdragon 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：7
      积分：106
      门派：XML.ORG.CN
      注册：2005/5/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给tangdragon发送一个短消息 把tangdragon加入好友 查看tangdragon的个人资料 搜索tangdragon在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看tangdragon的博客第4楼
    发贴心情 
    我发现你的答案完全正确, 呵呵, 而且很精练!  谢谢!
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/7 15:28:00
     
     asadafag 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：56
      积分：483
      门派：XML.ORG.CN
      注册：2005/3/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给asadafag发送一个短消息 把asadafag加入好友 查看asadafag的个人资料 搜索asadafag在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看asadafag的博客第5楼
    发贴心情 
    1、局部调整法证明存在一个最优解，使得存在a，使得该解中任意xi=a或a+1
    2、当3|n，分成n/3个3必然最好。一个求导就搞定的极值
    3、对模3 1、2分别讨论，完毕
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/10 23:39:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第6楼
    发贴心情 
    up
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/6/17 23:50:00
     
     neoedmund 帅哥哟，离线，有人找我吗？水瓶座1980-1-25
      
      
      等级：大一(高数修炼中)
      文章：26
      积分：159
      门派：XML.ORG.CN
      注册：2005/3/18

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给neoedmund发送一个短消息 把neoedmund加入好友 查看neoedmund的个人资料 搜索neoedmund在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看neoedmund的博客第7楼
    发贴心情 
    老题目了，应该算是代数题，作为计算机算法题有点“无趣”

    ----------------------------------------------
    交流有助学习

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/8/10 9:47:00
     
     13575277524 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：54
      门派：XML.ORG.CN
      注册：2005/8/18

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给13575277524发送一个短消息 把13575277524加入好友 查看13575277524的个人资料 搜索13575277524在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看13575277524的博客第8楼
    发贴心情 
    是不是用分治法来做思路要好一点呢？？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2005/8/18 10:12:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/28 4:05:26

    本主题贴数8，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 93.750ms