算法笔记_012:埃拉(Ella哲学原理)托色尼筛选法(Java)

by admin on 2018年12月20日

1 问题讲述

Compute the Greatest Common Divisor of
Two Integers using Sieve of Eratosthenes.

翻:使用埃拉(Ella)托色尼筛选法总结两独整数的最大公约数。(PS:最大公约数也如太可怜公因数,指区区单或三只整数共有约数被极其特别之一个)

 

 


《算法导论》第二回(算法基础)

2 解决方案


2.1 Ella托色尼筛选法原理简介

引用自百度百科:

埃拉(Ella)托色尼筛选法(the Sieve of
Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉(Ella)托色尼(Eratosthenes
274B.C.~194B.C.)提议的一致栽筛选法。
是本着本数列中的自然数而推行之,用于求一定限制外的质数,它的容斥原理的完备性条件是p=H~。

切切实实求取质数的考虑:

(1)先拿1勾(现今数学界1既不是质数也不是合数)

(2)读取队列中时不过小的一再2,然后将2之翻番删去

(3)读取队列中即极小之频繁3,然后拿3的倍数删去

(4)读取队列中时但是小之勤5,然后将5之翻番删去

(5)如上所述直到需求的限制外装有的多次都删除或读取

脚看一下行上述手续求不超100的兼具质数的一个示意图:

哲学原理 1

 

 

2.1 插入排序

2.2 具体编码

本文求取五只数之最大公约数,采纳质因数分解法:把每个数分别分解质因数,再把各数中的整国有质因数提取出来连乘,所得的积压就是随即几乎独数之最大公约数

如:求24与60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24及60之任何国有的质因数是2、2、3,它们的积压是2×2×3=12,所以,(24,60)=12。

此,第一步,先使用埃拉(Ella)托色尼筛选法求取不大于数A的拥有质数,然后由这些质数中甄选A的保有质因数;第二步,依据第一步思想求取数B的具有质因数;第三步,求取数A和数B公共质因累;第四步,输出数A和数B的最大公约数。

切切实实代码如下:

 

package com.liuzhen.ex1;

import java.util.Scanner;

public class SieveOfEratosthenes {
    //返回一维数组,数组中的元素为不大于n的所有质数
    public static int[] getPrime(int n){
        int[] result1 = new int[n];   //定义一个一维数组,并从第2个元素依次初始化为相应的自然数
        for(int i = 2;i < n+1;i++){    
            result1[i-1] = i;
        }
        for(int i = 2;i < n;i++){
            for(int j = i+1;j < n+1;j++){
                if(j % i == 0)          //如果j能够整除i,使result[j-1]等于0
                    result1[j-1] = 0;
            }
        }
        int[] result2 = getNoneZero(result1);  //除去result数组中所有0元素
        return result2;     //数组中非零元素即为不大于n的所有质数
    }

    //返回一维数组,该数组的元素为参数数组中所有不为0的元素值
    public static int[] getNoneZero(int[] A){
        int len = 0; 
        for(int i = 0;i < A.length;i++){
            if(A[i] != 0)
                len = len+1;
        }
        int[] result = new int[len];
        int k = 0;
        for(int i = 0;i < A.length;i++){
            if(A[i] != 0){
                result[k] = A[i];
                k++;
            }
        }
        return result;
    }

    //求取一个数n的所有质因数(eg:24=2×2×2×3,则result[] = {2,2,2,3})
    public static int[] getNprime(int n){
        int[] primes = getPrime(n);
        int[] result;        //最终返回结果集
        int len = 0;         //返回结果集数组长度,初始化为0
        for(int i = 0;i < primes.length;i++){
            int temp = n;
            while(temp % primes[i] == 0){
                temp = temp/primes[i];
                len++;
            }
        }
        result = new int[len];
        int k = 0;
        for(int i = 0;i < primes.length;i++){
            int temp = n;
            while(temp % primes[i] == 0){
                temp = temp/primes[i];
                result[k] = primes[i];
                k++;
            }
        }
        return result;
    }

    //返回两个一维数组中所有共同元素
    public static int[] getCommonPrime(int[] A , int[] B){
        int[] result;
        int lenA = A.length;
        int lenB = B.length;
        if(lenA < lenB){
            result = new int[lenA];
            for(int i = 0;i < lenA;i++){
                int temp = A[i];
                for(int j = 0;j < lenB;j++){
                    if(temp == B[j]){
                        result[i] = A[i];
                        B[j] = 0;
                        break;
                    }
                }
            }
        }
        else{
            result = new int[lenB];
            for(int i = 0;i < lenB;i++){
                int temp = B[i];
                for(int j = 0;j < lenA;j++){
                    if(temp == A[j]){
                        result[i] = B[i];
                        A[j] = 0;
                        break;
                    }
                }
            }
        }
        int[] result1 = getNoneZero(result);
        return result1;
    }

    //求取数A和B的最大公约数
    public static void getMaxCommonDivisor(int A,int B){
        int[] primesA =  getNprime(A);  //数A所有质因子
        int[] primesB = getNprime(B);   //数B所有质因子
        int[] resultPrime = getCommonPrime(primesA,primesB);  //数A和数B的公共质因数
        int maxCommonDivisor = 1;
        System.out.println(A+"和"+B+"的公共质因数为:");
        for(int i = 0;i < resultPrime.length;i++){
            maxCommonDivisor *= resultPrime[i];
            System.out.print(resultPrime[i]+"\t");
        }
        System.out.println();
        System.out.print(A+"和"+B+"的最大公约数为:"+maxCommonDivisor);
    }

    public static void main(String[] args){
        System.out.println("请输入数字A和数字B的值:");
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        getMaxCommonDivisor(a,b);
    }
}

 

运作结果:

请输入数字A和数字B的值:
100 60
100和60的公共质因数为:
2    2    5    
100和60的最大公约数为:20


请输入数字A和数字B的值:
60 48
60和48的公共质因数为:
2    2    3    
60和48的最大公约数为:12


请输入数字A和数字B的值:
120 54
120和54的公共质因数为:
2    3    
120和54的最大公约数为:6

 

  • 思路分析
    俺们来设想一个有趣的事例,大家沾一个任务是:
    用一如既往适合扑克牌打乱然后举办排序
    咱俩来分析一下光景的流程
    1.洗牌,将所有牌打乱,放置于几上
    2.率先由台上的牌顶中获取一致摆设牌,放置于左边被
    3.上述就做到了我们的保有先导化工作
    4.今得举办科班的排序工作
    再也从牌顶取得一致摆设牌,拿在右侧中,记住这张牌的轻重缓急
    目光聚焦在左侧被,目光从左边为左扫视,
    (大家那里假要左手中的牌是坚守从左到右依次增北宋序排序的)
    而我们左手被之牌就是大家最后的输出结果
    也就是说大家左手被之牌始终是破好顺序的
    并且大家设定左手中的牌从左到右依次增大
    故此便于都排好序的牌子被的相比较生一端起
    于右手中的牌子及谬误手中的牌
    鉴于第一差大家左手被只有来同一张牌
    因此就需要一致破比
    大家尽管得确定右手中的牌应该插入到左边的牌的什么人地方
    就就是是紧跟于在错误,大于在右手
    然我们即使完成了第一次等排序
    脚我们累举办分析并打算打内部总括出有些较通用的原理
    跟着提炼出我们的排序算法
    俺们以取出牌顶的平摆放牌(注:不肯定是牌顶,只不过是如出一辙种植人为的确定,一栽标准而已,大家总是强调作风的一致性,这为是同样种风格,一旦确定这样的品格,就不用随便地去改变,坚贞不屈下去,而且,由于我们这里桌子上之牌始终是乱的,由此实际打这多少个牌中之呦职位取出一张牌用于比,那么些地方并无重大)
    留神现行我们的右边被就起了有限摆放牌
    暨上次同等,咱们的目光从左边为左扫视我们的左边
    连举行比
    然后按照相比较的结果插入我们右手中的牌子
    只顾,这么些部分是我们算法的第一
    望我们可静下心来
    精心想象一下当我们真的将在牌子在排序的时刻
    咱俩的大脑究竟是怎进行判定的
    此历程要分析地更加细越好
    越来越有助于大家本着程序流程和布局的辨析
    首先:
    (声明:
    小心谨慎起见,我们拿
    错误手中的牌子的个数记录也:j,如今j = 2
    将左手中的牌子看作一个数组对象left
    使left.length表示左手中的牌的个数也就是其一数组的长
    也就是left[0]代表left数组的第一个变量,并盖此类推
    右手中牌的轻重缓急的施用key这些变量来拓展表示
    )
    我们看清的流程是:
    if (key > left[left.length – 1]){
    直白当脚下左手被吃于的牌的右插入
    也就是说在本来混乱的数组中,这一点儿摆放牌其实是曾解除好顺序的
    由左手被之牌,总是拍好顺序的,因而
    当我们从桌面上拿出同摆牌的下
    假定第一坏相比就是发现了
    右手手中的牌比左手被最左边的牌子(其实也是左手被尽老的牌)大
    那么就是认证此时右手中的牌子比左手被随意一个且使稀
    据此当就该拿这张牌插入到左手牌的无限右侧的职
    这里默认左手的半空中丰富(也即是并非动)
    }else{
    拿眼光在左手被为左移动一各
    呢即使是关注更左侧的平摆设牌并拓展比
    并且,将方可比的牌子向左边走一个
    用以腾出插入的岗位
    }
    现今,大家来重新审视一下大家往左边被插一摆牌的历程
    使大家怀恋假使把这进程在电脑中效仿的语句
    俺们虽只好解决这样一个问题
    即便是哪些来存储这多少个数据(即左手中的牌子)
    行使数组吗?
    咱了解我们左手被的牌子的数并无定点
    如果应用一个数组的话,
    为数老板度不能开展动态变化
    由此大家好想到
    大家依据输入的混乱顺序的数组的尺寸
    向网报名一片一样大小的长
    如此左手(类相比变成一栽容器,也即是相仿于变量)就发了足的容量来进展数据的囤积
    这么大家便无须考虑再三总经理度变化之题材
    不过这样一来
    我们尽管浪费了内存空间
    挥洒中的笔触是这样的
    直当原来数据的数组中展开排序
    这样的话
    不畏节约了绝大多数底内存空间
    不过来一个弱点就是是咱无可知想起至原始的杂乱数据
    遵照自家自己的明白
    书写被的思绪好拔取以及方我们选的事例非常相近之一个例来分解
    不畏是我们不把洗好之牌放置于桌上
    而是径直就拿它放在左手被
    下一场前面的思绪就是差一点如出一辙
    俺们才的事例中
    桌面就极度给原始混乱数据
    要左手就一定给我们再一次向系统报名了平等块及原有数据一致大小的内存(或者说是一种植好伸缩长度的数据结构)
    下一场就是起始举办极端开首我们说话的排序操作

  • 总结
    上算法要是可以起生遭之例证中效仿类似的情形,是丰裕有助于精晓算法的原理和流程的。

  • 代码实现

package chapter2;

/**
 * 插入排序算法
 * Created by 王一航 on 2016/7/1.
 */
public class InsertionSort {
    //初始化数据
    static  int[] numbers;
    //主入口
    public static void main(String[] args) {
        init();//初始化待排序数据
        show();//打印输出数据
        sort();//进行排序
        show();//打印输出数据
    }
    //初始化数组
    public static void init(){
        //将未排序的数据赋值给数组(洗牌,并将洗好的牌放置在桌子上)
        numbers = new int[]{5,2,4,6,3,6,42,66,33,87,34,11,12,10,33,12,22,32,1};
    }
    //排序算法
    public static void sort(){
        //首先从桌子上的扑克牌中取出一张,放置在左手中(这也就是为什么j = 1,而不是j = 0)
        for(int j = 1; j < numbers.length; j++){
            int key = numbers[j];//(从桌子上取出一张牌,放置在右手中)
            int i = j - 1;//眼睛盯住左手中的牌,以便于等一下进行比较
            while((i >= 0) && (numbers[i] > key)){//和左手中的牌比较大小
                numbers[i + 1] = numbers[i];
                //发现比右手中的牌大,则将其向右移动一位,以腾出插入右手中牌的空间
                //numbers[j] = numbers[i];
                i--;//将目光向左移动,以便于下一次比较
            }
            numbers[i + 1] = key;//将右手中的牌插入左手中的腾出的空闲位置
        }
    }
    //打印数组
    public static void show(){
        for(int i = 0; i < numbers.length; i++){
            System.out.print(numbers[i] + " ");
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图