`

最大公约数的应用 - 分享

算法J#腾讯编程junit 
阅读更多
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次。
 
      

      
       


   
分享到：
| 分享一款JTree
评论
23 楼 jamie.wang 2010-06-30  
我写了个算法，很简单：找每个元素的正确位置，然后放进去，用递归的。
复制度为O(n) 

import static org.junit.Assert.assertTrue;

import java.util.Arrays;

import org.junit.Test;

public class MoveTest {

	public void doMove(int a[], int k, int c, int v, int i) {
		int n = a.length;
		if (i < n) {
			int j = (c + k) % n;
			int tmp = a[j];
			a[j] = v;
			doMove(a, k, j, tmp, ++i);
		}
	}

	public void move(int a[], int k) {
		assert null != a;
		assert 0 < k;

		int n = a.length;
		int r = k % n;

		if (1 > n || 0 == r) {
			return;
		}
		doMove(a, k, 0, a[0], 0);
	}

	@Test
	public void testMove0() {
		int a[] = {23, 5, 24, 15, 30};

		int k = 1;
		int e1[] = {30, 23, 5, 24, 15};
		move(a, k);
		assertTrue(Arrays.equals(a, e1));

		k = 2;
		int e2[] = {24, 15, 30, 23, 5};
		move(a, k);
		assertTrue(Arrays.equals(a, e2));

		k = 3;
		int e3[] = {30, 23, 5, 24, 15};
		move(a, k);
		assertTrue(Arrays.equals(a, e3));

		k = 4;
		int e4[] = {23, 5, 24, 15, 30};
		move(a, k);
		assertTrue(Arrays.equals(a, e4));

		k = 5;
		int e5[] = {23, 5, 24, 15, 30};
		move(a, k);
		assertTrue(Arrays.equals(a, e5));

		k = 7;
		int e6[] = {15, 30, 23, 5, 24};
		move(a, k);
		assertTrue(Arrays.equals(a, e6));

		k = 29;
		int e7[] = {30, 23, 5, 24, 15};
		move(a, k);
		assertTrue(Arrays.equals(a, e7));
	}
}
22 楼 maozj 2010-06-28  
bryande 写道
楼主算法设计的不好
可以参考楼上的
时间复杂度为O(n),空间复杂度为O(1)

----------------
楼上的结论是错的
21 楼 maozj 2010-06-28  
tanlingcau 写道
maozj 写道


1.2 算法2：

(1) 问题分析：

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

     其余数逐个向后移动一位。共操作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  0; j--) { // 其余数据逐个向后移动一位
				a[j] = a[j - 1];
			}

			a[0] = temp;
		}

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

	}

}


(3) 算法分析：

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

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

   


把最后k在放到temp中，一次移动k位。

-------------------------------
你的结论是错的
20 楼 maozj 2010-06-28  
qiyueguxing 写道
我很想知道楼上几位哥们从事的职业和行业
我猜测：1.你们是在校研究生
        2.你们还未出大学校门

----------------
Java工程师- 喜欢很基础的东西
19 楼 maozj 2010-06-28  
mathfox 写道
这种老兄，你的代码都是自己写的，还是天天复制啊

自己写的，你想说什么呢
18 楼 fudc 2010-06-25  
public static void main(String[] args) {
        int[] a = { 0, 1, 2, 3}; 
        int n = a.length; 
        int k = 2; 
        int temp = 0;
        int i = 0;
        int j = 0; 

        while (i < n) {
        j = i;
        while ((j + k) % n != i) {
        j = (j + k) % n;
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
        }

    boolean moved = false;
        do {
          i++;
          moved = false;
          for(int l = 0; l < i; l++){
          int j1 = l;
              while ((j1 + k) % n != l) {
            j1 = (j1 + k) % n;
            if (j1 == i) {
            moved = true;
            break;
            }
            }
              if (moved)
              break;
          }
        } while(moved && i < n);
        }
       
        for(int l : a)
          System.out.println(l);
}

这个应该满足腾讯的要求。用a[i]做了一个临时变量。
17 楼 bxf12315 2010-06-25  
能否这样考虑，先将01234放入一个队列中，然后如果移动3位的话，poll两次到一个stack中，然后先队列输出，然后stack输出。这样就完成了。
其实就是让队列和堆栈组成一个圆而已。 

List aa = new ArrayList();
		Queue aa1 = new PriorityQueue();
		Stack q = new Stack();
		aa.add(0);
		aa.add(4);
		aa.add(3);
		aa.add(2);
		aa.add(1);
		Collections.sort(aa);
		aa1.addAll(aa);

		q.add(aa1.poll());
		q.add(aa1.poll());
		
		System.out.println(aa1.toString());
		System.out.println(q.toString());
16 楼 ordinary 2010-06-25  
看看编程珠玑吧！
15 楼 weiqiang.yang 2010-06-25  
数组可以看成向量ab，最终要变成ba

先把a翻转，就是1,2,3,4变成4,3,2,1那种翻转，得到aR
然后把b翻转，得到bR

然后再把整个数组翻转(aRbR)R，就能得到ba

编程珠玑里面介绍的
14 楼 kimmking 2010-06-25  
seraphim871211 写道
kimmking 写道
第一题，加一个额外变量，记下当然开始的位置。什么都不做都可以。


这个有意思

前面有人说过了，前n-k位反转，后k位反转，之后整个数组反转就好。

用的时候从这个位置作为起点，到尾了回到头去，一直再到这个位置位置即可。
何必真的移动数组呢？
13 楼 seraphim871211 2010-06-25  
kimmking 写道
第一题，加一个额外变量，记下当然开始的位置。什么都不做都可以。


这个有意思

前面有人说过了，前n-k位反转，后k位反转，之后整个数组反转就好。
12 楼 Heart.X.Raid 2010-06-25  
这道题是我在腾讯实习笔试的时见到过，不过人家要求O(n)时间复杂度，1个辅助空间。 

	public void move(int[] data, int step){
		
		int length=data.length;
		if(length==1||length==0)
			return;
		
		int temp1=data[0];
                int temp2;
		for(int idx=0,c=1;c<=length;c++){
			temp2=data[idx=(idx+step)%length];
			data[idx]=temp1;
			temp1=temp2;
		}
		//打印结果
		for(int d:data){
			System.out.print(" "+d);
		}
	}
	
    public static void main(String args[]){
    	int a[]={0,2,5,1,4};
    	new Demo().move(a,6);
    }


上面的算法是O(n)时间复杂度，却用到了两个辅助变量temp1和temp2。
11 楼 kimmking 2010-06-25  
第一题，加一个额外变量，记下当然开始的位置。什么都不做都可以。


10 楼 cugbzc 2010-06-25  
szgaea 写道
cugbzc 写道

	public static void main(String[] args) throws ParseException, FileNotFoundException {
		int[] numbers = {1,2,3,4,5};
		int offset = 3;
		
		int length = numbers.length;
		int moveLength = length - offset;
		int[] temp = Arrays.copyOfRange(numbers, moveLength, length);
		System.arraycopy(numbers, 0, numbers, offset, moveLength);
		System.arraycopy(temp, 0, numbers, 0, offset);
		
		for(int number : numbers){
			System.out.print(number+" ");
		}
		System.out.println();
	}

这个的空间超出来了吧

所用的空间为：number.length + tmep.length。
请问哪里超了？
9 楼 szgaea 2010-06-25  
cugbzc 写道

	public static void main(String[] args) throws ParseException, FileNotFoundException {
		int[] numbers = {1,2,3,4,5};
		int offset = 3;
		
		int length = numbers.length;
		int moveLength = length - offset;
		
		int[] temp = Arrays.copyOfRange(numbers, moveLength, length);
		System.arraycopy(numbers, 0, numbers, offset, moveLength);
		System.arraycopy(temp, 0, numbers, 0, offset);
		
		for(int number : numbers){
			System.out.print(number+" ");
		}
		System.out.println();
	}

这个的空间超出来了吧
8 楼 cugbzc 2010-06-25   

	public static void main(String[] args) throws ParseException, FileNotFoundException {
		int[] numbers = {1,2,3,4,5};
		int offset = 3;
		
		int length = numbers.length;
		int moveLength = length - offset;
		
		int[] temp = Arrays.copyOfRange(numbers, moveLength, length);
		System.arraycopy(numbers, 0, numbers, offset, moveLength);
		System.arraycopy(temp, 0, numbers, 0, offset);
		
		for(int number : numbers){
			System.out.print(number+" ");
		}
		System.out.println();
	}
7 楼 likeblood 2010-06-25  
我真就没看懂这题 什么叫前面的元素 什么才算后面的元素 都没表达清楚 什么叫循环移动
举例也是一步出结果 都不知道怎么得出的 也许我智商很低吧 楼上各位真看懂了么
6 楼 bryande 2010-06-25  
楼主算法设计的不好
可以参考楼上的
时间复杂度为O(n),空间复杂度为O(1)
5 楼 tanlingcau 2010-06-25  
maozj 写道


1.2 算法2：

(1) 问题分析：

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

     其余数逐个向后移动一位。共操作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  0; j--) { // 其余数据逐个向后移动一位
				a[j] = a[j - 1];
			}

			a[0] = temp;
		}

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

	}

}


(3) 算法分析：

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

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

   


把最后k在放到temp中，一次移动k位。
4 楼 cjiaj1982 2010-06-25  
不能用LinkedList 么？
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    最大公因数.docx

    【最大公因数】是指在两个或多个整数之间共享的约数中最大的一个。它是数学中的基础概念，尤其在数论和代数领域中有着广泛的应用。在小学数学教育阶段，最大公因数（Greatest Common Divisor，简称GCD）是孩子们需要...

    小学五年级数学下册最大公因数PPT学习教案.pptx

    例如，学生可以选择自己喜欢的方法来计算一些给定的数的最大公因数，然后与小组成员讨论和分享结果。 规律性 通过实践活动，学生可以发现一些规律性，例如，某些数的最大公因数总是相同的等。这些规律性可以帮助...

    找最大公因数北师大数学五年级上PPT学习教案.pptx

    最大公因数（Greatest Common Divisor，GCD），又称为最大公约数，是数学中的一个基础概念，特别是在小学和初等数学教育中占据重要地位。这个概念在解决实际问题和理论探究中都有广泛的应用，比如简化分数、整数除法...

    新建 WinRAR 压缩文件_最大公约数_

    4. 质因数分解法：先对两个数进行质因数分解，然后取所有公共质因数的乘积，得到最大公约数。这种方法适用于理解数的结构，但在实际计算中不如前面的方法高效。 压缩文件列表中的"zuidagongyueshu"系列文件可能是用...

    人教版小学五年级数学下册最大公因数课件PPT学习教案.pptx

    学生可以和同学讨论，分享不同的方法来求两个数的最大公因数。 第五页：方法三：先写出一个数的因数，再看另一个数的因数中哪些是第一个数的因数，找到最大的那个。例如，27的因数是1、3、9、27；18的因数是1、2、3...

    五年级数学下册3因数与倍数3.4公因数与最大公因数教学反思苏教版20200505261

    在小学五年级数学下册的学习中，3.4单元主要探讨了因数与倍数的概念，特别是公因数和最大公因数这两个重要的数学概念。这个教学反思旨在深入剖析教学过程中可能遇到的问题以及如何改进教学策略，以促进学生对这些...

    自己写的排序，最大公约数，取自然数，zigzag等经典C++算法（内附算法说明）

    2. **计算最大公约数（Greatest Common Divisor, GCD）**：在数论中，两个或多个整数共有的最大正因数称为它们的最大公约数。常用的方法有欧几里得算法，也称为辗转相除法，通过不断用较大数除以较小数，再用除数与...

    人教版五年级数学下册《期末专项复习卷》全10套+答案.doc

    这篇资料主要涵盖了人教版小学五年级数学下册期末复习的重点知识，主要涉及了最大公因数（GCD）和最小公倍数（LCM）的概念及其应用。以下是相关知识点的详细说明： 1. **最大公因数**：指的是两个或多个整数共有...

    五年级上册数学课件-《总复习》 (共13张PPT) 北师大版（2014秋）.ppt

    这些练习旨在深化对最大公因数的理解，并检验学生是否能独立应用所学知识。 通过这堂课，学生应能掌握以下知识点： 1. 计算和列举一个数的所有因数。 2. 理解公因数的定义，并能找出两个数的公因数。 3. 了解最大...

    五年级数学下册 约分（一）教案 西师大版 教案.doc

    3. 巩固练习：在学生初步理解公因数和最大公因数的概念后，教师安排了练习题，如练习五的第1、2、3题，以强化学生对新知识的应用能力。 4. 课堂小结：最后，教师鼓励学生回顾课堂内容，分享他们的学习成果，提升...

    个人收藏分享-超过200个VHDL代码例程并且附有参考资料（绝对值得分享给大家）

    第63例 最大公约数七段显示器编码 第64例 交通灯控制器 第65例 空调系统有限状态自动机 第66例 FIR滤波器 第67例 五阶椭圆滤波器 第68例 闹钟系统的控制 第69例 闹钟系统的译码 第70例 闹钟系统的移位寄存器 第71例 ...

    算法文档无代码欧几里德算法的应用

    RSA加密算法的安全性基于大数分解的难度，而计算模逆元和寻找大数的质因数都需要用到最大公约数的计算，因此欧几里得算法是不可或缺的工具。 再者，欧几里得算法在计算机图形学中也有应用，比如在计算几何中，可以...

    五年级数学下册 通分教学建议 西师大版 教案.doc

    让学生从“找因数-找公因数-找最大公因数-短除法”过渡到“找倍数-找公倍数-找最小公倍数-短除法”，利用已有的知识基础，促进新知识的理解。 3. **最小公倍数**：在例1中，教师需指导学生理解如何使用短除法求两个...

    小学六年级数学总复习PPT学习教案.pptx

    - 倍数与约数：了解整数的倍数和约数关系，以及公倍数和公约数的概念，包括最小公倍数和最大公约数。 - 质数与合数：质数是只有1和其本身两个正约数的自然数，合数则是有超过两个正约数的自然数。 - 互质数：两个...

    小学六年级数的认识整理和复习建议PPT课件.pptx

    - **公因数和最大公因数**：几个数共有的因数，最大的一个称为最大公因数。 - **公倍数和最小公倍数**：几个数共有的倍数，最小的一个称为最小公倍数。 - **奇数和偶数**：能被2整除的数是偶数，不能被2整除的数...

    《因式分解-提公因式法》共5页.pdf-文档整理可打印

    这种分解方式可以帮助简化复杂的代数表达式，对于解方程、求最大公约数、最小公倍数等问题十分有用。 在提公因式法中，首先要确定公因式，这通常是多项式各项系数的最大公约数以及各变量的最低次幂。例如，对于...

    五年级下册数学课程纲要分享课PPT课件.pptx

    学生需要了解2、3、5的倍数特征，并学会找出100以内两个数的最大公因数和最小公倍数。 3. **体积与容积**： - 学习体积和容积的概念及其度量单位，如立方米、立方分米、立方厘米等。学生需要掌握如何进行单位间的...

    苏教版五年级数学（下册）教学反思10篇.docx

    教师可以利用学生的猜测，激发他们的思考，探索如何找到公因数和最大公因数，同时探讨为何是最大而不是最小。 5. 最小公倍数的教学策略：教师通过情境创设激发学生兴趣，让他们积极参与学习。在教学最小公倍数时，...

    干货分享：GMAT考试数学经典练习题1.docx

    - 问题11涉及最大公约数的求解，需要理解数论中因数分解和整除的关系。 通过这些题目，我们可以看到GMAT数学部分涵盖了概率、组合、几何、代数、数论等多个领域，要求考生具备扎实的数学基础和灵活的应用能力。在...

Magicbox
Global site tag (gtag.js) - Google Analytics