最大公约数的应用 - 分享

1.先看一家大公司笔试题

   数组中有n个数据，要将它们顺序循环向后移动k位，即前面的元素向后移动k位，后面的元素则循环向前移k位，例如，0、1、2、3、4循环移动3位后为2、3、4、0、1。考虑到n会很大，不允许用2n以上 个空间来完成此题。

1.1 算法1：

(1) 问题分析：
 
    由数学知识，通过求余运算就可以解决"循环"后移的问题。

(2) 代码：

package boke.written;

import java.util.Arrays;

/**
 * 题目：数组中有n个数据，要将它们顺序循环向后移动k位，即前面的元素向后移动k位，后面的元素则循环
 * 向前移k位，例如，0、1、2、3、4循环移动3位后为2、3、4、0、1。考虑到n会很大，不允许用2n以上 个空间来完成此题。
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.20
 * 
 */
public class GCDTest1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 0, 1, 2, 3, 4 };
		int n = a.length;
		int[] b = new int[n];
		int k = 3;

		for (int i = 0; i < n; i++) {
			b[(k + i) % n] = a[i]; // 求余解决循环后移
		}

		System.out.println(Arrays.toString(b));

	}

}

(3) 算法分析：

    时间复杂度为O(n), 空间效率为O(2n).

1.2 算法2：

(1) 问题分析：

    在算法有空间限制的情况下，一个简单的方法是：
 
    <1> 将最后一个存储空间的数据存储在临时存储空间中。

    <2> 其余数逐个向后移动一位。共操作k次就能完成问题的要求。

(2) 代码：

package boke.written;

import java.util.Arrays;

/**
 * 题目：数组中有n个数据，要将它们顺序循环向后移动k位，即前面的元素向后移动k位，后面的元素则循环
 * 向前移k位，例如，0、1、2、3、4循环移动3位后为2、3、4、0、1。考虑到n会很大，不允许用2n以上 个空间来完成此题。
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.20
 * 
 */
public class GCDTest2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 0, 1, 2, 3, 4 };
		int n = a.length;
		int k = 3;
		int temp;
		int j;

		for (int i = 0; i < k; i++) {
			temp = a[n - 1]; // 最后一个存储空间的数据存储在临时存储空间中

			for (j = n - 1; j > 0; j--) { // 其余数据逐个向后移动一位
				a[j] = a[j - 1];
			}

			a[0] = temp;
		}

		System.out.println(Arrays.toString(a));

	}

}

(3) 算法分析：

    若要考虑到有k>n的可能性，这样的移动会出现重复操作，可以在输入数据后，执行k = k % n操作，可以保证不出现重复移动的情况。这时算法的移动(赋值)次数为k * n，当n较大时，算法的效率比较低。

    时间复杂度为O(n * k), 空间效率为O(n).

1.3 算法3：

    (1) 问题分析：可以用一个临时存储空间把每一个数据一次移动到位呢?

        <1> 一组循环移动的情况：

             通过计算可以确定某个元素移动后的具体位置，如n=5，k=3时，0、1、2、3、4循环移动3位后为2、3、4、0、1。知道为什么吗？可通过计算得出0移动到3的位置，3移动到1的位置，1移动到4的位置，4移动到2的位置，2移动到0的位置；一组移动(0-3-1-4-2-0)正好将全部数据按要求进行了移动。

       <2> 多组循环移动的情况：

            再看一个例子，当n=6，k=3时，0、1、2、3、4、5经移动的结果是3、4、5、0、1、2。
            共有3组移动：0-3-0， 1-4-1， 2-5-2才能将全部数据操作完毕。

            那么，循环移动的的组数与n、k有怎么样的关系呢？再看一个例子。

            当n=6，k=2时，0、1、2、3、4、5经移动的结果是4、5、0、1、2、3。
            共有2组移动：0-2-4-0， 1-3-5-1才能将全部数据操作完毕。

       <3> 归纳总结：
    
           由以上的分析和实例，可感知到循环移动的组数与n与k的最大公约数有关。

       <4> 算法设计：
          
          a. 求n和k的最大公约数m
        b. 进行m组循环移动
           c. 每组移动进行n/m次。
           d. 某个元素移动的具体位置为： (i + k) % n
    (2) 代码：

package boke.written;

import java.util.Arrays;

/**
 * 题目：数组中有n个数据，要将它们顺序循环向后移动k位，即前面的元素向后移动k位，后面的元素则循环
 * 向前移k位，例如，0、1、2、3、4循环移动3位后为2、3、4、0、1。考虑到n会很大，不允许用2n以上 个空间来完成此题。
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.20
 * 
 */
public class GCDTest3 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 0, 1, 2, 3, 4, 5};
		int n = a.length;
		int k = 3;
		int m;
		int i;
		int j;
		int b0;
		int b1;
		int t;
		
		m = ff(n, k); // 最大公约数
		
		for (j = 0; j < m; j++) {
			b0 = a[j];
			t = j;
			
			for (i = 0; i < n/m; i++) {
				t = (t + k) % n;
				b1 = a[t];
				a[t] = b0;
				b0 = b1;
			}
			
		}
		System.out.println(Arrays.toString(a));

	}

	/**
	 * 求a和b的最大公约数
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public static int ff(int a, int b) {
		int i, t = 1;
		for (i = 2; i <= a && i <= b; i++) {
			while ((a % i == 0) && (b % i == 0)) {
				t = t * i;
				a = a / i;
				b = b / i;
			}
		}
		return t;
	}

}

 

     (3) 算法分析：

       算法中，每组循环移动都是从前向后进行的，这样每次移动之前，都需要将后面的数据存入辅助存储空间中，一次移动需要两次赋值，
总体大约需要2n次。
 
      

      
       


   

评论

3 楼 qiyueguxing 2010-06-25  

我很想知道楼上几位哥们从事的职业和行业
我猜测：1.你们是在校研究生
        2.你们还未出大学校门

2 楼 litianzzk 2010-06-25  

这个问题其实就是将一个有n+m个元素的数组的前n个元素和后m个元素交换位置，我记得《编程珠玑》里面有一个很妙的算法，是这样的，先将前n个元素位置反转，再将后m个元素的位置反转，最后整个数组倒转，这样就完成了。例如：
有数组1，2，3，4，5，6，7，现在要将5，6，7移到数组最前面，即得到5，6，7，1，2，3，4。可以这样做：
第一步，反转前4个元素的位置：4，3，2，1，5，6，7
第二步，反转后3个元素的位置：4，3，2，1，7，6，5
第三步，反转整个数组      ：5，6，7，1，2，3，4  
代码就不写了，因为非常简单。
很明显，时间复杂度O(n)，空间效率O(1)。

1 楼 mathfox 2010-06-25  

这种老兄，你的代码都是自己写的，还是天天复制啊