欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

几道简单的数学题目 博客分类: 读书与学习 面试算法 

程序员文章站 2024-03-19 17:33:40
...

        在一本杂志上看到一个面试的数学题目,很简单,用程序实现获得两个整数的最大公约数的算法。离开数学太久了,猛一看下去,没有一点概念,首先得弄清楚什么是公约数,回想一下,嗯,原来这就是公约数。就想怎样才能求得最大公约数,比较笨的方法就是先得出两个整数的所有公约数,然后找到那个最大的。这是个笨方法,但也能实现预期的结果。杂志中给出了一个非常简洁的方法,欧几里德算法,简单得还是有一点不太明白:

java 代码
  1. int  gcd( int  m,  int  n) {   
  2.      if (n== 0 return  m;   
  3.      return  gcd(n, m%n);   
  4. }   

        是如此的简单,根据欧几里德算法,通过递归实现了目的,首先用小的数对大的数取余,如果余数是零,那么两个数相同,或者这个较小的数就是它们的最大公约数,如果余数不为零,则继续用这次计算得出的余数对两个整数中比较小的数取余,如果余数为零,则这个比较小的数为最大公约数,如果余数不为零,则继续用本次的余数对上次获得的余数取余,如果余数为零,则上次计算得出的余数则为最大公约数,如果不为零则继续递归,直到得出最大公约数。

       考官的意图就是考察面试者的思考能力,所以也就选择了那个用这种方法实现算法的应试者。结果考官也的确实现了他的目的。不过有多少人能够想到这个方法呢!

       还有一道题目是我经历过的,计算所有小于100000的素数。这也是一个技巧的问题。首先弄明白了什么是素数,素数是只能被1和它本身相除的整数。实现的思路是,从2开始,假如一个数能够被小于他的一个素数整除,则该数不是素数,否则是素数。根据这个思路只要通过一个嵌套循环,对小于100000的数进行一个循环验证,看看它能不能被小于它的所以的素数整除。

java 代码
  1. List zNums( int  m) {           
  2.     List zNums =  new  ArrayList();  // 这里zNums 范型为Integer,但是由于编辑器的原因无法加入          
  3.     zNums.add( 2 );           
  4.      boolean  b =  true ;           
  5.      for  (  int  i= 3;  i < m; i++ )
  6.         b =  true ;           
  7.          for  (Integer n:zNums) {           
  8.              if  ( i%n ==  0 )  {           
  9.                 b =  false ;           
  10.                  break ;           
  11.              }           
  12.          }           
  13.           if  (b) zNums.add(i);           
  14.      }           
  15.      return zNums;
  16. }  

       或许还有更巧妙的方法。

       通过几道很小的数学题目倒引出了我对于数学的兴趣。

       看过王小波的小说和散文,王小波曾经一段时间就一们心思地学习数学,在其小说中的也有这样的角色,在无聊的时候会取出一本数学书去做练习,把数学当作一件有趣的事情去做,把数学和思考的乐趣,人的智慧联系在一起。

      在坛子里也曾看到过喜欢研究数学的偶像派人物。被他们那种研究学问的痴心,对于思考的乐趣的追求所吸引,感觉数学也是一门很有趣的科学!

 

相关标签: 面试 算法