几道简单的数学题目

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

java 代码

int
 gcd(
int
 m, 
int
 n) {
    
if
(n==
0
) 
return
 m;
    
return
 gcd(n, m%n);
}

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

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

       还有一道题目是我经历过的，计算所有小于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. }  

       或许还有更巧妙的方法。

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

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

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

 

评论

8 楼 Jameslyy 2007-09-07  

循环的方法也可以：

int gcd(a, b) {
    int r;
    while b !＝ 0 {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

7 楼 dwangel 2007-09-07  

递归……
楼主对递归理解有误，对数学也真的忘得太久了。
如果不要保存中间状态，没必要用递归。
辗转相除法，是应该中小学有的，中间过程的值不用保留。

6 楼 bluemeteor 2007-09-06  

关于求素数那个有俩个改动呵呵
1.
for ( int i=3;  i < m; i++ )

i++ => i+=2
2.
if (b) zNums.add(i); 
=>
if (b) {
if(i<=sqrt(m)){
        zNums.add(i); 
}
rNums.add(i);

其中rNums为最终返回结果，zNums为每次除数因子的List

5 楼 gof95 2007-09-06  

辗转相除法 小学还是初中课本里就学了吧 看来许多人都忘了

4 楼 Jameslyy 2007-09-06  

抛出异常的爱 写道

引用

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

欧几里德算法,如果不是能想到的人不多，怎么会被冠以他的名子呢？
主要还是要考数学有没有好好上课吧。

关键的是还有多少人记得欧几里德，记得欧几里德，就记得这种方法。如果不记得欧几里德，也知道这种方法的话，那他就是欧几里德第二了，这种人才实在难得。这种考试的方法有考数学的嫌疑，但是其初衷应该是考察面试者的思考能力。

3 楼 Jameslyy 2007-09-06  

realzhang 写道

for (Integer n:zNums)
     if (b) list.add(i);           
不太懂java，上面两句是什么意思呢？没看见有定义list呀怎么出来了list.add？

抱歉，代码是随手写的，没有输入到编辑器中，已经修改过来！

2 楼 抛出异常的爱 2007-09-06  

引用

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

欧几里德算法,如果不是能想到的人不多，怎么会被冠以他的名子呢？
主要还是要考数学有没有好好上课吧。

1 楼 realzhang 2007-09-06  

for (Integer n:zNums)
     if (b) list.add(i);           
不太懂java，上面两句是什么意思呢？没看见有定义list呀怎么出来了list.add？