一些经典小问题的算法（java)

1.判断闰年与日、月、年是否有效的函数

  四年一闰；百年不闰；四百年再闰。

static boolean isValidDate(int d, int m, int y) {
      if (d < 1 || m < 1 || m > 12) return false;
      if (m == 2) {
         if (isLeapYear(y)) return d <= 29;
         else return d <= 28;
      }
      else if (m == 4 || m == 6 || m == 9 || m == 11)
         return d <= 30;
      else 
         return d <= 31;
   }

static boolean isLeapYear(int year) {  
    return (year%4 == 0 && year%100 !=0) || (year%400 == 0);  
} 


2.如何判断一个数是否是质数(Prime Number)？
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。

定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
     证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
          如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.
 
  public boolean isPrime(int n)
{
      if(n < 2) return false;
      if(n == 2) return true;
      if(n%2==0) return false;
      for(int i = 3; i*i <= n; i += 2)
          if(n%i == 0) return false;
      return true;
}

时间复杂度O(Math.sqrt(n)/2),


3.分解质因数(Decomposition of prime factors)。
  每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 分解质因数只针对合数。
  求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。 短除法求质因数：


public Integer[] decPrime(int n) {  
    List<Integer> list = new ArrayList<Integer>();  
    for (int i=2;i <= n;i++){  
        while(n != i){  
            if(n%i != 0){  
            break;//不能整除肯定不是因数，
                  //都被除完之后。剩下的因数只能是奇数，且是质数。  
            }  
            list.add(Integer.valueOf(i));  
            n = n/i;  
        }  
    }  
    list.add(Integer.valueOf(n));  
    return list.toArray(new Integer[list.size()]);  
} 


4.求两个数的最大公约数(Greatest Common Divisor)。
  如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。
公约数中最大的一个公约数，称为这几个自然数的最大公约数。
  早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用f（x, y）表示x，y的最大公约数，取k = x/y，b = x%y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的，则有f（x, y）= f（y, x%y）（y > 0），如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者最大的公约数。

long gcd(long x,long y) {  
    if(x < y) {  
        long m = x;  
        x = y;//x存储较大的一个数  
        y = m;  
    }  
    long k = 0;  
    while(y != 0) {  
        k = x%y;  
        x = y;  
        y = k;  
    }  
    return  x;  
} 


5.求两个数的最小公倍数数(Least Common Multiple)。
  几个数公有的倍数叫做这几个数的公倍数，其中最小的一个公倍数，叫做这几个数的最小公倍数。自然数a、b的最小公倍数可以记作[a,b]，
自然数a、b的最大公约数可以记作(a,b），当(a,b)=1时，[a,b]= a*b。
  两个数的最大公约数和最小公倍数有着下列关系：
  最大公约数*最小公倍数=两数的乘积
  即(a,b)*[a,b]= a*b 。
  证明：设 a = x*(a,b),b = y*(a,b) 其中x,y不存在公约数。
        a * b = [x * (a,b)] * [y * (a,b)]
                 = [x * y * (a,b)] * (a,b)
                 = [a,b] * (a,b)

long lcm(long x,long y) {  
    return x*y/gcd(x,y);  
} 

6、回文数字(Palindrome Number)。
  若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：121,323.....
   判断一个数字是否是回文的方法如下：
boolean isPalindromeNumber(long l) {  
    char [] c = String.valueOf(l).toCharArray();  
    int len = c.length/2;  
    for (int i = 0; i < len; i++) {  
        if(c[i] != c[c.length-1-i]) {  
            return false;  
        }  
    }  
    return true;  
} 


7、牛顿迭代法求平方根（Newton's Method）。
 
/** 
* 求平方根 
* @param d 待开方数 
* @param precision 算术平方根的精度 
* @return 
*/ 
double sqrt(double d,double precision) {  
    double x1 = d/2, x2 =(x1 + d/x1)/2;  
    while(Math.abs(x2 -x1)>precision) {  
        x1 = x2;  
        x2 =(x1 + d/x1)/2;  
    }  
    return x1;  
} 

7.奇偶数快速判断(odd even)。
  判断奇数和偶数的方法，一般是除以2或者对2取模运算，结果为0则是偶数反之则是奇数。 在计算机内部数都是用二进制表示的，奇数最低位上一定是1，偶数为0。基于这个特点可以利用按位与运算进行奇偶数判断。

//如果是奇数返回true，否则是偶数 则返回false。  
boolean isOdd(long l) {  
    if((l & 0x01) == 0) {  
        return false;  
    }  
    return true;  
} 

下载源码：