`
hunix
  • 浏览: 21846 次
  • 性别: Icon_minigender_1
  • 来自: 孝感
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

关于《微软的面试试题的c语言算法》的讨论

阅读更多
本章中有二个问题:  
   
  一、《微软的面试试题的c语言算法》  
  先前有人给出了一道:  
   
  这是csdn的一个帖子:  
   
  求第1500个只有2,3,5因子的数          
  数是从小到大排列          
  第一个数是1,1=2^0*3^0*5^0          
  要求用C实现,至少要讲清楚算法思路    
  如:1,2,3,4,5,6,8,9,10,12,15,18,20,24,25......  
   
  我用了1个下午,编了一个非常秒的程序(程序见下),只花1秒钟就(有时要不了,看机性能)能搞定,   不知有人能用更简单的算法解决出来么?我向高手请教!!  
   
  程序1:  
   
  #include   <stdio.h>  
  #include   <time.h>  
   
  #define   M   1500  
   
  /*   M   ,   第M个   */  
   
  void   main()  
  {  
          double   a[M]={1.0};  
          int   x[3]={0};  
          int   y[3]={2,3,5};  
          int   count=1;  
          time_t   tm;  
   
          tm=time(0);  
          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
          while(count<M)  
          {  
          register   int   min;  
                  if(a[x[0]]<1.5*a[x[1]])  
                          if(a[x[0]]<2.5*a[x[2]])  
                                  min=0;  
                          else  
                                  min=2;  
                  else  
                          if(3*a[x[1]]<5*a[x[2]])  
                                  min=1;  
                          else  
                                  min=2;  
                  if(y[min]*a[x[min]]>a[count-1])  
                  {  
                          a[count]=y[min]*a[x[min]];  
                          count++;  
                          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
                  }  
                  x[min]++;  
          }  
   
          printf("*****************\n");  
          printf("%d   count,   LastResult:       %lf\n",count,a[count-1]);  
   
          printf("%d\n",(int)(time(0)-tm));   /*   计算时间(好机子,根本用不了1秒!)   */  
          getch();  
  }  
   
  答案:859963392  
  *********************************************************************************  
   
  二、由微软题联想到的  
   
  还有一个类似的题,题目是这样的:  
   
  求第1500个含有2,3,5因子的数(至少含有其中一个)          
  数是从小到大排列          
  第一个数是1,1=2^0*3^0*5^0*other...    
  (如14=   2^1*3^0*5^0*7)        
  要求用C实现,至少要讲清楚算法思路    
  如:1,2,3,4,5,6,8,9,10,12,14,15,16,18,20,22,24,25,26......  
   
  我也做出来了,比较复杂,请高手指教有更简单的方法没(也是1秒钟搞定)  
   
  程序2:  
   
  #include   <stdio.h>  
  #include   <time.h>  
   
  #define   M   1500  
   
  /*   M   ,   第M个   */  
   
  void   main()  
  {  
          double   a[M]={1.0};  
          int   x[3]={0};  
          int   y[3]={2,3,5};  
          int   count=1;  
          time_t   tm;  
   
          tm=time(0);  
          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
          while(count<M)  
          {  
          register   int   min;  
                  if(a[x[0]]<1.5*a[x[1]])  
                          if(a[x[0]]<2.5*a[x[2]])  
                                  min=0;  
                          else  
                                  min=2;  
                  else  
                          if(3*a[x[1]]<5*a[x[2]])  
                                  min=1;  
                          else  
                                  min=2;  
                  if(y[min]*a[x[min]]>a[count-1])  
                  {  
                          a[count]=y[min]*a[x[min]];  
                          count++;  
                          printf("%d   count,   result:       %lf\n",count,a[count-1]);  
                  }  
                  x[min]++;  
          }  
   
          printf("*****************\n");  
          printf("%d   count,   LastResult:       %lf\n",count,a[count-1]);  
   
          printf("%d\n",(int)(time(0)-tm));   /*   计算时间(好机子,根本用不了1秒!)   */  
          getch();  
  }  
   
   
  答案:   2044  
   
  *************************************************************************************  
  附送N皇后经对称式修改后比较快的一种解法(引用与最快的八皇后问题一文中,我稍做了些修改):  
   
  /*     N   Queens   Problem   */  
  /*     试探-回溯算法,递归实现   */  
   
  /*     sum用来记录皇后放置成功的不同布局数;upperlim用来标记所有列都已经放置好了皇后。   */  
   
  #include   <time.h>  
   
  long   sum   =   0,   upperlim   =   1,half=0;  
   
  /*     试探算法从最右边的列开始。   */  
  void   test(long   row,   long   ld,   long   rd)  
  {  
        if   (row   !=   upperlim)  
        {  
   
      /*     row,ld,rd进行“或”运算,求得所有可以放置皇后的列,对应位为0,   */  
                      /*     然后再取反后“与”上全1的数,来求得当前所有可以放置皇后的位置,对应列改为1。   */  
                      /*     也就是求取当前哪些列可以放置皇后。   */  
        long   pos   =   upperlim   &   ~(row   |   ld   |   rd);  
      while   (pos)   /*     0   --   皇后没有地方可放,回溯。   */  
      {  
   
          /*     拷贝pos最右边为1的bit,其余bit置0。   */  
          /*     也就是取得可以放皇后的最右边的列。   */  
          {  
                            long   p   =   pos   &   -pos;  
   
                    /*     将pos最右边为1的bit清零。   */  
                                    /*     也就是为获取下一次的最右可用列使用做准备,   */  
                                    /*     程序将来会回溯到这个位置继续试探。   */  
                          pos   -=   p;                                                          
   
                    /*     row   +   p,将当前列置1,表示记录这次皇后放置的列。   */  
                    /*     (ld   +   p)   <<   1,标记当前皇后左边相邻的列不允许下一个皇后放置。   */  
                    /*     (ld   +   p)   >>   1,标记当前皇后右边相邻的列不允许下一个皇后放置。   */  
                                            /*     此处的移位操作实际上是记录对角线上的限制,只是因为问题都化归   */  
                                            /*     到一行网格上来解决,所以表示为列的限制就可以了。显然,随着移位   */  
                                            /*     在每次选择列之前进行,原来N×N网格中某个已放置的皇后针对其对角线   */  
                                            /*     上产生的限制都被记录下来了。     */  
   
                          if(row==0&&p>half)  
                                continue;  
                          else  
                                test(row   +   p,   (ld   +   p)   <<   1,   (rd   +   p)   >>   1);  
          }  
      }  
        }    
        else          
        {  
    /*     row的所有位都为1,即找到了一个成功的布局,回溯。   */  
      sum++;  
   
        }  
  }  
   
  int   main(int   argc,   char   *argv[])  
  {  
        time_t   tm;  
        int   n   =   16;  
   
        if   (argc   !=   1)  
      n   =   atoi(argv[1]);  
        tm   =   time(0);  
   
        /*     因为整型数的限制,最大只能32位,   */  
        /*     如果想处理N大于32的皇后问题,需要   */  
        /*     用bitset数据结构进行存储。   */  
        if   ((n   <   1)   ||   (n   >   32))                                      
        {  
      printf("   只能计算1-32之间\n");  
      exit(-1);  
        }  
        printf("%d   皇后\n",   n);  
   
        /*   采用对称式算法计算,增加全局变量half   */  
        half=(n-1)/2;  
        half=upperlim<<half;  
        /*     N个皇后只需N位存储,N列中某列有皇后则对应bit置1。   */  
        upperlim   =   (upperlim   <<   n)   -   1;  
   
   
        test(0,   0,   0);  
        printf("all   %ld   counts,   ji   suan   time   %d   miao   \n",   sum*2,   (int)   (time(0)   -   tm));  
        getch();  
        /*   78秒   1.8G   632M   */  
  }  
 
分享到:
评论

相关推荐

    微软面试逻辑题C语言解法.rar

    微软面试逻辑题C语言解法 请回答下面10个问题: 1。 第一个答案是b的问题是哪一个? (a)2;(b) 3;(c)4;(d)5;(e)6 2。唯一的连续两个具有相同答案的问题是: (a)2,3;(b)3,4;(c)4,5;(d...

    常见C++面试题汇总(最全c语言面试题)

    6、C语言面试题大汇总之微软亚洲技术中心面试题.txt 7、c语言面试题及答案_1.txt 8、面试题.htm 9、求职笔试面试大全.htm 10、如何回答十个最棘手的面试问题.htm 11、英语面试常见问题.htm 12、英语面试问答.htm ...

    微软面试逻辑题C语言解法

    经典问题的C语言解法 请回答下面10个问题: 1。 第一个答案是b的问题是哪一个? (a)2;(b) 3;(c)4;(d)5;(e)6 2。唯一的连续两个具有相同答案的问题是: (a)2,3;(b)3,4;(c...

    C语言工程师面试宝典

    C语言工程师面试宝典 本篇文章是面试部分的最后一篇,适用于计算机相关职位。技术面试篇主要分为两大类:通用问题和专业问题。通用问题指的是,对于你简历中的个人经历、研究项目、编程实践进行发问,主要是围绕你...

    BAT谷歌微软等各IT公司互联网C++ JAVA 计算机笔试面试真题复习资料108个文档合集.zip

    BAT谷歌微软等各IT公司互联网C++ JAVA 计算机笔试面试真题复习资料108个文档合集 C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案.docx c++笔试题汇总.pdf ...

    C++ JAVA 计算机笔试面试真题复习资料BAT谷歌微软等各IT公司互联网面试笔试资料库合集(108个).zip

    C++ JAVA 计算机笔试面试真题复习资料BAT谷歌微软等各IT公司互联网面试笔试资料库合集(108个) Google笔试面试 IQ智力面试题笔试题 JAVA笔试面试资料 NET面试题笔试题 web开发 中兴资料 微软笔试面试 数据库面试题...

    互联网行业面试笔试真题资料BAT谷歌微软等笔试面试真题复习资料合集200MB.zip

    互联网行业面试笔试真题资料BAT谷歌微软等笔试面试真题复习资料合集200MB: 2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 360校园招聘2015届技术类笔试题.pdf 4399游戏2015校园招聘游戏开发类笔试题...

    编程之法 面试和算法心得

    本书源自July在CSDN博客上的一系列分享——“微软面试100题”。从2010年起,July开始着手整理这些题目,逐渐意识到可以从这100道题中挑选出更加典型的问题,并深入分析每一个案例,最终形成了一套系统的面试准备资料...

    CSDN上 July的博客 微软面试算法一百题的代码实现(C 语言).zip

    【标题】"CSDN上 July的博客 微软面试算法一百题的代码实现(C 语言)" 提供的是一系列针对C++编程语言的面试准备材料,特别关注于算法的实现,采用C语言进行编码。这表明内容可能包括C++的基础语法、高级特性以及与...

    Java 微软面试题

    这些题目涵盖了广泛的Java和计算机科学基础,主要涉及算法设计、数据结构、字符串处理、内存管理以及逻辑思维。以下是对部分题目的详细解析: 1. **两两之差绝对值最小的值**:这是一个关于数组处理的问题,可以...

    微软等数据结构+算法面试100题全部答案集锦

    ### 微软等数据结构+算法面试100题全部答案集锦 #### 知识点概述 本篇文章将深入探讨“微软等数据结构+算法面试100题全部答案集锦”中提及的一些核心算法题目及其解决方案。这些题目不仅涵盖了常见的数据结构如...

    新鲜出炉:微软等数据结构+算法面试100题第81-100题[V0.1版最后20题]

    - **目的**: 分享微软及其他知名IT公司面试中常见的数据结构与算法题目,旨在帮助求职者准备面试。 - **系列特点**: 持续更新和优化,旨在提供高质量的学习资源。 #### 3. 第81-100题的介绍 - 这些题目是系列的最后...

    C语言笔试 面试大集合

    "C语言笔试面试大集合"这个资源集锦了多家知名公司,包括微软(MS)、IBM和华为(HW)等在内,对于C语言的笔试和面试题目,是准备技术面试的宝贵资料。 一、C语言基础 C语言的基础涵盖变量、数据类型、运算符、控制...

    微软经典数据结构算法试题

    微软的经典数据结构与算法面试题是评估编程能力和逻辑思维的重要工具,尤其对于C语言和嵌入式开发的工程师来说,掌握这些基础知识至关重要。以下将详细解释题目中的几个关键知识点: 1. 反转链表: - **循环算法**...

    微软面试100题系列【最低积分】

    微软面试100题系列是一份针对计算机编程领域,尤其是C语言编程的面试准备资源。这份资料涵盖了多种计算机科学和技术的基础知识,旨在帮助求职者在面试中展现出扎实的理论基础和实践经验。以下将针对C语言、编程和...

    IT各类面试试题

    5. **常见算法试题**:算法是解决问题的有效方法,面试中常见的算法题包括排序(快速排序、归并排序、堆排序等)、查找(二分查找、哈希查找)、图论(最短路径、最小生成树)、动态规划等。理解算法的时间复杂度和...

Global site tag (gtag.js) - Google Analytics