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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → DS排序难题3道…… ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 16948 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： DS排序难题3道…… 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第11楼
    发贴心情 

    又想了一下，还是有问题呀……正如chenminyi说的，固定第二个数后如何在固定第三个数？
    如：1 3 6 9 13 14 19 50，K=25
    第一个数取1，
    第二个数取13，
    第三个数先在3-9中找，
    case1:出现某个数使三个数之和大于25，则直接将第二个数向左二分并重新开始第三个数的查找，…………
    case2:所有的第三个数都是总和小于25，则第三个数再从第二个数右边开始二分，如果求得的每个和都小于25，那第二个数还是往左边二分，如果求得的和有的大于25，有的小于25呢？第二个数该怎么办？
    而且即便第三个数在3-50中二分查找，如果出现了有的大于25有的小于25的情况呢？第二个数好像还是不好进行准确的移位……
    求救啊！chenminyi可不可以给出你的算法稍详细一点的步骤？？
    还有Supremgooooo，但愿他能回来看看这帖子…………

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 13:16:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第12楼
    发贴心情 
    以下是引用chenminyi在2006-12-17 12:29:00的发言：
    我看是先固定一个数，接下来用递归的方法找到两个数的和满足要求的两个数，我计算过，复杂度为n,所以总的复杂度刚好是n*n。

    “用递归的方法找到两个数的和满足要求的两个数”，应该怎么进行？且复杂度是n？

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 13:25:00
     
     Smilingface 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(要不要学学XML呢?)
      文章：84
      积分：577
      门派：XML.ORG.CN
      注册：2006/3/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Smilingface发送一个短消息 把Smilingface加入好友 查看Smilingface的个人资料 搜索Smilingface在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Smilingface的博客第13楼
    发贴心情 
    以下是引用teng_t1986在2006-12-16 18:27:00的发言：
    都是习题指导上的增补题

    3.一数组中只有0，1，2三种数，在O(logn)时间内排序，这题和荷兰国旗问题是一样的，我觉得最少也得O(n)那，不知道O(logn)怎么来的……[/size][/B]

    PS:我下载了最新的习题指导勘误，这三题都没有。

    望有人能给出解答，只要算法思想即可，不必写程序了。谢谢！



    这个题印错了，可以确定是O(N)，张铭在某个地方说过，忘记是哪里了。:-)
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 19:41:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第14楼
    发贴心情 
    那就说详细一点：
    假设这三个数是a，b，c，数组长n；

    1）a很好办，就是从头开始依次指；
    2）当a指定了某一个数后，如果这个数大于k，算法结束；
    3）否则考虑b，记b的查找区间下标为bl，br，初始时bl=a+1，br=n-1，b在[bl，br]这个区间内二分查找，直到找到第一个b，使a+b<k，不如果没有找到，考虑下一个a；
    4）如果找到，记c的查找区间下标为cl，cr，初始时cl=a+1，cr=n-1，考虑c，c在[cl，cr]这个区间内二分查找，直道找到某一个c，使a+b+c=k，如果没有找到，说明b还是太大了，把br指向b-1，转3）；
    5）如果找到，则a，b，c是一个解，现在关键是找下一个解：要考虑让b小一点，c大一点；或者b大一点，c小一点。对于第一种情况：由于[bl，b]中的元素都满足a+b<k，所以要试这中间的每一个b，固定了b后，cl指向c+1，转4）；对于第二种情况，b的取值应该在[b+1，br]中，依次检查这中间的b，直到a+b〉=k，考虑下一个a，否则c在cr=c-1，转4）

    btw:应该没有更好的算法了，5）处的实现可以再修改一下，但是效率不能改，否则就丢失解了。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 22:28:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第15楼
    发贴心情 
    你这个算法似乎是O(n^2 * log n)的。
    因为对每一个a，第4步对每一个b，要花O(log n)的时间来找c，然后由于b是一个一个递减的，所以对每一个，要试O(n)个不同的b（从而对每一个a，耗时为O(nlogn)），而a又有n个，所以总时间复杂度是O(n^2 * log n)。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 22:42:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第16楼
    发贴心情 
    to supremgoooo：我也是这么想的，可是有反例啊：

    1 3 4 10 19 21 50  K=41,有答案41=1+19+21
    a=1,b=10,a+b=11<K,c在3至50中找30，没找到，说明b还是太大了，把br指向b-1,
    b=3,c在3至50中找37，未找到，
    b不能再减少了，移动a，a=3，
    然后b和c都不能取比a小的数，故最后查找失败…………

    感觉错误出在4）：为什么说“说明b还是太大了”？根据上例，b其实是太小了，此时a=1，b=10，而答案应该a=1,b=19,c=21。。

    是不是应该让bl和cl都从1开始找？为什么要是a+1呢？题目说可以有重复元素啊…。
    另外，logician说的我也没注意看，还是n^2logn吗？

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/17 22:51:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第17楼
    发贴心情 
    先取一个数m，令r = K-m，接下来还有2个数需要确定，其和为r，可以想象一个N*N的矩阵~假设n个数排序后分别为a1~an，如下图
         a1      a2 …  an
    a1 2*a1           a1+an
    a2         2*a2
    .  
    .  
    an                   2*an

    显然可以证明2*ai>=ap + aq，若p<=i且q<=i；2*ai<=ap + aq，若p>=i且q>=i；
    这样在2*a1~2*an中二分查找r（即在正方形的对角线上进行二分搜索）,使得2*ai <= r <= 2*a(i+1)
    由上面的分析可以知道所以的p,q若p<i且q<i或者p>i+1且q>i+1，r!=ap+aq;因此可以在矩阵的其他部分进行查找~假设i=n/2，则一次查找过程在n*n个组合可能去掉了一半的组合可能
    令开销函数为T(n*n)， 有T(n*n) = 2*T(n*n/4)+logn  /*可以想象为原正方形一下去掉了2个1/4小正方形，需要对剩下的2个小正方形递归查找 */
    由master理论可知，T(n*n) = (n*n)^log4(2) = (n*n)^(1/2) = n
    所以总的复杂度为n*n

    这是我最初的思路，后来想了想，由于每次查找得到的i不一定是n/2，开销函数应修改为       T(n*n) = 2*T(i*(n-i))+logn ，这样下面的递归也不能在对角线上进行查找， 因此算法需要进行修改，不过我想最终的平均复杂度应该还是n*n；

    ：）

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/18 0:29:00
     
     chenminyi 帅哥哟，离线，有人找我吗？狮子座1984-7-28
      
      
      等级：大三(要不要学学XML呢?)
      文章：69
      积分：555
      门派：XML.ORG.CN
      注册：2006/7/20

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给chenminyi发送一个短消息 把chenminyi加入好友 查看chenminyi的个人资料 搜索chenminyi在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看chenminyi的博客第18楼
    发贴心情 
    可以将该算法推广到从n个数中选取m个数其和为K，假设K < cn （c为常数）
    则其复杂度为(cn)^logm
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/18 22:39:00
     
     mxf3306 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：112
      积分：823
      门派：XML.ORG.CN
      注册：2006/7/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给mxf3306发送一个短消息 把mxf3306加入好友 查看mxf3306的个人资料 搜索mxf3306在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看mxf3306的博客第19楼
    发贴心情 
    题1我觉得在规定时间内不可能实现。题3已经改过来了。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/20 21:19:00
     
     teng_t1986 帅哥哟，离线，有人找我吗？天秤座1986-10-22
      
      
      威望：1
      头衔：智能缔造者
      等级：计算机学士学位(版主)
      文章：368
      积分：2273
      门派：IEEE.ORG.CN
      注册：2006/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给teng_t1986发送一个短消息 把teng_t1986加入好友 查看teng_t1986的个人资料 搜索teng_t1986在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给teng_t1986 访问teng_t1986的主页 引用回复这个贴子 回复这个贴子 查看teng_t1986的博客第20楼
    发贴心情 
    chenmingyi你写的我没仔细看，不过我已经想出第3题的正确答案了：
    a(第一个数)还是一次遍历数组，
    b和c统一处理：先b=c=中间数，
    然后判断：
    if(a+b+c<k){
       if(b==c)
           b往右二分移位；
       else
           二分：一种b往右二分移位，一种c往右二分移位***
    }
    注意***处进行了二分，所以搜索树是一颗二*树，
    但由于该树枝长为logn，所以最后搜索结果数量即叶子节电树为2^logn=n级，
    最终总搜索时间代价正好是n^2级。

    我想这就是正确答案，星期一想出来的，因为我工作日无法上网，所以一直没公开出来，
    不幸的是，今天我又想到了一个反例（其实也不能说是反例），看：

    如果在b、c搜索过程中，第一次移b，第二次移c，如此交替，则在此情况下搜索树枝长可能为2logn，但这样的话时间代价为2^(2logn)=n^2…………
    又郁闷了。。。

    第一题，我想了一种变态的数组情况：
    A:11111111111111156
    B:11111111111111178
    显然中值为6，但似乎不可能在logn时间内找到，如果1的数量极多的话……
    但O(n)级的还是很简单的，大家再思考一下吧。

    ----------------------------------------------
    书山奋战不觉难，
    一刻光阴莫等闲。
    长路遥遥飞浩志，
    前尘洗却作泥丸。
    粗茶薄被心灯暖，
    明月清窗几案寒。
    欲待桂枝香万里，
    海阔天空俱欢颜。

    My blog:http://hi.baidu.com/tengteng2007

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/12/22 18:19:00
     
     GoogleAdSense天秤座1986-10-22
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Google AdSense 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/19 16:15:09

    本主题贴数22，分页： [1] [2] [3]

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