标签：算法

gcd(最大公约数算法)数学证明(转)

本文转自:http://www.cnblogs.com/ider/archive/2010/11/16/gcd_euclid.html,原文作者:Ider。内容有整理。

常识：如果 a≥b 并且 b≤a，那么 a=b.

前提：
1）只在正数(原谅为非负整数)范围内讨论两个数 m 和 n 的最大公约数，即 m, n ∈ N.
2）不考虑0的情况。(原文为处理0的特殊情况)

引理：
假设 k|a(表示a能够被整除), k|b，则对任意的 x,y  ∈ Z， k|(xa+yb)均成立.
证明：
　　k|a => a=pk, k|b => b==qk (其中 p,q ∈ Z)
　　于是有 xa+yb=xpk+yqk=(xp+yq)k
　　因为 k|(xp+yq)k, 所以 k|(xa+yb)
这上面的结论表示，对于都能被k整除的a和b,对a和b进行整数倍的乘法，并相加起来的结果仍然能够被k整除,可以理解为整除的结合率。

gcd的Euclid算法证明：
命题：对任意 m, n ∈ N，证明gcd(m,n) = gcd(n, m mod n)
证明：
证明第一节
　　令 k=gcd(m,n),则 k|m 并且 k|n;
　　令 j=gcd(n, m mod n), 则j|n 并且 j|(m mod n);
　　对于m, 可以用n 表示为 m=pn+(m mod n);//即m可以表示为xn+y(m mod n)的方式,x为p,y为1
　　由引理可知 j|m（其中 x=p,y=1）, 又 j|n，于是 j 是 m 和 n 的公约数（但不一定是最大的）;
　　因为 k 是 m 和 n 的最大公约数，所以必有 k≥j;
证明第二节
　　通过另一种表示形式：(m mod n)=m-pn,同理可得：//即m mod n可以表示为xm+yn的方式，x为1,y为-p
　　k|(m mod n),又k|n，于是 k 是 (m mod n) 和 n 的公约数（也不一定是最大的）;
　　同样由 j 是 n 和 (m mod n) 的最大公约数可以得到 j≥k;
//证明第三节，使用常识
　　由常识，得出结论 k=j,
　　即gcd(m,n) = gcd(n, m mod n) ，得证。

选择数问题，最坏情况下时间为O(n)的算法实现参考

在前一篇讲选择数问题时，使用了一种类似于快速排序的算法来解决选择数问题，见:http://www.iflym.com/index.php/code/201108240001.html。
而根据算法导论上的一种最坏时间为O(n)的一种解法，其详细的步骤如下所示：

  1.     将数组s按5个为一组，划分成不同的小组,小组数
  2.     对每个小组，进行插入排序，并选择其中的中位数
  3.     将每个小组的中位数，组成一个新的数组，并递归的选择出最终的中位数m
  4.     以m作为参照数，将数组s划分成两个部分，使得m所处的位置数比左侧的数目大1
  5.     如果左侧的数目数恰好为寻找的第k位数，则m即为我们要找的数，否则继续在左侧或者右侧进行查找

有了几个的思路，具体算法就很简单了。参考代码如下所示：

private static int find2(int[] ints, int k, int start, int end) {
//如果k为1,则寻找最小数，如果k为end-start+1则寻找最大数
		//总长度小于5,直接插入排序并查找
......
		//寻找到中位数
		int z = findMiddle(ints, start, end);
		//按中位数分割数组，其中ints[divide]=z
		int divide = divide(ints, z, start, end);
		//判断在哪个部分
		int frontNum = divide - start;
		//恰好为中位数
		if(frontNum == k - 1)
			return ints[divide];
		//高部分
		if(frontNum < k)
			return find2(ints, (k - frontNum), divide + 1, end);
		//低部分
		return find2(ints, k, start, divide - 1);
	}

继续阅读“选择数问题，最坏情况下时间为O(n)的算法实现参考”

解决1分2分5分硬币组合的数学问题

    本文部分信息来源于 http://topic.csdn.net/u/20110913/21/54ef3c9d-6e86-4a4e-8359-cc8f0d728770.html
    问题的提出如下：1分2分5分的硬币，组成1角，共有多少种组合，如果是组成1块，又有多少种组合。

    这个问题看似很简单，答案为10种。但如果要真正去算，或者写程序来实现。想必大多数的人都会使用3层for循环来实现。即分别令i=0（表示1分),j=0(表示2分),k=0(表示5分），然后循环条件为3者之和小于10,得出的结果为三者之和大于10。即实现算术 x+2y+5z=10，然后求x,y,z的组合。
    然而，问题在于提出的问题并没有问具体的组合方式，而是只问了究竟有多少种，那么如果再使用这种算法就有点得不偿失了。

    文中有一个叫tsx86的解法，将此题变成了纯粹的数学题，如下所示：

如果这个和越大，那相应的复杂度会很高。所以
因此，本题目组合总数为10以内的偶数+5以内的奇数+0以内的偶数，

某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2
某个奇数m以内的奇数个数也可以表示为(m+2)/2

所以，求总的组合次数可以编程为：
number=0;
for (int m=0;m<=10;m+=5){
number+=(m+2)/2;
}

这样程序简单太多了。

    以上文的原理就在于，将x+y*2+5*z=10转换成为10-5z=x+y*2，当z从0到2时，就转换成了求1和2的组合了，实际上就变成了10-5z中，可以有多少个偶数。故产生的结果就如上所示了。

继续阅读“解决1分2分5分硬币组合的数学问题”