求最大公约数、幂运算

求两个数的最大公约数

1
2
3
4
5
6
7
8


long gcd(long m, long n) {
	while (n != 0) {
		long ren = m % n;
		m = n;
		n = ren;
	}
	return m;
}

幂运算

时间复杂度为O(logN)的算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/**
 * 求幂运算
 * 
 * @param x
 *            底数
 * @param n
 *            指数
 * @return 结果
 */
long pow(int x, int n) {
	if (n == 0) {
		return 1;
	}
	if (n % 2 == 0) {
		return pow(x * x, n / 2);
	} else {
		return pow(x * x, n / 2) * x;
	}
}

阶乘

传统递归版:

1
2
3


long fab(n) {
	return n==1 ? 1 : n * fab(n-1);
}

尾递归版:

尾递归: 避免每一次递归都在堆栈中保存一个局部变量(普通递归会在每个栈中存储中间值n)。性能更优，可防止内存溢出。

1
2
3
4
5
6
7


long fab(n) {
	return fab(n,1);
}

long fab(n,a) {
	return n==1? a : fab(n-1,n*a);
}