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

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

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 11234 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 一道找工作的笔试题 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     cozy1984 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：9
      积分：113
      门派：XML.ORG.CN
      注册：2006/3/27

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cozy1984发送一个短消息 把cozy1984加入好友 查看cozy1984的个人资料 搜索cozy1984在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看cozy1984的博客楼主
    发贴心情 一道找工作的笔试题

    有1-1000的数字存放在一个空间为1001的数组中,其中只有两个是重复的.问怎样可以做到数组的每个元素只被访问一次且不能用辅助存储空间就能够找出那个重复的数字?

    我设想的是用一个数组A[3][10]来实现,我想这应该不算题目所说的辅助存储空间吧.


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/31 23:33:00
     
     kouyan 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：124
      积分：801
      门派：XML.ORG.CN
      注册：2006/5/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kouyan发送一个短消息 把kouyan加入好友 查看kouyan的个人资料 搜索kouyan在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给kouyan 引用回复这个贴子 回复这个贴子 查看kouyan的博客第2楼
    发贴心情 
    我觉得你都开了一个数组A[3][10]，应该是辅助存储空间吧，难道只有new一个才算开存储空间吗，那我静态空间开多大都可以了，这样的话应该比较的就是谁能用最小的空间来实现了吧。

    这个“数组的每个元素只被访问一次”该怎么理解呢？是不是只能读一次后就再也不能读和写了，我觉得再写也是访问了(在操作系统上是这么定义的)。

    我觉其实可以利用数组的下标值来做。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 1:15:00
     
     kouyan 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：124
      积分：801
      门派：XML.ORG.CN
      注册：2006/5/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kouyan发送一个短消息 把kouyan加入好友 查看kouyan的个人资料 搜索kouyan在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给kouyan 引用回复这个贴子 回复这个贴子 查看kouyan的博客第3楼
    发贴心情 
    我的方法，每个元素只读一次：
    假设原来的数组是a[1001]，
    那个重复的数字是（a[0] + a[1] + .....+ a[1000]） - （1 + 2 + .....+ 1000）
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 8:33:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第4楼
    发贴心情 
    这个牛!

    :)

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 9:22:00
     
     lionx 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1500分!)
      文章：144
      积分：1074
      门派：Lilybbs.net
      注册：2006/7/13

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给lionx发送一个短消息 把lionx加入好友 查看lionx的个人资料 搜索lionx在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给lionx  引用回复这个贴子 回复这个贴子 查看lionx的博客第5楼
    发贴心情 
    如果只用一个辅助空间的话效率就会提高很多： while (A[0]!=A[A[0]])
     {
      temp = A[0];
      A[0] = A[temp];
      A[temp] = temp;
     }//A是数组，循环结束后A[0]就是那个重复的数。原理就是变换群的性质。其实辅助空间的定义很不确定。数组内循环用的i算不算
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 9:32:00
     
     kouyan 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：124
      积分：801
      门派：XML.ORG.CN
      注册：2006/5/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kouyan发送一个短消息 把kouyan加入好友 查看kouyan的个人资料 搜索kouyan在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给kouyan 引用回复这个贴子 回复这个贴子 查看kouyan的博客第6楼
    发贴心情 
    以下是引用lionx在2006-11-1 9:32:00的发言：
    如果只用一个辅助空间的话效率就会提高很多： while (A[0]!=A[A[0]])
      {
       temp = A[0];
       A[0] = A[temp];
       A[temp] = temp;
      }//A是数组，循环结束后A[0]就是那个重复的数。原理就是变换群的性质。其实辅助空间的定义很不确定。数组内循环用的i算不算

    我觉得你这样把数组的原来存储顺序都给破坏了，应该不行吧,
    而且你不停的读写了A[0]，这与题意“数组的每个元素只被访问一次”不符吧


    [此贴子已经被作者于2006-11-1 11:42:16编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 10:00:00
     
     w84u 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：4
      积分：103
      门派：XML.ORG.CN
      注册：2006/5/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给w84u发送一个短消息 把w84u加入好友 查看w84u的个人资料 搜索w84u在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看w84u的博客第7楼
    发贴心情 
    int FindDup(int A[])
    {
     //找出第一个存放不是自身的元素
     for(i=0;i<1001;i++)
         {
            if(a[i]!=i)
            break;
         }


     //如果第一个存放不是自身的元素是a[1000],即1000就是所要找的位置
        if(i=1000)
          return i;
     

     //如果第一个存放就不是自身元素,则人工进行循环,原因下面叙述.
     if(0 == i)
      {
       i=a[0];
       a[0]=0;
      }

     //循环进行条件a[i]!=i;
     //一旦元素被遍历,则先元素指向的元素赋值给i,然后将元素指向自身a[i]=i;
     //因为即要保存元素,又要保存元素指向的元素 需要交换必须有tmp变量
     //这就是人工循环i=0的原因,因为a[0]已经被遍历 且遍历之后a[0]被赋值0
     //所以a[0]可以用来做tmp变量
     //只不过交换之后要对a[0]赋值0,利用之后要还原现场,呵呵

        while(a[i]!=i)
         {
             a[0] =a[i];
             a[i]=i;
             i=a[0];
       a[0]=0;
          }
     //循环必能退出,因为如果每个a[i]存放都是i的话 就与题目1001数组存放1-1000矛盾.
     return i;
    }

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 14:09:00
     
     w84u 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(高数修炼中)
      文章：4
      积分：103
      门派：XML.ORG.CN
      注册：2006/5/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给w84u发送一个短消息 把w84u加入好友 查看w84u的个人资料 搜索w84u在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看w84u的博客第8楼
    发贴心情 
    倒 3楼正解
    掉陷阱了
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/1 14:12:00
     
     kiangb 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：13
      积分：217
      门派：XML.ORG.CN
      注册：2006/5/11

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给kiangb发送一个短消息 把kiangb加入好友 查看kiangb的个人资料 搜索kiangb在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看kiangb的博客第9楼
    发贴心情 
    同意三楼的
    [此贴子已经被作者于2006-11-2 23:21:33编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/2 10:53:00
     
     computerlover 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：59
      积分：330
      门派：XML.ORG.CN
      注册：2006/9/23

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给computerlover发送一个短消息 把computerlover加入好友 查看computerlover的个人资料 搜索computerlover在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看computerlover的博客第10楼
    发贴心情 
    三楼的强，我估计这个题是考智力的，看你想没想到三楼的方法，倒不是考ＤＳ方面的知道，像算法的时空效率，

    ----------------------------------------------
    很爱计算机，但无人交流。苦恼…… 很爱写代码，但盗版软件不好用，代码正确但编译或连接通不过。恼火……

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

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

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