文章目录

幂运算

package cn.edut.test_algorithm;

public class Demo_PowerOperation {
	public static void main(String[] args) {
		//n>=1
		System.out.println(pow_bad(2,10)); // 1024
		System.out.println(pow(2,10));
	}
	
	/** * 分治法 , O(logN) * @param x * @param n * @return */
	public static long pow(long x , int n) {
		if(n==0) {
			return 1 ; 
		}
		if(n==1) { //base case 
			return x ; 
		}
		
		//n奇偶分情况
		if(n%2==0) {//偶
			return pow(x*x , n/2);
		}else {//奇
			return pow(x*x, n/2)*x ;
		}
		 
	}
	
	/** * ***算法 * @am x * @param n * @return */
	public static long pow_bad(long x , int n) {
		return n-->1 ? pow_bad(x, n)*x : x; 
	}
}

欧几里得算法

package cn.edut.test_algorithm;

/** * 欧几里得算法 * 找两个数的最大公因数 * 辗转相除法， 又名欧几里德算法（Euclidean algorithm） * @author Administrator * */
public class Demo_EuclidAlgorithm {
	public static void main(String[] args) {
		
		System.out.println(myGcd(1989,1590)); //3
		
		System.out.println(gcd(1989,1590));
	}
	
	public static Integer gcd(Integer Max, Integer Min) {
		return Max%Min==0 ? Min : gcd(Min,Max%Min) ;
	}
	public static Long gcd(Long Max, Long Min) {
		return Max%Min==0 ? Min : gcd(Min,Max%Min) ;
	}
	
	
	
	
	
	/** * 我的第一次写的方法（太蠢） * @param N * @param M * @return */
	public static int myGcd(int N,int M) {
		int out =1 ;
		int min = Integer.min(N, M);
		
		for(int i=1 ;i<=min ; i++)
		{
			if(N%i==0 && M%i==0) {
				out = i;
			}
		}
		return out ;
	}
}

折半查找（太废了，懒得写）