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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → [原创]北大06年试卷中的编程题（凭印象） ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 77255 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： [原创]北大06年试卷中的编程题（凭印象） 举报  打印  推荐  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的博客第31楼
    发贴心情 

    又改了一下，可以处理n=3了：
    int find_pivot(int *A,int *B,int n){
     int pa,pb;
     pa=pb=n/2;

     int dist=n/4;
     if(dist==0)dist=1;

     while(dist>=1){

      if(A[pa]==B[pb]){
       return A[pa];
      }

      if(A[pa]<B[pb]){
       pa+=dist;
       pb-=dist;
      }else{
       pa-=dist;
       pb+=dist;
      }

      dist/=2;
     }

     return A[pa];
    }

    不过n=2是还是不行（还没习惯在电脑面前思考:<），比如说A=1,3，B=2,3，一上来pa==pb==A[1]，于是便返回3…………55555555555555555
    我在想想吧……

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

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/28 18:31:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第32楼
    发贴心情 
    不仅仅是n=1，2，3时，你的dist是可能的答案所在范围的半长，当它跳出while时——如果不是从if（相等）这个条件，那么也有好几种情况，不能一概的返回a的值。你可以看一下前面逻辑员版主写的返回条件，要分子数列1，2长度讨论。你这里要分1，2，3讨论。

    没关系，你已经写的不错了，今年那些考上的同学多数也没有作出这道题

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/28 22:11: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的博客第33楼
    发贴心情 
    ……真的要做硬性讨论阿……
    另外，n==1时好像无论如何都是正确的吧？

    不过我刚刚找了一下，题目好像是只要求写出算法思想，不要写代码吗？

    我会努力找出不要硬性讨论的算法的……

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

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/28 22:23:00
     
     cozy1984 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：9
      积分：113
      门派：XML.ORG.CN
      注册：2006/3/27

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cozy1984发送一个短消息 把cozy1984加入好友 查看cozy1984的个人资料 搜索cozy1984在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看cozy1984的博客第34楼
    发贴心情 
    我认为可以不用什么递归,也行啊!
    int i,j,k;
    int c[2*n-1]
    i=j=k=0;
    while(i<n and j<n)
    {  
    if (a[i]<b[j])   c[k++]=a[i++];
    else c[k++]=b[j++];
    }
    大家讨论讨论,我认为这个也可以实现把.
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/29
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第35楼
    发贴心情 
    这个的时间复杂度就不是O(log n)了吧？而且还需要Θ(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/5/29 0:16:00
     
     cozy1984 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：9
      积分：113
      门派：XML.ORG.CN
      注册：2006/3/27

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cozy1984发送一个短消息 把cozy1984加入好友 查看cozy1984的个人资料 搜索cozy1984在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看cozy1984的博客第36楼
    发贴心情 
    哦,我错了.
    头脑发热去了,题目要求没看清.
    惭愧啊!
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/29 0:21:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

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

    ----------------------------------------------
    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/5/29 0:29:00
     
     leeweui 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：0
      积分：56
      门派：XML.ORG.CN
      注册：2006/5/15

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给leeweui发送一个短消息 把leeweui加入好友 查看leeweui的个人资料 搜索leeweui在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看leeweui的博客第38楼
    发贴心情 
    真的假的啊
    怎么北大的数据结构教材上说排序算法的时间代价上限是O(nlogn)呢？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/29 23:12:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第39楼
    发贴心情 
    倒………
    麻烦楼上的看帖和看书都仔细一点啊……
    1、楼主的题目说的是两个已经排好序的数列（这种情况下，有O(n)复杂度的算法将其合并为一个），而不是两个无序数列。
    2、楼主的回忆确实是有问题，后面holmesyj已经给出了正确的版本。
    3、“北大的数据结构教材上说排序算法的时间代价上限是O(nlogn)”。首先，应该叫“渐进时间复杂度下限”，不是“上限”。其次，这个下限只对“基于比较的排序”有效，对于其它基于数值的排序（如基数排序、桶排序等）无效。再次，这个下限是最坏情况下的，前面已经说了，当A和B都是已排序数列时，显然有O(n)时间的算法（如MergeSort中用的Merge过程）。

    ----------------------------------------------
    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/5/29 23:28: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的博客第40楼
    发贴心情 
    唉，真是没办法了，我后来又想在原来那个算法基础上改一下：从保存两个值改为保存4个值，再在算法结束时求那四个值的中值（这样一般n==2的情况就解决了，且最后返回值也不是从单一数组中选择了），可惜还是碰到了特殊情况…………事到如今，我只能庆幸自己不是06考的了………………

    另外，指定习题集的7.17题，已知数组中只有0，1，2三个值，要求在O(logn)时间内排序，这题正确吗？我觉得就是荷兰国旗问题，至少也要用O(n)一次遍历呀，还望高人指教（最好能给出O(logn)的代码）。

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

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 9:23: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/20 9:55:01

    本主题贴数47，分页： [1] [2] [3] [4] [5]

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